查看:9965|回复：20
助理工程师
最近迷上了数独游戏，linux下的游戏，android市场上有，但我不太喜欢。我更喜欢linux版下的操作方式。于是就想把它搬到android手机上玩。
花了一周的业余时间，终于出了一个简单版本了。
现在发到论坛里，希望各位能试用下。提个意见。
这是我的第一个android游戏。
玩的时候，建议别把左下的按钮打开；否则提示太丰富，游戏太简单了。不如自己一个一个的敲可能数字，有趣很多。
(206.23 KB)
00:21, 下载次数: 1433
助理工程师
怎么上传附件啊？
技术成就梦想
在左下角，有个选择文件的框，那个功能模块叫上传图片，其实也能上传RAR文件另外你也可以上传到，然后在这里给出链接~
不积跬步无以至千里
谢谢楼主分析
资深技术经理
引用:原帖由 stefan58 于
21:47 发表
最近迷上了数独游戏，linux下的游戏，android市场上有，但我不太喜欢。我更喜欢linux版下的操作方式。于是就想把它搬到android手机上玩。
花了一周的业余时间，终于出了一个简单版本了。
现在发到论坛里，希望各位能试用下。提 ... 楼主，这个有无源代码呢？求源代码。。
助理工程师
引用:原帖由 rongwei84n 于
09:44 发表
楼主，这个有无源代码呢？求源代码。。 Sudoku源代码。
代码如果再对提示的可能数字进行分析计算，都可让系统自己去把数字填满了。
(1023.18 KB)
14:49, 下载次数: 1621
本帖最后由 stefan58 于
14:55 编辑
资深技术经理
引用:原帖由 stefan58 于
14:49 发表
Sudoku源代码。
代码如果再对提示的可能数字进行分析计算，都可让系统自己去把数字填满了。 楼主的id让我想起了&吸血鬼日记&里面的那个男主角，斯特凡。。 超帅的;P1
助理工程师
呵呵，果真是萝卜青菜，各有所爱，来顶了！！！ 加油&&O_O
╰☆╮听悲伤的歌，看幸福的戏…年少轻狂…幸福时光......
【学习只是为了明白自己的无知】 ...
呵呵呵去下载了玩一下 娱乐娱乐也表示对楼主的支持
想要在网络的海洋自由的遨游吗？系统攻防欢迎你！！！
一个人没有金钱并不可怕，没有地位也并不可悲，只有不善巧思，缺乏智慧，才是人生最大的缺憾。
更多精彩请关注
资深技术经理
引用:原帖由 stefan58 于
14:49 发表
Sudoku源代码。
代码如果再对提示的可能数字进行分析计算，都可让系统自己去把数字填满了。 今天上午把楼主的代码看了一遍，大爱！:lol1&&:lol1
提示: 作者被禁止或删除 内容自动屏蔽
资深技术经理
引用:原帖由 爱吃西瓜 于
19:18 发表
厉害啊................... 替楼主感谢你，因为我读了楼主的源代码一遍，受益匪浅。。:$1
助理工程师
引用:原帖由 rongwei84n 于
09:25 发表
替楼主感谢你，因为我读了楼主的源代码一遍，受益匪浅。。:$1 第一次用java写点东西，代码相当混乱。
请各位同学多多包含。
我也不喜欢网上的数独游戏，见楼主自编了，下载……表示支持！
高端产品围观下
资深技术经理
引用:原帖由 stefan58 于
19:23 发表
第一次用java写点东西，代码相当混乱。
请各位同学多多包含。 好谦虚的楼主，真的不错呢。。:loveliness:1
怎么下下来解压不了...说格式未知或数据损坏了。。
引用:原帖由 stefan58 于
14:49 发表
Sudoku源代码。
代码如果再对提示的可能数字进行分析计算，都可让系统自己去把数字填满了。 eclipse代入进去提示错误啊，具体怎么操作~！急！
引用:原帖由 rongwei84n 于
17:47 发表
楼主的id让我想起了&吸血鬼日记&里面的那个男主角，斯特凡。。 超帅的;P1 eclipse代入进去提示错误啊，具体怎么操作~！急！加我Q，重金礼谢
为什么下载下来 SRC里面全是错c++实现的简单数独计算器 - qq - 博客园
平时挺喜欢写小程序的，但是不知道写啥，偶然看到关于数独的新闻，觉得用小程序实现再合适不过了，网上一搜，有原理，有程序，但是没有找到优秀的代码，干脆自己写了一个，虽然也不优秀，起码自己看得懂。
1、每个格子可以是1-9的数，n行m列的数确定后，则第n行，第m列，nm所在的&宫&里其他的格子就不能是这个数了。
2、刚开始每个格子都有9个&候选数&，逐步把初始数据添加到最终的格子中，并把相应的格子中的候选数更新，如1所说。
3、开始计算，选出候选数最少的格子，对这些数迭代测试，如把候选数中的第1个添加到最终的格子中。和2一样更新其他格子的候选数列表。
4、3之后自然还是3，所以把3实现为递归要简单一些。而且考虑到本题实际情况最多递归81层，不会栈溢出。而且递归本身还保存了后续所需数据，简化了操作。
代码注释：
g_currentIndex：格子中已经确定结果的个数（添加到格子中的数的个数，递归的深度），索引表示的，所以0代表已添加1个。
g_affectedFlags：位标志，某次添加数据是否对格子产生影响，回退操作要使用。
g_candidate：每个格子的候选列表，用bitset的索引表示。第n位为1，代表n是候选数。
g_candidateNum：每个格子的候选个数，为什么不用bitset的count呢？因为速度太慢。
结果截图：
#include&iostream&
#include&set&
#include&bitset&
#include&cstring&
#include&time.h&
using namespace
int g_currentIndex=-1;
bitset&81& g_affectedFlags[9][9];
bitset&10& g_candidate[9][9];
int g_candidateNum[9][9];
int resultN
const int maxNum=5;
int g_map[9][9]={
{8,0,0,0,0,0,0,0,0},
{0,0,3,6,0,0,0,0,0},
{0,7,0,0,9,0,2,0,0},
{0,5,0,0,0,7,0,0,0},
{0,0,0,0,4,5,7,0,0},
{0,0,0,1,0,0,0,3,0},
{0,0,1,0,0,0,0,6,8},
{0,0,8,5,0,0,0,1,0},
{0,9,0,0,0,0,4,0,0},
void AddElement(int row,int column,int num)
++g_currentI
g_map[row][column]=
for(int i=0;i&9;++i)
if(g_map[row][i]==0 && g_candidate[row][i].test(num))
g_candidate[row][i].reset(num);
--g_candidateNum[row][i];
g_affectedFlags[row][i].set(g_currentIndex);
if(g_map[i][column]==0 && g_candidate[i][column].test(num))
g_candidate[i][column].reset(num);
--g_candidateNum[i][column];
g_affectedFlags[i][column].set(g_currentIndex);
int palaceRow=row&2?(row&5?6:3):0;
int palaceColumn=column&2?(column&5?6:3):0;
for(int i=0;i&3;++i)
for(int j=0;j&3;++j)
row=palaceRow+i;
column=palaceColumn+j;
if(g_map[row][column]==0 && g_candidate[row][column].test(num))
g_candidate[row][column].reset(num);
--g_candidateNum[row][column];
g_affectedFlags[row][column].set(g_currentIndex);
void RecoverElement(int row,int column,int num)
g_map[row][column]=0;
for(int i=0;i&9;++i)
if(g_map[row][i]==0 && g_affectedFlags[row][i].test(g_currentIndex))
g_candidate[row][i].set(num);
++g_candidateNum[row][i];
g_affectedFlags[row][i].reset(g_currentIndex);
if(g_map[i][column]==0 && g_affectedFlags[i][column].test(g_currentIndex))
g_candidate[i][column].set(num);
++g_candidateNum[i][column];
g_affectedFlags[i][column].reset(g_currentIndex);
int palaceRow=row&2?(row&5?6:3):0;
int palaceColumn=column&2?(column&5?6:3):0;
for(int i=0;i&3;++i)
for(int j=0;j&3;++j)
row=palaceRow+i;
column=palaceColumn+j;
if(g_map[row][column]==0 && g_affectedFlags[row][column].test(g_currentIndex))
g_candidate[row][column].set(num);
++g_candidateNum[row][column];
g_affectedFlags[row][column].reset(g_currentIndex);
--g_currentI
void Init()
for(int i=0;i&9;++i)
for(int j=0;j&9;++j)
g_candidate[i][j].set();
g_candidateNum[i][j]=10;
for(int i=0;i&9;++i)
for(int j=0;j&9;++j)
if(g_map[i][j]!=0)
AddElement(i,j,g_map[i][j]);
bool FindBest(int &row,int &column)
int min=999;
for(int i=0;i&9;++i)
for(int j=0;j&9;++j)
if(g_map[i][j]==0 && g_candidateNum[i][j]&1 && g_candidateNum[i][j]&min)
min=g_candidateNum[i][j];
if(min==999)
return false;
return true;
bool CheckResult()
set&int& elements2;
for(int i=0;i&9;++i)
for(int j=0;j&9;++j)
elements.insert(g_map[i][j]);
elements2.insert(g_map[j][i]);
if(elements.size()!=9)
return false;
if(elements2.size()!=9)
return false;
elements.clear();
elements2.clear();
elements.clear();
for(int i=0;i&3;++i)
for(int j=0;j&3;++j)
column=j*3;
for(int k=0;k&9;++k)
elements.insert(g_map[row+k/3][column+k%3]);
if(elements.size()!=9)
return false;
elements.clear();
return true;
void OutputResult()
for(int i=0;i&9;++i)
for(int j=0;j&9;++j)
cout&&g_map[i][j]&&" ";
bool Try()
if(!FindBest(row,column))
return true;
for(int i=1;i&10;++i)
if(!g_candidate[row][column].test(i))
AddElement(row,column,i);
if(g_currentIndex==80 && CheckResult())
cout&&endl&&"Result:"&&++resultNum&&
OutputResult();
if(resultNum&=maxNum)
return false;
return false;
RecoverElement(row,column,i);
return true;
int main()
double start,end,
start=clock();
if(resultNum)
cout&&endl&&"OK!"&&
cout&&endl&&"Wrong Input!"&&
end=clock();
cout&&"Costed time:"&&cost&&"ms"&&
个人觉得这种方法已经到了速度的极限，高手的代码竟然能够达到几十毫秒，表示自叹不如!
我用的例子是&史上最难数独&，确实只有一个解，代码中maxNum可以限制显示结果数量。
附其他高手的截图一张：
阅读(...) 评论()查看: 2764|回复: 6
谁能写一个高效的c++数独代码呢？
主题帖子精华
在线时间 小时
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
才可以下载或查看，没有帐号？
如果还不知道什么叫做数独，那么请看百度百科吧。
九宫格数独：
写的代码要求如下：
3、必须有注释，如果没有注释，你就不要贴上来了，我最讨厌没有注释的程序
4、尽可能地能求出所有解
5、在开始的时候先判断下是否有解，有的时候给出的数独根本没有解。
请高人露面吧。贴上你的c++之类的代码吧。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
最高效的是DLX算法，对任何布局可瞬间求解。但网上的程序都没注释，就不贴上来了。
& &Dancing Link算法(以下简称DLX)是解NPC难题中的精确覆盖(Exact Cover)的高效算法，一个问题，如果能转化成Exact Cover模型，则都能用DLX解。数独的解法也不列外。
& && & 对于一个N*N的(N=K*K)数独，我们可以用一个3位的N进制数rck(0&=r,c,k&N)来表示第r行第c列放的数是k+1。这样我们就可以用N*N*N个状态来表示所有可能的状态，这同时也是转化成Exact Cover后矩阵的行的个数。
& && & 而对于每一个状态rck，该状态的Exact Cover的模型放置是怎样的呢？我们可以用[0,N*N)区间表示行冲突，[N*N,2*N*N)区间表示小方块冲突，[2*N*N,3*N*N)区间表示列冲突，[3*N*N,4*N*N)区间表示k这个数放置的位置。这里的4*N*N就是转化成Exact Cover后矩阵的列的个数。
& && & 至此，数独的Exact Cover模型已经建立完毕，剩下的就是DLX算法的实现了。
非常有价值
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
风云剑 在人工智能方面研究比较深，发的帖子比较切中主题。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
被机器人弄起来的
说说我对DLX算法的体会
是将求解状态以十字链表形式保留，减少了出入栈的花费，但本质上依然是NP的，而且可能出现重复求解。
选择最短的列来寻找适合的行，在递归前几层会迅速消耗“密切相关”的行与列，造成强烈剪枝的假象；但“关系疏远”的就没有改善。以我处理过的例子，各层循环数大概为 19、15、10、6、2、1（貌似很好）、20、17、11、8、3、1（又来？）、、20、17、11、8、3、1（还来！）……19、15、10、 6、2、1…… 你慢慢玩，偶回家吃饭了。
估计DLX近似O(a^n)。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
1、DLX做对称性01矩阵时存在重复分析的情况
如下面矩阵
它实质是两个相同子矩阵组成的，按基本DLX方法，会在求左上子矩阵一解后对右下矩阵重复求解。更好的办法是分割子矩阵，然后全问题解就是两部分解的组合。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
2、再看一般的精确覆盖01矩阵，任两行、任两列的交换后解是不变的。我们可以将一个0和1均匀分布的矩阵通过行列交换变成
左下、右上都是零的矩阵：
“x” 是不能彻底划分到左侧右侧的那些行，“+”是前“x”这类行的公共列。类似DLX算法的剪枝，不过我们首先选择的是“+”这类列。很快整个01矩阵被分成 L和R两个小矩阵，再分治。
如是这般，似乎能通向O(n^v * log n)的复杂性，log n是分治成本，n^v则是每次行列交换的计算成本。v是多少在于行列交换算法成本，我现在能到 3，但交换结果一般。
行列的交换算法有很大的优化潜力。高效的交换结果应当是L和R矩阵尽量大而接近，“+”列列数少而且每列短。这样能充分发挥分割分治的优势。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
还有就是，既然矩阵任两行、任两列的交换后解是不变的，能否构建一个HASH方法，记录已计算矩阵，避免重复计算。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
Powered by我是一个C++初学者，控制台实现了一个解数独的小程序。
代码如下：
//"数独游戏"V1.0
//李国良于日编写完成
#include &iostream&
#include &fstream&
#include &string&
#include &Windows.h&
using namespace
const int ArSize = 9;
string loadFile(int arr[ArSize][ArSize]);//读取文件，返回文件名
void printMap(int arr[ArSize][ArSize]);//显示数独
void solve(int arr[ArSize][ArSize], int enumer[ArSize], int i, int j);//计算当前单元格的候选数
bool solveV(int arr[ArSize][ArSize], int i, int j);//判断当前单元格是否可填
bool lopMap(int arr[ArSize][ArSize]);//循环遍历未解单元格，调用solveV求解
bool loopMap(int arr[ArSize][ArSize]);//暴力求解！！！
void saveFile(int arr[ArSize][ArSize], string str);//保存文件
int main()
SetConsoleTitle("数独游戏");
int map[ArSize][ArSize];
for (auto &row : map)
for (auto &ival : row)
ival = -1;
string name = loadFile(map);
printMap(map);
bool surplus = lopMap(map);
cout && "lopMap()解答完毕" &&
printMap(map);
if (!surplus)
loopMap(map);
cout && "loopMap()解答完毕" &&
printMap(map);
saveFile(map, name);
cin.get();
cin.get();
string loadFile(int arr[ArSize][ArSize])
string fileN
ifstream inF
cout && "请输入文件名：" &&
while (true)
cin && fileN
inFile.open(fileName + ".txt");
if (!inFile.is_open())
cout && "文件未能成功打开，请重新输入文件名：" &&
bool judg = true;
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
inFile && arr[i][j];
if (arr[i][j] & 0 || arr[i][j] & 9)
judg = false;
cout && "文件\"" && fileName && ".txt" && "\"载入成功！" &&
inFile.close();
cout && "文件内容有误，请重新输入文件名：" &&
inFile.close();
return fileN
void printMap(int arr[ArSize][ArSize])
int num = 0;
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
cout && arr[i][j];
if (j != 8)
cout && " ";
if (!arr[i][j])
cout && num && "剩余单元格！" && endl &&
void solve(int arr[ArSize][ArSize], int enumer[ArSize], int i, int j)
for (int num = 0; num & ArS ++num)
enumer[num] = num + 1;
for (int m = 0; m & ArS ++m)
if (arr[m][j])
enumer[arr[m][j] - 1] = 0;
for (int n = 0; n & ArS ++n)
if (arr[i][n])
enumer[arr[i][n] - 1] = 0;
for (int m = i / 3 * 3; m & i / 3 * 3 + 3; ++m)
for (int n = j / 3 * 3; n & j / 3 * 3 + 3; ++n)
if (arr[m][n])
enumer[arr[m][n] - 1] = 0;
bool solveV(int arr[ArSize][ArSize], int i, int j)
int enumeration[ArSize];
int ation[ArSize];
solve(arr, enumeration, i, j);
int x = 0;
for (int i = 0; i & ArS ++i)
if (enumeration[i])
if (x == 1)
arr[i][j] = enumeration[y];
return true;
for (y = 0; y & ArS ++y)
if (enumeration[y])
for (int m = 0; m & ArS ++m)
if (arr[m][j] == 0 && m != i)
solve(arr, ation, m, j);
if (ation[y])
if (!ation[y])
arr[i][j] = enumeration[y];
return true;
for (int n = 0; n & ArS ++n)
if (arr[i][n] == 0 && n != j)
solve(arr, ation, i, n);
if (ation[y])
if (!ation[y])
arr[i][j] = enumeration[y];
return true;
bool judge = false;
for (int m = i / 3 * 3; m & i / 3 * 3 + 3; ++m)
for (int n = j / 3 * 3; n & j / 3 * 3 + 3; ++n)
if (arr[m][n] == 0 && (m != i || n != j))
solve(arr, ation, m, n);
if (ation[y])
if (!ation[y])
arr[i][j] = enumeration[y];
return true;
return false;
bool lopMap(int arr[ArSize][ArSize])
int num = 0;
while (true)
int number = 0;
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
if (!arr[i][j])
if (!solveV(arr, i, j))
number += 1;
if (!number || num == number)
return num == 0 ? true : false;
bool loopMap(int arr[ArSize][ArSize])
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
if (!arr[i][j])
int enumer[ArSize];
solve(arr, enumer, i, j);
for (int n = 0; n & ArS ++n)
if (enumer[n])
int maps[ArSize][ArSize];
for (int x = 0; x & ArS ++x)
for (int y = 0; y & ArS ++y)
maps[x][y] = arr[x][y];
maps[i][j] = enumer[n];
if (lopMap(maps))
for (int x = 0; x & ArS ++x)
for (int y = 0; y & ArS ++y)
arr[x][y] = maps[x][y];
return true;
bool judge = true;
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
if (!maps[i][j])
int num = 0;
int enumerat[ArSize];
solve(maps, enumerat, i, j);
for (auto n : enumerat)
judge = false;
if (judge)
if (loopMap(maps))
for (int x = 0; x & ArS ++x)
for (int y = 0; y & ArS ++y)
arr[x][y] = maps[x][y];
return true;
return false;
void saveFile(int arr[ArSize][ArSize], string str)
ofstream outF
outFile.open(str + "answer.txt");
if (!outFile.is_open())
cout && "文件保存失败！" &&
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
outFile && arr[i][j];
if (j != 8)
outFile && " ";
outFile &&
cout && "文件\"" && str && "answer.txt" && "\"保存成功！" &&
outFile.close();
loopMap()函数使用了递归，递归函数写的非常伤脑筋，感觉这个函数写的不好，目前还没找到改进的办法，姑且能用。
阅读(...) 评论()