The N Queen is the problem of placing N Chess queens on an N×N chessboard so that no two queens attack each other.
Let us first understand what we want to achieve? what is the input and what will be the expected output?
You are given a chess board of N * N size, you have to place N Queens in chess board in such a way that no queens are attacking each other.
Sample Input and output for 4 * 4 chess board
Remember, Queens attacks on same row, on same column as well as diagonally.
In the sample example shown above, you can see in the output section there is 1d array with values,
[1, 3, 0, 2] What it represents is,
1 = At row 0, Queen is placed at 1st column.
3 = At row 1, Queen is placed at 3rd column.
0 = At row 2, Queen is placed at 0th column.
2 = At row 3, Queen is placed at 2nd column.
So, 1d array gives us sufficient information on N Queens position information.
Same thing can be represented using 2d array like shown below, but if you observe, we are interested in only positions of Queen in each row and no need of complete 2d array as there is lot of waste space in considering 2d array, which can be optimized by taking 1d array.
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
We will take 1 dimensional array of size N and then fill the x coordinates of queens placed in each row.
arr[row] = col;
Example:
arr[0] = 1; At row 0, queen is placed at column 1.
arr[1] = 3; At row 1, queen is placed at column 3.
arr[2] = 0; At row 2, queen is placed at column 0.
arr[3] = 2; At row 3, queen is placed at column 2.
Algorithm
In the last pose we saw, N Queens Puzzle using 2D array
In this post, We will use Backtracking algorithm approach for placing N Queens on N*N chess board.
- Since Queens attack on same rows, only one Queen per row can be set.
- Since Queens attack on same column, only one Queen per column can be set.
- We can start placing Queens either column wise that is one column at a time or can start placing Queens row wise that is one row at a time. We will be using Row wise placement. Start from Row 0, check the safe position to place on Row 0 and place a queen on row 0. once queen is placed on Row 0, move to Row 1 and so on.
- Before placing a queen on any position in a row, we first check is there any other already placed queens on prior rows attacking on this position. if no already placed queen is attacking, then only place a queen on position.
- So when we are working on say Row 2. and we are looking for safe position on Row 2, then we need to check the safe position on Row 2 against Row 1 and Row 0 as that are the rows where we already placed a Queens.
- If queen placement is not leading to a solution, then backtrack and change the position of already placed queen and retry.
How to check position is safe to place a Queen.
Consider placing the queen at position (2, 2), Which Queens can attack at this position?
array[1]=1 array[1]=3
\ /
array[2]=2
/ \
array[3]=1 array[3]=3
1. We need to check that there is no attack from same column.
Before placing a queen in row 1, we will check in which column queen at row 0 is placed, this can
be done by checking,
array[1]==array[0]
in general it is, array[n] = array[i],
here n is the row at which we are trying to place a queen say 1 and
i the loop from 0 to n-1, in our case it is 0
It means if we are working for say row 2, and safe position in row 2 can be checked by,
array[row] == array[previousRows].
if value of array[2] is equal to array[0] or array[2] is equal to array[1] then column at where we
are trying to place a queen at row 2 is not safe position and some other Queen is present at same
column above.
2. We need to check that there is no attack from upper left and upper right diagonal.
Two queens are on the same diagonal by checking the differences between the rows and columns
of the two Queens.
If the differences are the same, they're on the same diagonal.
Basically, if the slope of the line between the two queens is +-1, they're on the same diagonal.
Let us take an example here.
Assume that we already placed first queen in (2, 2) – 2nd queen is placed in 2nd column.
If we look at the diagonal cells (1,1), (1,3), (3,1), (3.3), we can observe that,
So diagonal cells of array[2]=2 is,
array[1]=1 array[1]=3
\ /
array[2]=2
/ \
array[3]=1 array[3]=3
|x1 - x2| == |y1 - y2| then some Queen is attacking diagonally.
|1 - 2| == |1 - 2| = 1 (for cell 1,1)
|1 - 2| == |3 - 2| = 1 (for cell 1,3)
|3 - 2| == |1 - 2| = 1 (for cell 3,1)
|3 - 2| == |3 - 2| = 1 (for cell 3,3)
(ColumnOfRow2 - ColumnOfRow1) == (Row2 - Row1)
for checking two queens are on same minor diagonal in our case it is array[1]=1
(ColumnOfRow1 - ColumnOfRow2) == (Row2 - Row1)
for checking two queens are on same major diagonal in our case it is array[1]=3
Java Program to place N Queens on N*N Chess board.
package javabypatel.backtracking;
public class NQueens1DArray {
public static void main(String[] args) {
placeQueens(4);
}
private static void placeQueens(int gridSize) {
//If Grid is 1*1 or 2*2 or 3*3 then solution is not possible as,
//In 1*1 or 2*2 grid, Queen placed in 1st row at any position will attack queen placed at all the positions in row 2.
//In 3*3 grid, Queen placed in 1st row and 2nd row for all combinations position will attack queen placed at all the positions in row 3.
if(gridSize<4){
System.out.println("No Solution available");
}else{
int[] board = new int[gridSize]; // Lets take example of 4*4
placeAllQueens(board, 0);
printBoard(board);
}
}
private static boolean placeAllQueens(int[] board, int row) {
if(row == board.length){
return true;
}
boolean isAllQueensPlaced = false;
for (int column = 0; column < board.length; column++) {
board[row] = column;
if(isSafe(board, row)){
isAllQueensPlaced = placeAllQueens(board, row+1);
}
if(isAllQueensPlaced){
return true;
}
}
return false;
}
// Return true if queen placement board[row] does not conflict with
// other queens board[0] through board[row-1]
private static boolean isSafe(int[] board, int row) {
for (int i = 0; i < row; i++) {
//Check any column
if(board[row] == board[i]){
return false;
}
//Check upper left and upper right diagonal
if(Math.abs(board[row] - board[i]) == Math.abs(row-i)){
return false;
}
}
return true;
}
private static void printBoard(int[] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if(j==board[i]){
System.out.print("Q ");
}else{
System.out.print("_ ");
}
}
System.out.println();
}
}
}
Output:
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
You may also like to see
N Queens Puzzle using 2D array.
Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Tower Of Hanoi Program in Java.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment