Backtracking — N Queens Problem

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

N Queens Problem

Approach: In this approach we will see the basic solu­tion with O(N^2) extra space we will improve it fur­ther to O(N) space. Click here to see the solu­tion.

  • 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:

  1. Place the queens col­umn wise, start from the left most column
  2. If all queens are placed.
    1. return true and print the solu­tion matrix.
  3. Else
    1. Try all the rows in the cur­rent column.
    2. Check if queen can be placed here safely if yes mark the cur­rent cell in solu­tion matrix as 1 and try to solve the rest of the prob­lem recursively.
    3. If plac­ing the queen in above step leads to the solu­tion return true.
    4. If plac­ing the queen in above step does not lead to the solu­tion , BACKTRACK, mark the cur­rent cell in solu­tion matrix as 0 and return false.
  4. If all the rows are tried and noth­ing worked, return false and print NO SOLUTION.

Bet­ter Solu­tion: If you notice in 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 col­umn. Click here to see the Bet­ter Solu­tion.

Com­plete Code:

Output:
 0 0 1 0
 1 0 0 0
 0 0 0 1
 0 1 0 0

Ref­er­ence :
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf
http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

You may also like...

  • Car­los de la Torre

    A clas­sic in Com­puter Sci­ences. You’ll find this use­ful: https://thewalnut.io/visualizer/visualize/3595/267/
    It is a visu­al­iza­tion of the N-Queens, solved using a dif­fer­ent algo­rithm. It is con­sid­ered a con­straint sat­is­fac­tion prob­lem and uses a local-search algo­rithm (with a min-conflicts heuris­tic) to solve it. The code is also there, although in Javascript. I think it would be inter­est­ing to port this recur­sive imple­men­ta­tion to Python or Javascript and come up with another cool visualization.

  • wil­son

    here can we solve by plac­ing queen row wise??

    • Pradeep Muru­gan

      Yes it’s similar

  • Soham Patel Patel