求解数独的C++实现##
动机###
在做数独的时候，抱着好奇心想做一个数独求解的程序。
当时我并没有接触多少算法，也是抱着试试看的心态编写了这个数独求解器。
解数独的方法###
要写一个求解数独的程序，必须要线弄清楚要用什么方法去求解数独。一般是采取简单的摒除法，然而事实上摒除法并不能做比较高级的数独。深究下去发现较高级的数独可用的方法多达十种，而且面对不同的数独要运用不同的方法，相应的算法打码量十分庞大，而且并没有一个一定的套路。计算机擅长重复单调工作，为了程序能更好的设计，我考虑使用候选数法，在候选数法不能得到解的时候采取搜索的方法，这样能保证一定的性能下一定能求出一个数独的解。
设计思路###
主要流程####
这里主要涉及两个功能，一个是摒除法，一个是搜索。
那么这里是先使用摒除法，如果摒除法不可继续求解的时候使用搜索，搜索之后使用摒除法探求正确性，一旦有错回溯并搜索下一个可能解。
这是程序的大致框架：
求解数独框架
（自豪地使用processon）
主要功能####
采用分离实现和接口的方式。
//sudoku.h
class sudoku
{
public:
sudoku();//读取文件，初始化数独
void printsudo();//打印数独
int solve();//求解
void outputsudoku();//输出解文件
int checksudoku();//检查数独是否正确
private:
int search();//搜索求解
int checkclear();//返回未填写的格子数
void base_solve();//摒除求解
void clear_solv_sudoku(int, int, int);//删除不可能的候选数
void update_ques_sudoku();//填写唯一候选数到数独
int ques_sudoku[9][9];//数独
int solv_sudoku[9][9][9];//候选数
};
为了能更好的计算候选数，同时不给原来的数独带来麻烦，我设计两个数组：一个是用来记录数独的，一个是用来记录候选数的。
填充数独的时候先使用摒除法base_solve()，首先删除不可能的候选数clear_solv_sudoku(int, int, int)，然后填写唯一候选数到数独update_ques_sudoku()。然后在不能继续摒除的时候使用搜索search()。
总体程序框架如下：
数独总体框架
（自豪地使用processon）
功能实现####
接下来就是对应的编写相应代码
//sudoku.cpp
#include <iostream>
using std::cout;
using std::endl;
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::ios_base;
#include "sudoku.h"
//读取文件并初始化数组
sudoku::sudoku()
{
//读取文件到数组
ifstream infile;
infile.open("sudoku.txt");
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
infile >> ques_sudoku[i][j];
}
}
infile.close();
//初始化候选数
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j] == 0)
{
for (int k = 0; k < 9; k++)
{
solv_sudoku[i][j][k] = 1;
}
}
else
{
for (int k = 0; k < 9; k++)
{
solv_sudoku[i][j][k] = 0;
}
}
}
}
}
//检查数独是否正确
//正确返回1，错误返回0
int sudoku::checksudoku()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j] < 0 || ques_sudoku[i][j] >9)
{return 0; }
for (int k = 0; k < 9; k++)
{
for (int l = 0; l < 9; l++)
{
if (i == k && ques_sudoku[i][j] == ques_sudoku[k][l] && ques_sudoku[i][j] && j != l)
{return 0; }
if (j == l && ques_sudoku[i][j] == ques_sudoku[k][l] && ques_sudoku[i][j] && i != k)
{return 0; }
if (((i >= 0 && i <= 2) && (j >= 0 && j <= 2) && (k >= 0 && k <= 2) && (l >= 0 && l <= 2) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 3 && i <= 5) && (j >= 0 && j <= 2) && (k >= 3 && k <= 5) && (l >= 0 && l <= 2) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 6 && i <= 8) && (j >= 0 && j <= 2) && (k >= 6 && k <= 8) && (l >= 0 && l <= 2) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 0 && i <= 2) && (j >= 3 && j <= 5) && (k >= 0 && k <= 2) && (l >= 3 && l <= 5) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 3 && i <= 5) && (j >= 3 && j <= 5) && (k >= 3 && k <= 5) && (l >= 3 && l <= 5) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 6 && i <= 8) && (j >= 3 && j <= 5) && (k >= 6 && k <= 8) && (l >= 3 && l <= 5) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 0 && i <= 2) && (j >= 6 && j <= 8) && (k >= 0 && k <= 2) && (l >= 6 && l <= 8) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 3 && i <= 5) && (j >= 6 && j <= 8) && (k >= 3 && k <= 5) && (l >= 6 && l <= 8) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
if (((i >= 6 && i <= 8) && (j >= 6 && j <= 8) && (k >= 6 && k <= 8) && (l >= 6 && l <= 8) && ques_sudoku[i][j] == ques_sudoku[k][l]) && ques_sudoku[i][j] && i != k && j != l)
{return 0; }
}
}
}
}
return 1;
}
//删除不可能的候选数
void sudoku::clear_solv_sudoku(int num1, int num2, int key)
{
//清理自身
for (int k = 0; k < 9; k++)
{
solv_sudoku[num1][num2][k] = 0;
}
for (int i = 0; i < 9; i++)
{
solv_sudoku[i][num2][key - 1] = 0;//清理行
solv_sudoku[num1][i][key - 1] = 0;//清理列
}
//清理区块
if (num1 >= 0 && num1 <= 2)
{
if (num2 >= 0 && num2 <= 2)
{
for (int i = 0; i <= 2; i++)
{
for (int j = 0; j <= 2; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 3 && num2 <= 5)
{
for (int i = 0; i <= 2; i++)
{
for (int j = 3; j <= 5; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 6 && num2 <= 8)
{
for (int i = 0; i <= 2; i++)
{
for (int j = 6; j <= 8; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
}
if (num1 >= 3 && num1 <= 5)
{
if (num2 >= 0 && num2 <= 2)
{
for (int i = 3; i <= 5; i++)
{
for (int j = 0; j <= 2; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 3 && num2 <= 5)
{
for (int i = 3; i <= 5; i++)
{
for (int j = 3; j <= 5; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 6 && num2 <= 8)
{
for (int i = 3; i <= 5; i++)
{
for (int j = 6; j <= 8; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
}
if (num1 >= 6 && num1 <= 8)
{
if (num2 >= 0 && num2 <= 2)
{
for (int i = 6; i <= 8; i++)
{
for (int j = 0; j <= 2; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 3 && num2 <= 5)
{
for (int i = 6; i <= 8; i++)
{
for (int j = 3; j <= 5; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
if (num2 >= 6 && num2 <= 8)
{
for (int i = 6; i <= 8; i++)
{
for (int j = 6; j <= 8; j++)
{
solv_sudoku[i][j][key - 1] = 0;
}
}
}
}
}
//填写唯一候选数到数独
void sudoku::update_ques_sudoku()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
int count = 0;
for (int k = 0; k < 9; k++)
{
if (solv_sudoku[i][j][k] == 1)
{count++; }
}
if (count == 1)
{
for (int k = 0; k < 9; k++)
{
if (solv_sudoku[i][j][k] == 1)
{ques_sudoku[i][j] = k + 1; }
}
}
}
}
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j])
{
for (int k = 0; k < 9; k++)
{
solv_sudoku[i][j][k] = 0;
}
}
}
}
}
//返回数独空格数
int sudoku::checkclear()
{
int count = 0;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j] == 0)
{count++; }
}
}
return count;
}
//摒除求解
void sudoku::base_solve()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j] != 0)
{
clear_solv_sudoku(i, j, ques_sudoku[i][j]);
}
}
}
update_ques_sudoku();
}
//打印数独
void sudoku::printsudo()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << ques_sudoku[i][j] << " ";
}
cout << endl;
}
}
//搜索求解
int sudoku::search()
{
//搜索第一个空格
int blank_x, blank_y;//第一个空格地址
for (int i = 0, count = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (ques_sudoku[i][j] == 0)
{
blank_x = i;
blank_y = j;
count++;
break;
}
}
if (count)
{break; }
}
//清理第一个数字此key可能性
int test_key;//第一个要测试的key
int test_key_count = 0;
for (int k = 0; k < 9; k++)//没有其余选择跳出
{
if (solv_sudoku[blank_x][blank_y][k] == 1)
{
test_key = k;
solv_sudoku[blank_x][blank_y][k] = 0;
test_key_count++;
break;
}
}
if (test_key_count == 0)
{return 1; }
//记录数独
int mark_ques_sudoku[9][9];
int mark_solv_sudoku[9][9][9];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
for (int k = 0; k < 9; k++)
{
mark_ques_sudoku[i][j] = ques_sudoku[i][j];
mark_solv_sudoku[i][j][k] = solv_sudoku[i][j][k];
}
}
}
//清理该解所有可能性
for (int k = 0; k < 9; k++)
{
solv_sudoku[blank_x][blank_y][k] = 0;
}
//试填该解
ques_sudoku[blank_x][blank_y] = test_key + 1;
//摒除求解
int result = solve();
//返回值判断
if (result == 1)
{return 0; }
//回溯
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
for (int k = 0; k < 9; k++)
{
ques_sudoku[i][j] = mark_ques_sudoku[i][j];
solv_sudoku[i][j][k] = mark_solv_sudoku[i][j][k];
}
}
}
//搜索求解
search();
return 0;
}
//求解
int sudoku::solve()
{
for (int test = 0;;)
{
//检查完全性
if (checkclear() == 0)
{return 1; }
//摒除数独
base_solve();
test = checkclear();
//检查正确性
int result = checksudoku();
if (result == 1)//是-继续
{ }
if (result == 0)//否-返回0
{return 0; }
//检查完全性
int search_result;
if (checkclear() == 0)
{return 1; }
//检查是否可以继续摒除
if (checkclear() == test)
{search_result = search(); }
//回溯上一次搜索
if (search_result == 1)
{return 0; }
}
}
//输出解文件
void sudoku::outputsudoku()
{
ofstream outfile;
outfile.open("sudokuanswer.txt");
outfile << "The answer is:" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
outfile << ques_sudoku[i][j] << " ";
}
outfile << endl;
}
outfile.close();
}
测试程序####
接下来就是测试这些函数的功能，最终架起求解数独的程序。
//sudokutest.cpp
#include <iostream>
using std::cout;
using std::endl;
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::ios_base;
#include "sudoku.h"
#include <Windows.h>
int main()
{
//预先测试文件
cout << "Opening \"sudoku.txt\"" << endl;
ifstream infile;
infile.open("sudoku.txt");
if (infile.fail())
{
cout << "Fail opening \"sudoku.txt\"" << endl;
system("pause");
return 0;
}
infile.close();
sudoku n;
if (!n.checksudoku())
{
cout << "Illegal sudo!" << endl;
system("pause");
return 0;
}
n.printsudo();
cout << endl;
n.solve();
cout << "Answer" << endl;
n.printsudo();
n.outputsudoku();
system("pause");
return 0;
}
将文件编译之后，得到程序。
程序以同目录下的sudoku.txt文件为题目求解，0代表空格，并输出答案sudokuanswer.txt。
示范测试数独题目：
0 0 0 0 0 2 0 0 0
0 7 0 1 0 8 0 9 0
0 0 1 0 0 0 3 0 0
2 5 0 7 0 4 0 8 0
0 0 0 0 0 0 0 0 0
0 8 0 6 0 9 0 1 2
0 0 3 0 0 0 9 0 0
0 6 0 3 0 5 0 2 0
0 0 0 8 0 0 0 0 0
程序测试结果：
测试结果
运算时间大约控制在100毫秒左右
后记###
整个程序花费了一个下午和晚上的时间来完成。测试了多个数独都能正常的解出来，暂未发现有什么错误和问题。
整个程序大体上就是设计一个回溯算法，然后使用摒除法来减少回溯的性能损耗。
来自个人博客http://blog.csdn.net/shellqiqi/article/details/50571822
网友评论