回溯数独
数独(sudoku)想来大家都不会陌生，下面是一个号称非常难的数独，我们看看用回溯算法解决它需要多少时间。
和全排列一样，使用回溯时首先要设计一个状态类，对于数独而言，这个状态就是这个9×9的格子盘，另外，对于每个格子，我们也抽象出来一个Grid类，具体做啥用，下面会提到。
初始状态时，已经填了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即是这一贪心方法的实现：
完整代码如下：//#include "stdafx.h"#include <map>#include <stack>#include <cassert>//#include "..\Utility\GFClock.h"using namespace std;const int TEMPLATE_SIZE = 9;const int SUB_SIZE = 3;bool bSolved = false;int gCount = 0;class Grid{public:Grid(){}int val;int nRemainCount; // 还有几个数可以填//记录该grid不能再填的数字map<int, int> valMap;bool Conflict(int val){return valMap.find(val) != valMap.end();}//自身或其他地方填了数字影响了当前格子可以选择的数字集合void IncCount(int _val){valMap[_val]++;nRemainCount = 9 - valMap.size();}void DecCount(int _val){valMap[_val]--;if (valMap[_val] == 0){valMap.erase(_val);}nRemainCount = 9 - valMap.size();}};int board[TEMPLATE_SIZE][TEMPLATE_SIZE] = {{0, 0, 0, 0, 0, 0, 0, 1, 2},{0, 0, 0, 0, 3, 5, 0, 0, 0},{0, 0, 0, 6, 0, 0, 0, 7, 0},{7, 0, 0, 0, 0, 0, 3, 0, 0},{0, 0, 0, 4, 0, 0, 8, 0, 0},{1, 0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 2, 0, 0, 0, 0},{0, 8, 0, 0, 0, 0, 0, 4, 0},{0, 5, 0, 0, 0, 0, 6, 0, 0}};class SUDOKUState{public:bool CanPlace(int val){return !m_grids[m_curY][m_curX].Conflict(val);}bool IsFinal(){return m_nRemained == 0;}bool IsDead(){return m_curY == -1 && m_curY == -1;}//将第y行，第x列的数字挪去void RemoveNumber(int val){assert(!posTrace.empty());pair<int, int> prePos = posTrace.top();m_curX = prePos.first;m_curY = prePos.second;m_grids[m_curY][m_curX].val = 0;m_grids[m_curY][m_curX].DecCount(val);for (int r = 0;r < TEMPLATE_SIZE;r++){if (r != m_curY){m_grids[r][m_curX].DecCount(val);}}for (int c = 0 ; c < TEMPLATE_SIZE; c++){if (c != m_curX){m_grids[m_curY][c].DecCount(val);}}for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++){for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++){if (r == m_curY || c == m_curX){continue;}m_grids[r][c].DecCount(val);}}posTrace.pop();m_nRemained ++;}void PlaceNumber(int val){m_grids[m_curY][m_curX].val = val;m_grids[m_curY][m_curX].IncCount(val);for (int r = 0;r < TEMPLATE_SIZE;r++){if (r != m_curY){m_grids[r][m_curX].IncCount(val);}}for (int c = 0 ; c < TEMPLATE_SIZE; c++){if (c != m_curX){m_grids[m_curY][c].IncCount(val);}}for (int r = (m_curY / 3) * 3; r < (m_curY / 3) * 3 + 3; r ++){for (int c = (m_curX / 3) * 3; c < (m_curX / 3) * 3 + 3; c++){if (r == m_curY || c == m_curX){continue;}m_grids[r][c].IncCount(val);}}m_nRemained --;posTrace.push(make_pair<int,int>(m_curX, m_curY));DecideNextPlace();}SUDOKUState(int a[TEMPLATE_SIZE][TEMPLATE_SIZE]){m_nRemained = TEMPLATE_SIZE * TEMPLATE_SIZE;for (int i = 0; i <TEMPLATE_SIZE;i++){for (int j = 0; j< TEMPLATE_SIZE;j++){m_grids[i][j].nRemainCount = TEMPLATE_SIZE;m_grids[i][j].val = a[i][j];if (a[i][j] != 0){//在第i行第j列放了数字a[i][j]m_curX = j;m_curY = i;PlaceNumber(a[i][j]);}}}DecideNextPlace();}//计算下一步放数字的格子，贪心void DecideNextPlace(){if (m_nRemained == 0){return;}int minv = 10000;for (int r = 0; r < TEMPLATE_SIZE; r++){for (int c = 0; c < TEMPLATE_SIZE; c++){if (m_grids[r][c].val == 0 && m_grids[r][c].nRemainCount < minv){minv = m_grids[r][c].nRemainCount;m_curX = c; m_curY = r;}}}//有一个空格子已经没有数可以选择了if (minv == 0){m_curX = -1;m_curY = -1;}}void PrintBoard(){for (int i = 0; i <TEMPLATE_SIZE;i++){for (int j = 0; j< TEMPLATE_SIZE;j++){cout << m_grids[i][j].val << " ";}cout << endl;}}Grid m_grids[TEMPLATE_SIZE][TEMPLATE_SIZE];std::stack<pair<int,int> > posTrace; //记录放置的位置记录int m_nRemained;//还有多少个要放置//当前需要放置的位置int m_curX;int m_curY;};void Solve(SUDOKUState& state){if (bSolved){return;}//cout << gCount++ << endl;gCount++;if (state.IsFinal()){state.PrintBoard();bSolved = true;return;}if (state.IsDead()){return;}for (int i = 1; i < 10; i++){if (!state.CanPlace(i)){continue;}state.PlaceNumber(i);Solve(state);state.RemoveNumber(i);}}int _tmain(int argc, _TCHAR* argv[]){SUDOKUState state(board);state.PrintBoard();cout << endl;//GFClock gfClock;Solve(state);//cout << gfClock.Elapsed() << " ms" << endl;cout << gCount << " times called" << endl;return 0;}
