home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / me34src.zip / me3 / mutt / package / queen.mut < prev    next >
Lisp/Scheme  |  1995-01-14  |  2KB  |  83 lines
  1.   ;; place N queens on a NxN board
  2.   ;; C Durland    Public Domain
  3.  
  4. (include me.mh)
  5.  
  6. (array small-int boardx 20 boardy 20)
  7. (small-int nQueens N)
  8.  
  9. (defun
  10.   put-queen (int x y)(s)
  11.   {
  12.     (move-cursor (+ y 1) (+ 1 (* x 2)) (concat s));(update)
  13.   }
  14.   print-board
  15.   {
  16.     (move-cursor 0 0 ".---------------.")
  17.     (move-cursor 1 0 "|*|*|*|*|*|*|*|*|")
  18.     (move-cursor 2 0 "|*|*|*|*|*|*|*|*|")
  19.     (move-cursor 3 0 "|*|*|*|*|*|*|*|*|")
  20.     (move-cursor 4 0 "|*|*|*|*|*|*|*|*|")
  21.     (move-cursor 5 0 "|*|*|*|*|*|*|*|*|")
  22.     (move-cursor 6 0 "|*|*|*|*|*|*|*|*|")
  23.     (move-cursor 7 0 "|*|*|*|*|*|*|*|*|")
  24.     (move-cursor 8 0 "|*|*|*|*|*|*|*|*|")
  25.     (move-cursor 9 0 "`---------------'")
  26.   }
  27. )
  28.  
  29.  
  30. (defun
  31.   print-solution
  32.   {
  33.     (int j)
  34.     (for (j 0)(< j N)(+= j 1) (msg "(" (boardx j) "," (boardy j) ")"))
  35.   }
  36.   threat (int a b x y)
  37.   {
  38.     (or
  39.       (== a x)(== b y)
  40.       (== (- a b)(- x y))
  41.       (== (+ a b)(+ x y))
  42.     )
  43.   }
  44.   conflict (int x y)
  45.   {
  46.     (int n)
  47.     (for (n 0)(< n nQueens)(+= n 1)
  48.       (if (threat x y (boardx n) (boardy n)) { TRUE (done) }))
  49.     FALSE
  50.   }
  51.   fill-board (int x y)
  52.   {
  53.     (int i j z)(z x)
  54.  
  55.     (for (i z)(< i N)(+= i 1)
  56.     {
  57.       (for (j z)(< j N)(+= j 1)
  58.       {
  59.         (if (conflict i j) ()
  60.     {
  61.       (put-queen i j nQueens)
  62.       (boardx nQueens i)(boardy nQueens j)(+= nQueens 1)
  63.       (fill-board i j)
  64.       (if (== nQueens N){ TRUE (done) })
  65.       (-= nQueens 1)(put-queen i j ".")
  66.     })
  67.       })
  68.       (z 0)
  69.     })
  70.     FALSE
  71.   }
  72.   Queens
  73.   {
  74.     (N (convert-to NUMBER (ask "Number of queens (max 8) = ")))
  75.     (if (or (> N 8) (< N 1)) { (msg "Bogus number of queens")(done) })
  76.     (nQueens 0)(print-board)
  77.     (if (fill-board 0 0) { (msg "done") (get-key) }
  78.     (msg "No solution"))
  79.   }
  80. )
  81.  
  82. (defun MAIN { (Queens) })
  83.