01
05/2015
[LeetCode] Sudoku Solver
Sudoku Solver
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.
解题思路：
之前没有玩过数独，于是就上网恶补了一下。于是我就陷入了一个误区，数独的几种技巧想用程序完全实现出来。于是乎，纠结了很久。本来用程序员思维来做非常容易的，就是回溯而已。我实现了唯一余数法和行列摒除法，若不能继续求解，则用暴力法。代码如下。57ms。
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
set<int> allCan({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
map<int, set<int>> candidates;
map<int, set<int>> rowLeft; //某一行还剩下哪些数
map<int, set<int>> colLeft; //某一列还剩下哪些数
for (int i = 0; i < 9; i++){
rowLeft[i] = allCan;
colLeft[i] = allCan;
}
for (int i = 0; i<9; i++){
for (int j = 0; j<9; j++){
if (board[i][j] == '.'){
candidates[get1D(i, j)] = allCan;
prunning(board, i, j, candidates);
}
else{
rowLeft[i].erase(board[i][j]-'0');
colLeft[j].erase(board[i][j] - '0');
}
}
}
while (candidates.size()>0){
int unknowNumber = candidates.size();
//唯一余数法
{
for (map<int, set<int>>::iterator it = candidates.begin(); it != candidates.end();){
if (it->second.size() == 1){
int i = get2Di(it->first);
int j = get2Dj(it->first);
board[i][j] = *(it->second.begin()) + '0';
rowLeft[i].erase(board[i][j] - '0');
colLeft[j].erase(board[i][j] - '0');
candidates.erase(it++);
}
else{
it++;
}
}
for (int i = 0; i<9; i++){
for (int j = 0; j<9; j++){
if (board[i][j] == '.'){
prunning(board, i, j, candidates);
}
}
}
}
//行摒除法
{
for (int i = 0; i < 9; i++){
for (set<int>::iterator it = rowLeft[i].begin(); it != rowLeft[i].end();){
int pos = -1;
bool onlyOne = true;
for (int j = 0; j < 9; j++){
int index = get1D(i, j);
if (candidates.find(index) != candidates.end() && candidates[index].find(*it) != candidates[index].end()){
if (pos >= 0){
onlyOne = false;
break;
}
pos = j;
}
}
if (onlyOne&&pos >= 0){
board[i][pos] = *it + '0';
colLeft[pos].erase(*it);
rowLeft[i].erase(it++);
candidates.erase(get1D(i, pos));
}
else{
it++;
}
}
}
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
if (board[i][j] == '.'){
prunning(board, i, j, candidates);
}
}
}
}
//列摒除法
{
for (int j = 0; j < 9; j++){
for (set<int>::iterator it = colLeft[j].begin(); it != colLeft[j].end();){
int pos = -1;
bool onlyOne = true;
for (int i = 0; i < 9; i++){
int index = get1D(i, j);
if (candidates.find(index) != candidates.end() && candidates[index].find(*it) != candidates[index].end()){
if (pos >= 0){
onlyOne = false;
break;
}
pos = i;
}
}
if (onlyOne&&pos >= 0){
board[pos][j] = *it + '0';
rowLeft[pos].erase(*it);
colLeft[j].erase(it++);
candidates.erase(get1D(pos, j));
}
else{
it++;
}
}
}
for (int i = 0; i<9; i++){
for (int j = 0; j<9; j++){
if (board[i][j] == '.'){
prunning(board, i, j, candidates);
}
}
}
}
if (unknowNumber == candidates.size()){
break;
}
}
//若仍未解答出来，则暴力枚举
if (candidates.size() > 0){
dfsCheck(board, candidates, candidates.begin());
}
}
bool dfsCheck(vector<vector<char> > &board, map<int, set<int>> &candidates, map<int, set<int>>::iterator it){
if (it == candidates.end()){
return true;
}
int i = get2Di(it->first);
int j = get2Dj(it->first);
for (set<int>::iterator setIt = it->second.begin(); setIt != it->second.end(); setIt++){
board[i][j] = *setIt+'0';
it++;
if (isValidSudoku(board) && dfsCheck(board, candidates, it)){
return true;
}
it--;
board[i][j] = '.';
}
}
private:
int get1D(int i, int j){
return i * 9 + j;
}
int get2Di(int index){
return index / 9;
}
int get2Dj(int index){
return index % 9;
}
void prunning(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
pruningGrid(board, i, j, candidates);
pruningRow(board, i, j, candidates);
pruningColumn(board, i, j, candidates);
}
void pruningGrid(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
while (i % 3 != 0){
i--;
}
while (j % 3 != 0){
j--;
}
for (int m = i; m < i + 3; m++){
for (int n = j; n < j + 3; n++){
if (board[m][n] != '.'){
candidates[index].erase(board[m][n] - '0');
}
}
}
}
void pruningRow(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
for (int m = 0; m < 9; m++){
if (board[i][m] != '.'){
candidates[index].erase(board[i][m] - '0');
}
}
}
void pruningColumn(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
for (int m = 0; m < 9; m++){
if (board[m][j] != '.'){
candidates[index].erase(board[m][j] - '0');
}
}
}
bool isValidSudoku(vector<vector<char>>& board) {
//验证每一行是否有效
for (int i = 0; i<9; i++){
if (!checkRowValid(board, i)){
return false;
}
}
//验证每一列是否有效
for (int i = 0; i<9; i++){
if (!checkColumnValid(board, i)){
return false;
}
}
//验证每一格是否有效
for (int i = 0; i<9; i = i + 3){
for (int j = 0; j<9; j = j + 3){
if (!checkGridValid(board, i, j)){
return false;
}
}
}
return true;
}
//验证每个格是否有效，传入的是左上角的下标
bool checkGridValid(vector<vector<char>>& board, int m, int n){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = m; i<m + 3; i++){
for (int j = n; j<n + 3; j++){
if (board[i][j] == '.'){
continue;
}
if (flag[board[i][j] - '1']){
return false;
}
flag[board[i][j] - '1'] = true;
}
}
return true;
}
//验证每一行是否有效，传入的是行号
bool checkRowValid(vector<vector<char>>& board, int m){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = 0; i<9; i++){
if (board[m][i] == '.'){
continue;
}
if (flag[board[m][i] - '1']){
return false;
}
flag[board[m][i] - '1'] = true;
}
return true;
}
//验证每一列是否有效，传入的是列号
bool checkColumnValid(vector<vector<char>>& board, int n){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = 0; i<9; i++){
if (board[i][n] == '.'){
continue;
}
if (flag[board[i][n] - '1']){
return false;
}
flag[board[i][n] - '1'] = true;
}
return true;
}
};只包含唯一余数法。113ms
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
set<int> allCan({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
map<int, set<int>> candidates;
for (int i = 0; i<9; i++){
for (int j = 0; j<9; j++){
if (board[i][j] == '.'){
candidates[get1D(i, j)] = allCan;
prunning(board, i, j, candidates);
}
}
}
while (candidates.size()>0){
int unknowNumber = candidates.size();
//唯一余数法
for (map<int, set<int>>::iterator it = candidates.begin(); it != candidates.end();){
if (it->second.size() == 1){
int i = get2Di(it->first);
int j = get2Dj(it->first);
board[i][j] = *(it->second.begin()) + '0';
candidates.erase(it++);
}
else{
it++;
}
}
for (int i = 0; i<9; i++){
for (int j = 0; j<9; j++){
if (board[i][j] == '.'){
prunning(board, i, j, candidates);
}
}
}
if (unknowNumber == candidates.size()){
break;
}
}
//若仍未解答出来，则暴力枚举
if (candidates.size() > 0){
dfsCheck(board, candidates, candidates.begin());
}
}
bool dfsCheck(vector<vector<char> > &board, map<int, set<int>> &candidates, map<int, set<int>>::iterator it){
if (it == candidates.end()){
return true;
}
int i = get2Di(it->first);
int j = get2Dj(it->first);
for (set<int>::iterator setIt = it->second.begin(); setIt != it->second.end(); setIt++){
board[i][j] = *setIt+'0';
it++;
if (isValidSudoku(board) && dfsCheck(board, candidates, it)){
return true;
}
it--;
board[i][j] = '.';
}
}
private:
int get1D(int i, int j){
return i * 9 + j;
}
int get2Di(int index){
return index / 9;
}
int get2Dj(int index){
return index % 9;
}
void prunning(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
pruningGrid(board, i, j, candidates);
pruningRow(board, i, j, candidates);
pruningColumn(board, i, j, candidates);
}
void pruningGrid(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
while (i % 3 != 0){
i--;
}
while (j % 3 != 0){
j--;
}
for (int m = i; m < i + 3; m++){
for (int n = j; n < j + 3; n++){
if (board[m][n] != '.'){
candidates[index].erase(board[m][n] - '0');
}
}
}
}
void pruningRow(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
for (int m = 0; m < 9; m++){
if (board[i][m] != '.'){
candidates[index].erase(board[i][m] - '0');
}
}
}
void pruningColumn(vector<vector<char> > &board, int i, int j, map<int, set<int>> &candidates){
int index = get1D(i, j);
for (int m = 0; m < 9; m++){
if (board[m][j] != '.'){
candidates[index].erase(board[m][j] - '0');
}
}
}
bool isValidSudoku(vector<vector<char>>& board) {
//验证每一行是否有效
for (int i = 0; i<9; i++){
if (!checkRowValid(board, i)){
return false;
}
}
//验证每一列是否有效
for (int i = 0; i<9; i++){
if (!checkColumnValid(board, i)){
return false;
}
}
//验证每一格是否有效
for (int i = 0; i<9; i = i + 3){
for (int j = 0; j<9; j = j + 3){
if (!checkGridValid(board, i, j)){
return false;
}
}
}
return true;
}
//验证每个格是否有效，传入的是左上角的下标
bool checkGridValid(vector<vector<char>>& board, int m, int n){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = m; i<m + 3; i++){
for (int j = n; j<n + 3; j++){
if (board[i][j] == '.'){
continue;
}
if (flag[board[i][j] - '1']){
return false;
}
flag[board[i][j] - '1'] = true;
}
}
return true;
}
//验证每一行是否有效，传入的是行号
bool checkRowValid(vector<vector<char>>& board, int m){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = 0; i<9; i++){
if (board[m][i] == '.'){
continue;
}
if (flag[board[m][i] - '1']){
return false;
}
flag[board[m][i] - '1'] = true;
}
return true;
}
//验证每一列是否有效，传入的是列号
bool checkColumnValid(vector<vector<char>>& board, int n){
bool flag[9];
memset(flag, 0, sizeof(bool)* 9);
for (int i = 0; i<9; i++){
if (board[i][n] == '.'){
continue;
}
if (flag[board[i][n] - '1']){
return false;
}
flag[board[i][n] - '1'] = true;
}
return true;
}
};转载请注明：康瑞部落 » [LeetCode] Sudoku Solver
0 条评论