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 the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
  • Empty cells are indicated by the character ‘.’.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character ‘.’.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

Difficulty: Hard

这道题求数独到一个解.数独解的个数不一定.这道题是唯一解的.具体如何判断数独解的个数暂时不清楚…这里需要遍历每个格子,如果是数字,则继续下一个位置,如果是’.‘,判断如果填入数字1是否符合数独规则,如果符合数独规则那么填入数字1并继续递归.如果递归失败,则进行回溯,将数字改成’.‘,再尝试下一数字2… 这里也可以看成深度优先DFS,因为需要先确定了最后一个’.‘填入的数字

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.size()==0 || board[0].size()==0) return;
        solve(board);
    }
    
    bool solve(vector<vector<char> > &board)
    {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j]=='.') {
                    //从1到9一个个尝试
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board))
                                return true; //如果是解 就返回true
                            else
                                board[i][j] = '.'; //如果不是解,就返回
                        }
                    }
                    return false; //1-9 都尝试过了没解,返回false,说明上一层错误
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char> > &board,int row,int col,char c)
    {
        for (int i=0; i<9; i++) {
            if (board[i][col] != '.' && board[i][col] == c) return false; //验证行
            if (board[row][i] != '.' && board[row][i] == c) return false; //验证列
            //验证3x3的块.遍历这个board的这个3x3的块,看看是否有与c相同的字符,有的话就不合法.
            if (board[3*(row/3)+i/3][3*(col/3)+i%3] != '.' && board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
        }
        
        return true;
    }
};
 
comments powered by Disqus