저는 무작위로 보드에 여왕벌을 채워서 Scheme에서 N-Queens 문제를 해결하려고합니다. 그들의 열 내의 여왕을 가장 적은 수의 왕비가 공격하는 행으로 이동시킨다.Scheme - Hill-climbing/min-conflict 방법을 사용하여 NQueens를 해결합니다
내 알고리즘은 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))
)
))
보드의 모든 왕비가 이동 된 경우 문 여부를 확인하는 경우 첫 번째. 그들이 가지고있는 경우 충돌이 있는지 검사합니다 ((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 " ")
))
편집 : 아마도 문제는 내 (해결) 함수가 열을 반복하는 방식이라고 생각합니다. 항상 증가하는 순서로 진행하는 경우 처음 몇 개의 열에 충돌이 없지만 합법적 인 솔루션이 될 수없는 위치에 있으면 나머지 열은 최소한의 충돌은 발생하지 않지만 충돌은 거의 발생하지 않습니다.