九宫格游戏c语言代码 C++代码实现寻找九宫格游戏所有答案

今天无意中看到新浪微博上一条关于九宫格游戏的一条消息。

英《每日邮报》报道，芬兰数学家因卡拉花费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;

}