leetcode刷题：回溯算法16（解数独）

力扣题目链接

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

提示：

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

有一说一 ，兄弟们，AC那一刻，我差点哭出来了。做了12小时，中间重做了4次。思路很清晰，但不知道自己哪里错了，就重新做。经过四次重做理清思路，最后一次已经眼看成功了，却还有19个数没填成功。我又卡了一个多小时，最后灵光一现，如果我是对的呢！就打印10个的情况。AC！5个！AC！0个！AC！！！
原来只是我打印时没看到我数字小的情况，最小看到19，我就以为到19就回退出问题了。
思路：
因为是char数组，不能直接传，要转成引用类型，引用传值。计算有多少 “ .“ ，就是要填的数字的数量
当数量为0时返回
二维递归+回溯。
添加元素时要判断是否冲突。

package com.programmercarl.backtracking;

import com.programmercarl.util.GenerateArray;

import java.util.Arrays;


public class SolveSudoku {
    //递归终止条件，一共有多少个数字要填
    int needNums = 0;
    char[][] result;

    public void solveSudoku(char[][] board) {
        //把当前字符数组转化为引用类型
        Character[][] temp = new Character[board.length][board.length];
        //计算一共有多少要填的数字
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') {
                    needNums++;
                }
                temp[i][j] = board[i][j];
            }
        }
        backtracking(temp);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                board[i][j] = result[i][j];
            }
        }
    }


    public void backtracking(Character[][] board) {
        if (needNums == 0) {
            result = new char[board.length][board.length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    result[i][j] = board[i][j];
                }
            }
            return;
        }
        for (int i = 0; i < board.length; i++) {
            //可用数组
            char[] flag = new char[9];
            Arrays.fill(flag, '0');
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] != '.') {
                    //如果当前元素不是 .
                    continue;
                }
                for (char k = '1'; k <= '9'; k++) {
                    //如果在周围或横或纵没有这个元素  并且 这个元素没有被用过
                    if (isNoFindSelfInAround(board, i, j, k) && flag[k - '1'] == '0') {
                        board[i][j] = k;
                        needNums--;
                        //递归
                        backtracking(board);
                        //回溯
                        needNums++;
                        board[i][j] = '.';
                    }
                }
                //如果能运行到这，说明 1 - 9 没有找到需要的数字，则返回
                return;
            }
        }
    }

    
    public boolean isNoFindSelfInAround(Character[][] board, int x, int y, char curNum) {
        int offsetX = x - x % 3;
        int offsetY = y - y % 3;
        //周围九个相对位置
        boolean flag;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                flag = (board[offsetX + i][offsetY + j] == curNum);
                if (flag) {
                    //发现相同
                    return false;
                }
            }
        }

        //横纵不得相同
        for (int i = 0; i < board.length; i++) {
            flag = (board[x][i] == curNum) || (board[i][y] == curNum);
            if (flag) {
                //发现相同
                return false;
            }
        }
        return true;
    }


    public void printArr(Character[][] board) {
        System.out.println();
        System.out.println("======================");
        for (int ii = 0; ii < board.length; ii++) {
            for (int jj = 0; jj < board.length; jj++) {
                System.out.print(board[ii][jj] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("==============原结果==============");
        char[][] board = GenerateArray.generateArrays("[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]n");
        for (int ii = 0; ii < board.length; ii++) {
            for (int jj = 0; jj < board.length; jj++) {
                System.out.print(board[ii][jj] + " ");
            }
            System.out.println();
        }
        System.out.println("==============目标结果==============");
        char[][] board2 = GenerateArray.generateArrays("[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]");
        for (int ii = 0; ii < board2.length; ii++) {
            for (int jj = 0; jj < board2.length; jj++) {
                System.out.print(board2[ii][jj] + " ");
            }
            System.out.println();
        }

        new SolveSudoku().solveSudoku(board);
    }
}