[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.

解题思路:

之前没有玩过数独,因而就上网恶补了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;
}
};

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [LeetCode] Sudoku Solver

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡