遡及法による八皇后問題解決(JAVA使用)...
現在の碁盤の大きさがN*Nであると仮定すると,すべての皇后の位置の解を見つける必要がある.
基本的な考え方は以下の通りです.
皇后位置解を格納するためのリストを定義します.
1.最初の行から、皇后を置くことができる最初の位置を見つけます.
2.見つければリストの末尾に加え、次の行に進み、その行の最初に皇后を置くことができる位置を見つけます.見つからない場合は、リストの末尾のノードを削除し、前の行に遡ってその行の次の皇后を置くことができる位置を探します.繰り返し2
リストに既にN個の要素が存在していること、すなわち、リスト中のN個の要素が皇后位置の解のセットであることを確認すると、リスト中のすべての要素が出力され、リスト末尾ノードが削除される.
最後の列になっている場合は、前の行に戻ります.
次はコード実装
基本的な考え方は以下の通りです.
皇后位置解を格納するためのリストを定義します.
1.最初の行から、皇后を置くことができる最初の位置を見つけます.
2.見つければリストの末尾に加え、次の行に進み、その行の最初に皇后を置くことができる位置を見つけます.見つからない場合は、リストの末尾のノードを削除し、前の行に遡ってその行の次の皇后を置くことができる位置を探します.繰り返し2
リストに既にN個の要素が存在していること、すなわち、リスト中のN個の要素が皇后位置の解のセットであることを確認すると、リスト中のすべての要素が出力され、リスト末尾ノードが削除される.
最後の列になっている場合は、前の行に戻ります.
次はコード実装
import java.util.LinkedList;
import java.util.List;
public class Main {
private static int sum=0;
public static void main(String[] args) {
fun(0, 8, new LinkedList());
}
public static void fun(int i,int n,List list){
Point point = null;
for(int j=0 ;j < n ;j++){
point = new Point(i, j);
boolean flag = checkPosition(point,n,list);
if(flag){
list.add(point);
if(list.size() != n){
fun(i + 1, n, list);
}else{
System.out.println(" "+(++sum)+" "+list);
((LinkedList) list).removeLast();
}
}
if(j == n-1){
if(i != 0){
((LinkedList) list).removeLast();
}
}
}
}
public static boolean checkPosition(Point point,int n,List list){
for (Point onePoint:
list) {
if(point.getX() == onePoint.getX() || point.getY() == onePoint.getY()){
return false;
}
if(Math.abs(point.getX()-onePoint.getX()) == Math.abs(point.getY()-onePoint.getY())
){
return false;
}
}
return true;
}
}