现在的位置: 首页 > 综合 > 正文

回溯法 回溯全排列

2017年09月30日 ⁄ 综合 ⁄ 共 16388字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

回溯全排列

2013-01-20 00:18 271人阅读 评论(0) 收藏 举报

回溯的实质是在问题的解空间进行深度优先搜索。DFS是个图的算法，但是回溯算法中的图在哪里呢？我们把解空间中的一个解状态当成一个节点，由于解空间非常庞大，所以这个图也就大到无法想象了。

举个例子吧，比如全排列问题，对于n个元素进行全排列，一共有n!种可能，比如n=9时，一共有9! = 362880种排列。初始化，我们什么都没有，定义如下状态

[cpp] view
plaincopy

  1. #define PT_SIZE 9  
  2. class PTState  
  3. {  
  4.     int m_solution[PT_SIZE];  
  5.     int m_arranged;  
  6. };  

其中m_arranged表示已经在m_solution中排列的数字，刚开始时啥都没做，当然是m_arranged为0啦，而m_solution这个数组是用来放要排列的数字的，比如

123456789对应于m_solution[i] = i + 1

那么接下来要做啥呢？当然是开始排第一个数了，也就是要填m_solution[0]啦，这时你有多少种选择呢？嗯，当然是1, 2, 3, 4, 5 ,6, 7,8,9种，这还要说吗？那么先尝试谁呢？

从小到小依次填好了。

下面这个图是n=3时的解空间搜索图，其中白色的节点是初始节点，一个数都没填，第一行全是问号，第二行有个标记，表示还没有排列一个数。当第一位选1的时，节点变成了紫色，此时m_arranged = 1, 还剩两个数没有填。这时填第二个数时，发现只能填2或者3，当填上2后，又到了下面一个蓝色的节点，该节点的状态中m_arranged = 2，再扩展下去，第三位只能填3，于是到了最下面的黄色节点。

此时，再想扩展黄色节点时，发现m_arranged已经是3了，这时表明这是一个最终的节点，无法再扩展了，于是得到了一个排列。那么其他排列如何得到呢？回到黄色节点上面的蓝色节点，我们发现第三位除了3再也不能填其他数了，没法继续扩展，没办法，再回到上面的紫色节点，这时发现，紫色节点中的第二位还能填3，于是可以顺利扩展到下面的第二个蓝色节点。这个过程便是回溯和扩展节点的主要过程。

在编程实现时，由于我们无法存储所有的状态节点，只能保持一个当前状态，然后通过扩展到下一个节点，来修改当前节点的状态，但是当扩展完一个节点时，必须得恢复到原来节点的状态，才能进行下一个扩展。这个逻辑写成代码便是如下形式：

[cpp] view
plaincopy

  1. Solve (State & state)  
  2. for action in A  
  3.     if state.CanMove(action)  
  4.         state.Forward(action);  
  5.         Solve(state)  
  6.         state.Recover(action);  
  7.           

在我们这个全排列的例子中，具体代码如下

[cpp] view
plaincopy

  1. void Solve(PTState& state)  
  2. {  
  3.     if (state.IsFinal())  
  4.     {  
  5.         gCount ++;  
  6.         return;  
  7.     }  
  8.       
  9.     for (int i = 1; i <= PT_SIZE; i++)  
  10.     {  
  11.         if (state.CanPlace(i))  
  12.         {  
  13.             state.Place(i);  
  14.             Solve(state);  
  15.             state.Remove(i);  
  16.         }  
  17.     }  
  18. }  

其中的state便是上面图中的节点，其中记录了当前已经放置的数的个数，以及具体数的排列。其中，当扩展到黄色节点，也即发现再也无法扩展时，直接返回。这种节点称为终节点，终结点的判断非常简单，只要查一下m_arranged是不是为PT_SIZE(9)就可以了。当到达终节点时，通常是找到了一个解，这里是找到了有一个新的排列，我们只记录一下个数。

[cpp] view
plaincopy

  1. bool IsFinal()  
  2. {  
  3.     return m_arranged == PT_SIZE;  
  4. }  

调用时，先初始化状态，然后调用Solve(state)即可，其中state的初始化也非常简单，将m_arranged设为0即可。

然后我们具体实现PTState的几个函数，CanPlace, Place,和Remove, 先来看CanPlace(int i)，此时当前状态下已排了m_arranged个数，那么当前要排的是第几个数呢？嗯，是第m_arranged个数(从0开始计数)，也就是我们要填m_solution[m_arranged], 但是到底m_solution[m_arranged]能不能填 i 呢？根据排列的定义，前面填过的数不能再填了？那我们怎么知道哪些数填过了呢？

哪些数填过了，这个信息其实也可以放在PTState中，作为状态的一部分，对于Solve函数来说完全不可见，在全排列这个例子中，我们可以用一个数组m_used来记录哪些数是否被排过，当i已经被排列过时，m_used[i] = 1，否则为0.

[cpp] view
plaincopy

  1. class PTState  
  2. {  
  3.   
  4.     int m_solution[PT_SIZE];  
  5.     int m_arranged;  
  6.       
  7.     int m_used[PT_SIZE + 1];  
  8. };  

初始状态时，m_used为全零。 当查询某个数是否可以填时，CanPlace的实现就相当容易了

[html] view
plaincopy

  1. bool CanPlace(int i)  
  2. {  
  3.     if (m_used[i] == 0)  
  4.     {  
  5.         return true;  
  6.     }  
  7.     return false;  
  8. }  

但是我们还得维护状态中的这些信息，这个可以在Place和Remove中悄悄地完成，这两个函数都比较简单：

[cpp] view
plaincopy

  1. void Place(int i)  
  2. {  
  3.     m_used[i] = 1;  
  4.     m_solution[m_arranged++] = i;  
  5.       
  6. }  
  7. void Remove(int i)  
  8. {  
  9.     m_arranged --;  
  10.     m_used[i] = 0;  
  11. }  

其中，Place修改了当前state的状态，等于是在搜索图中扩展到了下一个状态，而Remove正好相反，是刚扩展的节点完全搜索了之后，回到上一步的状态，这时需要根据扩展时施行的动作，进行反动作，在这里就是把排的数再扔掉。

完整模板和全排列的代码如下

[cpp] view
plaincopy

  1. int gCount = 0;  
  2. void Solve(PTState& state)  
  3. {  
  4.     if (state.IsFinal())  
  5.     {  
  6.         //state.PrintSolution();  
  7.         gCount ++;  
  8.         return;  
  9.     }  
  10.       
  11.     for (int i = 1; i <= PT_SIZE; i++)  
  12.     {  
  13.         if (state.CanPlace(i))  
  14.         {  
  15.             state.Place(i);  
  16.             Solve(state);  
  17.             state.Remove(i);  
  18.         }  
  19.     }  
  20. }  

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include "..\Utility\GFClock.h"  
  3.   
  4. // 1-9  
  5. const int PT_SIZE = 10;  
  6.   
  7. class PTState  
  8. {  
  9. public:  
  10.     PTState()  
  11.     {  
  12.         m_arranged = 0;  
  13.         memset(m_used, 0, sizeof(int) * (PT_SIZE + 1));  
  14.     }  
  15.   
  16.     bool IsFinal()  
  17.     {  
  18.         return m_arranged == PT_SIZE;  
  19.     }  
  20.     void PrintSolution()  
  21.     {  
  22.         for (int i = 0; i < PT_SIZE ; i++)  
  23.         {  
  24.             cout << m_solution[i];  
  25.         }  
  26.         cout << endl;  
  27.     }  
  28.   
  29.     bool CanPlace(int i)  
  30.     {  
  31.         if (m_used[i] == 0)  
  32.         {  
  33.             return true;  
  34.         }  
  35.         return false;  
  36.     }  
  37.   
  38.     void Place(int i)  
  39.     {  
  40.         m_used[i] = 1;  
  41.         m_solution[m_arranged++] = i;  
  42.           
  43.     }  
  44.     void Remove(int i)  
  45.     {  
  46.         m_arranged --;  
  47.         m_used[i] = 0;  
  48.     }  
  49.   
  50.   
  51.     int m_solution[PT_SIZE];  
  52.     int m_arranged;  
  53.       
  54.     int m_used[PT_SIZE + 1];  
  55. };  
  56.   
  57. int gCount = 0;  
  58. void Solve(PTState& state)  
  59. {  
  60.     if (state.IsFinal())  
  61.     {  
  62.         //state.PrintSolution();  
  63.         gCount ++;  
  64.         return;  
  65.     }  
  66.       
  67.     for (int i = 1; i <= PT_SIZE; i++)  
  68.     {  
  69.         if (state.CanPlace(i))  
  70.         {  
  71.             state.Place(i);  
  72.             Solve(state);  
  73.             state.Remove(i);  
  74.         }  
  75.     }  
  76. }  
  77. int _tmain(int argc, _TCHAR* argv[])  
  78. {  
  79.     GFClock clock;  
  80.     PTState state;  
  81.     Solve(state);  
  82.     cout << gCount << endl;  
  83.     cout << clock.Elapsed() << endl;  
  84. }  

前面有个文章介绍了回溯算法的一般流程和模板，并套用来解决了全排列问题，其实这个模板可以套用来解决很多问题，比如本文要介绍的数独。

数独(sudoku)想来大家都不会陌生，下面是一个号称非常难的数独，我们看看用回溯算法解决它需要多少时间。

和全排列一样，使用回溯时首先要设计一个状态类，对于数独而言，这个状态就是这个9×9的格子盘，另外，对于每个格子，我们也抽象出来一个Grid类，具体做啥用，下面会提到。

[cpp] view
plaincopy

  1. class Grid  
  2. {  
  3. public:  
  4.     Grid(){}  
  5.     int val; //当为0时，grid为空格，非0时，val为已填的数字  
  6.     int nRemainCount; // 还有几个数可以填  
  7.   
  8.     //记录该grid不能再填的数字  
  9.     map<int, int> valMap;  
  10.   
  11.     bool Conflict(int val)  
  12.     void IncCount(int _val)  
  13.     void DecCount(int _val);  
  14. };  


[cpp] view
plaincopy

  1. class SUDOKUState  
  2. {  
  3. public:  
  4.     SUDOKUState(int a[TEMPLATE_SIZE][TEMPLATE_SIZE]);  
  5.     bool CanPlace(int val);  
  6.     void RemoveNumber(int val)  
  7.     void PlaceNumber(int val);  
  8.     bool IsFinal();  
  9.   
  10.     Grid m_grids[TEMPLATE_SIZE][TEMPLATE_SIZE];  
  11.     std::stack<pair<int,int> > posTrace;     //记录放置的位置记录  
  12.     int m_curX;//当前要放置数字的空格位置  
  13.         int m_curY;  
  14.         int m_nRemained; //还有多少个要放置  
  15.         bool IsDead();  
  16.         void DecideNextPlace()};  

回溯模板还是和全排列差不多

[cpp] view
plaincopy

  1. void Solve(SUDOKUState& state)  
  2. {  
  3.     if (bSolved)  
  4.     {  
  5.         return;  
  6.     }  
  7.     //cout << gCount++ << endl;  
  8.     if (state.IsFinal())  
  9.     {  
  10.         state.PrintBoard();  
  11.         bSolved = true;  
  12.         return;  
  13.     }  
  14.     if (state.IsDead())  
  15.     {  
  16.         return;  
  17.     }  
  18.   
  19.     for (int i = 1; i < 10; i++)  
  20.     {  
  21.         if (!state.CanPlace(i))  
  22.         {  
  23.             continue;  
  24.         }  
  25.         state.PlaceNumber(i);  
  26.         Solve(state);  
  27.         state.RemoveNumber(i);  
  28.     }  
  29. }  


我们先来看一下数独的状态如何扩展。

初始状态时，已经填了17个格子，那么还有m_nRemained = 81 - 17 = 64个格子没填，m_nRemained这个变量为0时说明状态节点已经是终节点，也即找到了一个数独的解，这里我们不需要把所有解都输出来，所以到找到一个解时，可以设定一个全局参数bSolved为true, 其他节点再扩展时直接返回。

扩展节点时，我们犯愁了，数独未填的格子中我们究竟选哪个填呢？嗯，最简单的做法是随机选一个空格，然后看看这个空格可以填哪些数，比如第二行第七列的空格就只能填4或者9，只能扩展两个节点，而第一行第一列的空格可以填3,4,5,6,8,9六个数。

于是问题就来了，如果我们随机选择填的空格，倘若该空格的候选数字比较多，那么待扩展的节点也会比较多，搜索空间会大很多。这种情况下能不能找到解呢？答案是可以的，但是也许要跑好几天，我一开始试了一下随机选择要填的空格，结果递归调用了1000多万次都没见半点要结束的样子。

这时需要引入一个启发式的方法，即下一步要选择哪个空格填数，按照数独玩家的经验，当然是填候选填数最少的那个空格，比如第二行第7列那个，只有2个备选数字4和7, 状态中的函数DecideNextPlace即是这一贪心方法的实现：

[cpp] view
plaincopy

  1. void DecideNextPlace()  
  2. {  
  3.     if (m_nRemained == 0)  
  4.     {  
  5.         return;  
  6.     }  
  7.     int minv = 10000;  
  8.     for (int r = 0; r < TEMPLATE_SIZE; r++)  
  9.     {  
  10.         for (int c = 0; c < TEMPLATE_SIZE; c++)  
  11.         {  
  12.             if (m_grids[r][c].val == 0 && m_grids[r][c].nRemainCount < minv)  
  13.             {  
  14.                 minv = m_grids[r][c].nRemainCount;  
  15.                 m_curX = c;   
  16.                 m_curY = r;  
  17.             }  
  18.         }  
  19.     }  
  20.     //有一个空格子已经没有数可以选择了  
  21.     if (minv == 0)  
  22.     {  
  23.         m_curX = -1;  
  24.         m_curY = -1;  
  25.     }  
  26. }  


这个方法比较简单，遍历所有空格，看看哪个空格还能用的数字最少，就选哪个空格，m_curX和m_curY分别记录了选中空格的行列，接下来放数字就放在这个格子里头了。

为了快速地获取每个格子的备选数字，我在抽象出来的Grid类中维护了一个map, 用来统计该格子g的同行同列以及同section(3×3的那个子区域)的每个数字的出现次数，显然

如果某个数字的出现次数大于1，那么这个数字就不能在g中出现了，反之可以出现。于是CanPlace可以调用当前要放的空格g的Conflict方法：

[cpp] view
plaincopy

  1. bool Conflict(int val)  
  2. {  
  3.     return valMap.find(val) != valMap.end();  
  4. }  

此时一切都很顺利，但麻烦来了，每个格子的map的维护可别忘了，当空格g中填入数字a时，不仅g的map需要更改，它的同行同列同sec的所有格子也受影响，于是SUDUKUState的PlaceNumber实现比较麻烦，如下：

[cpp] view
plaincopy

  1. void PlaceNumber(int val)  
  2. {  
  3.     m_grids[m_curY][m_curX].val = val;  
  4.     m_grids[m_curY][m_curX].IncCount(val);  
  5.     for (int r = 0;r < TEMPLATE_SIZE;r++)  
  6.     {  
  7.                 if (r != m_curY)  
  8.         {  
  9.             m_grids[r][m_curX].IncCount(val);  
  10.         }  
  11.     }  
  12.     for (int c = 0 ; c < TEMPLATE_SIZE; c++)  
  13.     {  
  14.         if (c != m_curX)  
  15.         {  
  16.             m_grids[m_curY][c].IncCount(val);  
  17.         }  
  18.     }  
  19.   
  20.     for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++)  
  21.     {  
  22.         for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++)  
  23.         {  
  24.             if (r == m_curY || c == m_curX)  
  25.             {  
  26.                 continue;  
  27.             }  
  28.             m_grids[r][c].IncCount(val);  
  29.         }  
  30.     }  
  31.     m_nRemained --;  
  32.     posTrace.push(make_pair<int,int>(m_curX, m_curY));  
  33.     DecideNextPlace();  
  34. }  


这里受影响的格子都调用自身的IncCount方法，表示val这个数的出现又加1了。

[cpp] view
plaincopy

  1. void IncCount(int _val)  
  2. {  
  3.     valMap[_val]++;  
  4.     nRemainCount = 9 - valMap.size();  
  5. }  

同样，当节点扩展完后，需要恢复原来的状态，此时需要执行反动作，即把之前放的空格中的数字拿掉，此时有个问题出现了，之气的空格是哪个呢？由于每次PlaceNumber后，都会调用DecideNextPlace,所以m_curX和m_curY已经不再是原来的选中空格位置，为了解决这个问题，我在状态类中加了一个栈posTrace,用来维护已经放过了的位置信息，那么栈顶即为上一步放数的格子。有了此信息后，我们只要再调用有关格子的DecCount方法，并将posTrace出栈，更新当前空格位置，就可以恢复到原来的状态，因此RemoveNumber方法与PlaceNumber完全是反着来：

[cpp] view
plaincopy

  1. void RemoveNumber(int val)  
  2. {  
  3.     assert(!posTrace.empty());  
  4.     pair<int, int> prePos = posTrace.top();  
  5.   
  6.     m_curX = prePos.first;  
  7.     m_curY = prePos.second;  
  8.     m_grids[m_curY][m_curX].val = 0;  
  9.     m_grids[m_curY][m_curX].DecCount(val);  
  10.     for (int r = 0;r < TEMPLATE_SIZE;r++)  
  11.     {  
  12.         if (r != m_curY)  
  13.         {  
  14.             m_grids[r][m_curX].DecCount(val);  
  15.         }  
  16.     }  
  17.     for (int c = 0 ; c < TEMPLATE_SIZE; c++)  
  18.     {  
  19.         if (c != m_curX)  
  20.         {  
  21.             m_grids[m_curY][c].DecCount(val);  
  22.         }  
  23.     }  
  24.   
  25.     for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++)  
  26.     {  
  27.         for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++)  
  28.         {  
  29.             if (r == m_curY || c == m_curX)  
  30.             {  
  31.                 continue;  
  32.             }  
  33.             m_grids[r][c].DecCount(val);  
  34.         }  
  35.     }  
  36.     posTrace.pop();  
  37.     m_nRemained ++;  
  38. }  



最后需要说明的是，SUDOKUState中有个IsDead方法

[cpp] view
plaincopy

  1. bool IsDead()  
  2. {  
  3.     return m_curY == -1 && m_curY == -1;  
  4. }  

当我们在调用DecideNextStep时，如果发现已经没有空格可以填数了，此时我们对m_curX和m_curY设了个特殊值，以此来表示当前节点是一个死节点，可以提前返回了，这其实是剪枝技术的应用。

这个程序非常快，一共调用了10374次Solve, vs2005 release下只花了52ms

完整代码如下：

[cpp] view
plaincopy

  1. //#include "stdafx.h"  
  2. #include <map>  
  3. #include <stack>  
  4. #include <cassert>  
  5. //#include "..\Utility\GFClock.h"  
  6. using namespace std;  
  7. const int TEMPLATE_SIZE = 9;  
  8. const int SUB_SIZE = 3;  
  9. bool bSolved = false;  
  10. int gCount = 0;  
  11. class Grid  
  12. {  
  13. public:  
  14.     Grid(){}  
  15.     int val;  
  16.     int nRemainCount; // 还有几个数可以填  
  17.   
  18.     //记录该grid不能再填的数字  
  19.     map<int, int> valMap;  
  20.     bool Conflict(int val)  
  21.     {  
  22.         return valMap.find(val) != valMap.end();  
  23.     }  
  24.   
  25.     //自身或其他地方填了数字影响了当前格子可以选择的数字集合  
  26.     void IncCount(int _val)  
  27.     {  
  28.         valMap[_val]++;  
  29.         nRemainCount = 9 - valMap.size();  
  30.     }  
  31.     void DecCount(int _val)  
  32.     {  
  33.         valMap[_val]--;  
  34.         if (valMap[_val] == 0)  
  35.         {  
  36.             valMap.erase(_val);  
  37.         }  
  38.         nRemainCount = 9 - valMap.size();  
  39.     }  
  40. };  
  41.   
  42.   
  43. int board[TEMPLATE_SIZE][TEMPLATE_SIZE] = {  
  44.     {0, 0, 0, 0, 0, 0, 0, 1, 2},  
  45.     {0, 0, 0, 0, 3, 5, 0, 0, 0},  
  46.     {0, 0, 0, 6, 0, 0, 0, 7, 0},  
  47.     {7, 0, 0, 0, 0, 0, 3, 0, 0},  
  48.     {0, 0, 0, 4, 0, 0, 8, 0, 0},  
  49.     {1, 0, 0, 0, 0, 0, 0, 0, 0},  
  50.     {0, 0, 0, 1, 2, 0, 0, 0, 0},  
  51.     {0, 8, 0, 0, 0, 0, 0, 4, 0},  
  52.     {0, 5, 0, 0, 0, 0, 6, 0, 0}  
  53. };  
  54. class SUDOKUState  
  55. {  
  56. public:  
  57.   
  58.     bool CanPlace(int val)  
  59.     {  
  60.         return !m_grids[m_curY][m_curX].Conflict(val);  
  61.     }  
  62.     bool IsFinal()  
  63.     {  
  64.         return m_nRemained == 0;  
  65.     }  
  66.   
  67.     bool IsDead()  
  68.     {  
  69.         return m_curY == -1 && m_curY == -1;  
  70.     }  
  71.     //将第y行，第x列的数字挪去  
  72.     void RemoveNumber(int val)  
  73.     {  
  74.         assert(!posTrace.empty());  
  75.         pair<int, int> prePos = posTrace.top();  
  76.   
  77.         m_curX = prePos.first;  
  78.         m_curY = prePos.second;  
  79.         m_grids[m_curY][m_curX].val = 0;  
  80.         m_grids[m_curY][m_curX].DecCount(val);  
  81.         for (int r = 0;r < TEMPLATE_SIZE;r++)  
  82.         {  
  83.             if (r != m_curY)  
  84.             {  
  85.                 m_grids[r][m_curX].DecCount(val);  
  86.             }  
  87.         }  
  88.         for (int c = 0 ; c < TEMPLATE_SIZE; c++)  
  89.         {  
  90.             if (c != m_curX)  
  91.             {  
  92.                 m_grids[m_curY][c].DecCount(val);  
  93.             }  
  94.         }  
  95.   
  96.         for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++)  
  97.         {  
  98.             for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++)  
  99.             {  
  100.                 if (r == m_curY || c == m_curX)  
  101.                 {  
  102.                     continue;  
  103.                 }  
  104.                 m_grids[r][c].DecCount(val);  
  105.             }  
  106.         }  
  107.         posTrace.pop();  
  108.         m_nRemained ++;  
  109.     }  
  110.     void PlaceNumber(int val)  
  111.     {  
  112.         m_grids[m_curY][m_curX].val = val;  
  113.         m_grids[m_curY][m_curX].IncCount(val);  
  114.         for (int r = 0;r < TEMPLATE_SIZE;r++)  
  115.         {  
  116.             if (r != m_curY)  
  117.             {  
  118.                 m_grids[r][m_curX].IncCount(val);  
  119.             }  
  120.         }  
  121.         for (int c = 0 ; c < TEMPLATE_SIZE; c++)  
  122.         {  
  123.             if (c != m_curX)  
  124.             {  
  125.                 m_grids[m_curY][c].IncCount(val);  
  126.             }  
  127.         }  
  128.   
  129.         for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++)  
  130.         {  
  131.             for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++)  
  132.             {  
  133.                 if (r == m_curY || c == m_curX)  
  134.                 {  
  135.                     continue;  
  136.                 }  
  137.                 m_grids[r][c].IncCount(val);  
  138.             }  
  139.         }  
  140.         m_nRemained --;  
  141.         posTrace.push(make_pair<int,int>(m_curX, m_curY));  
  142.         DecideNextPlace();  
  143.     }  
  144.   
  145.     SUDOKUState(int a[TEMPLATE_SIZE][TEMPLATE_SIZE])  
  146.     {  
  147.         m_nRemained = TEMPLATE_SIZE * TEMPLATE_SIZE;  
  148.         for (int i = 0; i <TEMPLATE_SIZE;i++)  
  149.         {  
  150.             for (int j = 0; j< TEMPLATE_SIZE;j++)  
  151.             {  
  152.                 m_grids[i][j].nRemainCount = TEMPLATE_SIZE;  
  153.                 m_grids[i][j].val = a[i][j];  
  154.                 if (a[i][j] != 0)  
  155.                 {  
  156.                     //在第i行第j列放了数字a[i][j]  
  157.                     m_curX = j;  
  158.                     m_curY = i;  
  159.                     PlaceNumber(a[i][j]);  
  160.                 }  
  161.             }  
  162.         }  
  163.         DecideNextPlace();  
  164.     }  
  165.     //计算下一步放数字的格子，贪心  
  166.     void DecideNextPlace()  
  167.     {  
  168.         if (m_nRemained == 0)  
  169.         {  
  170.             return;  
  171.         }  
  172.         int minv = 10000;  
  173.         for (int r = 0; r < TEMPLATE_SIZE; r++)  
  174.         {  
  175.             for (int c = 0; c < TEMPLATE_SIZE; c++)  
  176.             {  
  177.                 if (m_grids[r][c].val == 0 && m_grids[r][c].nRemainCount < minv)  
  178.                 {  
  179.                     minv = m_grids[r][c].nRemainCount;  
  180.                     m_curX = c;   
  181.                     m_curY = r;  
  182.                 }  
  183.             }  
  184.         }  
  185.   
  186.         //有一个空格子已经没有数可以选择了  
  187.         if (minv == 0)  
  188.         {  
  189.             m_curX = -1;  
  190.             m_curY = -1;  
  191.         }  
  192.     }  
  193.   
  194.     void PrintBoard()  
  195.     {  
  196.         for (int i = 0; i <TEMPLATE_SIZE;i++)  
  197.         {  
  198.             for (int j = 0; j< TEMPLATE_SIZE;j++)  
  199.             {  
  200.                 cout << m_grids[i][j].val << " ";  
  201.             }  
  202.             cout << endl;  
  203.         }  
  204.     }  
  205.       
  206.     Grid m_grids[TEMPLATE_SIZE][TEMPLATE_SIZE];  
  207.     std::stack<pair<int,int> > posTrace;     //记录放置的位置记录  
  208.     int m_nRemained;    //还有多少个要放置  
  209.       
  210.     //当前需要放置的位置  
  211.     int m_curX;  
  212.     int m_curY;   
  213. };  
  214.   
  215. void Solve(SUDOKUState& state)  
  216. {  
  217.     if (bSolved)  
  218.     {  
  219.         return;  
  220.     }  
  221.     //cout << gCount++ << endl;  
  222.     gCount++;  
  223.     if (state.IsFinal())  
  224.     {  
  225.         state.PrintBoard();  
  226.         bSolved = true;  
  227.         return;  
  228.     }  
  229.     if (state.IsDead())  
  230.     {  
  231.         return;  
  232.     }  
  233.   
  234.     for (int i = 1; i < 10; i++)  
  235.     {  
  236.         if (!state.CanPlace(i))  
  237.         {  
  238.             continue;  
  239.         }  
  240.         state.PlaceNumber(i);  
  241.         Solve(state);  
  242.         state.RemoveNumber(i);  
  243.     }  
  244. }  
  245. int _tmain(int argc, _TCHAR* argv[])  
  246. {  
  247.     SUDOKUState state(board);     
  248.     state.PrintBoard();  
  249.     cout << endl;  
  250.     //GFClock gfClock;  
  251.     Solve(state);  
  252.     //cout << gfClock.Elapsed() << " ms" << endl;  
  253.     cout << gCount << " times called" << endl;  
  254.     return 0;  
  255. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞