凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 37. Sudoku Solver

分类:algorithm| 发布时间:2016-09-29 18:45:00


题目

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.

题意

求出数独的解,你可以假定有且仅有一个解。

解法 1

可以通过 DFS 算法得到。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0);
    }

    bool dfs(vector<vector<char>>& board, const int pos) {
        if (pos == 81) {
            return true;
        }

        int x = pos / 9, y = pos % 9;
        if (board[x][y] != '.') {
            return dfs(board, pos + 1);
        }

        for (char i = '0'; i <= '9'; ++i) {
            board[x][y] = i;
            if (isValidSudoku(board) && dfs(board, pos + 1))
                return true;
        }

        board[x][y] = '.';
        return false;
    }

    bool isValidSudoku(vector<vector<char>>& board) {
        int col[9][9] = {0}, row[9][9] = {0}, rec[9][9] = {0};
        for(int i = 0; i < 9; ++ i) {
            for(int j = 0; j < 9; ++ j) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                    if(col[i][num] || row[j][num] || rec[k][num])
                        return false;

                    col[i][num] = row[j][num] = rec[k][num] = 1;
                }
            }
        }

        return true;
    }
};

这个算法应该比较好理解,同时还用到了上一题的函数来判断解是否合法。 但是效率就比较差了,其实不用每次都检查整个数独是否合法,只用检查当前的行列以及区块就行了。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0);
    }

    bool dfs(vector<vector<char>>& board, const int pos) {
        if (pos == 81)
            return true;

        int x = pos / 9, y = pos % 9;
        if (board[x][y] != '.')
            return dfs(board, pos + 1);

        for (char i = '0'; i <= '9'; ++i) {
            board[x][y] = i;
            if (check(board, x, y) && dfs(board, pos + 1))
                return true;
        }

        board[x][y] = '.';
        return false;
    }

    bool check(vector<vector<char>>& board, int x, int y) {
        int col[9] = {0}, row[9] = {0}, rec[9] = {0};
        const int start_x = (x / 3) * 3, start_y = (y / 3) * 3;
        for(int i = 0; i < 9; ++ i) {
            if(board[x][i] != '.') {
                int num = board[x][i] - '0' - 1;
                if (col[num]) {
                    return false;
                }

                col[num] = 1;
            }

            if (board[i][y] != '.') {
                int num = board[i][y] - '0' - 1;
                if (row[num]) {
                    return false;
                }

                row[num] = 1;
            }

            int delta_x = i % 3, delta_y = i / 3;
            if (board[start_x + delta_x][start_y + delta_y] != '.') {
                int num = board[start_x + delta_x][start_y + delta_y] - '0' - 1;
                if (rec[num]) {
                    return false;
                }

                rec[num] = 1;
            }
        }

        return true;
    }
};

可以看到修改后的版本有了较大的提升。 其实我们可以更进一步,给定一个坐标,得到该坐标上合法的值。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0);
    }

    bool dfs(vector<vector<char>>& board, const int pos) {
        if (pos == 81) {
            return true;
        }

        int x = pos / 9, y = pos % 9;
        if (board[x][y] != '.') {
            return dfs(board, pos + 1);
        }

        int nums[9] = { 0 };
        getValidNums(board, x, y, nums);
        for (char i = 0; i < 9; ++i) {
            if (nums[i]) continue;
            board[x][y] = i + '1';
            if (dfs(board, pos + 1))
                return true;
        }

        board[x][y] = '.';
        return false;
    }

    void getValidNums(vector<vector<char>>& board, int x, int y, int *nums) {
        const int start_x = (x / 3) * 3, start_y = (y / 3) * 3;
        for(int i = 0; i < 9; ++ i) {
            if(board[x][i] != '.') {
                int num = board[x][i] - '0' - 1;
                nums[num] = 1;
            }

            if (board[i][y] != '.') {
                nt num = board[i][y] - '0' - 1;
                nums[num] = 1;
            }

            int new_x = start_x + i % 3, new_y = start_y + i / 3;
            if (board[new_x][new_y] != '.') {
                int num = board[new_x][new_y] - '0' - 1;
                nums[num] = 1;
            }
        }
    }
};

通过直接获取指定坐标的合法的值可以免除每次检查某个值在特定点上是否合法的操作,大大减少了相关的时间。 可以看到这个版本相比上一个版本效率已经不在一个数量级上了。 那么这个算法是否可以再进一步呢?在这个算法中每次调用 dfs(...) 函数都需要获取合法的数字,其实这个操作也是可以去掉了。 具体方法是一开始就根据 board 来生成每一行每一列以及每一块的合法的值, 而不用每次调用 dfs(...) 都生成,减少可能出现的重复。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        memset(col, 0, sizeof(col));
        memset(row, 0, sizeof(row));
        memset(rec, 0, sizeof(rec));
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') continue;
                int temp = 3 * (i / 3) + j / 3;
                int num = board[i][j] - '1';
                col[j][num] = row[i][num] = rec[temp][num] = 1;
            }
        }

        dfs(board, 0);
    }

    bool dfs(vector<vector<char>>& board, const int pos) {
        if (pos == 81) {
            return true;
        }

        const int x = pos / 9, y = pos % 9;
        if (board[x][y] != '.') {
            return dfs(board, pos + 1);
        }

        int temp = 3 * (x / 3) + y / 3;
        for (char i = 0; i < 9; ++i) {
            if (col[y][i] || row[x][i] || rec[temp][i]) {
                continue;
            }

            col[y][i] = row[x][i] = rec[temp][i] = 1;
            if (dfs(board, pos + 1)) {
                board[x][y] = i + '1';
                return true;
            }

            col[y][i] = row[x][i] = rec[temp][i] = 0;
        }

        return false;
    }

private:
    int col[9][9];
    int row[9][9];
    int rec[9][9];
};

解法 2

这个方法是这里分享的:Sharing my 2ms C++ solution with comments and explanations

class Solution {
    struct cell { // encapsulates a single cell on a Sudoku board
        uint8_t value; // cell value 1..9 or 0 if unset
        uint8_t numPossibilities; // number of possible (unconstrained) values for the cell
        bitset<10> constraints; // if bitset[v] is 1 then value can't be v
        cell() : value(0), numPossibilities(9),constraints() {};
    };

    array<array<cell,9>,9> cells;

    // sets the value of the cell to [v]
    // the function also propagates constraints to other cells and deduce new values where possible
    bool set(int i, int j, int v) {
        // updating state of the cell
        cell& c = cells[i][j];
        if (c.value == v)
            return true;

        if (c.constraints[v])
            return false;

        c.constraints = bitset<10>(0x3FE); // all 1s
        c.constraints.reset(v);
        c.numPossibilities = 1;
        c.value = v;

        // propagating constraints
        for (int k = 0; k<9; k++) {
            // to the row:
            if (i != k && !updateConstraints(k, j, v))
                return false;

            // to the column:
            if (j != k && !updateConstraints(i, k, v))
                return false;

            // to the 3x3 square:
            int ix = (i / 3) * 3 + k / 3;
            int jx = (j / 3) * 3 + k % 3;
            if (ix != i && jx != j && !updateConstraints(ix, jx, v))
                return false;
        }

        return true;
    }

    // update constraints of the cell i,j by excluding possibility of 'excludedValue'
    // once there's one possibility left the function recurses back into set()
    bool updateConstraints(int i, int j, int excludedValue) {
        cell& c = cells[i][j];
        if (c.constraints[excludedValue])
            return true;

        if (c.value == excludedValue)
            return false;

        c.constraints.set(excludedValue);
        if (c.value || --c.numPossibilities > 1)
            return true;

        for (int v = 1; v <= 9; v++) {
            if (!c.constraints[v]) {
                return set(i, j, v);
            }
        }

        return false;
    }

    // backtracking state - list of empty cells
    vector<pair<int, int>> bt;

    // find values for empty cells
    bool findValuesForEmptyCells() {
        // collecting all empty cells
        bt.clear();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (!cells[i][j].value)
                    bt.push_back(make_pair(i, j));
            }
        }

        // making backtracking efficient by pre-sorting empty cells by numPossibilities
        sort(bt.begin(), bt.end(), [this](const pair<int, int>&a, const pair<int, int>&b) {
                return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities; });
        return backtrack(0);
    }

    // Finds value for all empty cells with index >=k
    bool backtrack(int k) {
        if (k >= bt.size())
            return true;

        int i = bt[k].first;
        int j = bt[k].second;
        // fast path - only 1 possibility
        if (cells[i][j].value)
            return backtrack(k + 1);

        auto constraints = cells[i][j].constraints;
        // slow path >1 possibility.
        // making snapshot of the state
        array<array<cell,9>,9> snapshot(cells);
        for (int v = 1; v <= 9; v++) {
            if (!constraints[v]) {
                if (set(i, j, v)) {
                    if (backtrack(k + 1))
                        return true;
                }

                // restoring from snapshot,
                // note: computationally this is cheaper
                // than alternative implementation with undoing the changes
                cells = snapshot;
            }
        }

        return false;
    }

public:
    void solveSudoku(vector<vector<char>> &board) {
        cells = array<array<cell,9>,9>(); // clear array
        // Decoding input board into the internal cell matrix.
        // As we do it - constraints are propagated and even additional values are set as we go
        // (in the case if it is possible to unambiguously deduce them).
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && !set(i, j, board[i][j] - '0'))
                    return; // sudoku is either incorrect or unsolvable
            }
        }

        // if we're lucky we've already got a solution,
        // however, if we have empty cells we need to use backtracking to fill them
        if (!findValuesForEmptyCells())
            return; // sudoku is unsolvable

        // copying the solution back to the board
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (cells[i][j].value)
                    board[i][j] = cells[i][j].value + '0';
            }
        }
    }
};