; 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