跳转至

37. 解数独

难度：困难

题目

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

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

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

示例：

Example1

输入：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"]
]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

Example1

提示：

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

Reference

题解

使用回溯算法，对于每个空单元格，检查其所在行，所在列与所在方格，逐个检查其可以填入的数值。如果 有可以填入的字符，则依次进行尝试。若某个空格没有任何可以填入的数值，或所有可填入的值都是错误的 ，意味着当前搜索路径存在错误，需要返回上一个状态进行下一步尝试。

如果方格被完全填满，则可以立即返回。并通过返回值告诉上一步，可以直接返回结果。

bool dfs(char **board, int boardSize, int *boardColSize)
{
    int x = 0, y = 0, i = 0, j = 0;
    bool flag = true, candidate[9] = {false};
    for (x = 0; x < 9 && flag; x++)
        for (y = 0; y < 9 && flag; y++)
            if (board[x][y] == '.')
                flag = false;
    if (flag)
        return true;
    x--;
    y--;
    for (i = 0; i < 9; i++)
    {
        if (board[x][i] != '.')
            candidate[board[x][i] - '1'] = true;
        if (board[i][y] != '.')
            candidate[board[i][y] - '1'] = true;
        if (board[3 * (x / 3) + i / 3][3 * (y / 3) + i % 3] != '.')
            candidate[board[3 * (x / 3) + i / 3][3 * (y / 3) + i % 3] - '1'] = true;
    }
    for (i = 0; i < 9 && !flag; i++)
    {
        if (!candidate[i])
        {
            board[x][y] = '1' + i;
            flag = flag || dfs(board, boardSize, boardColSize);
            if (flag)
                return flag;
            board[x][y] = '.';
        }
    }
    return flag;
}

void solveSudoku(char** board, int boardSize, int* boardColSize){
    dfs(board, boardSize, boardColSize);
}

评论