home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / misc / euphoria / queens.ex < prev    next >
Encoding:
Text File  |  1994-04-05  |  2.1 KB  |  104 lines
  1. -- The N Queens Problem:
  2. -- Place N Queens on an NxN chess board
  3. -- such that they don't threaten each other.
  4.  
  5. without type_check
  6.  
  7. constant N = 8 -- try some other sizes
  8.  
  9. constant ROW = 1, COLUMN = 2
  10. constant TRUE = 1, FALSE = 0
  11.  
  12. type square(sequence x)
  13. -- a square on the board
  14.     return length(x) = 2
  15. end type
  16.  
  17. type row(integer x)
  18. -- a row on the board
  19.     return x >= 1 and x <= N
  20. end type
  21.  
  22. function threat(square q1, square q2)
  23. -- do two queens threaten each other?
  24.     if q1[COLUMN] = q2[COLUMN] then
  25.     return TRUE
  26.     elsif q1[ROW] - q1[COLUMN] = q2[ROW] - q2[COLUMN] then
  27.     return TRUE
  28.     elsif q1[ROW] + q1[COLUMN] = q2[ROW] + q2[COLUMN] then
  29.     return TRUE
  30.     elsif q1[ROW] = q2[ROW] then
  31.     return TRUE
  32.     else
  33.     return FALSE
  34.     end if
  35. end function
  36.  
  37. function conflict(square q, sequence queens)
  38. -- Would square p cause a conflict with other queens on board so far?
  39.     for i = 1 to length(queens) do
  40.     if threat(q, queens[i]) then
  41.         return TRUE
  42.     end if
  43.     end for
  44.     return FALSE
  45. end function
  46.  
  47. integer soln
  48. soln = 0 -- solution number
  49.  
  50. procedure print_board(sequence queens)
  51. -- print a solution, showing the Queens on the board
  52.     integer k
  53.  
  54.     position(1, 1)
  55.     printf(1, "Solution #%d\n\n  ", soln)
  56.     for c = 'a' to 'a' + N - 1 do
  57.     printf(1, "%2s", c)
  58.     end for
  59.     puts(1, "\n")
  60.     for r = 1 to N do
  61.     printf(1, "%2d ", r)
  62.     for c = 1 to N do
  63.         if find({r,c}, queens) then
  64.         puts(1, "Q ")
  65.         else
  66.         puts(1, ". ")
  67.         end if
  68.     end for
  69.     puts(1, "\n")
  70.     end for
  71.     puts(1, "\nPress Enter. (q to quit) ")
  72.     while TRUE do
  73.     k = get_key()
  74.     if k = 'q' then
  75.         abort(1)
  76.     elsif k != -1 then
  77.         exit
  78.     end if
  79.     end while
  80. end procedure
  81.  
  82. procedure place_queen(sequence queens)
  83. -- place queens on a NxN chess board
  84. -- (recursive procedure)
  85.     row r -- only need to consider one row for each queen
  86.  
  87.     r = length(queens)+1
  88.     if r > N then
  89.     soln = soln + 1
  90.     print_board(queens)
  91.     return
  92.     end if
  93.     for c = 1 to N do
  94.     if not conflict({r,c}, queens) then
  95.         place_queen(append(queens, {r,c}))
  96.     end if
  97.     end for
  98. end procedure
  99.  
  100. clear_screen()
  101. place_queen({})
  102.  
  103.  
  104.