cpp_code_block

// 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;
}



// *********************************************************************  //