C++ solution - DFS - easy understanding


  • 15
    L
    int totalNQueens(int n) {
        vector<bool> col(n, true);
        vector<bool> anti(2*n-1, true);
        vector<bool> main(2*n-1, true);
        vector<int> row(n, 0);
        int count = 0;
        dfs(0, row, col, main, anti, count);
        return count;
    }
    void dfs(int i, vector<int> &row, vector<bool> &col, vector<bool>& main, vector<bool> &anti, int &count) {
            if (i == row.size()) {
                count++;
                return;
            }
           for (int j = 0; j < col.size(); j++) {
             if (col[j] && main[i+j] && anti[i+col.size()-1-j]) {
                 row[i] = j; 
                 col[j] = main[i+j] = anti[i+col.size()-1-j] = false;
                 dfs(i+1, row, col, main, anti, count);
                 col[j] = main[i+j] = anti[i+col.size()-1-j] = true;
          }
        }
    }

  • 4
    C

    Nice job!
    I think row is useless, delete it is ok.

    class Solution {
    public:
    int totalNQueens(int n) {
    
    	int count = 0;
    	vector<bool> cols(n, true);
    	vector<bool> main(2 * n - 1, true);
    	vector<bool> anti(2 * n - 1, true);
    	helper(0, count, cols, main, anti);
    	return count;
    }
    private:
    void helper(int s, int& count, vector<bool>& cols, vector<bool>& main, vector<bool>& anti)
    {
    	if (s == cols.size())
    	{
    		count++;
    		return;
    	}
    	for (int i = 0; i < cols.size(); i++)
    	{
    		if (cols[i] && main[s + i] && anti[s + cols.size() - 1 - i])
    		{
    			cols[i] = main[s + i] = anti[s + cols.size() - 1 - i] = false;
    			helper(s + 1, count, cols, main, anti);
    			cols[i] = main[s + i] = anti[s + cols.size() - 1 - i] = true;
    		}
    	}
    }
    };
    

    And I want to share my 4ms Solution. The ideas are same but the diagonal conflict checking method diffes.

    class Solution {
    public:
    int totalNQueens(int n) {
    
    	int count = 0;
    	vector<bool> mark(n);
    	vector<int> cols(n, -1);
    	for (int i = 0; i < n; i++)
    	{
    		cols[0] = i;
    		mark[i] = true;
    		helper(1, n, count, mark, cols);
    		cols[0] = -1;
    		mark[i] = false;
    	}
    	return count;
    }
    private:
    void helper(int s, int n, int& count, vector<bool>& mark, vector<int>& cols)
    {
    	if (s == n)
    	{
    		count++;
    		return;
    	}
    	for (int i = 0; i < n; i++)
    	{
    		if (!mark[i])
    		{
    			bool mark2 = true;
    			for (int k = 0; k < s; k++)
    			{
    				if (abs(s - k) == abs(i - cols[k]))
    				{
    					mark2 = false;
    					break;
    				}
    			}
    			if (mark2)
    			{
    				cols[s] = i;
    				mark[i] = true;
    				helper(s + 1, n, count, mark, cols);
    				cols[s] = -1;
    				mark[i] = false;
    			}
    		}
    	}
    }
    };
    

  • 0
    J

    Why can (i+j) and (i+col.size()-1-j) prove two elements are on the diagonal ?Could you prove this formula?


  • 0

  • 0
    A

    @lchen77
    I find a mistake , if (col[j] && main[i+j] && anti[i+col.size()-1-j])should be if (col[j] && anti[i+j] && main[i+col.size()-1-j])
    it means that your main and anti should exchange .


Log in to reply
 

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