N Queens Problem in Java using Backtracking
N Queen problem is of placing N 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 is the expected output?
You are given a chess board of N * N size, you have to place N Queens on a chess board in such a way that no queens are attacking each other.
Note: Queens attacks on same row, on same column as well as diagonally.
Sample Input and output for 4 * 4 chess board
Algorithm
We will use Backtracking algorithm for placing N Queens on N*N chess board.
1. Since Queens attack on same rows, so only one Queen per row can be set.
2. Since Queens attack on same column, so only one Queen per column can be set.
3. 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.
4. 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.
5. 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.
6. If queen placement is not leading to a solution, then backtrack and change the position of already
placed queen and retry.
Java Program to place N Queens on N*N Chess board.
package javabypatel;
public class NQueens2DArray {
public static void main(String[] args) {
placeQueens(4); // Lets take example of 4*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][gridSize];
placeAllQueens(board, 0);
printBoard(board);
}
}
private static boolean placeAllQueens(int board[][], int row){
if(row>=board.length){
return true;
}
boolean isAllQueensPlaced = false;
for (int j = 0; j < board.length; j++) {
if(isSafe(board, row, j)){
board[row][j] = 1;
isAllQueensPlaced = placeAllQueens(board, row+1);
}
if(isAllQueensPlaced){
break;
}else{
board[row][j] = 0;
}
}
return isAllQueensPlaced;
}
private static boolean isSafe(int board[][], int row, int col){
//Check Left Upper Diagonal
for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
if(board[i][j] == 1){
return false;
}
}
//Check Right Upper Diagonal
for (int i = row-1, j = col+1; i >= 0 && j < board.length; i--, j++) {
if(board[i][j] == 1){
return false;
}
}
//Check in same Column
for (int i = row-1; i >= 0; i--) {
if(board[i][col] == 1){
return false;
}
}
return true;
}
private static void printBoard(int[][] board){
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board.length; col++) {
if(board[row][col] == 1){
System.out.print("Q ");
}else{
System.out.print("_ ");
}
}
System.out.println();
}
System.out.println("");
}
}
Output:
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
You may also like to see
N Queens Puzzle Optimized using 1D 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
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment