Java solution, 1d array, math, no backtracking


  • 0
    G

    well, just want to share my idea.
    use 1d array to track the valid positions. A valid set of positions must meet:

    1. no cell has same value
    2. diff of any 2 cells' values must be different with diff of index of the 2 cells

    code:

    public class NQueens {
    	public String[] int2str(int[] m)
    	{
    		String[] strs = new String[m.length];
    		
    		for (int i = 0; i < m.length; i++) {
    			String s = "";
    			for (int j = 0; j < m.length; j++) {
    				s += (m[i] == j) ? 'Q' : '.';
    			}
    			strs[i] = s;
    		}
    		return strs;
    	}
    	
    	public boolean safe(int[]m, int d)
    	{
    		for (int i = 0; i < d; i++) {
    			if (m[i] == m[d]) return false;
    			if (Math.abs(m[i] - m[d]) == d - i) return false;
    		}
    		return true;
    	}
    	public void find(int[] m, int d)
    	{
    		if (d >= m.length) return;
    		
    		// check
    		for (int i = 0; i < m.length; i++) {
    			m[d] = i;
    			if (!safe(m, d)) continue;
    			if (d < m.length-1) {
    				find(m, d+1);
    			} else { // d == m.length -1
    				ok_coordinates.add(m.clone());
    			}
    		}
    	}
    	List<int[]> ok_coordinates = new ArrayList<>();
    	public List<String[]> s0(int n) {
    		List<String[]> r = new ArrayList<String[]>();
    
    		int[] m = new int[n]; // well, i could use 'r' directly, but i wanted to print out the 1d idx array for debugging.
    
    		find(m, 0);
    		
    		for (int[] c : ok_coordinates) {
    			r.add(int2str(c));
    		}
    		return r;
    	}
    
    	public List<String[]> solveNQueens(int n) {
    		return s0(n);
    	}
    }

Log in to reply
 

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