C++ & Recursive Backtracking with simple valid check on row, col, diagonal and anti-diagonal.


  • 0
    B

    This post is simple, straightforward way to understand the problem. Not the most efficient way. I initialize all the strings in the beginning to make it clear. If you build one row at a time, some of the checks in the isvalid function could be avoided. There are better solution posted if you want to optimize.

    https://discuss.leetcode.com/topic/13617/accepted-4ms-c-solution-use-backtracking-and-bitmask-easy-understand This one has clear explanation and optimization.

    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string>> result; // each string will be n
            string s(n, '.');
            vector<string> board(n, s);
            helper(result, board, 0, n);
            
            return result;
        }
        
        void helper(vector<vector<string>>& result, vector<string> board, int row, int n)
        {
            if(row==n) 
            {
                result.push_back(board);
                return;
            }
            
            
            for(int c=0; c<n; c++)
            {
            
                if(isValid(board, row, c, n)) 
                {   
                    board[row][c]='Q';
                    helper(result, board, row+1, n);
                    board[row][c]='.';
                }
            }
        }
        
        bool isValid(vector<string>& board,int row,int col, int n)
        {
            for(int i=0; i<n; i++) // check all columns
            {
                if(i!=col && board[row][i]=='Q') return false;
            }
            
            for(int i=0; i<n; i++) // check all rows
            {
                if(i!=row && board[i][col]=='Q') return false;
            }
            
            for(int i=row+1, j=col+1; i<n && j<n; i++, j++) //diagonal down
            {
                if(board[i][j]=='Q') return false;
            }
            
            for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)// diagonal up
            {
                if(board[i][j]=='Q') return false;
            }
            
            for(int i=row+1, j=col-1; i<n && j>=0; i++, j--) // anti diagonal down
            {
                if(board[i][j]=='Q') return false;
            }
            
            for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++)// anti diagonal up
            {
                if(board[i][j]=='Q') return false;
            }
            
            return true;
        }
        
        
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.