C++ 完美破解九宫格（数独）游戏

看到CSDN上有位大神用C#写了一个破解数独的程序（点击打开链接），不过我对C#也不懂，比较喜欢C++，就用标准C++也写了一个，希望各位喜欢。三纯程序，纯控制台程序，纯各人爱好，纯算法程序，无win API。基本思路与之前那个类似，采用brute force加剪枝，找到第一个符合条件的情况就立即退出不再查找。一般一个合格的数独只有唯一解，如果你的数独多解的话，那也就不叫数独了。

代码如下：

#include <iostream>

#include <deque>

using namespace std;

const int MAX_SIZE = 9;		// 九宫格

struct Pos {

	Pos(int x, int y) : row(x), col(y) {};

	int row;

	int col;

};

typedef deque <Pos> qpos;

qpos Q;		// 记录要放置数字的位置

// 九宫格数组，0表示玩家要放置数字的位置

int sudoku[MAX_SIZE][MAX_SIZE] = {

	{0, 0, 3, 0, 5, 0, 0, 0, 9},

	{0, 0, 0, 1, 0, 0, 0, 2, 5},

	{0, 8, 0, 0, 3, 7, 0, 0, 0},

	{0, 0, 0, 0, 0, 8, 0, 9, 7},

	{2, 0, 0, 0, 6, 0, 0, 0, 4},

	{9, 4, 0, 0, 0, 0, 8, 0, 1},

	{0, 0, 0, 6, 9, 0, 4, 0, 0},

	{8, 0, 0, 0, 0, 5, 0, 0, 0},

	{6, 0, 0, 0, 1, 0, 9, 0, 0},

};

void printSudoku()

{

	cout << "-------------------------" << endl;

	for (int i = 0; i < MAX_SIZE; i++) {

		for (int j = 0; j <MAX_SIZE; j++) {

			if (j % 3 == 0) {

				cout << "| ";

			}

			cout << sudoku[i][j] << " ";

		}

		cout << "| ";

		cout << endl;

		if ( (i+1) % 3 == 0 ) {

			cout << "-------------------------" << endl;

		}

	}

}

bool check(Pos p, int n)

{

	int cur_row = p.row;

	int cur_col = p.col;

	// 验证行列是否合格

	for (int i = 0; i < MAX_SIZE; i++) {

		if (n == sudoku[i][cur_col] || n == sudoku[cur_row][i]) {

			return false;

		}

	}

	// 验证九宫格内是无复生数字

	int grid_row = ( cur_row / 3 ) * 3;

	int grid_col = ( cur_col / 3 ) * 3;

	for (int i = 0; i < 3; i++) {

		if (n == sudoku[grid_row][i + grid_col] ||

			n == sudoku[grid_row + i][grid_col]) {

			return false;

		}

	}

	return true;

}

bool place(qpos & Q)

{

	// 递归结束条件为没有要断续放置数字的位置

	if (Q.empty()) {

		printSudoku();

		return true;

	}

	Pos cur(Q.front().row, Q.front().col);	// 当前需要放置的位置信息

	Q.pop_front();

	for (int i = 1; i <= 9; i++) {		// 从1到9轮流尝试

		if ( check(cur, i) ) {

			sudoku[cur.row][cur.col] = i;	// 放置数字i到当前位置

			if ( !place(Q) ) {		// 放置下一位置

				// 下一位置放置失败，则在当前位置尝试放置下一个i

				sudoku[cur.row][cur.col] = 0;	// 将当前位置值重置

			} else {	// 下一位置放置成功

				return true;

			}

		}

	}

	Q.push_front(cur);	//当前位置不论怎么放置数字，下一位置都无法放置成功，

				// 重新插入该位置信息，返回上一级放置位置

	return false;

}

int main()

{

	// Q中保存需要放置数字的位置

	for (int i = 0; i < MAX_SIZE; i++) {

		for (int j = 0; j < MAX_SIZE; j++) {

			if (0 == sudoku[i][j]) {

				Q.push_back(Pos(i, j));

			}

		}

	}

	place(Q);

	return 0;

}

我也来个运行截图：

上面的程序只会打印出一种符合的数独，如果你想将所以可能的情况都打印出来怎么办，一般情况下，合格的数独都只有一种解，那万一有一个不合格的数独，你又想知道它的全部解，那么，你可以用下面的方法：

/**

 * 打印所有符合条件的情况

 */

void place2(qpos & Q)

{

	// 递归结束条件为没有要断续放置数字的位置

	if (Q.empty()) {

		printSudoku();

		return;

	}

	Pos cur(Q.front().row, Q.front().col);	// 当前需要放置的位置信息

	Q.pop_front();

	for (int i = 1; i <= 9; i++) {		// 从1到9轮流尝试

		if ( check(cur, i) ) {

			sudoku[cur.row][cur.col] = i;	// 放置数字i到当前位置

			place2(Q);

			sudoku[cur.row][cur.col] = 0;	// 将当前位置值重置

		}

	}

	Q.push_front(cur);	// 重新插入该位置信息，返回上一级放置位置

}

巴特西

C++ 完美破解九宫格（数独）游戏

最新文章

热门文章