Java method hit 4ms


  • 0
    H

    Logic is very simple, iterating by row, checking column by array mark.

     public List<List<String>> solveNQueens(int n) {
                int mark[] = new int[n];
                boolean x_mark[] = new boolean[n];
                List<List<String>> ret= new ArrayList<List<String>>();
                Recur(n, mark, x_mark, ret, n);
                return ret;
            }
            public boolean valid(int n, int row, int index, int mark[])
            {
                for(int i = row + 1; i < n; i++) {
                    int colDis = Math.abs(index - mark[i]);
                    int rowDis = i - row;
                    if(colDis == rowDis) return false;
                }
                return true;
            }
            public boolean Recur(int n, int mark[], boolean x_mark[], List<List<String>> ret, int depth)
            {
                if(depth == 0)
                {
                    List<String> s_ret = new ArrayList<String>();
                    char[] lin = new char[n];
                    for(int i = 0; i < n; i++)
                    	lin[i] = '.';
                    for(int i = 0; i < n; i++)
                    {
                    	lin[mark[i]] = 'Q';
                    	s_ret.add(new String(lin));
                    	lin[mark[i]] = '.';
                    }
                    
                    ret.add(s_ret);
                    return true;
                }
                else
                {
                    for(int i = 0; i < n; i++){
                        if(!x_mark[i] && valid(n, depth - 1, i, mark)){
                            x_mark[i] = true;
                            mark[depth - 1] = i;
                            Recur(n, mark, x_mark, ret, depth - 1);
                            x_mark[i] = false;
                        }
                    }
                }
                return true;
            }

Log in to reply
 

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