2 つのクイーンが同じ行または列にならないようにボードにクイーンをランダムに配置し、列内のクイーンを最も少ない数で攻撃されている行に移動することにより、Scheme の N-Queens 問題を解決しようとしています。女王の。
私のアルゴリズムは、6 未満の任意のサイズのボードで機能します。6 以上のボード サイズがパラメーターとして使用される場合、プログラムは無限に再帰するように見えます。
すべてのコードを追加しますが、無限再帰が発生すると思われる部分は次のとおりです。
(define (solve col)
(if (= col (vector-length board))
(begin
(do ((i 0 (+ i 1))) ((>= i (vector-length board)))
(if (not (= (move i) 0))
(set! legal #f))
)
(if (eqv? legal #t)
(begin
(display steps)
(newline)
(display board)
)
(begin
;(random-fill (build-list (vector-length board) add)) ;
(display board)
(solve 0))
)
)
(begin
(move col)
(solve (+ col 1))
)
))
最初の if ステートメントは、ボード上のすべてのクイーンが移動されたかどうかを確認します。競合がある場合は、競合があるかどうかを確認します ((move i) は、競合がない場合は 0 を返します)。競合がある場合、フラグが立てられ、プログラムはクイーンの移動を続行します。
ここで問題です。パズルは最初のパスで解決されるか、まったく解決されません。最初のパスの後にボードが合法である場合、明らかに問題はなく、すべて問題ありません。ただし、そうでない場合は、同じボードが何度も試行され続けます。これは、コードの (ディスプレイ ボード) チェックのおかげでわかります。
ボード サイズが 6 を超えると、最初のパスでパズルが解ける可能性が低いため、コードは機能しないと思います。新しいランダム ボードを作成する行を追加しようとしましたが、その時点で実行時間が最悪で、役に立ちません。
以下にプログラムのコードを示します。ご不明な点がございましたら、お気軽にお問い合わせください。
#lang swindle
(define steps 0)
(define board (make-vector 0))
(define legal #t)
;function to be called for hill-climbing method of solving problem
(define (nq-mc size)
(set! steps 0)
(set! board (make-vector size))
(random-fill (build-list size add))
(set! legal #t)
(solve 0)
;writes solution to txt file
(define out-board (open-output-file "board-mc.txt" 'replace))
(iter-write board out-board)
(close-output-port out-board)
)
;function for filling board randomly, no queens will be on same row or col
(define (random-fill list)
(if (eqv? list '())
(display board)
(let ([var (random-element list)])
(vector-set! board (- (length list) 1) var)
(random-fill (remv var list))
)
))
;helper function for randomization, retrieves random number from legal options
(define (random-element list)
(list-ref list (random (length list))))
(define (solve col)
(if (= col (vector-length board))
(begin
(do ((i 0 (+ i 1))) ((>= i (vector-length board)))
(if (not (= (move i) 0))
(set! legal #f))
)
(if (eqv? legal #t)
(begin
(display steps)
(newline)
(display board)
)
(begin
;(random-fill (build-list (vector-length board) add))
(display board)
(solve 0))
)
)
(begin
(move col)
(solve (+ col 1))
)
))
;moves a queen to location of least-conflict
(define (move col)
(let ((conf-vec (make-vector (vector-length board))))
(do ((i 0 (+ i 1))) ((= i (vector-length board)))
(vector-set! conf-vec i (conflicts i col))
)
(let ((min (vector-ref conf-vec 0)))
(do ((i 0 (+ i 1))) ((= i (vector-length board)))
(cond [(< (vector-ref conf-vec i) (vector-ref conf-vec min))
(set! min i)]
[(= (vector-ref conf-vec i) (vector-ref conf-vec min))
(if (not (eqv? (vector-ref board col) i))
(if (= (random 2) 0)
(set! min i)
)
)]
)
)
(vector-set! board col min)
(vector-ref conf-vec min))
))
;function for determining how many queens are attacking a space
(define (conflicts row col)
(define conflict 0)
(do ((i 0 (+ i 1))) ((= i (vector-length board)))
(set! steps (+ steps 1))
(cond [(= i col) (+ conflict 0)]
[(= (vector-ref board i) row)
(set! conflict (+ conflict 1))]
[(= (abs (- i col)) (abs (- (vector-ref board i) row)))
(set! conflict (+ conflict 1))]
)
)
conflict)
;helper function for writing output to file in a easily machine-readable fashion
(define (iter-write vector out-port)
(do ((i 0 (+ i 1))) ((= i (vector-length board)))
(write (vector-ref vector i) out-port)
(fprintf out-port " ")
))
編集:おそらく問題は、私の(解決)関数が列を反復する方法であると考えています。常に昇順で行けば、最初の数列の競合がゼロであるが、合法的な解決策にならない場所にある場合、残りの列は競合が最も少ない場所に移動されますが、競合がゼロになることはありません。