Backtracking – N Queens Problem – Better Solution

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:

This earlier approach we have seen 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.

result[i]=j means queen at i-th row is placed at j-th column.

Check if Queens placed at (x1, y1) and (x2,y2) are safe

  • x1==x2 means same rows,
  • y1==y2 means same columns
  • |x2-x1|==|y2-y1| means they are placed in diagonals.

Code:


import java.util.Arrays;
public class NQueens {
static int[] result; // this array will store the result
// result[i]=j; means queen at i-th row is placed at j-th column.
// Queens placed at (x1, y1) and (x2,y2)
// x1==x2 means same rows, y1==y2 means same columns, |x2-x1|==|y2-y1| means
// they are placed in diagonals.
public boolean canPlace(int x2, int y2) {
// This function will check if queen can be placed (x2,y2), or we can
// say that Can queen at x2 row is placed at y2 column.
// for finding the column for x2 row, we will check all the columns for
// all the rows till x2-1.
for (int i = 0; i < x2; i++) {
//result[i] == y2 => columns are same
//|i – x2| == |result[i] – y2| => in diagonals.
if ((result[i] == y2)
|| (Math.abs(i – x2) == Math.abs(result[i] – y2))) {
return false;
}
}
return true;
}
public void placeQueens(int x, int size) {
for (int i = 0; i < size; i++) {
//check if queen at xth row can be placed at i-th column.
if (canPlace(x, i)) {
result[x] = i; // place the queen at this position.
if (x == size – 1) {
System.out.println("Order of " + size + " queens"
+ Arrays.toString(result));
}
placeQueens(x + 1, size);
}
}
}
public static void main(String[] args) {
int n = 6;
result = new int[n];
NQueens i = new NQueens();
i.placeQueens(0, n);
}
}

view raw

NQueens.java

hosted with ❤ by GitHub 

Output:	
Order of 6 queens[1, 3, 5, 0, 2, 4]
Order of 6 queens[2, 5, 1, 4, 0, 3]
Order of 6 queens[3, 0, 4, 1, 5, 2]
Order of 6 queens[4, 2, 0, 5, 3, 1]

Reference :”https://www.youtube.com/watch?v=p4_QnaTIxkQ”

Related Posts: