穷举法搜索幻方所有解Java代码
时间: 2024-03-17 12:46:50 浏览: 19
以下是用Java实现的穷举法搜索幻方所有解的代码:
```java
public class MagicSquare {
private static int[][] square;
private static int size;
public static void main(String[] args) {
size = 3; // 幻方的大小
square = new int[size][size];
search(0, 0);
}
private static void search(int row, int col) {
if (row == size) { // 如果搜索到最后一行,则判断是否为幻方
if (isMagicSquare()) {
printSquare();
}
return;
}
for (int i = 1; i <= size * size; i++) { // 枚举1~9的数字
if (!contains(i)) { // 如果该数字还没有被使用
square[row][col] = i; // 将该数字填入格子中
int nextRow = row, nextCol = col + 1;
if (nextCol == size) { // 如果已经填满一行,则搜索下一行
nextRow++;
nextCol = 0;
}
search(nextRow, nextCol); // 递归搜索下一个格子
square[row][col] = 0; // 恢复格子为空
}
}
}
private static boolean contains(int num) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (square[i][j] == num) {
return true;
}
}
}
return false;
}
private static boolean isMagicSquare() {
// 检查行
for (int i = 0; i < size; i++) {
int sum = 0;
for (int j = 0; j < size; j++) {
sum += square[i][j];
}
if (sum != size * (size * size + 1) / 2) {
return false;
}
}
// 检查列
for (int j = 0; j < size; j++) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += square[i][j];
}
if (sum != size * (size * size + 1) / 2) {
return false;
}
}
// 检查对角线
int sum1 = 0, sum2 = 0;
for (int i = 0; i < size; i++) {
sum1 += square[i][i];
sum2 += square[i][size - i - 1];
}
return sum1 == size * (size * size + 1) / 2 && sum2 == size * (size * size + 1) / 2;
}
private static void printSquare() {
System.out.println("找到一个幻方:");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(square[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
```
这个程序采用递归的方式搜索幻方的所有解。首先定义一个二维数组`square`表示幻方,然后从左上角的格子开始搜索,枚举1~9的数字填入格子中。如果填满了一行,则搜索下一行。如果搜索到最后一行,则判断是否为幻方。如果是,则输出解。这个程序会搜索出幻方的所有解,但是搜索的时间会随着幻方的大小指数级增长,所以只适用于小幻方的情况。