大学没用心读书，八皇后问题令我望而生畏，这几天零零散散将其写完，并调试完成，感觉不难。当补交大学时的作业。总共92个解，12个解是独立的。
package com.kevin.queen;
public class EightQueen {
static int[][] queens = new int[8][8];
// 最近一子位置
static int curI = -1;
static int curJ = -1;
// 第1子位置
static int oneI = -1;
static int oneJ = -1;
static int times = 0;
// 总答案集合
static int[][][] total = new int[92][8][8];
static int[][] flag = new int[92][1];
public static void main(String[] args) {
for (int i = 0; i < 8; i++) {
reset();
setQueen(1, 0, i);
}
// 求出独立解
// 初始化标识位
for (int i = 0; i < 92; i++) {
flag[i][0] = 1;
}
// 去重
int resultOne = 0;
int[][] temp = new int[8][8];
for (int time = 0; time < 92; time++) {
if (flag[time][0] == 1) {
// 拿出结果
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
temp[i][j] = total[time][i][j];
}
}
// 打印结果
resultOne++;
System.out.println("独立:" + resultOne);
printResultOnly(temp);
// 转换
int[][] tsfResultEast = transferEast(temp);
int[][] tsfResultSouth = transferSouth(temp);
int[][] tsfResultWest = transferWest(temp);
//翻过来
int[][] contrast = contrast(temp);
int[][] contrastEast = transferEast(contrast);
int[][] contrastSouth = transferSouth(contrast);
int[][] contrastWest = transferWest(contrast);
//对比
for(int timeTemp = time + 1; timeTemp < 92; timeTemp++){
boolean same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != tsfResultEast[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != tsfResultSouth[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != tsfResultWest[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != contrast[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != contrastEast[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != contrastSouth[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
same = true;
isSame: for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if(total[timeTemp][i][j] != contrastWest[i][j]){
same = false;
break isSame;
}
}
}
if(same){
flag[timeTemp][0] = 0;
}
}
}
}
}
/**
* 放子
*
* @param queen
* 当前在放的子
* @param pI
* 开始放的横坐标
* @param pJ
* 开始放的纵坐标
*/
private static void setQueen(int queen, int pI, int pJ) {
// printTest();
// 放子是否成功
boolean success = false;
int i = pI >= 0 ? pI : 0;
int j = pJ >= 0 ? pJ : 0;
line: for (; i < 8; i++) {
for (; j < 8; j++) {
if (queens[i][j] == 0 && i == queen - 1) {
success = true;
queens[i][j] = 100 + queen;
curI = i;
curJ = j;
// 设置第1子位置
if (queen == 1) {
oneI = i;
oneJ = j;
}
// 将影响的格增加1
setOne(true, curI, curJ);
// 放完后，要退出
break line;
}
}
j = 0;
}
// 下一子开始放的坐标
int nextI = curI;
int nextJ = curJ;
if (success) { // 如果放子成功
if (queen >= 8) {
times++;
printResult(queens);
// 将最后一子拿掉, 将影响的格减少1
queens[curI][curJ] = 0;
setOne(false, curI, curJ);
// 如果最后一子，刚好放在最后一格
if (curI == 7 && curJ == 7) {
queen = queen - 1;
int[] result = previous(queen);
nextI = result[1];
nextJ = result[2];
}
} else {
queen = queen + 1;
}
// 将位置向前移动一格
if (nextJ < 7) {
nextJ += 1;
} else if (nextI < 7) {
nextI += 1;
nextJ = 0;
} else {
// 如果向前移动已到最后
return;
}
} else { // 如果放子失败，说明方案错误 ，重置
queen = queen - 1;
if (queen <= 1) {
return;
}
// 将要放的子拿掉
int[] results = previous(queen);
// 如果向前移动已到最后
if (results[0] == 0) {
return;
}
nextI = results[1];
nextJ = results[2];
}
setQueen(queen, nextI, nextJ);
}
/**
* 重置
*/
private static void reset() {
// 最近一子位置
curI = -1;
curJ = -1;
oneI = -1;
oneJ = -1;
// 初始化
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
queens[i][j] = 0;
}
}
}
/**
* 打印结果
*/
private static void printResult(int[][] result) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (result[i][j] > 100) {
total[times - 1][i][j] = 1;
System.out.print(result[i][j] + " ");
} else {
total[times - 1][i][j] = 0;
System.out.print(result[i][j] + " ");
}
}
System.out.println("");
}
System.out.println("============================================== " + times);
}
/**
* 打印独立解
* @param result
*/
private static void printResultOnly(int[][] result) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println("");
}
}
/**
* 将影响的格设置为1 isSet: 是否放子。 true: 放子； false: 拿子
*/
private static void setOne(boolean isSet, int x, int y) {
// 将当前子所影响的格置为1
// 处理当前行
for (int k = 0; k < 8; k++) {
if (k != y) {
if (queens[x][k] < 100) {
if (isSet) {
queens[x][k] += 1;
} else {
if (queens[x][k] >= 1) {
queens[x][k] -= 1;
}
}
}
}
}
// 处理当前列
for (int k = 0; k < 8; k++) {
if (k != x) {
if (queens[k][y] < 100) {
if (isSet) {
queens[k][y] += 1;
} else {
if (queens[k][y] >= 1) {
queens[k][y] -= 1;
}
}
}
}
}
// 处理左上角斜线
int topLeftI = x;
int topLeftJ = y;
while (true) {
topLeftI -= 1;
topLeftJ -= 1;
if (topLeftI < 0 || topLeftJ < 0) {
break;
}
if (queens[topLeftI][topLeftJ] < 100) {
if (isSet) {
queens[topLeftI][topLeftJ] += 1;
} else {
if (queens[topLeftI][topLeftJ] >= 1) {
queens[topLeftI][topLeftJ] -= 1;
}
}
}
}
// 处理右下角斜线
topLeftI = x;
topLeftJ = y;
while (true) {
topLeftI += 1;
topLeftJ += 1;
if (topLeftI > 7 || topLeftJ > 7) {
break;
}
if (queens[topLeftI][topLeftJ] < 100) {
if (isSet) {
queens[topLeftI][topLeftJ] += 1;
} else {
if (queens[topLeftI][topLeftJ] >= 1) {
queens[topLeftI][topLeftJ] -= 1;
}
}
}
}
// 处理右上角斜线
topLeftI = x;
topLeftJ = y;
while (true) {
topLeftI -= 1;
topLeftJ += 1;
if (topLeftI < 0 || topLeftJ > 7) {
break;
}
if (queens[topLeftI][topLeftJ] < 100) {
if (isSet) {
queens[topLeftI][topLeftJ] += 1;
} else {
if (queens[topLeftI][topLeftJ] >= 1) {
queens[topLeftI][topLeftJ] -= 1;
}
}
}
}
// 处理左下角斜线
topLeftI = x;
topLeftJ = y;
while (true) {
topLeftI += 1;
topLeftJ -= 1;
if (topLeftI > 7 || topLeftJ < 0) {
break;
}
if (queens[topLeftI][topLeftJ] < 100) {
if (isSet) {
queens[topLeftI][topLeftJ] += 1;
} else {
if (queens[topLeftI][topLeftJ] >= 1) {
queens[topLeftI][topLeftJ] -= 1;
}
}
}
}
}
/**
* 将上一子拿掉
*/
public static int[] previous(int queen) {
int[] result = new int[3];
result[0] = 1;
// 将要放的子拿掉
int tempK = 0;
int tempL = 0;
line: for (int k = 0; k < 8; k++) {
for (int l = 0; l < 8; l++) {
if (queens[k][l] == 100 + queen) {
queens[k][l] = 0;
tempK = k;
tempL = l;
break line;
}
}
}
// 将影响的格减少1
setOne(false, tempK, tempL);
// 将位置向前移动一格
if (tempL < 7) {
tempL += 1;
} else if (tempK < 7) {
tempK += 1;
tempL = 0;
} else {
// 如果向前移动已到最后
result[0] = 0;
}
result[1] = tempK;
result[2] = tempL;
return result;
}
/**
* 将矩阵进行旋转:东
*/
private static int[][] transferEast(int[][] temp) {
int[][] result = new int[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
result[j][8 - 1 - i] = temp[i][j];
}
}
return result;
}
/**
* 将矩阵进行旋转: 南
*/
private static int[][] transferSouth(int[][] temp) {
int[][] result = new int[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
result[8 - 1 - i][8 - 1 - j] = temp[i][j];
}
}
return result;
}
/**
* 将矩阵进行旋转: 西
*/
private static int[][] transferWest(int[][] temp) {
int[][] result = new int[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
result[8 - 1 - j][i] = temp[i][j];
}
}
return result;
}
/**
* 翻过来
*/
private static int[][] contrast(int[][] temp) {
int[][] result = new int[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
result[i][8 - 1 - j] = temp[i][j];
}
}
return result;
}
/**
* 打印中间结果，用于测试
*/
private static void printTest() {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (queens[i][j] > 100) {
System.out.print(queens[i][j] + " ");
} else {
System.out.print(queens[i][j] + " ");
}
}
System.out.println("");
}
System.out.println("-----------------------------");
}
}
相关推荐
八皇后问题是一个经典的计算机编程问题，它涉及到回溯算法、数据结构和图形用户界面的设计。在C++中，特别是结合MFC（Microsoft Foundation Classes）框架，可以创建具有用户友好界面的程序来解决此问题。 首先，...
### 八皇后问题详解 #### 一、八皇后问题背景 八皇后问题是一个经典的计算机科学问题，也是数学领域中一个有趣的挑战。这个问题来源于国际象棋的背景：如何在一个8×8的国际象棋棋盘上放置八个皇后，使得没有任何...
它们被应用于解决各种复杂问题，包括经典的八皇后问题。八皇后问题是一个著名的棋盘放置问题，要求在8×8的棋盘上摆放8个皇后，使得任意两个皇后都不能在同一行、同一列或同一对角线上。下面将详细解释这些方法以及...
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
用回溯求解法求解八皇后问题，经典问题matlab实现，欢迎大家下载
数据结构八皇后问题实验报告是一份详尽的项目文档，主要涵盖了八皇后问题的解决方案，该问题是一个经典的计算机科学和算法问题，源自国际象棋。报告的作者花费了两周时间完成，显然投入了大量的精力和思考。 八皇后...
八皇后问题课程设计论文
解决八皇后问题的源码，带有注释，由于数据结构即算法的学习，如有其他需要，请留言
作业代码，汇编写八皇后问题，自己写了一份，在网上找的也在里面
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或...
linux c语言实现八皇后问题。希望对你的学习
八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一...
八皇后问题是一个经典的问题，在棋盘上放置八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。这个问题最早由数学家欧拉提出，后来被广泛用来作为回溯法的典型示例。在这个Java程序...
八皇后问题是计算机科学中一个经典的回溯算法应用实例，它要求在8×8的棋盘上摆放8个皇后，使得任何两个皇后都无法在同一行、同一列或同一对角线上互相攻击。这个问题最早由数学家路易斯·卡洛在19世纪提出，至今...
### Python 实现八皇后问题详解 #### 一、八皇后问题背景及定义 八皇后问题是一个经典的计算机科学问题，最早由国际象棋爱好者马克斯·贝瑟尔在1848年提出。该问题是在一个8×8的国际象棋棋盘上放置8个皇后，使得...
这个文档关于八皇后问题，一共两种代码，输出分别为0和1的矩阵或者直接输出位置序号两种输出结果。代码是C++语言编写。
八皇后问题源代码解析 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。它的目标是在n×n格的棋盘上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。解决这个问题...
八皇后问题 递归算法 可以输入皇后的值 输出排列的结果
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线...
经典的算法，八皇后问题，c++实现，回溯法