【计算机算法设计与分析】九宫格问题/三阶幻方问题（C++_回溯法）

问题描述

使用回溯算法计算九宫格问题的所有可行解，九宫格问题是指在 3×3 的网格中填入 1-9 个不重复的数字，同时满足以下条件：九宫格问题是指在 3×3 的网格中填入 1-9 个不重复的数字，并满足每行、每列或每条对角线上的所有元素之和都是 15。请注意，每个数字只能出现一次。

算法原理

回溯法，直白点说其实就是一个尝试一切可能的递归算法，也就是一种深度优先搜索算法，它的编写也满足递归的两个要点：结束条件和循环体。

• 结束条件（m==9）：九个位置都已经填满数字了，再判断是否满足幻方要求即可，不满足就回溯继续，满足就先输出再回溯；
• 循环体：整个递归函数在不断循坏给每个位置赋值，而中间的for循环就是不断实验给他赋什么值，而且由于整个九宫格中出现的数字不能重复，所有加了vis数组记录哪几个数字已经出现过了。

算法实现

#include <bits/stdc++.h>
using namespace std;
int g[9], vis[10]; //g[i]表示所有

bool judge() {
	if (g[0] + g[1] + g[2] == 15 &&
		g[3] + g[4] + g[5] == 15 &&
		g[6] + g[7] + g[8] == 15 &&
		g[0] + g[3] + g[6] == 15 &&
		g[1] + g[4] + g[7] == 15 &&
		g[2] + g[5] + g[8] == 15 &&
		g[0] + g[4] + g[8] == 15 &&
		g[2] + g[4] + g[6] == 15)
		return true;
	return false;
}

void output() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++)
			cout << g[i*3+j];
		cout << endl;
	}
	cout << "---------" << endl;
}

void dfs(int m) {
	if (m == 9)
		if (judge()) {
			output();
			return;
		}
		else
			return;
	for (int i = 1; i <= 9; i++) {
		if (vis[i])
			continue;
		vis[i] = 1;
		g[m] = i;
		dfs(m + 1);
		vis[i] = 0;
	}
}

int main() {
	memset(vis, 0, sizeof vis);
	dfs(0);
	return 0;
}

参考资料

三阶幻方（回溯）