# 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&amp;lt;=n;i++)
{
if(place(k,i))
{
x[k]=i;
if(k==n)
{
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