home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / mutt / queen.mut < prev    next >
Text File  |  1988-08-11  |  2KB  |  79 lines
  1. ; place N queens on a NxN board
  2.  
  3. (array int boardx 20 boardy 20)
  4. (int nQueens N)
  5.  
  6. (defun
  7.   put-queen (int x y)(s)
  8.   {
  9.     (move-cursor (+ y 1) (+ 1 (* x 2)))(puts s)(update)
  10.   }
  11.   print-board
  12.   {
  13.     (move-cursor 0 0)
  14.     (puts ".---------------.^M^J")
  15.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  16.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  17.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  18.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  19.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  20.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  21.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  22.     (puts "|*|*|*|*|*|*|*|*|^M^J")
  23.     (puts "`---------------'")
  24.   }
  25. )
  26.  
  27.  
  28. (defun
  29.   print-solution
  30.   {
  31.     (int j)
  32.     (for (j 0)(< j N)(+= j 1) (msg "(" (boardx j) "," (boardy j) ")"))
  33.   }
  34.   threat (int a b x y)
  35.   {
  36.     (or
  37.       (== a x)(== b y)
  38.       (== (- a b)(- x y))
  39.       (== (+ a b)(+ x y))
  40.     )
  41.   }
  42.   conflict (int x y)
  43.   {
  44.     (int n)
  45.     (for (n 0)(< n nQueens)(+= n 1)
  46.       (if (threat x y (boardx n) (boardy n)) { TRUE (done) }))
  47.     FALSE
  48.   }
  49.   fill-board (int x y)
  50.   {
  51.     (int i j z)(z x)
  52.  
  53.     (for (i z)(< i N)(+= i 1)
  54.     {
  55.       (for (j z)(< j N)(+= j 1)
  56.       {
  57.         (if (conflict i j) ()
  58.     {
  59.       (put-queen i j nQueens)
  60.       (boardx nQueens i)(boardy nQueens j)(+= nQueens 1)
  61.       (fill-board i j)
  62.       (if (== nQueens N){ TRUE (done) })
  63.       (-= nQueens 1)(put-queen i j ".")
  64.     })
  65.       })
  66.       (z 0)
  67.     })
  68.     FALSE
  69.   }
  70.   Queens
  71.   {
  72.     (N (atoi (ask "Number of queens = ")))
  73.     (nQueens 0)(print-board)
  74.     (if (fill-board 0 0) (msg "done")
  75.     (msg "No solution"))
  76.   }
  77. )
  78. (Queens)
  79.