Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// nineGridGames.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MaxStep = 10000;
int AnswerIndex = 1;
struct Point
{
int Value;
int Step;
vector<int> 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<<char(allPoints[i][j].Value == 0 ? '*':allPoints[i][j].Value + '0')<<" ";
}
cout<<endl;
}
}
void PrintAllPoints(Point(*curAllPoints)[9])
{
cout<<"----------------------答案: "<<(AnswerIndex++)<<" --------------------------"<<endl;
for(int i = 0;i < 9;i++)
{
for(int j = 0;j < 9;j++)
{
cout<<char(curAllPoints[i][j].Value == 0 ? '*':curAllPoints[i][j].Value + '0')<<" ";
}
cout<<endl;
}
}
void RemoveValueOnList(vector<int>& 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**";
string str =
"*8***7*5*"
"*9*81****"
"*652*****"
"**46*****"
"**3***2**"
"*****87**"
"*****489*"
"****56*3*"
"*7*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<<"九宫格初始化值:"<<endl;
PrintAllPoints();
cout<<"开始搜索:"<<endl;
bfs(allPoints,0);
cout<<"搜索结束...按任意键退出"<<endl;
char c;
cin>>c;
return 0;
}
// ********************************************************************* //
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.