How many different solutions to solve this problem?


  • 0
    C

    And what does backtracing mean?

    I used recursion to solve this problem, is it same as backtracing method?

    public class Solution {
    ArrayList<int[]> getSolutions(int[] m, int n)
    {
        ArrayList<int[]> ret = new ArrayList<int[]>();
        if(m.length>=n)
        {
            ret.add(m);
            return ret;
        }
        for(int i=0; i<n; i++)
        {
            boolean conflict = false;
            for(int j=0; j<m.length; j++)
            {
                if(i==m[j] || i-m[j]==m.length-j || m[j]-i==m.length-j)
                {
                    conflict = true;
                    break;
                }
            }
            if(!conflict)
            {
                int[] temp = new int[m.length+1];
                System.arraycopy(m, 0, temp, 0, m.length);
                temp[m.length] = i;
                ret.addAll(getSolutions(temp, n));
            }
        }
        return ret;
    }
    public List<String[]> solveNQueens(int n) {
        List<String[]> ret = new ArrayList<String[]>();
        if(n<=0) return ret;
        for(int[] matrix:getSolutions(new int[0], n))
        {
            String[] solve = new String[n];
            for(int i=0; i<matrix.length; i++)
            {
                StringBuffer sb = new StringBuffer();
                for(int j=0; j<matrix[i]; j++)
                {
                    sb.append('.');
                }
                sb.append('Q');
                for(int j=matrix[i]+1; j<n; j++)
                {
                    sb.append('.');
                }
                solve[i] = sb.toString();
            }
            ret.add(solve);
        }
        return ret;
    }
    

    }


  • 0
    V

    An Iterative Solution. I am also doing the same thing only without recursion. I feel it was simpler then recursion.

    bool ok(vector<int> &col, int c, int idx) {
    // Validates last queen with all previous queens. 
        for (int i = 0; i < idx; i++)
                if (col[i] == c || abs(col[i] - c) == abs(i - idx)) 
                    return false; // Clash!
        return true;
    }
    vector<vector<string> > solveNQueens(int n) {
        vector<int> col(n, 0);
        vector<vector<string> > ans;
        int row = 0;
        
        while (1) {
            if (row == n) {
                // Generate string for this solution.
                string str;
                for (int i = 0; i < n; i++) str = str + ".";
                vector<string> t(n, str);
                for (int i = 0; i < n; i++) t[col[i]][i] = 'Q';
                ans.push_back(t);
                
                col[--row]++; // go back to previous row and increment that queen by 1 column.
            }
            else if (col[row] == n) {
                col[row--] = 0;       // Reset this queen to column 0.
                if (row == -1) break; // all cases checked! :)
                col[row]++;           // go back to previous row and increment that queen by 1 column.
            }
            else if (!ok(col, col[row], row)) {
                col[row]++; // problem at this column, so go to next column.
            }
            else row++;   // everything's perfect, lets go to queen in next row.
        }
        return ans;
    } 

  • 0
    M

    This is an amusing code by Professer Song.

    https://github.com/MaskRay/LeetCode/blob/master/n-queens.cc

    class Solution {
    private:
      int c, n;
      vector<string> s;
      vector<vector<string>> q;
    public:
      vector<vector<string> > solveNQueens(int n) {
        q.clear();
        this->n = n;
        s.assign(n, string(n, '.'));
        f(n, 0, 0, 0);
        return q;
      }
      void f(int i, int l, int m, int r) {
        if (! i)
          q.push_back(s);
        else
          for (int x = (1<<n)-1&~(l|m|r); x; x &= x-1) {
            int y = x & -x;
            s[i-1][__builtin_ctz(y)] = 'Q';
            f(i-1, (l|y)<<1, m|y, (r|y)>>1);
            s[i-1][__builtin_ctz(y)] = '.';
          }
      }
    };

  • 1
    P

    The Queen problem can be solved using permutations generation (http://en.wikipedia.org/wiki/Eight_queens_puzzle#Solution_construction) as well:

    public class NQueens {
    	public List<String[]> solveNQueens(int n) {
    		//Initial permutation
    	    int[] cols = new int[n];
    	    for(int i = 0; i < n; i++) {
    	    	cols[i] = i;
    	    }
    	    
    	    //Iterate all permutations
    	    List<String[]> out = new ArrayList<String[]>();
    	    do{//n!
    	    	if(!isDiagonalThreat(cols)) {//O(n^2)
    	    		out.add(buldDisposition(cols));//O(n^2)
    	    	}
    	    } while ((cols = perm(cols)) != null);
    	    	    
    	    return out;
    	}
    
    	private String[] buildDisposition(int[] cols) {
    		String[] disposition = new String[cols.length];
    		for(int i = 0; i < disposition.length; i++) {
    			StringBuilder sb = new StringBuilder();
    			for(int j = 0; j < disposition.length; j++) {
    				sb.append(cols[i] == j ? 'Q' : '.');
    			}
    			disposition[i] = sb.toString();
    		}
    		return disposition;
    	}
    
    	//http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
    	private int[] perm(int[] cols) {
    		int i = cols.length-2;
    		while(i >=0 && cols[i] >= cols[i+1]) {
    			i--;
    		}
    		if(i == -1) {
    			return null;
    		}
    		int j = cols.length-1;
    		while(j>=0 && cols[i] >= cols[j]) {
    			j--;
    		}
    		
    		//Swap
    		int tmp = cols[i];
    		cols[i] = cols[j];
    		cols[j] = tmp;
    		
    		//Reverse
    		for(int k = 0;k < (cols.length-i-1)/2; k++) {
    		    //Swap
    			tmp = cols[i+1+k];
    			cols[i+1+k] = cols[cols.length-1-k];
    			cols[cols.length-1-k] = tmp;
    		}
    		return cols;
    	}
    
    	//Check for diagonals attacks
    	private boolean isDiagonalThreat(int[] cols) {
    		for(int j = 0; j < cols.length; j++) {
    			for(int k = j+1; k < cols.length; k++) {
    				int delta = k-j;
    				if(cols[j]-delta == cols[k] 
    						|| cols[j]+delta == cols[k]) {
    					return true;
    				}
    			}			
    		}
    		return false;
    	}
    }

Log in to reply
 

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