【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の誤りが発生することができて、今まで間違いの原因を探し出していないで、もし読者が見抜くならば、ご指導を惜しまないでください