Program to find all distinct solutions to N-Queens problem in Java

Post Views: 39

In this Java tutorial, we will find all solutions to N-Queens problem in java. We will use backtracking to find all unique solutions to the problem.

Problem Statement

An N*N chessboard is given. We have to place N queens on the chessboard so that no two queens can attack each other. We know that a queen can attack in a horizontal line, vertical line and also diagonally.

Input

A single integer N will be given as input. This N specifies the number of rows and columns for the chessboard.

Output

Print all distinct solutions of the problem. Each solution contains a distinct board configuration of all the queen’s placement. ‘Q’ denotes the presence of a queen whereas ‘.’ denotes empty space.
For example for N=4, print :

[ 
[".Q..",
 "...Q", 
 "Q...", 
 "..Q."], 

["..Q.",
 "Q...",
 "...Q", 
 ".Q.."] 
]

Algorithm

We build a solution by placing queens one column at a time. For a column, we check for each row to place the queen. If the current row does not conflict with the previously places queen then we go to the next column. Or else if the queen cannot be placed in any row, we backtrack to the previous column and try to find other configuration. When we fill all the columns, we add this configuration to the solution.

Start with the first column.
If all columns are complete, we find one solution.
For each row in the column check if the current position is safe or not.
If the position is safe, place the queen in the row and proceed to the next column. If this position does not lead to a solution, replace the queen with empty space (backtrack) and proceed.
Else if the row is not safe, go to the next row.
If all the rows of the column are not safe then backtrack to the previous column and search for another configuration.

Program to find all solutions to N-Queens problem in Java

import java.util.ArrayList;
import java.util.Scanner;


public class NQueen {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();

        char[][] board = new char[size][size];
        for (int rowNo = 0; rowNo < size; rowNo++) {
            for (int colNo = 0; colNo < size; colNo++) {
                board[rowNo][colNo] = '.';
            }
        }
        ArrayList<ArrayList<String>> ans = new ArrayList<>();

        NQueen(size, board, 0, ans);

        if (ans.size() == 0) {
            System.out.println("No solution!");
        } else {
            System.out.println(ans);
        }


    }

    public static void NQueen(int size, char[][] b, int colNo, ArrayList<ArrayList<String>> ans) {
        if (colNo == size) {
            ArrayList<String> al = new ArrayList<>();
            for (int rowNo = 0; rowNo < size; rowNo++) {
                char[] arr = b[rowNo];
                String s = new String(arr);
                al.add(s);
            }
            ans.add(al);
            return;
        }

        for (int rowNo = 0; rowNo < size; rowNo++) {

            if (isSafe(rowNo, colNo, b, size)) {

                b[rowNo][colNo] = 'Q';

                NQueen(size, b, colNo + 1, ans);

                b[rowNo][colNo] = '.';

            }
        }

        return;
    }

    public static boolean isSafe(int i, int j, char[][] b, int size) {

        for (int colNo = 0; colNo < j; colNo++) {
            if (b[i][colNo] == 'Q') {
                return false;
            }
        }
        int rowNo = i;
        int colNo = j;
        while (rowNo >= 0 && colNo >= 0) {
            if (b[rowNo][colNo] == 'Q') {
                return false;
            }
            rowNo--;
            colNo--;
        }
        colNo = j;
        rowNo = i;
        while (rowNo < size && colNo >= 0) {

            if (b[rowNo][colNo] == 'Q') {
                return false;
            }
            rowNo++;
            colNo--;
        }

        return true;

    }
}

Output for N=3:

No solution!

Output for N=5:

[[Q...., ...Q., .Q..., ....Q, ..Q..], [Q...., ..Q.., ....Q, .Q..., ...Q.], 
[..Q.., Q...., ...Q., .Q..., ....Q], [...Q., Q...., ..Q.., ....Q, .Q...], 
[.Q..., ...Q., Q...., ..Q.., ....Q], [....Q, ..Q.., Q...., ...Q., .Q...], 
[.Q..., ....Q, ..Q.., Q...., ...Q.], [....Q, .Q..., ...Q., Q...., ..Q..], 
[...Q., .Q..., ....Q, ..Q.., Q....], [..Q.., ....Q, .Q..., ...Q., Q....]]

Also, check out these posts: