; 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