Problem:
The N-Queens puzzle is one of the classical puzzle.
On a chess board, a queen can attack any chess on the same row, same column and on the cells in the 2 diagonal directions.
Given an integer n, we want to place n queens on a nxn chessboard, so that no two queens can attack each other.
We need to find the number of distinct solutions to the n-queens puzzle.
For Example:
given n = 4
There are two distinct solutions to put 4 queens on a 4x4 chessboard so that they can not attack each other. So the answer should be 2.
[
["xQxx", // Solution 1
"xxxQ",
"Qxxx",
"xxQx"],
["xxQx", // Solution 2
"Qxxx",
"xxxQ",
"xQxx"]
]
Solution:
This is a classic chess puzzle, we are seeking solution under constraint with try error. Track back is the technique we should use.
backtrack cell
iterate chess board cells
if cell is safe
put chess
if on last row
increase count
else
backtrack next cell
remove chess
When put a chess, we need to mark the cells on the same row, same column, same up slope diagonal and same down slope diagonal as unsafe.
These cells' can be grouped by their column and row numbers.
- cells on the same row has the same row number, the column number doesn't matter, we can use an array to group them int[] row = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element row[3] = 1, then all the cells with same row number 3 are marked as 1, no matter what are their column number.
- cells on the same column has the same column number, the row number doesn't matter, we can use another array to group them int[] col = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element col[2] = 1, then all the cells with the same column number 2 are marked as 1, no matter what are their row number.
- cells on the same up slope diagonal has the row number decrease while the column number increase, therefore the row + col number remains the same, we can use another array to group them int[] up = new int[2*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element up[3+2] = 1, then all the cells on the up slope diagonal are marked as 1, they are row 5 column 0, row 4 column 1, row 3 column 2, row 2 column 3, row 1 column 4 and row 0 column 5.
- cells on the same down slope diagonal has both the row number and column number increase, therefore the row - col number remains the same, we can use another array to group them int[] down = new int[3*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element down[2-3+2*N] unsafe, then all the cells on the down slope diagonal are marked as 1. The reason we add 2*N is because row - col can be a negative number, array index has to be non-negative. The range of row - col is from -2N to N, therefore, we add 2*N and the array size is 3*N. Given N = 6 for example, the same down slope cells are [0, 1], [1, 2], [2, 3], [3, 4], [4, 5].
Actually, we don't have to back track cell by cell, once we put a queen on a cell, we know the cells on the same row are invalid, so we should move a row instead of a cell for the next move.
class Solution {
int numOfSol = 0;
public static void main(String[] args) {
int n = 4;
int[][] board = new int[n][n];
int[] cols = new int[n]; //cells on the same column
int[] up = new int[2*n]; //cells on the up slop diagonal
int[] down = new int[3*n]; //cells on the down slop diagonal
System.out.println(nQueens(board, 0, 0, cols, up, down));
}
public static int nQueens(int[][] board, int row, int count, int[] cols, int[] up, int[] down) {
int n = board.length;
for(int col = 0; col < n; col++) {
/*
System.out.println("row=" + row + " col=" + col + " count =" + count);
Arrays.stream(cols).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(up).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(down).forEach(i -> System.out.print(i + " "));
System.out.println();
*/
if(isSafe(row, col, n, cols, up, down)) {
board[row][col] = 1;
cols[col] = 1; //mark cells on the same col unsafe, cells' row doesn't matter
up[row + col] = 1; //mark cells on the same up slope unsafe, cells' row decrease, col increase,the sum is the same
down[row - col + 2*n] = 1; //mark cells on the same down slope unsafe, cells' row and col increase, row - col is the same, add 2n to prevent ArrayIndexOutOfBoundsException
if(row + 1 == n) {
count++;
printBoard(board);
System.out.println();
} else {
count = nQueens(board, row + 1, count, cols, up, down);
}
board[row][col] = 0;
cols[col] = 0; //mark the same col cells safe
up[row + col] = 0; //mark the same up slope diagonal cells safe
down[row - col + 2*n] = 0; //mark the same down slope diagonal cells safe
}
}
return count;
}
private static boolean isSafe(int row, int col, int n, int[] cols, int[] up, int[] down) {
return cols[col] + up[row + col] + down[row-col + 2*n] == 0;
}
private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
int numOfSol = 0;
public static void main(String[] args) {
int n = 4;
int[][] board = new int[n][n];
int[] cols = new int[n]; //cells on the same column
int[] up = new int[2*n]; //cells on the up slop diagonal
int[] down = new int[3*n]; //cells on the down slop diagonal
System.out.println(nQueens(board, 0, 0, cols, up, down));
}
public static int nQueens(int[][] board, int row, int count, int[] cols, int[] up, int[] down) {
int n = board.length;
for(int col = 0; col < n; col++) {
/*
System.out.println("row=" + row + " col=" + col + " count =" + count);
Arrays.stream(cols).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(up).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(down).forEach(i -> System.out.print(i + " "));
System.out.println();
*/
if(isSafe(row, col, n, cols, up, down)) {
board[row][col] = 1;
cols[col] = 1; //mark cells on the same col unsafe, cells' row doesn't matter
up[row + col] = 1; //mark cells on the same up slope unsafe, cells' row decrease, col increase,the sum is the same
down[row - col + 2*n] = 1; //mark cells on the same down slope unsafe, cells' row and col increase, row - col is the same, add 2n to prevent ArrayIndexOutOfBoundsException
if(row + 1 == n) {
count++;
printBoard(board);
System.out.println();
} else {
count = nQueens(board, row + 1, count, cols, up, down);
}
board[row][col] = 0;
cols[col] = 0; //mark the same col cells safe
up[row + col] = 0; //mark the same up slope diagonal cells safe
down[row - col + 2*n] = 0; //mark the same down slope diagonal cells safe
}
}
return count;
}
private static boolean isSafe(int row, int col, int n, int[] cols, int[] up, int[] down) {
return cols[col] + up[row + col] + down[row-col + 2*n] == 0;
}
private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
The time complexity's upper bound is O(N!). Before we have conclusion, we have tried all the possibilities. The way we try all the possibilities is: pick one of the columns from first row, then pick a column at the second row with constraint, then third row, so on and so forth. There are N choices at first row, then at most (ignore diagonal constraint) N - 1 choices at the second row, then N - 2 choices at the next row, finally 1 choice at the last row. The space complexity is O(N*N), it is calculated as the sum of marker arrays and board array size. Actually, if we only need the count, the board array can be omitted, the marker array has O(N) size.
