n-皇后

/**
使用一维数组
leetcode 通过 ：Runtime: 2 ms, faster than 97.02% of Java online */
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        int [] visit = new int[n];
        dfs(res,visit,0,n);
        return res;
    }
    
    private void dfs(List<List<String>> res,int [] visit,int row,int n){
        if(row == n){
            List<String> t = new ArrayList();
            char [] temp = new char[n];
            int count = 0;
            while(count < n){
                for(int j = 0;j<n;j++){
                    if(visit[count] == j){
                        temp[j] = 'Q';
                    }else{
                        temp[j] = '.';
                    }
                }
                t.add(new String(temp));
                count++;
            }
            res.add(t);
            return;
        }
        for(int col=0;col<n;col++){
            if(isValid(row,col,n,visit)){
                visit[row] = col;
                dfs(res,visit,row+1,n);
            }
        }
        
    }
    
    private boolean isValid(int row,int col,int n,int [] visit){
        for(int i=0;i<row;i++){
            if(visit[i] == col || Math.abs(i-row) == Math.abs(visit[i]-col)){
                return false;
            }
        }
        return true;
    }
    
}

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
ArrayList<String[]> ret = new ArrayList<>();
    public ArrayList<String[]> solveNQueens(int n) {
        if(n <= 0) return ret;
        int[] array = new int[n];
        helper(array, 0);
        return ret;
    }


    //A[i] = j 表示  i 行 j 列 上放置了一个皇后

    public boolean check(int[] array,int k){

        //验证新加入的第k行是否可以

        for(int i = 0;i < k; i++){

            if(array[i] == array[k] || k - i == Math.abs(array[k] - array[i])) return false;

        }

        return true;

    }

   

    public void helper(int[] array,int k){

        if(k == array.length){

            String[] s = new String[array.length];

            for(int i = 0;i < array.length;i++){

                char[] ca = new char[array.length];

                Arrays.fill(ca, '.');

                ca[array[i]] = 'Q';

                s[i] = new String(ca);

            }

            ret.add(s);

            return;

        }

        for(int i = 0;i< array.length;i++){

            array[k] = i;

            if(check(array,k)){

                helper(array, k + 1);

            }

        }

    }

}

import java.util.*;
public class Solution {
    ArrayList<String[]> list = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        char[][] res = new char[n][n];
        for(char[] chs : res)
            Arrays.fill(chs, '.');
        int[] cols = new int[n];
        int[] slash1 = new int[2*n-1];
        int[] slash2 = new int[2*n-1];
        DFS(res, n, 0, cols, slash1, slash2);
        return list;
        
    }
    
    public void DFS(char[][] res, int n, int cur, int cols[], int slash1[], int slash2[]) {
        if(cur == n) {
            String[] s = new String[n];
            for(int i=0; i<n; i++)
                s[i] = new String(res[i]);
            list.add(s);
        }
        for(int i=0; i<n; i++) {
            if(cols[i] != 1 && slash1[cur + i] != 1 && slash2[n-1-cur+i] != 1) {
                cols[i] = 1;
                slash1[cur + i] = 1;
                slash2[n-1-cur+i] = 1;
                res[cur][i] = 'Q';
                DFS(res, n, cur+1, cols, slash1, slash2);
                cols[i] = 0;
                slash1[cur + i] = 0;
                slash2[n-1-cur+i] = 0;
                res[cur][i] = '.';
            }
        }
    }
}

I didn't invent a wheel here. We just remember the busy columns and diagonals and recursively try to put the queen into the next row. But I think the code below is short enough to be reproduced in the interview.

Hope it helps!

public class Solution { private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, String[] board, List<String[]> res) { if (r == board.length) res.add(board.clone()); else { for (int c = 0; c < board.length; c++) { int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1; if (!cols[c] && !d1[id1] && !d2[id2]) { char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    } public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], new String[n], res); return res;
    }
}