[LeetCode] N-Queens II

Problem: 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.

Example:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 9

Approach: This is classic backtracking problem. We will take a boolean 2D array of size n x n and we treat it like a chess board. Now at reach row starting from 0 to n in order, we will try to place queen at every possible column. When we see we can place queen at the last row safely, we can increase the number of solution by 1.

We can reduce the space by just taking 3 arrays one for columns of size n, and 2 for two diagonals of size 2n but as you see in the constraint n is always less than or equal to 9, we don't have to worry about it and make our solution complex.

Implementation in C#:

    public int TotalNQueens(int n)

    {

        if (n <= 1)

        {

            return n;

        }

        bool[,] board = new bool[n,n];

        return this.TotalNQueens(board, 0, n);

    }

    private int TotalNQueens(bool[,] board, int currRow, int n)

    {

        if (currRow == n)

        {

            return 1;

        }

        int result = 0;

        for (int i = 0; i < n; ++i)

        {

            if (this.CanPlaceQueen(board, currRow, i, n))

            {

                board[currRow, i] = true;

                result += this.TotalNQueens(board, currRow + 1, n);

                board[currRow, i] = false;

            }

        }

        return result;

    }

    private bool CanPlaceQueen(bool[,] board, int row, int col, int n)

    {

        for (int i = 0; i < n; ++i)

        {

            if (board[i,col])

            {

                return false;

            }

        }

        int r = row, c = col;

        while (r >= 0 && c >= 0)

        {

            if (board[r, c])

            {

                return false;

            }

            --r;

            --c;

        }

        r = row;

        c = col;

        while (r >= 0 && c < n)

        {

            if (board[r, c])

            {

                return false;

            }

            --r;

            ++c;

        }

        return true;

    }

Complexity: O(n * !n)