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
Tagged on:             

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close