今天无意中看到新浪微博上一条关于九宫格游戏的一条消息。
英《每日邮报》报道,芬兰数学家因卡拉花费3个月设计出世界上迄今难度最大九宫格游戏,它只有一个答案。
于是自己写了C++的代码程序去实现寻找九宫格游戏的所有答案。
芬兰数学家提出的确实只搜到一个答案,具体看截图:
程序的实现思想是:广度搜索 + 排除法 去寻找九宫格中所有符合的答案。
具体的代码如下:
#include
#include
#include
using namespace std;
const int MaxStep = 10000;
int AnswerIndex = 1;
struct Point
{
int Value;
int Step;
vector
listMyValues;
};
struct PointStates
{
Point myPoints[9][9];
};
Point allPoints[9][9];
PointStates allPointStates[82];
void PrintAllPoints()
{
for(int i = 0;i < 9;i++)
{
for(int j = 0;j
< 9;j++)
{
cout<
== 0 ? '*':allPoints[i][j].Value +
'0')<
}
cout<
}
}
void PrintAllPoints(Point(*curAllPoints)[9])
{
cout<
"<
--------------------------"<
for(int i = 0;i < 9;i++)
{
for(int j = 0;j
< 9;j++)
{
cout<
== 0 ? '*':curAllPoints[i][j].Value +
'0')<
}
cout<
}
}
void
RemoveValueOnList(vector&
v, int value)
{
for(int i = v.size() -1;i >=
0;i--)
{
if(v[i] == value)
{
v.erase(v.begin()
+ i);
}
}
}
void ChangeStates(Point(*curAllPoints)[9], int x, int y, int
value)
{
int i,j;
for(i = x / 3 * 3;i < x / 3 * 3 +
3;i++)
{
for(j = y / 3 * 3;j
< y / 3 * 3 + 3;j++)
{
if(curAllPoints[i][j].Step
== MaxStep)
{
RemoveValueOnList(curAllPoints[i][j].listMyValues,value);
}
}
}
for(i = 0;i < 9;i++)
{
if(curAllPoints[x][i].Step ==
MaxStep)
{
RemoveValueOnList(curAllPoints[x][i].listMyValues,value);
}
if(curAllPoints[i][y].Step ==
MaxStep)
{
RemoveValueOnList(curAllPoints[i][y].listMyValues,value);
}
}
}
void InitAllPoints()
{
string str = "8********"
"**36*****"
"*7**9*2**"
"*5***7***"
"****457**"
"***1***3*"
"**1****68"
"**85***1*"
"*9****4**";
//测试用例
int i,j;
for(i = 0;i < 9;i++)
{
for(j = 0;j <
9;j++)
{
char ch =
str[i*9 + j];
int v =
(ch=='*' ? 0 : ch-'0');
allPoints[i][j].Step
= (v == 0 ? MaxStep : 0);
allPoints[i][j].Value
= v;
if(v
==0)
{
for(int
m = 1;m < 10;m++)
{
allPoints[i][j].listMyValues.push_back(m);
}
}
}
}
for(i = 0;i < 9;i++)
{
for(j = 0;j <
9;j++)
{
if(allPoints[i][j].Step
!= MaxStep)
{
ChangeStates(allPoints,i,j,allPoints[i][j].Value);
}
}
}
}
void Copy(Point(*sAllPoints)[9],Point(*tAllPoints)[9])
{
for(int i = 0;i < 9;i++)
{
for(int j = 0;j
< 9;j++)
{
tAllPoints[i][j].Step
= sAllPoints[i][j].Step;
tAllPoints[i][j].Value
= sAllPoints[i][j].Value;
tAllPoints[i][j].listMyValues.clear();
for(int k =
0;k <
sAllPoints[i][j].listMyValues.size();k++)
{
tAllPoints[i][j].listMyValues.push_back(sAllPoints[i][j].listMyValues[k]);
}
}
}
}
//state: 0-> 继续 1->错误结束
2->正确结束
int GetCurrentState(Point(*curAllPoints)[9])
{
int state = 0,i,j;
bool isAllFixed = true;
for(i = 0;i < 9;i++)
{
for(j = 0;j <
9;j++)
{
if(curAllPoints[i][j].Step
== MaxStep)
{
isAllFixed
= false;
if(curAllPoints[i][j].listMyValues.size()
== 0)
{
state
= 1;
return
state;
}
}
}
}
state = isAllFixed ? 2 : state;
return state;
}
void bfs(Point(*curAllPoints)[9], int curStep)
{
int i,j,x,y;
int minCount = 10;
for(i = 0;i < 9;i++)
{
for(j = 0;j <
9;j++)
{
if((curAllPoints[i][j].Step
== MaxStep) &&
(curAllPoints[i][j].listMyValues.size() <
minCount))
{
minCount
= curAllPoints[i][j].listMyValues.size();
x
= i;y = j;
}
}
}
curAllPoints[x][y].Step = curStep + 1;
for(int m = 0; m<
curAllPoints[x][y].listMyValues.size();m++)
{
Copy(curAllPoints,allPointStates[curStep
+ 1].myPoints);
allPointStates[curStep +
1].myPoints[x][y].Value = curAllPoints[x][y].listMyValues[m];
ChangeStates(allPointStates[curStep
+ 1].myPoints,x,y,allPointStates[curStep +
1].myPoints[x][y].Value);
int state =
GetCurrentState(allPointStates[curStep + 1].myPoints);
switch(state)
{
case 0:
bfs(allPointStates[curStep
+ 1].myPoints,curStep + 1);
break;
case 2:
PrintAllPoints(allPointStates[curStep
+ 1].myPoints);
break;
}
}
}
int main()
{
InitAllPoints();
cout<
PrintAllPoints();
cout<
bfs(allPoints,0);
cout<
char c;
cin>>c;
return 0;
}