有效的数独

LeetCode 之 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

输入:
[
[“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”]
]
输出: true

说明

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符 ‘.’ 。
• 给定数独永远是 9x9 形式的。

解题思路

思路可以使用 几个数组来 遍历剔除 相应的规则，
以及一个用来检查 数独数据的函数。
可以把 char 转换成 int，再来设置。
再计算出它合适的 清除时机，

     	/// <summary>
        /// 对 数独的数据进行判断筛选。
        /// 把字符转换为索引并 存储。
        /// </summary>
        /// <param name="borad">数独数据</param>
        /// <param name="nums">目标数组，行，列等</param>
        /// <param name="y">坐标 y</param>
        /// <param name="x">坐标 x</param>
        /// <returns></returns>
       private bool CheckBoard(char[][] borad,int[] nums, int y, int x)
        {    
            //1的 字符码是 49
            int index = (int)(borad[y][x]) - 49;
            if (nums[index] == 1)
            {
                return false;
            }

            nums[index] = 1;
            return true;
        }
          public bool IsValidSudoku(char[][] board)
        {

            //思路 使用个 数组来 处理 所对应的规则，
            //并计算出它 合适的初始化时间。也就是 读取新的新的数独数据，
            //将 字符转换为  索引从0开始，进行设置 flag,如果存在就说明已经存储过了。
            
            int[] rowNums = new int[9];
            int[] columnNums = new int[9];
            int[][] grid = new int[][]  //3个不同的格子
            {
                new int[9],
                new int[9],
                new int[9],
            };
            //  y,x 代表 行，
            //x,y 代表 列
            for (int y = 0; y < 9; y++)
            {
                for (int x = 0; x < 9; x++)
                {

                    int index = x / 3;

                    if (board[y][x]!='.')
                    {
                        //检查行
                        if (!CheckBoard(board, rowNums, y, x))
                        {
                            return false;
                        }

                        //检查格子，这里 遍历是从左到右，0 ~9 分别对应 3个不同格子的第一列，第二列，以及第三列				
                        //一次遍历会 分别检查 这不同的三列。
                        if (!CheckBoard(board,grid[index],y,x))
                        {
                            return false;
                        }

                    }
                    

                    if (board[x][y]!='.')
                    {   //检查列
                        if (!CheckBoard(board, columnNums, x, y))
                        {
                            return false;
                        }
                    }
                    // 格子重新初始化的时机。
                    if ((x+1)%3==0&& (y+1)%3 ==0)
                    {
                        grid[index] = new int[9];
                    }
                }
                rowNums = new int[9];
                columnNums = new int[9];
            }

            return true;
        }