チョコレートパズルを継続渡しで(30分で解けるようになった)

scheme

ペントミノ パズル(明治ミルクチョコパズル)をGaucheで解く(1時間で解けるようになった) - Gemmaの日記とのことなのでここは意地で対抗。id:Gemmaさんの初めのコードと同様、重複を除去してなかったのでそれを検討。

いろいろ思案してたけど、よくよく考えてみればそんなに難しくない方法でできる。回転と反転によってできる8つのパターンのうち、どの2つも重ね合わせることのできない形を適当に1つ選び、その形に対しては0度回転の(元の)パターンと90度回転させたパターンの2つのみを許すようにすれば自然と対称な解は取り除かれる。

そこで、とりあえず

###
  ##
  #

の形のものを2つのパターンに制限して解いてみよう(元のコードはこちら)。

$ diff choco.scm~ choco.scm -u
--- choco.scm~	2008-06-14 21:00:14.000000000 +0900
+++ choco.scm	2008-06-17 01:01:47.000000000 +0900
@@ -65,19 +65,21 @@
         (list x&y x&-y -x&y -x&-y y&x y&-x -y&x -y&-x))))
 
 (define-constant *pento-pieces*
-  (map derivatives
-       '(((0 . 0) (0 . 1) (0 . 2) (1 . 2) (2 . 2))
-         ((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 0))
-         ((0 . 0) (0 . 1) (1 . 1) (2 . 1) (3 . 1))
-         ((0 . 0) (0 . 1) (1 . 1) (2 . 1) (1 . 2))
-         ((0 . 0) (0 . 1) (1 . 1) (2 . 1) (2 . 2))
-         ((0 . 0) (0 . 1) (0 . 2) (1 . 1) (2 . 1))
-         ((0 . 0) (1 . 0) (1 . 1) (2 . 0) (3 . 0))
-         ((0 . 0) (1 . 0) (1 . 1) (0 . 1) (1 . 2))
-         ((0 . 0) (0 . 1) (0 . 2) (1 . 2) (1 . 3))
-         ((0 . 0) (0 . 1) (0 . 2) (1 . 0) (1 . 2))
-         ((0 . 0) (1 . 0) (0 . 1) (-1 . 1) (-1 . 2))
-         ((0 . 0) (0 . 1) (1 . 1) (-1 . 1) (0 . 2)))))
+  (cons '(((0 . 0) (0 . 1) (1 . 1) (2 . 1) (1 . 2))    # 0度回転パターン
+          ((0 . 0) (0 . 1) (0 . 2) (-1 . 2) (1 . 1)))  # 90度回転パターン
+        (map derivatives
+             '(((0 . 0) (0 . 1) (0 . 2) (1 . 2) (2 . 2))
+               ((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 0))
+               ((0 . 0) (0 . 1) (1 . 1) (2 . 1) (3 . 1))
+               ((0 . 0) (0 . 1) (1 . 1) (2 . 1) (2 . 2))
+               ((0 . 0) (0 . 1) (0 . 2) (1 . 1) (2 . 1))
+               ((0 . 0) (1 . 0) (1 . 1) (2 . 0) (3 . 0))
+               ((0 . 0) (1 . 0) (1 . 1) (0 . 1) (1 . 2))
+               ((0 . 0) (0 . 1) (0 . 2) (1 . 2) (1 . 3))
+               ((0 . 0) (0 . 1) (0 . 2) (1 . 0) (1 . 2))
+               ((0 . 0) (1 . 0) (0 . 1) (-1 . 1) (-1 . 2))
+               ((0 . 0) (0 . 1) (1 . 1) (-1 . 1) (0 . 2))))))
+  
 
 (define (paint-square origin offset color)
   (receive (x y) (x-sum&y-sum origin offset)
$

実行します(Celeron(R) M processor 1500MHz)。

gosh> (time (let1 n 0                                                           
              (%choco (make-chocomap) '(0 . 0) *pento-pieces* '()               
                      (lambda (_ cont)                                          
                        (if (zero? (modulo n 10))                               
                            (print n))                                          
                        (inc! n)                                                
                        (cont))                                                 
                      (lambda () n))))
0
10
20
30
40
50
：
：
2290
2300
2310
2320
2330
;(time (let1 n 0 (%choco (make-chocomap) '(0 . 0) *pento-pieces* '() (la ...    
; real 1761.349                                                                 
; user 1542.580                                                                 
; sys   16.160                                                                  
2339
gosh>

%chocoの第5引数は成功継続で、解が見つかったときに呼ばれる継続処理。第6引数は失敗継続で、可能な選択肢を探索しきって行き詰まったときに呼ばれる継続処理。バックトラックで本質的なのは失敗継続で、成功継続はこの場合はおまけ。