Posts N-Queen Problem (geeksforgeeks - SDE Sheet)
Post
Cancel

N-Queen Problem (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

The n-queens puzzle is the problem of placing n queens on a (n×n) chessboard such that no two queens can attack each other. Given an integer n, find all distinct solutions to the n-queens puzzle. Each solution contains distinct board configurations of the n-queens placement, where the solutions are a permutation of [1,2,3..n] in increasing order, here the number in the ith place denotes that the ith-column queen is placed in the row with that number. For eg below figure represents a chessboard [3 1 4 2].

geeksforgeeks

SOLUTION

Each row can have at max 1 queen. So, in our recursive method, we keep incrementing only the row. For each row, we try to check if the queen can be placed between [0, N] one by one. If not, backtrack. Otherwise, place the queen and recursive do the same for next row. Once we have covered all the rows, we have a valid N queens setup, which we can add to the answer list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {

    public ArrayList<ArrayList<Integer>> nQueen(int n) {
        int[][] board = new int[n][n];
        return nQueenHelper(board, 0, new ArrayList<ArrayList<Integer>>());
    }

    public ArrayList<ArrayList<Integer>> nQueenHelper(int[][] board, int row, ArrayList<ArrayList<Integer>> res){

        int n = board.length;

        // If we've placed queens in all rows, store the solution
        if (row == n) {
            ArrayList<Integer> tempList = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 1) { // A queen is found at (i, j)
                        tempList.add(j + 1); // Store the 1-based column index
                        break; // Move to the next row after placing the queen
                    }
                }
            }
            // Add this solution to the result list
            res.add(tempList);
            return res;
        }

        // Try placing a queen in each column of the current row
        for (int column = 0; column < n; column++) {

            // Check if placing a queen at (row, column) is valid
            if (isValid(board, row, column)) {

                // Place the queen
                board[row][column] = 1;

                // Recursively place queen in the next row
                nQueenHelper(board, row + 1, res);

                // Backtrack by removing the queen
                board[row][column] = 0;

            }
        }

        return res;
    }

    // Function to check if placing a queen at (row, column) is valid
    public boolean isValid(int[][] board, int row, int column) {

        int n = board.length;

        // Check if there's any queen in the same column in previous rows
        for (int r = 0; r < row; r++) {
            if (board[r][column] == 1)
                return false;
        }

        // Check the left upper diagonal (top-left direction)
        int r = row;
        int c = column;
        while (r >= 0 && c >= 0) {
            if (board[r][c] == 1)
                return false;
            r--; c--; // Move diagonally up-left
        }

        // Check the right upper diagonal (top-right direction)
        r = row;
        c = column;
        while (r >= 0 && c < n) {
            if (board[r][c] == 1)
                return false;
            r--; c++; // Move diagonally up-right
        }

        // If no conflicts, return true
        return true;
    }
}
This post is licensed under CC BY 4.0 by the author.