home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / archives / ckermit.zip / the8queens < prev    next >
Lisp/Scheme  |  2003-12-02  |  3KB  |  115 lines
  1. ; The 8 Queens Problem
  2. ; Dat Thuc Nguyen
  3. ; 25 November 2003
  4. ;
  5. ; Prof. Dr. Niklaus Wirth described the 8-Queens Problem in details at: 
  6. ; http://www.acm.org/classics/dec95/.
  7. ; Since the introduction of the S-Expression in C-Kermit 8.0, I saw that 
  8. ; Wirth's outlined solution can be implemented concisely in the C-Kermit 
  9. ; scripting language.
  10. ;
  11. ; The attached C-Kermit script provides 92 solutions as Wirth found.
  12. ; Thanks to both Frank da Cruz and Niklaus Wirth for an inspirational
  13. ; experience with the art of programming.
  14. ;
  15. ;  Wirth's solution for the 8 Queens problem enlightens me an elegant
  16. ; approach in software design: using simple data structure to unlock
  17. ; tricky logic. The 8 Queens problem has been considered as a typical
  18. ; theme in artificial intelligent research (backtracking!). After I
  19. ; understood Wirth's solution and implemented it with very simple data
  20. ; structures and codes, for me it' s demystified.
  21. ;
  22. ; The French writer Antoine De Saint-Expury once said :"A design is
  23. ; optimal NOT when there is nothing more to add, BUT when there is nothing
  24. ; more to remove."
  25.  
  26. ; to keep track of queen position (row, col)
  27. declare \&x[] 1 1 1 1 1 1 1 1 1
  28.  
  29. ; To keep track of queen position rowwise.
  30. declare \&a[] 1 1 1 1 1 1 1 1 1
  31.  
  32. ; To keep track of queen position on \ diagonal
  33. declare \&b[] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  34.  
  35. ; To keep track of queen position on / diagonal
  36. declare \&c[] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  37.  
  38. define considerfirstcolumn {
  39.        (setq j 1 i 0 cnt 0 safe 0)
  40. }
  41.  
  42. define considernextquare {
  43.        if ( < i 8 ) {
  44.           (++ i)
  45.           (setq safe (AND \&a[i] \&b[i+j-1] \&c[i-j+8]))
  46.        }
  47. }
  48.  
  49. define considernextcolumn {
  50.        (++ j)
  51.        (setq i 0)
  52. }
  53.  
  54. define reconsiderpriorcolumn {
  55.        (-- j)
  56.        (setq i \&x[j]) ; retrieve previous queen position on previous column
  57. }
  58.  
  59. define setqueen {
  60.        (setq \\&x[j]     i)    ; save queen position
  61.        (setq \\&a[i]     0)    ; mark unsafe row
  62.        (setq \\&b[i+j-1] 0)    ; mark unsafe \ diagonal
  63.        (setq \\&c[i-j+8] 0)    ; mark unsafe / diagonal
  64.        (setq safe 0)           ; reset global variable safe
  65. }
  66.  
  67. define removequeen {
  68.        (setq \\&a[i]     1)    ; mark safe row
  69.        (setq \\&b[i+j-1] 1)    ; mark safe \ diagonal
  70.        (setq \\&c[i-j+8] 1)    ; mark safe / diagonal
  71. }
  72.  
  73. define regress {
  74.        reconsiderpriorcolumn
  75.        removequeen
  76.        if ( > j 1 AND == i 8 ) {    ; not first column AND last square?
  77.              reconsiderpriorcolumn
  78.              removequeen
  79.        }
  80. }
  81.  
  82. define trycolumn {
  83.        while true {
  84.              considernextquare
  85.              if ( safe OR == i 8 ) break
  86.        }
  87. }
  88.  
  89. define show_solution {
  90.        (++ cnt)
  91.        echo
  92.        echo
  93.        echo \m(cnt). Solution - Place each Queen at:
  94.        for \%r 1 8 1 echo "    row \%r   col \&x[\%r]"
  95. }
  96.  
  97. considerfirstcolumn
  98. while true {
  99.       trycolumn
  100.       if ( safe ) {
  101.          setqueen
  102.          considernextcolumn
  103.          if ( > j 8 ) {            ; last column of this iteration done?
  104.         show_solution
  105.             regress            ; more solutions for this iteration?
  106.          }
  107.       } else { 
  108.          regress            ; try another iteration
  109.       }
  110.       if ( == i 8 AND == j 1 ) break    ; done last square of first column?
  111. }
  112. echo
  113. echo
  114. exit
  115.