【DS】八皇后問題javaコード
13053 ワード
八皇后問題の概要:八皇后問題は、古くて有名な問題であり、遡及アルゴリズムの典型的な例題である.この問題は19世紀の有名な数学者ガウスが1850年に提出した:8 X 8格のチェスの上に8つの皇后を置いて、互いに攻撃することができなくて、つまり任意の2つの皇后はすべて同じ行、同じ列あるいは同じ斜線の上で、どれだけの振り方があるかを聞きます.ガウスは76の案があると考えている.1854年にベルリンの将棋雑誌で異なる著者が40種類の異なる解を発表し、後に図論的な方法で92種類の結果を解いた人がいた.コンピュータが発明された後、この問題を解決する方法はいくつかある.
解決方法:遡及アルゴリズム
Javaコード:
このクラスは、皇后が碁盤に置かれた位置を格納するために使用されます.
次のクラスは解法です.
印刷結果:
備考:運行する時、第93、94、95種類の解が現れて、前の5、6、7と繰り返して、しかもStackOverflowErrorの誤りが発生することができて、今まで間違いの原因を探し出していないで、もし読者が見抜くならば、ご指導を惜しまないでください
解決方法:遡及アルゴリズム
Javaコード:
public class QueenPosition {
private int x;
private int y;
public QueenPosition(int row, int column){
x = row;
y = column;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
このクラスは、皇后が碁盤に置かれた位置を格納するために使用されます.
次のクラスは解法です.
import java.util.ArrayList;
public class EightQueens {
static ArrayList<QueenPosition> path = new ArrayList<QueenPosition>();
static int pathCount = 0;// ，
public static void main(String[] args) {
// TODO Auto-generated method stub
findQueenSolution(0, 0, path);// ， （0，0） ， ， ， 。path
}
//
public static void findQueenSolution(int xStart, int yStart, ArrayList<QueenPosition> path){
for(int row = xStart; row < 8 ; row++){//
// ， ，
if(row > xStart){
yStart = 0;
}
//
boolean isFound = false;
for(int column = yStart; column < 8 && !isFound; column ++){
//
if(isLegal(row, column, path)){
// （ ），
path.add(new QueenPosition(row,column));
isFound = true;// ！
if(row == 7){
// ， ， ，
pathCount++;
printPath(path);
reCall(path);
}
}else{
//
if(column == 7){
// ， ，
reCall(path);
}
}
}
}
}
// （ ， ： ， ， column 0 7 ， ， ， ， （3，4）， ， （3，5） ， ++orginColumn ； （3，7）， ， ， ， ， ）
public static void reCall(ArrayList<QueenPosition> path){
int pathLength = path.size();
if(pathLength > 0){
// （ ， ）
int orginColumn = path.get(pathLength-1).getY();
path.remove(pathLength-1);//
int row = pathLength-1;
if(orginColumn == 7 && pathLength > 1){//
orginColumn = path.get(pathLength-2).getY();
path.remove(pathLength-2);
--row;
}
findQueenSolution(row, ++orginColumn, copyPath(path));//
}
}
public static boolean isLegal(int x, int y, ArrayList<QueenPosition> path){//
boolean legal = true;
int pathLength = path.size();
for(int index = 0; index < pathLength; index ++){
int xCor = path.get(index).getX();
int yCor = path.get(index).getY();
int xDiff = Math.abs(xCor - x);
int yDiff = Math.abs(yCor - y);
if((xDiff == yDiff) || xDiff == 0 || yDiff == 0){
// ， 0
legal = false;
break;
}
}
return legal;
}
//
public static void printPath(ArrayList<QueenPosition> path){
System.out.print(" " + pathCount + " ：");
for(int position = 0; position < path.size(); position ++){
System.out.print("(" + path.get(position).getX() + " , " + path.get(position).getY() + ") ");
}
System.out.println();
}
// arrayList, arrayList
public static ArrayList<QueenPosition> copyPath(ArrayList<QueenPosition> orginPath){
ArrayList<QueenPosition> copyList = new ArrayList<QueenPosition>();
for(int index = 0; index < orginPath.size(); index ++){
copyList.add(orginPath.get(index));
}
return copyList;
}
}
印刷結果:
1 ：(0 , 0) (1 , 4) (2 , 7) (3 , 5) (4 , 2) (5 , 6) (6 , 1) (7 , 3)
2 ：(0 , 0) (1 , 5) (2 , 7) (3 , 2) (4 , 6) (5 , 3) (6 , 1) (7 , 4)
3 ：(0 , 0) (1 , 6) (2 , 3) (3 , 5) (4 , 7) (5 , 1) (6 , 4) (7 , 2)
4 ：(0 , 0) (1 , 6) (2 , 4) (3 , 7) (4 , 1) (5 , 3) (6 , 5) (7 , 2)
5 ：(0 , 1) (1 , 3) (2 , 5) (3 , 7) (4 , 2) (5 , 0) (6 , 6) (7 , 4)
6 ：(0 , 1) (1 , 4) (2 , 6) (3 , 0) (4 , 2) (5 , 7) (6 , 5) (7 , 3)
7 ：(0 , 1) (1 , 4) (2 , 6) (3 , 3) (4 , 0) (5 , 7) (6 , 5) (7 , 2)
8 ：(0 , 1) (1 , 5) (2 , 0) (3 , 6) (4 , 3) (5 , 7) (6 , 2) (7 , 4)
9 ：(0 , 1) (1 , 5) (2 , 7) (3 , 2) (4 , 0) (5 , 3) (6 , 6) (7 , 4)
10 ：(0 , 1) (1 , 6) (2 , 2) (3 , 5) (4 , 7) (5 , 4) (6 , 0) (7 , 3)
11 ：(0 , 1) (1 , 6) (2 , 4) (3 , 7) (4 , 0) (5 , 3) (6 , 5) (7 , 2)
12 ：(0 , 1) (1 , 7) (2 , 5) (3 , 0) (4 , 2) (5 , 4) (6 , 6) (7 , 3)
13 ：(0 , 2) (1 , 0) (2 , 6) (3 , 4) (4 , 7) (5 , 1) (6 , 3) (7 , 5)
14 ：(0 , 2) (1 , 4) (2 , 1) (3 , 7) (4 , 0) (5 , 6) (6 , 3) (7 , 5)
15 ：(0 , 2) (1 , 4) (2 , 1) (3 , 7) (4 , 5) (5 , 3) (6 , 6) (7 , 0)
16 ：(0 , 2) (1 , 4) (2 , 6) (3 , 0) (4 , 3) (5 , 1) (6 , 7) (7 , 5)
17 ：(0 , 2) (1 , 4) (2 , 7) (3 , 3) (4 , 0) (5 , 6) (6 , 1) (7 , 5)
18 ：(0 , 2) (1 , 5) (2 , 1) (3 , 4) (4 , 7) (5 , 0) (6 , 6) (7 , 3)
19 ：(0 , 2) (1 , 5) (2 , 1) (3 , 6) (4 , 0) (5 , 3) (6 , 7) (7 , 4)
20 ：(0 , 2) (1 , 5) (2 , 1) (3 , 6) (4 , 4) (5 , 0) (6 , 7) (7 , 3)
21 ：(0 , 2) (1 , 5) (2 , 3) (3 , 0) (4 , 7) (5 , 4) (6 , 6) (7 , 1)
22 ：(0 , 2) (1 , 5) (2 , 3) (3 , 1) (4 , 7) (5 , 4) (6 , 6) (7 , 0)
23 ：(0 , 2) (1 , 5) (2 , 7) (3 , 0) (4 , 3) (5 , 6) (6 , 4) (7 , 1)
24 ：(0 , 2) (1 , 5) (2 , 7) (3 , 0) (4 , 4) (5 , 6) (6 , 1) (7 , 3)
25 ：(0 , 2) (1 , 5) (2 , 7) (3 , 1) (4 , 3) (5 , 0) (6 , 6) (7 , 4)
26 ：(0 , 2) (1 , 6) (2 , 1) (3 , 7) (4 , 4) (5 , 0) (6 , 3) (7 , 5)
27 ：(0 , 2) (1 , 6) (2 , 1) (3 , 7) (4 , 5) (5 , 3) (6 , 0) (7 , 4)
28 ：(0 , 2) (1 , 7) (2 , 3) (3 , 6) (4 , 0) (5 , 5) (6 , 1) (7 , 4)
29 ：(0 , 3) (1 , 0) (2 , 4) (3 , 7) (4 , 1) (5 , 6) (6 , 2) (7 , 5)
30 ：(0 , 3) (1 , 0) (2 , 4) (3 , 7) (4 , 5) (5 , 2) (6 , 6) (7 , 1)
31 ：(0 , 3) (1 , 1) (2 , 4) (3 , 7) (4 , 5) (5 , 0) (6 , 2) (7 , 6)
32 ：(0 , 3) (1 , 1) (2 , 6) (3 , 2) (4 , 5) (5 , 7) (6 , 0) (7 , 4)
33 ：(0 , 3) (1 , 1) (2 , 6) (3 , 2) (4 , 5) (5 , 7) (6 , 4) (7 , 0)
34 ：(0 , 3) (1 , 1) (2 , 6) (3 , 4) (4 , 0) (5 , 7) (6 , 5) (7 , 2)
35 ：(0 , 3) (1 , 1) (2 , 7) (3 , 4) (4 , 6) (5 , 0) (6 , 2) (7 , 5)
36 ：(0 , 3) (1 , 1) (2 , 7) (3 , 5) (4 , 0) (5 , 2) (6 , 4) (7 , 6)
37 ：(0 , 3) (1 , 5) (2 , 0) (3 , 4) (4 , 1) (5 , 7) (6 , 2) (7 , 6)
38 ：(0 , 3) (1 , 5) (2 , 7) (3 , 1) (4 , 6) (5 , 0) (6 , 2) (7 , 4)
39 ：(0 , 3) (1 , 5) (2 , 7) (3 , 2) (4 , 0) (5 , 6) (6 , 4) (7 , 1)
40 ：(0 , 3) (1 , 6) (2 , 0) (3 , 7) (4 , 4) (5 , 1) (6 , 5) (7 , 2)
41 ：(0 , 3) (1 , 6) (2 , 2) (3 , 7) (4 , 1) (5 , 4) (6 , 0) (7 , 5)
42 ：(0 , 3) (1 , 6) (2 , 4) (3 , 1) (4 , 5) (5 , 0) (6 , 2) (7 , 7)
43 ：(0 , 3) (1 , 6) (2 , 4) (3 , 2) (4 , 0) (5 , 5) (6 , 7) (7 , 1)
44 ：(0 , 3) (1 , 7) (2 , 0) (3 , 2) (4 , 5) (5 , 1) (6 , 6) (7 , 4)
45 ：(0 , 3) (1 , 7) (2 , 0) (3 , 4) (4 , 6) (5 , 1) (6 , 5) (7 , 2)
46 ：(0 , 3) (1 , 7) (2 , 4) (3 , 2) (4 , 0) (5 , 6) (6 , 1) (7 , 5)
47 ：(0 , 4) (1 , 0) (2 , 3) (3 , 5) (4 , 7) (5 , 1) (6 , 6) (7 , 2)
48 ：(0 , 4) (1 , 0) (2 , 7) (3 , 3) (4 , 1) (5 , 6) (6 , 2) (7 , 5)
49 ：(0 , 4) (1 , 0) (2 , 7) (3 , 5) (4 , 2) (5 , 6) (6 , 1) (7 , 3)
50 ：(0 , 4) (1 , 1) (2 , 3) (3 , 5) (4 , 7) (5 , 2) (6 , 0) (7 , 6)
51 ：(0 , 4) (1 , 1) (2 , 3) (3 , 6) (4 , 2) (5 , 7) (6 , 5) (7 , 0)
52 ：(0 , 4) (1 , 1) (2 , 5) (3 , 0) (4 , 6) (5 , 3) (6 , 7) (7 , 2)
53 ：(0 , 4) (1 , 1) (2 , 7) (3 , 0) (4 , 3) (5 , 6) (6 , 2) (7 , 5)
54 ：(0 , 4) (1 , 2) (2 , 0) (3 , 5) (4 , 7) (5 , 1) (6 , 3) (7 , 6)
55 ：(0 , 4) (1 , 2) (2 , 0) (3 , 6) (4 , 1) (5 , 7) (6 , 5) (7 , 3)
56 ：(0 , 4) (1 , 2) (2 , 7) (3 , 3) (4 , 6) (5 , 0) (6 , 5) (7 , 1)
57 ：(0 , 4) (1 , 6) (2 , 0) (3 , 2) (4 , 7) (5 , 5) (6 , 3) (7 , 1)
58 ：(0 , 4) (1 , 6) (2 , 0) (3 , 3) (4 , 1) (5 , 7) (6 , 5) (7 , 2)
59 ：(0 , 4) (1 , 6) (2 , 1) (3 , 3) (4 , 7) (5 , 0) (6 , 2) (7 , 5)
60 ：(0 , 4) (1 , 6) (2 , 1) (3 , 5) (4 , 2) (5 , 0) (6 , 3) (7 , 7)
61 ：(0 , 4) (1 , 6) (2 , 1) (3 , 5) (4 , 2) (5 , 0) (6 , 7) (7 , 3)
62 ：(0 , 4) (1 , 6) (2 , 3) (3 , 0) (4 , 2) (5 , 7) (6 , 5) (7 , 1)
63 ：(0 , 4) (1 , 7) (2 , 3) (3 , 0) (4 , 2) (5 , 5) (6 , 1) (7 , 6)
64 ：(0 , 4) (1 , 7) (2 , 3) (3 , 0) (4 , 6) (5 , 1) (6 , 5) (7 , 2)
65 ：(0 , 5) (1 , 0) (2 , 4) (3 , 1) (4 , 7) (5 , 2) (6 , 6) (7 , 3)
66 ：(0 , 5) (1 , 1) (2 , 6) (3 , 0) (4 , 2) (5 , 4) (6 , 7) (7 , 3)
67 ：(0 , 5) (1 , 1) (2 , 6) (3 , 0) (4 , 3) (5 , 7) (6 , 4) (7 , 2)
68 ：(0 , 5) (1 , 2) (2 , 0) (3 , 6) (4 , 4) (5 , 7) (6 , 1) (7 , 3)
69 ：(0 , 5) (1 , 2) (2 , 0) (3 , 7) (4 , 3) (5 , 1) (6 , 6) (7 , 4)
70 ：(0 , 5) (1 , 2) (2 , 0) (3 , 7) (4 , 4) (5 , 1) (6 , 3) (7 , 6)
71 ：(0 , 5) (1 , 2) (2 , 4) (3 , 6) (4 , 0) (5 , 3) (6 , 1) (7 , 7)
72 ：(0 , 5) (1 , 2) (2 , 4) (3 , 7) (4 , 0) (5 , 3) (6 , 1) (7 , 6)
73 ：(0 , 5) (1 , 2) (2 , 6) (3 , 1) (4 , 3) (5 , 7) (6 , 0) (7 , 4)
74 ：(0 , 5) (1 , 2) (2 , 6) (3 , 1) (4 , 7) (5 , 4) (6 , 0) (7 , 3)
75 ：(0 , 5) (1 , 2) (2 , 6) (3 , 3) (4 , 0) (5 , 7) (6 , 1) (7 , 4)
76 ：(0 , 5) (1 , 3) (2 , 0) (3 , 4) (4 , 7) (5 , 1) (6 , 6) (7 , 2)
77 ：(0 , 5) (1 , 3) (2 , 1) (3 , 7) (4 , 4) (5 , 6) (6 , 0) (7 , 2)
78 ：(0 , 5) (1 , 3) (2 , 6) (3 , 0) (4 , 2) (5 , 4) (6 , 1) (7 , 7)
79 ：(0 , 5) (1 , 3) (2 , 6) (3 , 0) (4 , 7) (5 , 1) (6 , 4) (7 , 2)
80 ：(0 , 5) (1 , 7) (2 , 1) (3 , 3) (4 , 0) (5 , 6) (6 , 4) (7 , 2)
81 ：(0 , 6) (1 , 0) (2 , 2) (3 , 7) (4 , 5) (5 , 3) (6 , 1) (7 , 4)
82 ：(0 , 6) (1 , 1) (2 , 3) (3 , 0) (4 , 7) (5 , 4) (6 , 2) (7 , 5)
83 ：(0 , 6) (1 , 1) (2 , 5) (3 , 2) (4 , 0) (5 , 3) (6 , 7) (7 , 4)
84 ：(0 , 6) (1 , 2) (2 , 0) (3 , 5) (4 , 7) (5 , 4) (6 , 1) (7 , 3)
85 ：(0 , 6) (1 , 2) (2 , 7) (3 , 1) (4 , 4) (5 , 0) (6 , 5) (7 , 3)
86 ：(0 , 6) (1 , 3) (2 , 1) (3 , 4) (4 , 7) (5 , 0) (6 , 2) (7 , 5)
87 ：(0 , 6) (1 , 3) (2 , 1) (3 , 7) (4 , 5) (5 , 0) (6 , 2) (7 , 4)
88 ：(0 , 6) (1 , 4) (2 , 2) (3 , 0) (4 , 5) (5 , 7) (6 , 1) (7 , 3)
89 ：(0 , 7) (1 , 1) (2 , 3) (3 , 0) (4 , 6) (5 , 4) (6 , 2) (7 , 5)
90 ：(0 , 7) (1 , 1) (2 , 4) (3 , 2) (4 , 0) (5 , 6) (6 , 3) (7 , 5)
91 ：(0 , 7) (1 , 2) (2 , 0) (3 , 5) (4 , 1) (5 , 4) (6 , 6) (7 , 3)
92 ：(0 , 7) (1 , 3) (2 , 0) (3 , 2) (4 , 5) (5 , 1) (6 , 6) (7 , 4)
備考:運行する時、第93、94、95種類の解が現れて、前の5、6、7と繰り返して、しかもStackOverflowErrorの誤りが発生することができて、今まで間違いの原因を探し出していないで、もし読者が見抜くならば、ご指導を惜しまないでください