Backtracking – N Queens Problem

by

Objective : In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary 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 solving it for N queens in NxN chess board.

N Queens Problem

Approach: In this approach we will see the basic solution with O(N^2) extra space we will improve it further to O(N) space. Click here to see the solution.

  • Create a solution matrix of the same structure as chess board.
  • Whenever place a queen in the chess board, mark that particular cell in solution matrix.
  • At the end print the solution matrix, the marked cells will show the positions of the queens in the chess board.

Algorithm:

  1. Place the queens column wise, start from the left most column
  2. If all queens are placed.
    1. return true and print the solution matrix.
  3. Else
    1. Try all the rows in the current column.
    2. Check if queen can be placed here safely if yes mark the current cell in solution matrix as 1 and try to solve the rest of the problem recursively.
    3. If placing the queen in above step leads to the solution return true.
    4. If placing the queen in above step does not lead to the solution , BACKTRACK, mark the current cell in solution matrix as 0 and return false.
  4. If all the rows are tried and nothing worked, return false and print NO SOLUTION.

Better Solution: If you notice in solution matrix, at every row we have only one entry as 1 and rest of the entries are 0. Solution matrix takes O(N2) space. We can reduce it to O(N). We will solve it by taking one dimensional array and consider solution[1] = 2 as “Queen at 1st row is placed at 2nd column. Click here to see the Better Solution.

Complete Code:


public class NQueensBT {
public int[][] solution;
public NQueensBT(int N) {
solution = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
solution[i][j] = 0;
}
}
}
public void solve(int N) {
if(placeQueens(0, N)){
//print the result
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(" " + solution[i][j]);
}
System.out.println();
}
}else{
System.out.println("NO SOLUTION EXISTS");
}
}
public boolean placeQueens(int queen, int N) {
// will place the Queens one at a time, for column wise
if(queen==N){
//if we are here that means we have solved the problem
return true;
}
for (int row = 0; row < N; row++) {
// check if queen can be placed row,col
if (canPlace(solution, row, queen)) {
// place the queen
solution[row][queen] = 1;
// solve for next queen
if(placeQueens(queen+1, N)){
return true;
}
//if we are here that means above placement didn't work
//BACKTRACK
solution[row][queen]=0;
}
}
//if we are here that means we haven't found solution
return false;
}
// check if queen can be placed at matrix[row][column]
public boolean canPlace(int[][] matrix, int row, int column) {
// since we are filling one column at a time,
// we will check if no queen is placed in that particular row
for (int i = 0; i < column; i++) {
if (matrix[row][i] == 1) {
return false;
}
}
// we are filling one column at a time,so we need to check the upper and
// diagonal as well
// check upper diagonal
for (int i = row, j = column; i >= 0 && j >= 0; i–, j–) {
if (matrix[i][j] == 1) {
return false;
}
}
// check lower diagonal
for (int i = row, j = column; i < matrix.length && j >= 0; i++, j–) {
if (matrix[i][j] == 1) {
return false;
}
}
// if we are here that means we are safe to place Queen at row,column
return true;
}
public static void main(String[] args) {
int N = 4;
NQueensBT q = new NQueensBT(N);
q.solve(N);
}
}

view raw

NQueensBT.java

hosted with ❤ by GitHub 

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

Reference :

Click to access H19-RecBacktrackExamples.pdf


http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

Related Posts:

4 thoughts on “Backtracking – N Queens Problem”

  1. A classic in Computer Sciences. You’ll find this useful: https://thewalnut.io/visualizer/visualize/3595/267/
    It is a visualization of the N-Queens, solved using a different algorithm. It is considered a constraint satisfaction problem and uses a local-search algorithm (with a min-conflicts heuristic) to solve it. The code is also there, although in Javascript. I think it would be interesting to port this recursive implementation to Python or Javascript and come up with another cool visualization.

    Reply

Leave a Reply to wilson Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.