N queens problem

N queens problem

Solution 

# [bonus] the size of the grid, this can be changed

n = 8

# this is to store the column number that has the logo

# on each row. For example, m[3] = 2 indicates the logo

# on row 3 is put in column 2. Initialize to -1.

m = [-1] * n

# search for row i with the given columns are still available

def search(i, columns):

if i == n: # no more row to try

return True

# try each available column that is not going to form a diagonal.

for column in columns:

flag = True

for j in range(i):

if abs(i – j) == abs(column – m[j]):

# this is a diagnal, we not going to try it

flag = False

break

if flag:

# not a diagonal, the logo can put at this column.

m[i] = column

columns.remove(column)

if search(i + 1, columns):

return True

columns.add(column)

m[i] = -1

return False

# let all columns available and start to search from the first row

columns = set()

for j in range(n):

columns.add(j)

if search(0, columns):

# display the output to the console

for i in range(n):

for j in range(n):

if m[i] == j:

print (‘1’, end=” “)

else:

print (‘0’, end=” “)

print()

else:

print (‘There is no solution…’)