Simple Backtrack with some explanations


  • 0
    A

    some notes:
    we know that queens attack horizontally, vertically and diagonally. So, we can have only one queen per row or column. That means we only have to go through the columns/rows, not the whole board.
    Also, using structures such as dx, dy make the code easier to understand.

     class Solution {
    public:
        vector<vector<string> > results;
        
        vector<vector<string> > solveNQueens(int n) {
            vector<string> curr;
            string init = "";
            for(int i = 0 ; i < n; i++)
                init +=".";
            for(int i = 0 ; i < n ; i++)
                curr.push_back(init);
            for(int i = 0; i < n; i++){
                curr[i][0]='Q';
                go(1,curr,n);
                curr[i][0]='.';
            }
            return results;
        }
        void go( int col, vector<string> &curr, int n){
            if (col == n){
    			results.push_back(curr);
    			return;
    		}
    		int dx[4] = { 1, 1, -1, -1 };
    		int dy[4] = { 1, -1, 1, -1 };
    		for (int i = 0; i <n; i++){
    			bool ok = true;
    			for (int j = 0; j < n; j++){
    				if (curr[i][j] == 'Q') 
    					ok = false;;
    			}
    			if (!ok) continue;
    			for (int p = 0; p < 4; p++){
    				int cur_row = i;
    				int cur_col = col;
    				while (cur_col <n && cur_col >= 0 && cur_row <n && cur_row >= 0){
    					if (curr[cur_row][cur_col] == 'Q') ok = false;
    					cur_row += dx[p];
    					cur_col += dy[p];
    				}
    			}
    			if (ok){
    				curr[i][col] = 'Q';
    			       go(col + 1, curr, n);
    
    				curr[i][col] = '.';
    			}
    		}
        }
    };

Log in to reply
 

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