[LeetCode] Sudoku Solver
來源：程序員人生 發布時間：2015-05-06 09:00:58 閱讀次數：2591次
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.
解題思路：
之前沒有玩過數獨，因而就上網惡補了1下。因而我就墮入了1個誤區，數獨的幾種技能想用程序完全實現出來。因而乎，糾結了很久。本來用程序員思惟來做非常容易的，就是回溯而已。我實現了唯1余數法和行列摒除法，若不能繼續求解，則用暴力法。代碼以下。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; //某1行還剩下哪些數
map<int, set<int>> colLeft; //某1列還剩下哪些數
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();
//唯1余數法
{
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 = ⑴;
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 = ⑴;
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;
}
};
只包括唯1余數法。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();
//唯1余數法
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;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
