Java program to solve NQueens Problem, using iterative approach and stack.
Note that this program finds all solutions, not only fundamental ones(rest can be obtained by rotating the board).
Main.java
import java.util.Scanner;
// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
System.out.println("NQueens Problem algorithm");
System.out.println("TheFlyingKeyboard.net 2018");
System.out.println("Enter size of a board");
NQueensSolver nQueensSolver = new NQueensSolver(reader.nextInt());
nQueensSolver.printSolutions();
}
}
NQueensSolver.java
import java.util.Stack;
// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class NQueensSolver {
private char[][] currentBoard;
private Stack<char[][]> previousBoards = new Stack<>();
private Stack<Integer> yPositions = new Stack<>();
private int xPosition = 0;
private int yPosition = 0;
private int solutionCount = 0;
private boolean isOver = false;
public NQueensSolver(int boardSize){
currentBoard = new char[boardSize][boardSize];
for(int i = 0; i < boardSize; ++i){
for(int j = 0; j < boardSize; ++j){
currentBoard[i][j] = ' ';
}
}
}
public void printSolutions(){
boolean isEmpty;
while(!isOver){
isEmpty = currentBoard[yPosition][xPosition] == ' ';
if(isEmpty){
if(xPosition == currentBoard.length - 1){
placeQueen();
++solutionCount;
printBoard();
goBack();
}else{
previousBoards.push(copy(currentBoard));
yPositions.push(yPosition);
placeQueen();
++xPosition;
yPosition = -1;
}
}else{
goBack();
}
++yPosition;
}
}
private void goBack(){
while(yPosition == currentBoard.length - 1){
if(previousBoards.size() == 0){
isOver = true;
return;
}
--xPosition;
yPosition = yPositions.pop();
currentBoard = previousBoards.pop();
}
}
private char[][] copy(char[][] arrayToCopy){
char[][] arrayCopy = new char[arrayToCopy.length][];
for(int i = 0; i < arrayToCopy.length; ++i)
{
char[] newArray = arrayToCopy[i];
int arrayLength = newArray.length;
arrayCopy[i] = new char[arrayLength];
System.arraycopy(newArray, 0, arrayCopy[i], 0, arrayLength);
}
return arrayCopy;
}
private void printBoard(){
for(int i = 0; i < currentBoard.length; ++i){
for (int j = 0; j < currentBoard.length; ++j){
System.out.print(currentBoard[i][j]);
}
System.out.println();
}
System.out.println("Solution number " + solutionCount);
System.out.println();
}
private void placeQueen(){
placeStraightX();
placeDiagonalX();
currentBoard[yPosition][xPosition] = 'Q';
}
private void placeStraightX(){
for(int i = 0; i < currentBoard.length; ++i){
currentBoard[i][xPosition] = 'X'; //Vertical
currentBoard[yPosition][i] = 'X'; //Horizontal
}
}
private void placeDiagonalX(){
int nextX = xPosition + 1;
int nextY = yPosition + 1;
while(nextX < currentBoard.length && nextY < currentBoard.length){
if(currentBoard[nextY][nextX] != 'Q'){
currentBoard[nextY][nextX] = 'X';
}
++nextY;
++nextX;
}
nextX = xPosition + 1;
nextY = yPosition - 1;
while(nextX < currentBoard.length && nextY >= 0){
if(currentBoard[nextY][nextX] != 'Q'){
currentBoard[nextY][nextX] = 'X';
}
--nextY;
++nextX;
}
}
}
Output
IN 10 OUT QXXXXXXX XXXXXXQX XXXXQXXX XXXXXXXQ XQXXXXXX XXXQXXXX XXXXXQXX XXQXXXXX Solution number 1 QXXXXXXX XXXXXXQX XXXQXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXXQXXX XXQXXXXX Solution number 2 QXXXXXXX XXXXXQXX XXXXXXXQ XXQXXXXX XXXXXXQX XXXQXXXX XQXXXXXX XXXXQXXX Solution number 3 QXXXXXXX XXXXQXXX XXXXXXXQ XXXXXQXX XXQXXXXX XXXXXXQX XQXXXXXX XXXQXXXX Solution number 4 XXXXXQXX QXXXXXXX XXXXQXXX XQXXXXXX XXXXXXXQ XXQXXXXX XXXXXXQX XXXQXXXX Solution number 5 XXXQXXXX QXXXXXXX XXXXQXXX XXXXXXXQ XQXXXXXX XXXXXXQX XXQXXXXX XXXXXQXX Solution number 6 XXXXQXXX QXXXXXXX XXXXXXXQ XXXQXXXX XQXXXXXX XXXXXXQX XXQXXXXX XXXXXQXX Solution number 7 XXQXXXXX QXXXXXXX XXXXXXQX XXXXQXXX XXXXXXXQ XQXXXXXX XXXQXXXX XXXXXQXX Solution number 8 XXXXQXXX QXXXXXXX XXXQXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXXXXQX XXQXXXXX Solution number 9 XXXXXXQX QXXXXXXX XXQXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX XQXXXXXX XXXXQXXX Solution number 10 XXXXQXXX QXXXXXXX XXXXXXXQ XXXXXQXX XXQXXXXX XXXXXXQX XQXXXXXX XXXQXXXX Solution number 11 XXXQXXXX QXXXXXXX XXXXQXXX XXXXXXXQ XXXXXQXX XXQXXXXX XXXXXXQX XQXXXXXX Solution number 12 XQXXXXXX XXXXXQXX QXXXXXXX XXXXXXQX XXXQXXXX XXXXXXXQ XXQXXXXX XXXXQXXX Solution number 13 XXXXQXXX XXQXXXXX QXXXXXXX XXXXXXQX XQXXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX Solution number 14 XXXXXXXQ XXQXXXXX QXXXXXXX XXXXXQXX XQXXXXXX XXXXQXXX XXXXXXQX XXXQXXXX Solution number 15 XXXQXXXX XXXXXQXX QXXXXXXX XXXXQXXX XQXXXXXX XXXXXXXQ XXQXXXXX XXXXXXQX Solution number 16 XXXXQXXX XXXXXXQX QXXXXXXX XXXQXXXX XQXXXXXX XXXXXXXQ XXXXXQXX XXQXXXXX Solution number 17 XXXXXQXX XXQXXXXX QXXXXXXX XXXXXXXQ XXXQXXXX XQXXXXXX XXXXXXQX XXXXQXXX Solution number 18 XXXXQXXX XXQXXXXX QXXXXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXQXXXX XXXXXXQX Solution number 19 XXXXXQXX XXQXXXXX QXXXXXXX XXXXXXXQ XXXXQXXX XQXXXXXX XXXQXXXX XXXXXXQX Solution number 20 XXXQXXXX XXXXXXXQ QXXXXXXX XXQXXXXX XXXXXQXX XQXXXXXX XXXXXXQX XXXXQXXX Solution number 21 XXXXXXXQ XXXQXXXX QXXXXXXX XXQXXXXX XXXXXQXX XQXXXXXX XXXXXXQX XXXXQXXX Solution number 22 XXXQXXXX XXXXXXXQ QXXXXXXX XXXXQXXX XXXXXXQX XQXXXXXX XXXXXQXX XXQXXXXX Solution number 23 XXXQXXXX XXXXXXQX QXXXXXXX XXXXXXXQ XXXXQXXX XQXXXXXX XXXXXQXX XXQXXXXX Solution number 24 XXXXXQXX XXXQXXXX QXXXXXXX XXXXQXXX XXXXXXXQ XQXXXXXX XXXXXXQX XXQXXXXX Solution number 25 XXXXXQXX XXQXXXXX QXXXXXXX XXXXXXQX XXXXQXXX XXXXXXXQ XQXXXXXX XXXQXXXX Solution number 26 XXXXXXQX XXQXXXXX QXXXXXXX XXXXXQXX XXXXXXXQ XXXXQXXX XQXXXXXX XXXQXXXX Solution number 27 XXXXQXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX XQXXXXXX Solution number 28 XQXXXXXX XXXXQXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX Solution number 29 XQXXXXXX XXXXXXXQ XXXXXQXX QXXXXXXX XXQXXXXX XXXXQXXX XXXXXXQX XXXQXXXX Solution number 30 XXXXXQXX XQXXXXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXQXXX XXXXXXXQ XXXQXXXX Solution number 31 XXXXXXQX XQXXXXXX XXXQXXXX QXXXXXXX XXXXXXXQ XXXXQXXX XXQXXXXX XXXXXQXX Solution number 32 XXXXXXXQ XQXXXXXX XXXQXXXX QXXXXXXX XXXXXXQX XXXXQXXX XXQXXXXX XXXXXQXX Solution number 33 XXXXQXXX XQXXXXXX XXXXXXXQ QXXXXXXX XXXQXXXX XXXXXXQX XXQXXXXX XXXXXQXX Solution number 34 XXXXXQXX XQXXXXXX XXXXXXQX QXXXXXXX XXXQXXXX XXXXXXXQ XXXXQXXX XXQXXXXX Solution number 35 XXXXQXXX XQXXXXXX XXXXXQXX QXXXXXXX XXXXXXQX XXXQXXXX XXXXXXXQ XXQXXXXX Solution number 36 XXQXXXXX XXXXQXXX XXXXXXQX QXXXXXXX XXXQXXXX XQXXXXXX XXXXXXXQ XXXXXQXX Solution number 37 XXXXXQXX XXXQXXXX XXXXXXQX QXXXXXXX XXXXXXXQ XQXXXXXX XXXXQXXX XXQXXXXX Solution number 38 XXXXQXXX XXXXXXXQ XXXQXXXX QXXXXXXX XXXXXXQX XQXXXXXX XXXXXQXX XXQXXXXX Solution number 39 XXQXXXXX XXXXXQXX XXXXXXXQ QXXXXXXX XXXXQXXX XXXXXXQX XQXXXXXX XXXQXXXX Solution number 40 XXXXXXQX XXXXQXXX XXQXXXXX QXXXXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXQXXXX Solution number 41 XXXXXQXX XXXQXXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXQXXX XQXXXXXX XXXXXXXQ Solution number 42 XXXXQXXX XXXXXXXQ XXXQXXXX QXXXXXXX XXQXXXXX XXXXXQXX XQXXXXXX XXXXXXQX Solution number 43 XXQXXXXX XXXXXQXX XXXQXXXX QXXXXXXX XXXXXXXQ XXXXQXXX XXXXXXQX XQXXXXXX Solution number 44 XXQXXXXX XXXXXQXX XXXXXXXQ QXXXXXXX XXXQXXXX XXXXXXQX XXXXQXXX XQXXXXXX Solution number 45 XXXXQXXX XXXXXXQX XXXQXXXX QXXXXXXX XXQXXXXX XXXXXXXQ XXXXXQXX XQXXXXXX Solution number 46 XQXXXXXX XXXXXQXX XXXXXXXQ XXQXXXXX QXXXXXXX XXXQXXXX XXXXXXQX XXXXQXXX Solution number 47 XQXXXXXX XXXXQXXX XXXXXXQX XXXQXXXX QXXXXXXX XXXXXXXQ XXXXXQXX XXQXXXXX Solution number 48 XQXXXXXX XXXXXXQX XXXXQXXX XXXXXXXQ QXXXXXXX XXXQXXXX XXXXXQXX XXQXXXXX Solution number 49 XXXXXXQX XQXXXXXX XXXXXQXX XXQXXXXX QXXXXXXX XXXQXXXX XXXXXXXQ XXXXQXXX Solution number 50 XXXXXXXQ XQXXXXXX XXXXQXXX XXQXXXXX QXXXXXXX XXXXXXQX XXXQXXXX XXXXXQXX Solution number 51 XXXQXXXX XQXXXXXX XXXXXXXQ XXXXXQXX QXXXXXXX XXQXXXXX XXXXQXXX XXXXXXQX Solution number 52 XXXQXXXX XQXXXXXX XXXXXXQX XXXXQXXX QXXXXXXX XXXXXXXQ XXXXXQXX XXQXXXXX Solution number 53 XXQXXXXX XXXXXQXX XQXXXXXX XXXXXXQX QXXXXXXX XXXQXXXX XXXXXXXQ XXXXQXXX Solution number 54 XXQXXXXX XXXXQXXX XQXXXXXX XXXXXXXQ QXXXXXXX XXXXXXQX XXXQXXXX XXXXXQXX Solution number 55 XXXXXQXX XXXXXXXQ XQXXXXXX XXXQXXXX QXXXXXXX XXXXXXQX XXXXQXXX XXQXXXXX Solution number 56 XXQXXXXX XXXXXXXQ XXXQXXXX XXXXXXQX QXXXXXXX XXXXXQXX XQXXXXXX XXXXQXXX Solution number 57 XXQXXXXX XXXXQXXX XXXXXXXQ XXXQXXXX QXXXXXXX XXXXXXQX XQXXXXXX XXXXXQXX Solution number 58 XXXXXQXX XXQXXXXX XXXXXXQX XXXQXXXX QXXXXXXX XXXXXXXQ XQXXXXXX XXXXQXXX Solution number 59 XXXXXQXX XXQXXXXX XXXXQXXX XXXXXXQX QXXXXXXX XXXQXXXX XQXXXXXX XXXXXXXQ Solution number 60 XXXXXQXX XXQXXXXX XXXXQXXX XXXXXXXQ QXXXXXXX XXXQXXXX XQXXXXXX XXXXXXQX Solution number 61 XXXQXXXX XXXXXXXQ XXXXQXXX XXQXXXXX QXXXXXXX XXXXXXQX XQXXXXXX XXXXXQXX Solution number 62 XXXQXXXX XXXXXXQX XXXXQXXX XXQXXXXX QXXXXXXX XXXXXQXX XXXXXXXQ XQXXXXXX Solution number 63 XXXQXXXX XXXXXQXX XXXXXXXQ XXQXXXXX QXXXXXXX XXXXXXQX XXXXQXXX XQXXXXXX Solution number 64 XQXXXXXX XXXQXXXX XXXXXQXX XXXXXXXQ XXQXXXXX QXXXXXXX XXXXXXQX XXXXQXXX Solution number 65 XXXQXXXX XQXXXXXX XXXXQXXX XXXXXXXQ XXXXXQXX QXXXXXXX XXQXXXXX XXXXXXQX Solution number 66 XXXQXXXX XQXXXXXX XXXXXXXQ XXXXQXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXXQXX Solution number 67 XXQXXXXX XXXXXXQX XQXXXXXX XXXXXXXQ XXXXQXXX QXXXXXXX XXXQXXXX XXXXXQXX Solution number 68 XXQXXXXX XXXXXQXX XQXXXXXX XXXXQXXX XXXXXXXQ QXXXXXXX XXXXXXQX XXXQXXXX Solution number 69 XXQXXXXX XXXXXQXX XQXXXXXX XXXXXXQX XXXXQXXX QXXXXXXX XXXXXXXQ XXXQXXXX Solution number 70 XXXXQXXX XXXXXXQX XQXXXXXX XXXXXQXX XXQXXXXX QXXXXXXX XXXQXXXX XXXXXXXQ Solution number 71 XXXXQXXX XXXXXXQX XQXXXXXX XXXXXQXX XXQXXXXX QXXXXXXX XXXXXXXQ XXXQXXXX Solution number 72 XXXXXXQX XXXQXXXX XQXXXXXX XXXXQXXX XXXXXXXQ QXXXXXXX XXQXXXXX XXXXXQXX Solution number 73 XXXXXXQX XXXQXXXX XQXXXXXX XXXXXXXQ XXXXXQXX QXXXXXXX XXQXXXXX XXXXQXXX Solution number 74 XXXXQXXX XXXXXXQX XQXXXXXX XXXQXXXX XXXXXXXQ QXXXXXXX XXQXXXXX XXXXXQXX Solution number 75 XXQXXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXQXXXX QXXXXXXX XXXXXXQX XXXXQXXX Solution number 76 XXXXXXQX XXQXXXXX XXXXXXXQ XQXXXXXX XXXXQXXX QXXXXXXX XXXXXQXX XXXQXXXX Solution number 77 XXXQXXXX XXXXXXQX XXXXQXXX XQXXXXXX XXXXXQXX QXXXXXXX XXQXXXXX XXXXXXXQ Solution number 78 XXXQXXXX XXXXXQXX XXXXXXXQ XQXXXXXX XXXXXXQX QXXXXXXX XXQXXXXX XXXXQXXX Solution number 79 XXXXQXXX XXQXXXXX XXXXXXXQ XXXQXXXX XXXXXXQX QXXXXXXX XXXXXQXX XQXXXXXX Solution number 80 XQXXXXXX XXXXXXQX XXQXXXXX XXXXXQXX XXXXXXXQ XXXXQXXX QXXXXXXX XXXQXXXX Solution number 81 XXXQXXXX XQXXXXXX XXXXXXQX XXQXXXXX XXXXXQXX XXXXXXXQ QXXXXXXX XXXXQXXX Solution number 82 XXXXQXXX XQXXXXXX XXXQXXXX XXXXXQXX XXXXXXXQ XXQXXXXX QXXXXXXX XXXXXXQX Solution number 83 XXQXXXXX XXXXXXQX XQXXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX QXXXXXXX XXXXQXXX Solution number 84 XXXXXQXX XXXQXXXX XQXXXXXX XXXXXXXQ XXXXQXXX XXXXXXQX QXXXXXXX XXQXXXXX Solution number 85 XXXXXQXX XXQXXXXX XXXXXXQX XQXXXXXX XXXQXXXX XXXXXXXQ QXXXXXXX XXXXQXXX Solution number 86 XXXXXQXX XXQXXXXX XXXXXXQX XQXXXXXX XXXXXXXQ XXXXQXXX QXXXXXXX XXXQXXXX Solution number 87 XXXQXXXX XXXXXXQX XXQXXXXX XXXXXXXQ XQXXXXXX XXXXQXXX QXXXXXXX XXXXXQXX Solution number 88 XXXQXXXX XQXXXXXX XXXXXXQX XXQXXXXX XXXXXQXX XXXXXXXQ XXXXQXXX QXXXXXXX Solution number 89 XXXXQXXX XQXXXXXX XXXQXXXX XXXXXXQX XXQXXXXX XXXXXXXQ XXXXXQXX QXXXXXXX Solution number 90 XXQXXXXX XXXXQXXX XQXXXXXX XXXXXXXQ XXXXXQXX XXXQXXXX XXXXXXQX QXXXXXXX Solution number 91 XXQXXXXX XXXXXQXX XXXQXXXX XQXXXXXX XXXXXXXQ XXXXQXXX XXXXXXQX QXXXXXXX Solution number 92
Java NQueens Problem Iteration Stack-based Algorithm