解数独

解数独

题目

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

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

输入：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"]]

输出：[["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"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解

题解

要一个检查位置的函数来判断当前位置能否填写某一数字。之后遍历每个位置，试着将1~9填入每个位置，直到填满整个9宫格结束遍历。

JS 实现：

var columns = [],//保存每一行的数字
    rows = [],//保存每一列的数字
    grids = [],//保存每一个九宫格的数字
    f = 0;//结束标记

// 初始化，遍历已有填充值
var init = function(board){
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      // 获取值
      const value = board[i][j];
      // 先判断非 . 元素
      if (value !== '.') {
          rows[i].push(value);
          columns[j].push(value);
          //九宫格下标
          const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
          grids[gridIndex].push(value);
        } 
      }
    }
};
//检查能否填入该位置
var check = function(i,j,board,value){
    const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 对应的盒子
    if (rows[i].includes(value) || columns[j].includes(value) || grids[gridIndex].includes(value)) {
        return false;
    }
    return true;
};
//遍历填充数独
var fillBoard = function(i,j,board){
    //已填满
    if(f == 1 || i > 8) {
        return ;
    }
    //需要填充
    if(board[i][j] == '.'){
        //遍历9个数字
        for(let num = 1; num < 10; num++){
            if(f == 0 && check(i,j,board,num.toString())){
                rows[i].push(num.toString());//更新列
                columns[j].push(num.toString());//更新行
                const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
                grids[gridIndex].push(num.toString());//更新小九宫格
                board[i][j] = num.toString();//填入数字
                if(i == 8 && j == 8) {//已填满
                    f = 1;
                    return;
                }else if(j == 8) fillBoard(i + 1,0,board);//换行
                else fillBoard(i,j+1,board);//换列
                 if(f == 0){//回溯
                    rows[i].pop();//更新列
                    columns[j].pop();//更新行
                    grids[gridIndex].pop();//更新小九宫格
                    board[i][j] = '.';//更新大九宫格
                }
            }
        }
    }else if(i == 8 && j == 8) {//遍历结束
        f = 1;
        return;
    }else if(j == 8) fillBoard(i + 1,0,board);//换行
    else fillBoard(i,j+1,board);//换列
    return board;
};
var solveSudoku = function(board) {
    f = 0;
    for(let i = 0; i < 9; i++){
        columns[i] = [];
        rows[i] = [];
        grids[i] = [];
    }
    init(board);  
    board = fillBoard(0,0,board);
};