数独程序开发文档

版权声明:本文及数独程序基于MIT协议发布。

背景

这半个学期的末尾,我们数学课一直在学习算法、程序框图以及初步的程序。寒假作业里面提供了二选一的作业:

  1. 完成一个统计实习报告
  2. 自学一门计算机程序设计语言,并开发一个小型的软件

我当然选择了第二个。

我本来想写一个KMP,或者后缀树,这样才能体现算法的精髓(至少我是这么认为的)。但是没有测试数据量的话这个高效算法的强大又体现不出来。我只得做了一个比较实用的小程序:数独计算器。

源码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline bool isNum(char c){
	return c>='0'&&c<='9';
}
inline int nextInt(){
	int i=0;char c;
	while(!isNum(c=getchar()));
	for(;isNum(c);i=i*10-'0'+c,c=getchar());
	return i;
}
int mat[9][9],solves=1;
bool row[9][10],col[9][10],blk[3][3][10];
inline void output(){
	cout<<"One possible solution:"<<endl;
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			if(mat[i][j]){
				putchar(mat[i][j]+'0');
			}else{
				putchar(' ');
			}
			if(j%3==2){
				putchar('|');
			}else{
				putchar(' ');
			}
		}
		cout<<endl;
		if(i%3==2){
			cout<<"------------------"<<endl;
		}
	}
}
bool dfs(int x,int y){
	if(y==9){
		x++,y=0;
	}
	if(x==9){
		output();
		return (--solves)==0;
	}
	if(mat[x][y]){
		return dfs(x,y+1);
	}
	mat[x][y]=1;
	bool *r=row[x],*c=col[y],*b=blk[x/3][y/3];
	for(int &i=mat[x][y];i<=9;i++){
		if(!(r[i]||c[i]||b[i])){
			r[i]=c[i]=b[i]=true;
			if(dfs(x,y+1)){
				return true;
			}
			r[i]=c[i]=b[i]=false;
		}
	}
	mat[x][y]=0;
	return false;
}
int main(int argc,char**args){
	for(int i=1;i<argc;i++){
		if(args[i][0]=='-'){
			if(++i==argc){
				cout<<"Missing parameter for option:"<<args[i]<<endl;
				break;
			}
			switch(args[i-1][1]){
				case 'o':{
					freopen(args[i],"w",stdout);
					break;
				}
				case 'i':{
					freopen(args[i],"r",stdin);
					break;
				}
				case 's':{
					solves=0;
					char *p=args[i];
					for(;isNum(*p);solves=solves*10-'0'+(*p),p++);
					break;
				}
			}
		}else if(strcmp(args[i],"help")==0){
			cout<<"\
***** Soduku Solver 0.0.1 *****\n\
Command:\n\
	soduku [-o outputFile] [-i inputFile] [-s solvesCount]\n\
Input:\n\
	A 9 by 9 number matrix which indicates the soduku.\n\
	For blank, use '0' instead.\
"<<endl;
			return 0;
		}else{
			cout<<"Unknown parameter:"<<args[i]<<endl;
		}
	}
	memset(row,0,sizeof(row));
	memset(col,0,sizeof(col));
	memset(blk,0,sizeof(blk));
	cout<<"Please input the soduku:"<<endl;
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			mat[i][j]=nextInt();
			row[i][mat[i][j]]=true;
			col[j][mat[i][j]]=true;
			blk[i/3][j/3][mat[i][j]]=true;
		}
	}
	if(!dfs(0,0)){
		cout<<"Unable to give enough solutions as required.";
	}
}

开发文档

这个程序(soduku.exe)能够在有限时间内给出数独的解。

算法

核心为深度有限搜索,通过递归与回溯实现。

流程图

深搜函数:
Soduku_flowchart_dfs

感谢flowchart.js提供的流程图渲染

核心代码

使用C++实现:

bool dfs(int x,int y){
	if(y==9){
		x++,y=0;
	}
	if(x==9){
		output();
		return (--solves)==0;
	}
	if(mat[x][y]){
		return dfs(x,y+1);
	}
	mat[x][y]=1;
	bool *r=row[x],*c=col[y],*b=blk[x/3][y/3];
	for(int &i=mat[x][y];i<=9;i++){
		if(!(r[i]||c[i]||b[i])){
			r[i]=c[i]=b[i]=true;
			if(dfs(x,y+1)){
				return true;
			}
			r[i]=c[i]=b[i]=false;
		}
	}
	mat[x][y]=0;
	return false;
}

使用方法

默认在windows环境下。linux环境需重新编译,并在程序名前加./

首先打开Command。有几种方式:

  • Win+R,输入cmd
  • 在开始菜单中找到命令提示符并打开
  • Windows 7及以上可以在当前文件夹下按住shift再选择在此处打开命令窗口(推荐)

然后切换到soduku.exe所在位置(使用cd命令)。

测试程序是否已经正确安装,输入soduku help打开帮助:

直接运行soduku,然后从左到右,从上到下输入数独题目。如果为空(未确定),则 输入0。两两数字中间使用空格隔开。

最后按回车执行。

就能得到答案了!

更多选项

正如在帮助里面看到的,我还添加了一些其他选项来方便使用。

设置输出文件

在运行soduku的时候,在命令后面添加-o <FILENAME>就可以把输出结果储存到文件里面去了。出于效率考虑,如果设置了输出,在控制台上是看不到结果的。

设置输入文件

如果你不想每次都输入数独题目,或者需要通过批处理批量处理题目,那么就加上-i <FILENAME>选项吧!

<FILENAME>的路径是相对于soduku程序而言的。上同。

设置解个数上限

尽管有多个解的数独是不规范的,但是如果你想出一道数独题,那么你可能需要用到这个功能。

输入一个数独,再用-s <NUM>来设置最多输出<NUM>个解。

比如说,soduku -s 2:

结语

这个程序能够很快给出一个数独的解,但是用户界面的门槛有点高。以后考虑给这种应用程序加上GUI。

avatar
Kerry Su