普通は再帰かループで解くNクイーンを、整数線形計画法で(半分力任せに)解くJavaプログラム。
ソースはこちら(N-Queen (Java + LpSolve))
LpSolveのAPIを使って制約式を追加しながら問題をソルバに丸投げして解いてもらってユニーク解とその個数を探索する。
ただ、思ったほどパフォーマンスは悪くない。
N=8で400ミリ秒、N=9で5秒、N=10で1分、N=11で40分ほど。
あと、回転と鏡像で重なる解を排除する処理が、整数計画に定式化した形だとすっごい簡単に書けることに気づいた。
他にも何かLpSolve使えないかなぁ…。
ソースはこちら(N-Queen (Java + LpSolve))
LpSolveのAPIを使って制約式を追加しながら問題をソルバに丸投げして解いてもらってユニーク解とその個数を探索する。
ただ、思ったほどパフォーマンスは悪くない。
N=8で400ミリ秒、N=9で5秒、N=10で1分、N=11で40分ほど。
あと、回転と鏡像で重なる解を排除する処理が、整数計画に定式化した形だとすっごい簡単に書けることに気づいた。
他にも何かLpSolve使えないかなぁ…。
//LP_SolveによるNクイーンのユニーク解探索プログラム //2009/2/10 import lpsolve.*; import java.io.*; public class NQueenLpSolve { static int N; static int feasible_patterns; static long solution_time; public static void main(String[] args) { for(N = 1; N <18; N ++) {
return null; else return array; } double[] makeArray(int init) { double[] array = new double[SIZE * SIZE]; if(init == 0) return array; for(int i = 0; i <array.length; i++)