数独游戏 C++ 回溯法

C++ 数独游戏（回溯）

数独游戏的规则：

1 每个数字在每一行只能出现一次

2 每个数字在每一列只能出现一次

3 每个数字在每一区只能出现一次

下面的input.txt是一个例子的约束条件 第一列表示每一个数所在的行 第二列表示每一个数所在的列，第三个这个位置上的值。

Input.txt

1 1 7

1 4 1

1 8 8

1 9 3

2 1 4

2 3 2

2 5 7

2 6 3

3 4 4

3 5 5

3 8 2

3 9 7

4 3 7

4 7 3

4 8 1

4 9 2

5 2 4

5 3 3

5 4 8

6 3 5

6 5 9

7 2 2

7 3 1

7 5 8

8 2 3

8 4 2

8 6 1

8 7 8

9 7 2

9 8 6

9 9 1

一 回溯法

//============================================#include <iostream>#include <stdio.h>using namespace std; int State[9][9];///------------------------------void InitState(){       for (int i=0; i<9; i++)       {              for (int j=0; j<9;j++)              {                     State[i][j] = 0;              }       }} //------------------------------- void Load(){       freopen("input.txt","r",stdin); //输入从input.txt       int x, y, value;       int temp = 0;       while (scanf ("%d %d %d", &x, &y, &value) != EOF)       {              State[x-1][y-1] = value;       }} //---------------------------------//检查每一个小区内只能出现一次bool ChechZone(int x, int y, int i){       int xZone = 3 * (x / 3);   //找到每个小区的位置       int yZone = 3 * (y / 3);        int j = 0;       int k = 0;       bool flag = true;       for (j=xZone; j<xZone+3; j++)  //遍历小区的三行三列       {              for (k=yZone; k<yZone+3; k++)              {                     //if (x == j && y == k)                     //{                     //     continue;                     //}                      if ((x != j || y != k) && State[j][k] == i)                     {                            flag = false;                         goto A1;                     }              }       }A1:       return flag;} //--------------------------------//检查是否符合条件bool ChechAssign(int x, int y, int i){       bool flag = true;       for (int k=0; k<9; k++)       {              if (k != y && i == State[x][k] )               {                     flag = false;              }                                 if (k != x && i == State[k][y] )               {                     flag = false;              }              if (!ChechZone(x, y, i))              {                     flag = false;              }       }       return flag;}///------------------------------int Search (int depth){       if (depth >= 81)       {              //return Chech();              return 1;       }        int x, y;       x = depth / 9 ;       y = depth % 9 ;        //检查x y有没有被 赋值       if (0 != State[x][y])       {              return Search (depth + 1);       }       else  //尝试赋值       {              for (int i=1; i<=9; i++)              {                     //检查是否违反约束条件                     State[x][y] = i;                     if (ChechAssign(x, y, i))                     {                            if (Search(depth + 1))                            {                                   return 1;                            }                     }                     State[x][y] = 0;              }              return 0;       }} ///---------------------------------------void OutputState(){       for (int i=0; i<9; i++)       {              for (int j=0; j<9; j++)              {                     cout << State[i][j] << " ";                     if (0 == (j+1) % 3)                     {                            cout << " ";                     }              }                     if (0 == (i + 1) % 3)              {                          cout << endl;              }              cout << endl;       }       cout << endl;}   //-------------------------------------int main (){       cout << "=======初始化========"<< endl  <<  endl;       InitState();       //输入函数       Load();    OutputState();       cout << "=======结果为======="<< endl  <<  endl;    //搜索              if (Search(0))              {                            OutputState();}              else               {                     //输出提示信息                     cout << "搜索失败！！！"<< endl;              }              cout << "===================="<< endl  <<  endl;       return 0;}

二 优化后的回溯

就是先排序后再回溯 排序的依据是：先算出第一个空格的所在行各所在列对他的约束的个数。然后从大到小进行排序。

优化后的程序如下：

#include <iostream>#include <stdio.h>using namespace std; // ------------------------------------------------------------------------- int State[9][9];int StateSort[81][3];       //记录每个空元素的所在行列已有的数字个数 非空元素为0 void Print(){       for (int i=0; i<81; i++)       {              for (int j=0; j<3; j++)              {                     cout << StateSort[i][j] << " ";              }              cout << endl;       }} ///------------------------------void InitState(){       int i, j;       for (i=0; i<9; i++)    //初始化State       {              for (j=0; j<9;j++)              {                     State[i][j] = 0;              }       }        for (i=0; i<81; i++)  // 初始化StateSort       {               StateSort[i][0] = i / 9 + 1;              StateSort[i][1] = i % 9 + 1;              StateSort[i][2] = 0;       }//     Print();} //-------------------------------void Load(){       freopen("input.txt","r",stdin); //输入从input.txt       int x, y, value;       while (scanf ("%d %d %d", &x, &y, &value) != EOF)       {              State[x-1][y-1] = value;          }} //---------------------------------void Count()// 算出每一个空元素的所在行和列约束的个数{       int k;       for (int i=0; i<9; i++)       {              for (int j=0; j<9; j++)              {                     if (State[i][j] == 0)                     {                            int nCount = 0;                            for (k=0; k<9; k++)                            {                                   if ( 0 != State[i][k])                                   {                                          nCount++;                                   }                            }                            for (k=0; k<9; k++)                            {                                   if (0 != State[k][j])                                   {                                          nCount++;                                   }                            }                            StateSort[i*9+j][2] = nCount;                     }                            }       }} //---------------------------------------------void Sort() {       int pivotkey[3] ;       for (int i=1; i<=81;i++)       {              if (StateSort[i][2] > StateSort[i-1][2])              {                     pivotkey[2] = StateSort[i][2];                     pivotkey[1] = StateSort[i][1];                     pivotkey[0] = StateSort[i][0];                                 for (int j=i-1; (pivotkey[2]>StateSort[j][2]) && (j>=0); --j)                     {                            StateSort[j+1][2] = StateSort[j][2];                            StateSort[j+1][1] = StateSort[j][1];                            StateSort[j+1][0] = StateSort[j][0];                     }                     StateSort[j+1][2] = pivotkey[2];                     StateSort[j+1][1] = pivotkey[1];                     StateSort[j+1][0] = pivotkey[0];              }       }       //Print();} //---------------------------------//检查每一个小区内只能出现一次bool ChechZone(int x, int y, int i){       int xZone = 3 * (x / 3);   //找到每个小区的位置       int yZone = 3 * (y / 3);        int j = 0;       int k = 0;       bool flag = true;       for (j=xZone; j<xZone+3; j++)  //遍历小区的三行三列       {              for (k=yZone; k<yZone+3; k++)              {                     if ((x != j || y != k) && State[j][k] == i)                     {                            flag = false;                         goto A1;                     }              }       }A1:       return flag;} //--------------------------------//检查是否符合条件bool ChechAssign(int x, int y, int i){       bool flag = true;       for (int k=0; k<9; k++)       {              if (k != y && i == State[x][k] )               {                     flag = false;              }                                 if (k != x && i == State[k][y] )               {                     flag = false;              }              if (!ChechZone(x, y, i))              {                     flag = false;              }       }       return flag;}//-----------------------------------int DCount (){    int g_Count = 0;       for (int i=0; i<81; i++)       {              if (0 != StateSort[i][2])              {                     g_Count++;              }       }       return g_Count;}  ///------------------------------- int Search (int depth){       if (depth >= DCount())       {              return 1;       }        int x, y;       x = StateSort[depth][0] - 1;       y = StateSort[depth][1] - 1;        //检查x y有没有被 赋值       if (0 != State[x][y])       {              return Search (depth + 1);       }       else  //尝试赋值       {              for (int i=1; i<=9; i++)              {                     State[x][y] = i;                     //检查是否违反约束条件                     if (ChechAssign(x, y, i))                     {                            if (Search(depth + 1))                            {                                   return 1;                            }                     }                     State[x][y] = 0;              }              return 0;       }} ///---------------------------------------void OutputState(){       for (int i=0; i<9; i++)       {              for (int j=0; j<9; j++)              {                     cout << State[i][j] << " ";                     if (0 == (j+1) % 3)                     {                            cout << " ";                     }              }                     if (0 == (i + 1) % 3)              {                          cout << endl;              }              cout << endl;       }       cout << endl;} //-------------------------------------int main (){       cout << "=======初始化========"<< endl  <<  endl;       InitState();       //输入函数       Load();    OutputState();       //计算每个元素所在行列已有的数字个数 非空元素为0       Count();       //Print();       //cout <<"+++++++++"<<endl;       //排序    Sort();       //Print();        cout << "The Depth : " << DCount() << endl <<endl;       cout << "=======结果为======="<< endl  <<  endl;    //搜索              if (Search(0))              {                     //输出                     OutputState();              }              else               {                     //输出提示信息                     cout << "搜索失败！！！"<< endl;              }              cout << "===================="<< endl  <<  endl;              cout << DCount();       return 0;}// -------------------------------------------------------------------------// $Log: $

江西理工大学 Fangshenghui2010-5-1
原文链接: https://www.cnblogs.com/fangshenghui/archive/2010/05/01/1725691.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍