home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Columbia Kermit
/
kermit.zip
/
ckscripts
/
the8queens
< prev
next >
Wrap
Lisp/Scheme
|
2020-01-01
|
3KB
|
115 lines
; The 8 Queens Problem
; Dat Thuc Nguyen
; 25 November 2003
;
; Prof. Dr. Niklaus Wirth described the 8-Queens Problem in details at:
; http://www.acm.org/classics/dec95/.
; Since the introduction of the S-Expression in C-Kermit 8.0, I saw that
; Wirth's outlined solution can be implemented concisely in the C-Kermit
; scripting language.
;
; The attached C-Kermit script provides 92 solutions as Wirth found.
; Thanks to both Frank da Cruz and Niklaus Wirth for an inspirational
; experience with the art of programming.
;
; Wirth's solution for the 8 Queens problem enlightens me an elegant
; approach in software design: using simple data structure to unlock
; tricky logic. The 8 Queens problem has been considered as a typical
; theme in artificial intelligent research (backtracking!). After I
; understood Wirth's solution and implemented it with very simple data
; structures and codes, for me it' s demystified.
;
; The French writer Antoine De Saint-Expury once said :"A design is
; optimal NOT when there is nothing more to add, BUT when there is nothing
; more to remove."
; to keep track of queen position (row, col)
declare \&x[] 1 1 1 1 1 1 1 1 1
; To keep track of queen position rowwise.
declare \&a[] 1 1 1 1 1 1 1 1 1
; To keep track of queen position on \ diagonal
declare \&b[] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
; To keep track of queen position on / diagonal
declare \&c[] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
define considerfirstcolumn {
(setq j 1 i 0 cnt 0 safe 0)
}
define considernextquare {
if ( < i 8 ) {
(++ i)
(setq safe (AND \&a[i] \&b[i+j-1] \&c[i-j+8]))
}
}
define considernextcolumn {
(++ j)
(setq i 0)
}
define reconsiderpriorcolumn {
(-- j)
(setq i \&x[j]) ; retrieve previous queen position on previous column
}
define setqueen {
(setq \\&x[j] i) ; save queen position
(setq \\&a[i] 0) ; mark unsafe row
(setq \\&b[i+j-1] 0) ; mark unsafe \ diagonal
(setq \\&c[i-j+8] 0) ; mark unsafe / diagonal
(setq safe 0) ; reset global variable safe
}
define removequeen {
(setq \\&a[i] 1) ; mark safe row
(setq \\&b[i+j-1] 1) ; mark safe \ diagonal
(setq \\&c[i-j+8] 1) ; mark safe / diagonal
}
define regress {
reconsiderpriorcolumn
removequeen
if ( > j 1 AND == i 8 ) { ; not first column AND last square?
reconsiderpriorcolumn
removequeen
}
}
define trycolumn {
while true {
considernextquare
if ( safe OR == i 8 ) break
}
}
define show_solution {
(++ cnt)
echo
echo
echo \m(cnt). Solution - Place each Queen at:
for \%r 1 8 1 echo " row \%r col \&x[\%r]"
}
considerfirstcolumn
while true {
trycolumn
if ( safe ) {
setqueen
considernextcolumn
if ( > j 8 ) { ; last column of this iteration done?
show_solution
regress ; more solutions for this iteration?
}
} else {
regress ; try another iteration
}
if ( == i 8 AND == j 1 ) break ; done last square of first column?
}
echo
echo
exit