不確定特異点

広く深く、ところどころ超深く

8クイーン問題を解いてみる

久しぶりに8クイーン問題を解きたくなったのでプログラムを書いてみました。そういえば、Common Lisp で書いたのは今回が初めてかも。

8 Queens Problem

単純にバックトラックしているだけで、ゲーム盤の対称性は考慮してません。

動作結果

N = 8 で 92 個の解が得られました。

CL-USER> (show (solve 1))
  0 1 2 3 4 5 6 7
0 Q . . . . . . . 
1 . . . . Q . . . 
2 . . . . . . . Q 
3 . . . . . Q . . 
4 . . Q . . . . . 
5 . . . . . . Q . 
6 . Q . . . . . . 
7 . . . Q . . . . 

NIL
CL-USER> (time (length (solve)))
Evaluation took:
  0.001 seconds of real time
  0.000916 seconds of total run time (0.000911 user, 0.000005 system)
  100.00% CPU
  2,194,407 processor cycles
  0 bytes consed
  
92

N をもう少し増やしてみました。僕の PC (Mac Book Pro) だと、N = 15 を超えると数時間オーダーになってしまうようです。手軽に重い計算をさせることができるので、処理系の速度を簡易ベンチマークするのにいいかも。

CL-USER> (setq N 14)
14
CL-USER> (board-init)
#(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL
  NIL NIL NIL NIL NIL NIL NIL NIL)
CL-USER> (time (length (solve)))
Evaluation took:
  13.727 seconds of real time
  13.743852 seconds of total run time (13.648550 user, 0.095302 system)
  [ Run times consist of 0.144 seconds GC time, and 13.600 seconds non-GC time. ]
  100.12% CPU
  32,929,911,772 processor cycles
  52,763,856 bytes consed
  
365596
CL-USER> (setq N 15)
15
CL-USER> (board-init)
#(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL
  NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
CL-USER> (time (length (solve)))
Evaluation took:
  91.988 seconds of real time
  92.060469 seconds of total run time (91.523577 user, 0.536892 system)
  [ Run times consist of 0.960 seconds GC time, and 91.101 seconds non-GC time. ]
  100.08% CPU
  220,666,245,231 processor cycles
  364,919,376 bytes consed
  
2279184