Java TrackBack Solution


  • 0
    public class Solution {
    	public List<List<String>> solveNQueens(int n) {
    		List<List<String>> result = new ArrayList<>();
    		char[][] temp = new char[n][n];
    		for (int i = 0; i < n; i++)
    			temp[i] = new char[n];
    		for (int i = 0; i < n; i++)
    			Arrays.fill(temp[i], '.');
    		backtracking(result, n, temp, 0);
    		return result;
    	}
    
    	private void backtracking(List<List<String>> result, int n, char[][] temp, int k) {
    		for (int i = 0; i < n; i++) {
    			temp[k][i] = 'Q';
    			if (isPossible(n, temp, k, i)) {
    				if (k == n - 1) {
    					List<String> list = new ArrayList<>();
    					for (char[] cs : temp)
    						list.add(new String(cs));
    					result.add(list);
    				} else {
    					backtracking(result, n, temp, k + 1);
    				}
    			}
    			temp[k][i] = '.';
    		}
    	}
    
    	private boolean isPossible(int n, char[][] temp, int k, int i) {
    		for (int j = 0; j < n; j++)
    			if (j == k)
    				continue;
    			else if (temp[j][i] == 'Q')
    				return false;
    		for (int j = 0; j <= i; j++)
    			if (j == i)
    				continue;
    			else if (temp[k][j] == 'Q')
    				return false;
    		for (int p = k - 1, q = i - 1; p >= 0 && q >= 0; p--, q--) {
    			if (temp[p][q] == 'Q')
    				return false;
    		}
    		for (int p = k - 1, q = i + 1; p >= 0 && q < n; p--, q++) {
    			if (temp[p][q] == '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.