home *** CD-ROM | disk | FTP | other *** search
- ; 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
-