你一定听说过“数独”游戏。
如【图1.png】,玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个同色九宫内的数字均含1-9,不重复。
数独的答案都是唯一的,所以,多个解也称为无解。
本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说,恐怕易如反掌了。
本题的要求就是输入数独题目,程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的,并且题目有唯一的解。
格式要求,输入9行,每行9个字符,0代表未知,其它数字为已知。
输出9行,每行9个数字表示数独的解。
例如:
输入(即图中题目):
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
程序应该输出:
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764
再例如,输入:
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
程序应该输出:
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。
代码如下,比较完美的解决了
- #include <iostream>
- #include <cmath>
- #include <string>
- #include <stack>
- #include <vector>
- #include <iomanip>
- #include <stack>
- #include <set>
- #include <map>
- #include <cstdio>
- using namespace std;
- int Table[10][10];//保存棋盘
- map<int,bool> line[10];//保存每一行是否存在某个数字
- map<int,bool> column[10];//保存每一列是否存在某个数字
- map<int,bool> latex[10];//保存某个九宫格是否存在某个数字
- struct point
- {
- int x;
- int y;
- };
- vector<point> Queue;//保存需要操作的节点位置
- void dfs(int k)
- {
- if(k==Queue.size())
- {
- cout<<endl;
- for(int i=1;i<=9;i++)
- {
- for(int j=1;j<=9;j++)
- {
- cout<<Table[i][j];
- }
- cout<<endl;
- }
- }
- int x=Queue[k].x;//取出x
- int y=Queue[k].y;//取出y
- int latexindex=((x-1)/3)*3+((y-1)/3)+1;//计算九宫格位置
- for(int i=1;i<=9;i++)
- {
- if(!line[x][i]&&!column[y][i]&&!latex[latexindex][i])//判断在弟x行y列 弟latexindex个九宫格能否放置y
- {
- //修改Table
- Table[x][y]=i;
- //修改map
- line[x][i]=true;
- column[y][i]=true;
- latex[latexindex][i]=true;
- dfs(k+1);
- //还原Table
- Table[x][y]=0;
- //还原map
- line[x][i]=false;
- column[y][i]=false;
- latex[latexindex][i]=false;
- }
- }
- }
- int main()
- { //输入数据
- for(int i=1;i<=9;i++)
- {
- string temp;
- cin>>temp;
- for(int j=1;j<=9;j++)
- Table[i][j]=temp[j-1]-'0';
- }
- //设置map 、 queue
- for(int i=1;i<=9;i++)
- {
- for(int j=1;j<=9;j++)
- {
- if(Table[i][j]!=0)
- {
- line[i][Table[i][j]]=true; //设置map->line
- column[j][Table[i][j]]=true; //设置map->column
- int latexindex=((i-1)/3)*3+((j-1)/3)+1;//计算九宫格位置
- latex[latexindex][Table[i][j]]=true;//设置map->latex
- }
- else
- {
- point temp;
- temp.x=i;
- temp.y=j;
- Queue.push_back(temp);
- }
- }
- }
- dfs(0);
- return 0;
- }