51、N 皇后

class Solution {
    public List<List<String>> result = new ArrayList<List<String>>();
    public int[][] arr;
    public List<List<String>> solveNQueens(int n) {
        arr = new int[n][n];
        find(n,0);
        return result;
    }
    public void find(int n, int count){
        if(count == n){
            List<String> temp = new ArrayList<>();
            for(int i = 0; i < n; i++){
                String str = "";
                for(int j= 0; j < n; j++){
                    if(arr[i][j] == 1){
                        str = str + "Q";
                    }else{
                        str = str + ".";
                    }
                }
                temp.add(str);
            }
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < n; i++){
            if(check(i,n,count)){
                arr[count][i] = 1;
                find(n,count+1);
                arr[count][i] = 0;
                
            }
        }
    }
    public boolean check(int index,int n,int count){
        for(int j = count - 1; j >= 0; j--){
            if(arr[j][index] == 1){
                return false;
            }
        }
        for(int j = count - 1, index1 = index - 1; j >= 0 &&index1 >= 0; j-- , index1--){
            if(arr[j][index1]==1){
                return false;
            }
        }
        for(int j = count - 1, index2 = index + 1; j >= 0 &&  index2<n; j-- ,index2++){
            if(arr[j][index2]==1){
                return false;
            }
        }
        return true;
    }
}

37、解数独

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHander(board);
    }
    public boolean solveSudokuHander(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    continue;
                }
                for(char k = '1'; k <= '9'; k++){
                    if(judge(board,i,j,k)){
                        board[i][j] = k;
                        if(solveSudokuHander(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                    
                }
                return false;
            }
        }
        return true;
    }
    public boolean judge(char[][] board, int i, int j, char k){
        for(int m = 0; m < 9; m++){
            if(board[i][m]==k){
                return false;
            }
        }
        for(int n = 0; n < 9; n++){
            if(board[n][j]==k){
                return false;
            }
        }
        int startRow = (i/3)*3;
        int startCol = (j/3)*3;
        for(int m = startRow; m < startRow+3; m++){
            for(int n = startCol; n < startCol+3; n++){
                if(board[m][n]==k){
                    return false;
                }
            }
        }
        return true;
    }
}