[数据结构与算法]Leetcode——37. 解数独

概述

题目链接

• 题目意思非常清楚，不需要额外解释

分析

• 该题，容易想到需要使用回溯法解

  回溯法基本思想这里不再解释，可以结合DFS理解

思路

• 如何确定每个位置可以填入的值？

  • 一种思路是利用函数，每次去判断列、行、小方格内的数字情况
  • 令一种思路是使用三个哈希数组，分别记录每列、每行、每个小方格内的使用数字情况

  大部分情况下，我们优先时间，所以选择方法二

• 回溯的起点在哪？

  • 从任意一个空位置开始即可

代码

class Solution {
public:
  
    // 记录每行、每列、每个九宫格的数字使用情况
    bool line[9][9];	
    bool column[9][9];
    bool block[3][3][9];

    bool flag = false;		// 记录结果
    void backTrack(int row, int col, vector<vector<char>> &board) {
        //使得 row col合法
        if(col == 9){
            ++row;
            col = 0;
        }
       
        //终止条件
        if(row == 9){
            flag = true;//找到答案
            return;
        }

        if (board[row][col] != '.'){
            backTrack(row, col + 1, board);
        }else {
            /*
            	这里之所以不用
            	for(int i in col)
            		for(int j in row)
            			...
            	是因为，此题不需要区分不同的起始位置，因为无论你从哪个位置开始解，最终的结果都只有唯一一个的（题目保证）
            	所以直接对位置进行选择数值填入，然后递归+回溯处理
            */
            for (int k = 0; k < 9 ; ++k) {
                if (!line[row][k] && !column[col][k] && !block[row / 3][col / 3][k]) {
                    line[row][k] = column[col][k] = block[row / 3][col / 3][k] = true;

                    board[row][col] = k + '0' + 1;
                    backTrack(row, col + 1, board);
                    if (flag) return;       // 已经找到结果了不需要再递归下去
                    board[row][col] = '.';
                    
                    line[row][k] = column[col][k] = block[row / 3][col / 3][k] = false;		// 回溯
                }

            }
        }

    }
    void solveSudoku(vector<vector<char>>& board) {
        // 统计初始情况
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;     
                }
            }
        }
        backTrack(0, 0, board);
    }
};

扩展

根据官方题解，可以有以下改进：

• 空间改进，使用位来保存已经存在的位置
• 时间改进，当某个位只有一个合法数字时，先去填该位置，可以减少回溯次数

本题解，只从最好实现的角度，不讨论以上两种改进，有兴趣同学可自行搜索