Leetcode 52. N - Queens problem

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 234
Joined: Wed Oct 10, 2018 3:48 am

Leetcode 52. N - Queens problem

Post by dendiz » Mon Feb 11, 2019 11:07 pm

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
8-queens.png
8-queens.png (8.24 KiB) Viewed 39 times
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
This is a classical backtracking exhaustive search problem. There no shortcuts, you have to brute force through the entire search space.
But there are some space optimizations that we can do. Normally a NxN board would be represented by an NxN matrix, but we can use a Nx1 matrix and assign the index of a value to the row (or column). E.g

Code: Select all

Q . .
. Q .
. . Q
could be represented as

Code: Select all

{0, 1, 2}
meaning the i'th element is the column number that contains the Queen. With this approach we try to place a queen at every possible position and if the placement is valid we move on the next row and start all over until we placed a queen at each row and column.

Code: Select all

    int total = 0;
    public int f(int[] board, int idx, int n) {
        if (idx == n) {
            total++;
            return 1;
        }
        for(int i=0;i<n;i++) {
            if (isValid(board, idx, i)) {
                board[idx] = i;
                int r = f(board, idx + 1,n);
            }
        }
        return -1;
    }
In this piece of code, idx is the current row number. The validation code needs to check that there are no duplicates columns in the array for 0..current idx. Since each index is a separate row, we don't need to check for queens on the same row (there can be none anyway due to the representation we chose). To check the diagonals we check that i'th row - current row != i'th column - current column. If the difference in column and row are equal it means it's a diagonal.

Code: Select all

    public boolean isValid(int[] board, int idx, int col) {
        for(int i=0;i<idx;i++) {
            if (board[i] == col) return false;
            if (Math.abs(i - idx) == Math.abs(board[i] - col)) {
                return false;
            }
        }
        return true
    }
 

Post Reply