Leetcode 52 Solution

This article provides solution to leetcode question 52 (n-queens-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 52" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/n-queens-ii

Solution

class Solution {
    int m_count;
public:
    void solveNQueens(vector<int>& board, int n, int layer)
    {
        if (board.size() == layer)
        {
            m_count++;
            return;
        }



        for (int i = 0; i < n; i++)
        {
            board[layer] = i;



            bool valid = true;
            for (int j = 0; j < layer; j++)
            {
                if (board[j] == i || abs(board[j] - i) == abs(j - layer))
                {
                    valid = false;
                    break;
                }
            }



            if (valid)
                solveNQueens(board, n, layer + 1);
        }
    }



    int totalNQueens(int n) {
        m_count = 0;
        vector<int> board(n);
        solveNQueens(board, n, 0);
        return m_count;
    }
};