37. Sudoku Solver

题目：Sudoku Solver

原题描述

原题链接：https://leetcode.com/problems/sudoku-solver/?tab=Description 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

给出一张数独表，完成填写。 空白部分用’.’表示，题目保证有且仅有唯一解。

思路

采用回溯法，假设数组按照从左到右从上到下的顺序扫描，每遇到一个空格，从1到9枚举出第一个能够满足当前位置合法的字符，然后扫描下一个空格进行枚举，一直到所有的空格都填满，则表示已经完成。如果当前空格枚举到9都不能合法，则把当前空格置为’.’，回溯到上一个空格，上一个空格的字符在原有的字符上加一，然后继续枚举出第一个能合法的字符，再继续往下，然后有问题则继续回溯，一直到所有空格都填满，或者第一个空格回溯到了9也不能满足为止（当然题目保证有唯一解，肯定可以填满。）

代码

class Solution { public: void solveSudoku(vector<vector<char>>& board) { // ve用来存储每一个空格的位置信息 vector<pair<int, int>> ve; for(int i = 0; i < 9; ++i) { for(int j = 0; j < 9; ++j) { if(board[i][j] == '.') { ve.push_back(std::make_pair(i, j)); } } } if(!ve.size()) return; int len = ve.size(), index = 0; while(1) { int row = ve[index].first, col = ve[index].second; // 数独无解，退出 if(index == 0 && board[row][col] == '9') break; // 所有空格都已经填满，退出。 if(index == len) break; // 当前空格为初始状态'.'，则转化成'0' if(board[row][col] == '.') { board[row][col] = '0'; } // 从当前字符的下一个开始枚举 board[row][col] += 1; while(board[row][col] <= '9' && !isOk(board, row, col)) { board[row][col] += 1; } // 满足要求则递归判断下一个空格，否则回溯到上一个空格 if(board[row][col] <= '9') { index++; }else{ board[row][col] = '.'; index--; } } } private: // 判断当前位置上数字是否合法，即分别在对应的行、列、子块都唯一 bool isOk(vector<vector<char>>& board, int row, int col) { for(int i = 0; i < 9; ++i) { if(i == row) continue; if(board[i][col] == board[row][col]) return false; } for(int i = 0; i < 9; ++i) { if(i == col) continue; if(board[row][i] == board[row][col]) return false; } int stR = row / 3, stC = col / 3; for(int i = stR * 3; i < stR * 3 + 3; ++i) { for(int j = stC * 3; j < stC * 3 + 3; ++j) { if(i == row && j == col) continue; if(board[i][j] == board[row][col]) return false; } } return true; } };

优化

这个解法还可以优化一下，比如在所有空格都是初始化的时候对每个空格都进行一次枚举，确定每个空格能在初始状态下能够满足的字符有哪几个，这样就不用每次都从’1’到’9’开始枚举啦，具体就让读者们自己试着写写吧