求数独游戏最优算法
这两天经常在想有没有一个好一点的算法，解决数独九宫格的问题，无果，特来求教~
相信大家对数独游戏应该都有了解，不了解也没关系。再说一下游戏规则：
在9阶方阵中，包含了81个小格（九列九行），其中又再分成九个小正方形（称为宫），每宫有九个小格。游戏开始时，盘面上有些小格已经填了数字（称为初盘），游戏者要在空白的小格中填入1到9的数字，使得最后每行、每列、每宫都不出县重复的数字，而且每一个游戏都只有一个唯一的解答（称为终盘）。
规则说清楚了，下面说说要求，首先随机生成“初盘”，能使最后有且仅有一解，或者能手工录入“初盘”信息；然后通过一个最优的算法，将结果求出并输出，格式不限。（最好不要用什么穷举法，没意义……）
[解决办法]
关注中！！
[解决办法]
mathe好像专门写过这方面的算法文章。
http://blog.csdn.net/mathe/archive/2007/08/23/1755672.aspx
[解决办法]
帮顶一下
[解决办法]
mathe的数独游戏已经作得很好了~
常见的是用DLX算法来解决数独问题（忍不住又提起这个：《Dancing Links》，http://www-cs-faculty.stanford.edu/~knuth/preprints.html 能下载到），效率不错。
[解决办法]
顶一下 很有挑战呀
[解决办法]
以前写的一个
没有判断输入是否合法，而且是根据唯一性来判断的
#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
enum STRATEGY {LOOKUPINMATRIX, LOOKUPINROW, LOOKUPINCOLUMN};
//#define OUTPUT_DEBUG
const char* szDataFile = "data1.txt"; //数据文件名
int data[9][9]; //魔法数独的数据
int curstepx[9]; //每次搜索最多搜出的步数不超过9步，必须
int curstepy[9]; //记录每步的相关信息，在哪一行哪一列放下哪个数字
int curstepnumber[9];
STRATEGY strategy[9]; //每一步所采用的策略
int curstepcount= 0; //搜索出的步数
int datatemplate[9][9] = { //数据模板，将所有数据分成9个小方块
{1, 1, 1, 2, 2, 2, 3, 3, 3},
{1, 1, 1, 2, 2, 2, 3, 3, 3},
{1, 1, 1, 2, 2, 2, 3, 3, 3},
{4, 4, 4, 5, 5, 5, 6, 6, 6},
{4, 4, 4, 5, 5, 5, 6, 6, 6},
{4, 4, 4, 5, 5, 5, 6, 6, 6},
{7, 7, 7, 8, 8, 8, 9, 9, 9},
{7, 7, 7, 8, 8, 8, 9, 9, 9},
{7, 7, 7, 8, 8, 8, 9, 9, 9}};
//本文所有方法
void LookupInMatrix(int tdata[][9], int numberToPut);
void LookupInRow(int tdata[][9], int numberToPut);
void LookupInColumn(int tdata[][9], int numberToPut);
bool TryOneStep();
void MakeStep();
void Output(int tdata[][9]);
//本文所有方法
void LookupInMatrix(int tdata[][9], int numberToPut)
{
int i, j, k;
bool flag = false;
int count = 0;
int xToPut, yToPut;
for (k=1; k <=9; k++) //遍历1-9个方阵
{
count = 0; //寻找可下该数字的点的个数
flag = false;
for (i=0; i <9; i++)
for (j=0; j <9; j++)
{
if (datatemplate[i][j] == k)
{
if (tdata[i][j] == 0)
{
xToPut = i;
yToPut = j;
count++;
}
if (tdata[i][j] == numberToPut)
flag = true;
}
}
//如果可行，记下并在暂存数据中执行这一操作
if (!flag && count==1)
{
curstepx[curstepcount] = xToPut;
curstepy[curstepcount] = yToPut;
curstepnumber[curstepcount] = numberToPut;
strategy[curstepcount] = LOOKUPINMATRIX;
curstepcount++;
tdata[xToPut][yToPut] = numberToPut;
}
}
}
void LookupInRow(int tdata[][9], int numberToPut)
{
int row, j;
bool flag = false;
int count = 0;
int xToPut, yToPut;
for (row=0; row <9; row++)
{
count=0;
flag = false;
for (j=0; j <9; j++)
{
if (tdata[row][j] == 0)
{
xToPut = row;
yToPut = j;
count++;
}
if (tdata[row][j] == numberToPut)
flag = true;
}
//如果可行，记下这一操作, 并在暂存数据中执行该操作
if (!flag && count==1)
{
curstepx[curstepcount] = xToPut;
curstepy[curstepcount] = yToPut;
curstepnumber[curstepcount] = numberToPut;
strategy[curstepcount] = LOOKUPINROW;
curstepcount++;
tdata[xToPut][yToPut] = numberToPut;
}
}
}
void LookupInColumn(int tdata[][9], int numberToPut)
{
int col, i;
bool flag = false;
int count = 0;
int xToPut, yToPut;
for (col=0; col <9; col++)
{
count=0;
flag = false;
for (i=0; i <9; i++)
{
if (tdata[i][col] == 0)
{
xToPut = i;
yToPut = col;
count++;
}
if (tdata[i][col] == numberToPut)
flag = true;
}
//如果可行，记下这一操作, 并在暂存数据中执行该操作
if (!flag && count==1)
{
curstepx[curstepcount] = xToPut;
curstepy[curstepcount] = yToPut;
curstepnumber[curstepcount] = numberToPut;
strategy[curstepcount] = LOOKUPINCOLUMN;
curstepcount++;
tdata[xToPut][yToPut] = numberToPut;
}
}
}
bool TryOneStep()
{
int tdata[9][9] = {0};
int i=1, j, k, row, col;
bool success = false;
for (i=1; i <=9; i++) //依次标记出1-9的不可下点
{
memcpy(tdata, data, sizeof(int)*9*9); //复制到临时数据区
for (j=0; j <9; j++)
for(k=0; k <9; k++)
{
if (tdata[j][k] == i)
{
for(row=0; row <9; row++)
{
if (tdata[row][k] == 0)
tdata[row][k] = -1;
}
for(col=0; col <9; col++)
{
if (tdata[j][col] == 0)
tdata[j][col] = -1;
}
}
}
#ifdef OUTPUT_DEBUG
cout < < "屏蔽关于" < < i < < "的不可下点后:" < < endl;
Output(tdata);
#endif
curstepcount = 0;
LookupInMatrix(tdata, i);
LookupInRow(tdata, i);
LookupInColumn(tdata, i);
if (curstepcount != 0)
{
MakeStep();
return true;
}
}
return false;
}
void MakeStep()
{
int i=0;
for (; i <curstepcount; i++)
{
if (data[curstepx[i]][curstepy[i]] != 0)
{
cout < < "Error occured!\n" < < endl;
exit(-1);
}
data[curstepx[i]][curstepy[i]] = curstepnumber[i];
cout < < "在 " < < curstepx[i]+1 < < "行, " < < curstepy[i]+1 < < "列处下数字: " < < curstepnumber[i] < < ", \t";
switch(strategy[i])
{
case LOOKUPINMATRIX:
cout < < "来自于MATRIX策略" < < endl;
break;
case LOOKUPINROW:
cout < < "来自于ROW策略" < < endl;
break;
case LOOKUPINCOLUMN:
cout < < "来自于COLUMN策略" < < endl;
break;
default:
cout < < "未知策略" < < endl;
}
}
}
void Output(int tdata[][9])
{
int i, j;
for (i=0; i <9; i++)
{
for (j=0; j <9; j++)
{
cout < < tdata[i][j] < < "\t";
}
cout < < endl;
}
}
int main()
{
ifstream fin(szDataFile);
if (!fin)
{
cout < < "error in open files!\n";
return -1;
}
int i, j;
for (i=0; i <9; i++)
for (j=0; j <9; j++)
{
fin >> data[i][j];
}
#ifdef OUTPUT_DEBUG
i = 0;
j = 6;
while(i++ <j)TryOneStep();
cout < < endl < < j < < "次后, 数据如下图: " < < endl;
Output(data);
TryOneStep();
#else
while(TryOneStep());
#endif
cout < < "已完成搜索: " < < endl;
Output(data);
return 0;
}
