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

 

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

• 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

 

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 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<=n;i++)
  {
    if(place(k,i)) 
     {
       x[k]=i;
       if(k==n)
        {
          for(int j=1;j<=n;j++)
          cout<<x[ j ]<<" ";
       }
      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<k;j++) 
     {
       if((x[ j ] == i) || ((abs(x[ j ] – i ) == (abs(j-k)))
           return FALSE;
       return TRUE;
    }

Topic : n queen problem | Backtracking