Backtracking - N Queens Problem - Better Solution | Algorithms

Backtracking - N Queens Problem - Better Solution | 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: This ear­lier approach we have seen solu­tion matrix, at every row we have only one entry as 1 and rest of the entries are 0. Solu­tion matrix takes O(N2) space. We can reduce it to O(N). We will solve it by tak­ing one dimen­sional array and con­sider solution[1] = 2 as "Queen at 1st row is placed at 2nd column. result[i]=j means queen at i-th row is placed at j-th column. Check if Queens placed at (x1, y1) and (x2,y2) are safe x1==x2 means same rows, y1==y2 means same columns |x2-x1|==|y2-y1| means they are placed in diagonals.

Read full article from Backtracking - N Queens Problem - Better Solution | Algorithms