Phiras\’s Blog

December 19, 06

8-queen problem in LISP

Filed under: AI — phiras @ 1:08 am

Here is a simple lisp implementation to the 8-queen problem

(define mainDiag (vector #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f))
(define subDiag (vector #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f))
(define row (vector #f #f #f #f #f #f #f #f))
(define sol (vector 0 0 0 0 0 0 0 0))
(define solNum 0)

(define print (lambda (i j)
(if (< i 8 )
(begin (if (= j (vector-ref sol i)) (display ” Q “) (display ” X “))
(if (< j 8 ) (print i (+ 1 j)) (begin (newline) (print (+ i 1) 1)))
)
)
)
)

(define visit (lambda (r c)
(begin
(vector-set! row r #t)
(vector-set! subDiag (- (+ 8 c) r) #t)
(vector-set! mainDiag (+ c r) #t)
)
)
)

(define unVisit (lambda (r c)
(begin
(vector-set! row r #f)
(vector-set! subDiag (- (+ 8 c) r) #f)
(vector-set! mainDiag (+ c r) #f)
)
)
)

(define solve (lambda (c)
(if (= c 8 )
(begin (set! solNum (+ solNum 1)) (display “Solution : “)(display solNum) (newline) (display sol) (newline) (print 0 1) (newline))
(backTrackLoop 0 c)
)
)
)

(define backTrackLoop (lambda (r c)
(if (not (= r 8))
(if (and (not (vector-ref subDiag (- (+ 8 c) r)))
(not (vector-ref mainDiag (+ c r)))
(not (vector-ref row r)))
(begin (vector-set! sol c (+ 1 r)) (visit r c) (solve (+ c 1)) (unVisit r c) (backTrackLoop (+ r 1) c))
(backTrackLoop (+ r 1) c)
)
)
)
)

(solve 0)

2 Comments »

  1. Hi Jim. Photos i received. Thanks

    Comment by Bill Compton — June 4, 07 @ 7:20 pm

  2. sweet site thx

    Comment by kris — March 20, 08 @ 4:00 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: