LeetCode: 37. Sudoku Solver

题目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

大意就是说: 已知某个有且仅有唯一解的数独, 让我们写个代码解开它。

解题思路

用 DFS 就可以做出了。这里我们利用 LeetCode: 36. Valid Sudoku 的思路, 对数独进行标记。

AC源码

class Solution {
public:
    bool solveSudoku(vector<vector<char>>& board, int i, int j, int flag[][9])
    {
         if(i==9) return true;
         if(j==9) return solveSudoku(board, i+1, 0, flag);

        if(board[i][j] != '.')
        {
            return solveSudoku(board, i, j+1, flag);
        }
        else
        {
            for(int digit = 0; digit < 9; ++digit)
            {
                int f = flag[0][i] | flag[1][j] | flag[2][i/3*3+j/3];
                if(f & (1 << digit))
                {
                    continue;
                }
                else
                {
                    // 标记
                    flag[0][i] |= (1 << digit);
                    flag[1][j] |= (1 << digit);
                    flag[2][i/3*3+j/3] |= (1 << digit);
                    board[i][j] = digit + '1';

                    if(solveSudoku(board, i, j+1, flag)) return true;

                    // 取消标记
                    board[i][j] = '.';
                    flag[0][i] &= ~(1 << digit);
                    flag[1][j] &= ~(1 << digit);
                    flag[2][i/3*3+j/3] &= ~(1 << digit);
                }
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        int flag[3][9] = {0}; // 0: row, 1: column, 2: rect

        // 初始化标记
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[i].size(); ++j){
                if(board[i][j] != '.')
                {
                    int value = 1 << (board[i][j] - '0' - 1);
                    if(flag[0][i] & value) return ;
                    else flag[0][i] |= value;

                    if(flag[1][j] & value) return ;
                    else flag[1][j] |= value;

                    int rectIdx = i/3*3 + j/3;
                    if(flag[2][rectIdx]&value) return ;
                    else flag[2][rectIdx] |= value;
                }
            }
        }
        solveSudoku(board, 0, 0, flag);
    }
};