package pers.vic.basics.leetcode;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * @author Vic.xu
 * @description: 37. 解数独{@literal https://leetcode-cn.com/problems/sudoku-solver/}
 * @date: 2020/12/1 0001 11:13
 */
public class J0037_H_SolveSudoku {
    /*
    编写一个程序，通过填充空格来解决数独问题。
    一个数独的解法需遵循如下规则：
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    空白格用 '.' 表示。

    提示：
    给定的数独序列只包含数字 1-9 和字符 '.' 。
    你可以假设给定的数独只有唯一解。
    给定数独永远是 9x9 形式的。
     */

    /**
     * 借鉴36题的 校验数独是否合法的方法
     *
     * @param board
     */
    public static void solveSudoku(char[][] board) {

        // 每个元素存储整行的数字 按位存储  如 先存元素4    --> 000000100， 再存元素1  --> 000000101
        int[] rows = new int[L];
        //每个元素存一整列 如，[0] 存 第一列  [1]存第二列
        int[] columns = new int[L];
        // 每个元素存 一个3X3的九宫格：  [index] = i/3*3 + j/3
        int[] boxes = new int[L];

        //把数字初始化到 上述三个元素
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L; j++) {
                char cur = board[i][j];
                // 分别存入所在行、列和九宫格 是否已经包含当前元素
                checkAndPut(cur, i, j, rows, columns, boxes);
            }
        }
        dfs(board, 0, 0, rows, columns, boxes);
    }

    /**
     * 判断当前行当前列当前九宫格是否包含 均不包含则存入相应位置
     */
    public static boolean checkAndPut(char item, int row, int column, int[] rows, int[] columns, int[] boxes) {
        int n = item - '0';
        boolean rowContain = (rows[row] >> n & 1) == 1;

        boolean columnContain = (columns[column] >> n & 1) == 1;

        int boxIndex = row / 3 * 3 + column / 3;
        boolean boxContain = (boxes[boxIndex] >> n & 1) == 1;

        if (rowContain || columnContain || boxContain) {
            return false;
        }
        rows[row] = rows[row] | 1 << n;
        columns[column] = columns[column] | 1 << n;
        boxes[boxIndex] = boxes[boxIndex] | 1 << n;
        return true;
    }

    /**
     *  把放入对应行列box的下标对应的位数重新置为0
     */
    public static boolean rollbackIndex(char item, int row, int column, int[] rows, int[] columns, int[] boxes) {
        int n = item - '0';
        int boxIndex = row / 3 * 3 + column / 3;
        remoteIndex(rows, row, n);
        remoteIndex(columns, column, n);
        remoteIndex(boxes, boxIndex, n);
        return true;
    }


    // 从某一个下标中删除：即把某位置为0
    private static void remoteIndex(int[] nums, int index, int n) {
        int ret = nums[index] & ~(1 << n);
        nums[index] = ret;
    }

    static int L = 9;

    public static boolean dfs(char[][] board, int row, int column, int[] rows, int[] columns, int[] boxes) {
        //结束条件：填写完毕
        if (column == L) {
            row++;
            column = 0;
        }
        if (row == L) {
            return true;
        }
        if ('.' == board[row][column]) {
            int boxIndex = row / 3 * 3 + column / 3;
            //从1 到9 开始填写到当前位置
            for (int i = 1; i <= 9; i++) {
                char cur = (char) (i + '0');
                // 分别验证所在行、列和九宫格 是否已经包含当前元素
                boolean checkAndPut = checkAndPut(cur, row, column, rows, columns, boxes);
                // 如果不能放当前字符 则换其他字符尝试
                if (!checkAndPut) {
                    continue;
                }
                //可以存放 则继续方下一个位置
                board[row][column] = cur;
                if (dfs(board, row, column + 1, rows, columns, boxes)) {
                    return true;
                }
                //撤销当前位置 ，以及撤销当前行列box中的位置
                board[row][column] = '.';
                rollbackIndex(cur, row, column, rows, columns, boxes);

            }
        } else {
            return dfs(board, row, column + 1, rows, columns, boxes);
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] board = /*{{'.', '.', '.'}, {'.', '.', '.'}, {'.', '.', '.'}};*/
             /*    {{'.', '.', '.', '.', '.', '.', '.', '.', '.'}
                , {'.', '.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};*/
        {{'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'}};
        for (int i = 0; i < board.length; i++) {
            System.out.println(Arrays.toString(board[i]));
        }
        solveSudoku(board);
        System.out.println("");
        for (int i = 0; i < board.length; i++) {
            System.out.println((i+1)  +"->" + Arrays.toString(board[i]));
        }

    }

}