N-Queens Problem
N- queen problem states that if no of queens are placed on a chessboard, then no two queens can attack each other.
The following program states the same:
package com.backtracking.test;
public class QueenProblem {
private int[][] chessTable;
private int numOfQueens;
public QueenProblem(int numOfQueens) {
this.chessTable = new int[numOfQueens][numOfQueens];
this.numOfQueens = numOfQueens;
}
public void solve() {
if (setQueens(0)) {
printQueens();
} else {
System.out.println("There is no solution..");
}
}
private boolean setQueens(int colIndex) {
if (colIndex == numOfQueens) {
return true;
}
for (int rowIndex = 0; rowIndex < numOfQueens; ++rowIndex) {
if (isPlaceValid(rowIndex, colIndex)) {
chessTable[rowIndex][colIndex] = 1; // Queeen is placed
if (setQueens(colIndex + 1)) {
return true;
}
// BACKTRACKING
chessTable[rowIndex][colIndex] = 0;
// if position is found incorrect then we have to reset the queen's position
}
}
return false;
}
private boolean isPlaceValid(int rowIndex, int colIndex) {
for (int i = 0; i < colIndex; i++) {
if (chessTable[rowIndex][i] == 1) {
return false;
}
}
// diagonals
for (int i = rowIndex, j = colIndex; i >= 0 && j >= 0; i--, j--) {
if (chessTable[i][j] == 1) {
return false;
}
}
// other diagonals
for (int i = rowIndex, j = colIndex; i < chessTable.length && j >= 0; i++, j--) {
if(chessTable[i][j] == 1) {
return false;
}
}
return true;
}
private void printQueens() {
for (int i = 0; i < chessTable.length; ++i) {
for (int j = 0; j < chessTable.length; ++j) {
if (chessTable[i][j] == 1) {
System.out.print(" Q ");
} else {
System.out.print(" - ");
}
}
System.out.println();
}
}
}
package com.backtracking.test;
public class QueensProblemTest {
public static void main(String[] args) {
QueenProblem queenProblem = new QueenProblem(20);
queenProblem.solve();
}
}
Output
Comments
Post a Comment