【DS】八皇后問題javaコード

13053 ワード

八皇后問題の概要:八皇后問題は、古くて有名な問題であり、遡及アルゴリズムの典型的な例題である.この問題は19世紀の有名な数学者ガウスが1850年に提出した:8 X 8格のチェスの上に8つの皇后を置いて、互いに攻撃することができなくて、つまり任意の2つの皇后はすべて同じ行、同じ列あるいは同じ斜線の上で、どれだけの振り方があるかを聞きます.ガウスは76の案があると考えている.1854年にベルリンの将棋雑誌で異なる著者が40種類の異なる解を発表し、後に図論的な方法で92種類の結果を解いた人がいた.コンピュータが発明された後、この問題を解決する方法はいくつかある.
解決方法:遡及アルゴリズム
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の誤りが発生することができて、今まで間違いの原因を探し出していないで、もし読者が見抜くならば、ご指導を惜しまないでください