Posts N-Queens II
Post
Cancel

N-Queens II

Problem Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

leetcode

Solution

First part of the question:

N-Queens I

Similar to N-Queens I, we go through each row one by one as we can place only a single queen in any given row. For each row, we try to check if we can place the queen on any of the columns. If a column is present, check for [row+1, 0] to [row+1, endOfColumn] for the next queen which can be placed. If it’s not possible to place it, we can move to the next square. To check if it’s possible to place a certain queen at any place, we mainly need to consider its cells above, cells in the same row, left diagonal and right diagonal.

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
class Solution {

    public int totalNQueens(int n) {

        // Create an n x n chessboard represented by a 2D array.
        int[][] board = new int[n][n];

        // Start the recursive solving process and return the result.
        return check(board, 0, n);

    }

    // Recursive function to solve the N-Queens puzzle.
    public int check(int[][] board, int row, int n){

        // If we have successfully placed all queens (reached the end of the board), return 1 solution.
        if(row == n){
            return 1;
        }

        int total = 0; // Counter to keep track of the total number of solutions.

        // Iterate through each column in the current row and try placing a queen.
        for(int c=0; c<board[0].length; c++){

            if(canPlaceQueen(board, row, c)){

                // Place the queen in the current cell.
                board[row][c] = 1;

                // Recur for the next row and add the number of solutions obtained from it.
                total += check(board, row+1, n);

                // Backtrack: Remove the queen from the current cell to explore other possibilities.
                board[row][c] = 0; // Set the cell value back to 0

            }

        }

        return total;

    }

    // Function to check if it's safe to place a queen in the given cell.
    public boolean canPlaceQueen(int[][] board, int i, int j){

        // Check the current row for any queen conflict.
        // This part can actually be removed because we are any way ensure that we move to the next row after placing a queen in the current row.
        for(int x=0; x<board[0].length; x++){
            if(board[i][x] == 1) return false;
        }

        // Check the current column for any queen conflict.
        for(int x=i; x>=0; x--){
            if(board[x][j] == 1) return false;
        }

        // Check the left diagonal for any queen conflict.
        for(int x=i, y=j; x>=0 && y>=0; x--, y--){
            if(board[x][y] == 1) return false;
        }

        // Check the right diagonal for any queen conflict.
        for(int x=i, y=j; x>=0 && y<board[0].length; x--, y++){
            if(board[x][y] == 1) return false;
        }

        return true; // If no conflicts are found, it's safe to place a queen in the cell.

    }

}
This post is licensed under CC BY 4.0 by the author.