返回

[Leetcode]37. Sudoku Solver(C++)

题目描述

题目链接:37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

例子

见官网例子。

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

解题思路

用回溯法暴力递归搜索所有解即可。需要对每一个方块、每一行、每一列都用一个向量数字的使用情况。代码如下:

#include <vector>

class Solution {
public:
    void solveSudoku(std::vector<std::vector<char>>& board) {
        std::vector<std::vector<bool>> used(27, std::vector<bool>(10, false));

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                int block_index = int(i / 3.0) * 3 + j / 3;
                int row_index = 9 + i;
                int col_index = 18 + j;

                if (board[i][j] != '.') {
                    int index = board[i][j] - '0';
                    used[block_index][index] = true;
                    used[row_index][index] = true;
                    used[col_index][index] = true;
                }
            }
        }

        solve(board, used, 0, 0);
    }

private:
    bool solve(std::vector<std::vector<char>>& board,
               std::vector<std::vector<bool>>& used, int row, int col) {
        // reach the end of board
        if (row == 9) return true;

        if (board[row][col] != '.') {
            int r = row;
            int c = col;
            if (c == 8) {
                r++;
                c = 0;
            } else {
                c++;
            }

            if (solve(board, used, r, c)) {
                return true;
            } else {
                return false;
            }
        }

        // calcualte index of hashable
        int block_index = int(row / 3.0) * 3 + col / 3;

        int row_index = 9 + row;
        int col_index = 9 * 2 + col;

        for (int i = 1; i <= 9; ++i) {
            if (!used[block_index][i] && !used[row_index][i] &&
                !used[col_index][i]) {
                used[block_index][i] = true;
                used[row_index][i] = true;
                used[col_index][i] = true;
                board[row][col] = '0' + i;
                int r = row;
                int c = col;
                if (c == 8) {
                    r++;
                    c = 0;
                } else {
                    c++;
                }

                if (solve(board, used, r, c)) {
                    return true;
                }

                used[block_index][i] = false;
                used[row_index][i] = false;
                used[col_index][i] = false;
                board[row][col] = '.';
            }
        }

        return false;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n^2)

GitHub 代码同步地址: 37.SudokuSolver.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy