n queen problem | Backtracking

n queen problem

A classic chess puzzle

n queen problem is Place 8 queen pieces on a chess board so that none of them can attack one another

8 tuple chess - n queen problem


The N Queens Problem

  • Place N Queens on an N by N chessboard so that none of them can attack each other
  • Number of possible placements?
  • In 8 x 8

64 * 63 * 62 * 61 * 60 * 58 * 59 * 57 = 4,426,165,368  roughly four and a half billion possible set ups
n choose k
n queen problem

  • How many ways can you choose k things from a set of n items?
  • In this case there are 64 squares and we want to choose 8 of them to put queens on

State Space Tree of the Four-queens Problem

n queen problem - Backtracking


The Implicit tree for 4 queen problem for solution <2,4,1,3>

  • Build the state space tree
    — The Root represents an initial state
    — The Nodes reflect the specific choices made for the components of a solution.
    — Promising and non-promising nodes
    — leaves
  • Explore  The state space tree using depth-first search
  • “Prune” non-promising nodes
    —   dfs stops exploring subtree rooted at nodes leading to no solutions and…
    —   backtracks to its parent node

n queen problem
n queen problem
n queen problem

n queen problem algorithm

Void NQueens(int k, int n)
  // using backtracking, this prints all possible placements of n-queens
 //on an chessboard of size n×n so that none are not attacked.
 for(int i=1;i&amp;lt;=n;i++)
          for(int j=1;j&amp;lt;=n;j++)
          cout&amp;lt;&amp;lt;x[ j ]&amp;lt;&amp;lt;" ";
      else Nqueens(k+1,n);
 boolean place(int k, int i)
    // Returns true if a queen can be placed in kth row and ith column.
    //Returns false otherwise.
    for (int j=1;j&amp;lt;k;j++) 
       if((x[ j ] == i) || ((abs(x[ j ] – i ) == (abs(j-k)))
           return FALSE;
       return TRUE;

Topic : n queen problem | Backtracking

Leave a Reply