Backtracking - N Queens Problem | Algorithms

Backtracking - N Queens Problem | Algorithms

by SJ · May 10, 2015 Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen's prob­lem asks how to place 8 queens on an ordi­nary chess board so that none of them can hit any other in one move.(Source: http://www.math.utah.edu/~alfeld/queens/queens.html) Here we are solv­ing it for N queens in NxN chess board. N Queens Problem Approach: Cre­ate a solu­tion matrix of the same struc­ture as chess board. When­ever place a queen in the chess board, mark that par­tic­u­lar cell in solu­tion matrix. At the end print the solu­tion matrix, the marked cells will show the posi­tions of the queens in the chess board. Algo­rithm: Place the queens col­umn wise, start from the left most column If all queens are placed. return true and print the solu­tion matrix. Else Try all the rows in the cur­rent column.

Read full article from Backtracking - N Queens Problem | Algorithms