#n-queen

Researching the n-Queens problem the night before it was assigned paid off!  Today we tackled Complexity analysis with the specific case of n-Queen problem.  The idea is to find all solutions of 'n' number of queens on a square board of size 'n'.  A solution being a placement of n queens such that they do not threat each other.

After an hour or two on wikipedia last night I found out that the recursive method had the best balance of simplicity and efficiency.  However, it turned out that the algorithm would be the easiest part of the project...

My partner and I had some trouble figuring out the testing framework.  The calls were much more complicated than we had seen before and a very weird thing happend after which, we lost all confidence in the tests.  Before dealing with the main recursive algorithm we had to populate the functions that would check threats between queens.  We didn't fully understand at first how to fill out those functions, but went with our intuitions.  The weird thing was that after dealing with row threats, which passed the row tests.  Dealing with column threats, made the row tests fail!  We couldn't figure out why this was happening and because of bad timing with lunch and lectures, we couldn't get much help from the staff.  We lost a good hour on this...

After lunch we were able to get some help on the expected implementation of the threat calculating functions. After that, everything went very smoothly.

The recursive function development went very well, and after implementing the algorithm on the first of the 4 problems, we were able to simply copy and paste the algorithm into the other 3 problems of the set and we got the answers we were looking for very quickly!

Prolog Programming for Artificial Intelligenceの第4版を読んでいる。演習問題の7.8をやってみた結果をメモしておく。

問題の概要は、N-Queen問題をFinite Domain上のCLP（Constraint Logic Programming）ライブラリを用いて解くときに、盤上の左の方のQueenから位置を試していくより、真ん中の方を優先した方が速くなるので試してみよというものだ。

通常、PrologのCLPにおいてはlabelingという述語を用いて、変数を確定する順番を定める。例えばlabeling([], [X1,X2, ... ,Xn])であれば、左のほうから（X1、X2、…の順に）値を試していく。labelingの第１引数は順番の決め方を指定するもので、[]だと左からになる。使用していた処理系SWI-Prologには、真ん中の変数からなどというオプションはなかった。仕方ないので、真ん中の方の変数が最初に来るように変数のリストを並べ替えて、labeling([], ...)を使うようにした。

並び替え部分のコードは次の通り。

% リスト Xs を（可能な限り）同じ長さで 2 つのリストに分けた時の、 %% 各リストの長さを求める。 %% 例: halflengths([1,2,3,4,5], 3, 2). halflengths(Xs, L1, L2) :- length(Xs, L), R is L mod 2, L1 is L // 2 + R, L2 is L // 2. %% リスト Xs を真ん中で２つのリストに分ける。 %% Xs の長さが奇数の場合は１つ目のリストが 1 つ分長くなる。 %% 例: half([1,2,3], [1,2], [3]). half(Xs, Y1, Y2) :- halflengths(Xs, L1, L2), length(Y1, L1), length(Y2, L2), append(Y1, Y2, Xs). %% ２つのリストを交互にマージしたようなリストを考える。 %% 例: merge([1,2], [3,4], [1,3,2,4]). merge([], X, X). merge(X, [], X). merge([X|Xs], [Y|Ys], [X,Y|Zs]) :- merge(Xs, Ys, Zs). %% リスト Xs から、真ん中の元が先に来るようなリスト Ys を構築 %% 例: middlefirst([1,2,3,4,5], [3,4,2,5,1]). middlefirst(Xs, Ys) :- half(Xs, H1, H2), reverse(H1, R1), merge(R1, H2, Ys).

labelingを行う前に上記middlefirstによる並べ替え処理を入れて実行した場合のベンチマークをとってみた結果が以下である。leftfirstというのが並べ替え処理を入れない場合、midfirstは入れた場合。さらに、labelingの第１引数に[ff]を指定した場合も載せてある。ここで、実行時間としては、最初の解を見つけるまでのCPU時間を述語statisticsで３回繰り返し測った平均を使用している。

google.load("visualization", "1", {packages:["corechart"]}); google.setOnLoadCallback(drawChart); function drawChart() { var data = google.visualization.arrayToDataTable([ ['N','leftfirst','midfirst','leftfirst ([ff])','midfirst ([ff])'], [4,0.666666666666667,0.666666666666667,0.666666666666667,0.666666666666667], [5,0.666666666666667,0.666666666666667,1,0.666666666666667], [6,2,3,3,2.33333333333333], [7,1.33333333333333,1,1.33333333333333,1], [8,6.33333333333333,6.33333333333333,6.66666666666667,6.66666666666667], [9,4,3.66666666666667,4.66666666666667,4], [10,9.33333333333333,9,6.33333333333333,5.33333333333333], [11,5.33333333333333,5.33333333333333,9,8], [12,20,21,20.6666666666667,19.3333333333333], [13,10.3333333333333,11.3333333333333,27.3333333333333,28.3333333333333], [14,135,133.333333333333,19,18.6666666666667], [15,106,105.333333333333,7.66666666666667,7.33333333333333], [16,738.333333333333,719.333333333333,10.3333333333333,10], [17,490.666666666667,476.666666666667,13,11.6666666666667], [18,3213.33333333333,3178.66666666667,13.6666666666667,14.3333333333333], [19,258.333333333333,258.333333333333,14.3333333333333,15], [20,16777,16789,28.3333333333333,30.3333333333333], [21,804.666666666667,790.333333333333,13.6666666666667,14.3333333333333], [22,138128.666666667,137760.333333333,15,13], [23,2343,2342.66666666667,21.6666666666667,22.3333333333333], [24,36592.6666666667,36504.3333333333,18.3333333333333,18.3333333333333], [25,4689.33333333333,4617,53.3333333333333,57.6666666666667] ]); var options = { title: 'Benchmark Results', vAxis: {title: "CPU Time (ms)", logScale: true}, hAxis: {title: "N"} }; var chart = new google.visualization.LineChart(document.getElementById('nqueen_chart_div')); chart.draw(data, options); }