N Queen Problem using Backtracking | Java

Revision en4, by akattack, 2019-10-27 15:13:41

## What is N Queen Problem?

We are given N chess’s queens and is asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

• Same Row
• Same Column
• Same Diagonal (left or right)

Solution using Backtracking

import java.util.Scanner;

public class Board {

int chessBoard[][];
int queens;

public Board(int queens) {
chessBoard = new int[20][20];
this.queens = queens;
}

void displayBoard(){
int i, j;
for(i=0; i<queens; i++){
for(j=0; j<queens; j++){
if(chessBoard[i][j] == 1)
System.out.print(" * ");
else
System.out.print(" - ");
}
System.out.print("\n");
}
System.out.print("\n");
System.out.print("\n");
}

void reset(){
for(int i=0; i<queens; i++){
for(int j=0; j<queens; j++){
chessBoard[i][j] = 0;
}
}
}

boolean isValidPlace(int row, int col){
int i,j;

//Checking horizontally
for(i=col; i>=0; i--){
if(chessBoard[row][i] == 1)
return false;
}

//checking left diagonal
for(i=row, j=col; i>=0 && j>=0; i--,j--){
if(chessBoard[i][j] == 1)
return false;
}

//checking right diagonal
for(i=row, j=col; i<queens && j>=0; i++,j--){
if(chessBoard[i][j] == 1)
return false;
}

return true;
}
}

public class NQueen {

int queens;
boolean flag;
Board board;

public NQueen(int queens) {
this.flag = false;
this.board = new Board(queens);;
this.queens = queens;
}

void solveNqueen(){

int i;
//starting from (0,0) of the board
hasSolution(0,0);

//After running hasSolution() still flag == false
//It means no Solution
if(!flag)
System.out.println("No Solution");

}

boolean hasSolution(int ctr, int colQueen){

//Reached beyond last column
//Means solution (configuration) found

if(colQueen == queens){
flag = true;
board.displayBoard();
//intentionally returning false to find more possible solution
return false;
}

int i,j;
for(i=ctr; i<queens; i++){

//checking if position is safe
if(board.isValidPlace(i,colQueen)){
//setting current value to 1 means placing a queen
board.chessBoard[i][colQueen] = 1;
//moving to next column's 1st row
if(hasSolution(0,colQueen+1))
return true;

//backtrack
//reset to 0 means removing queen
board.chessBoard[i][colQueen] = 0;
}

}

//When no row is safe in current column
return false;
}
}

public class App {

static Scanner in = new Scanner(System.in);

public static void main(String args[]){
System.out.println("Enter number of Queens");
int queens = in.nextInt();

NQueen nQueen = new NQueen(queens);
nQueen.solveNqueen();

}
}

Reference: My Programming Blog

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 akattack 2019-10-27 15:13:41 7
en3 akattack 2019-10-17 18:18:22 37 Tiny change: 'ference: [Pencil Programmer](https://' -> 'ference: [My Programming Blog](https://'
en2 akattack 2019-10-17 18:16:10 28 Tiny change: 'Problem?\nWe are g' -> 'Problem?\n------------------------\n\nWe are g' (published)
en1 akattack 2019-10-17 18:15:25 3634 Initial revision (saved to drafts)