home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / euphoria / queens.ex < prev    next >
Text File  |  1994-01-31  |  2KB  |  93 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. -- Usage: ex queens | more
  5.  
  6. without type_check
  7.  
  8. constant N = 8 -- try some other sizes
  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.  
  53.     printf(1, "Solution #%d\n\n  ", soln)
  54.     for c = 'a' to 'a' + N - 1 do
  55.     printf(1, "%2s", c)
  56.     end for
  57.     puts(1, "\n")
  58.     for r = 1 to N do
  59.     printf(1, "%2d ", r)
  60.     for c = 1 to N do
  61.         if find({r,c}, queens) then
  62.         puts(1, "Q ")
  63.         else
  64.         puts(1, ". ")
  65.         end if
  66.     end for
  67.     puts(1, "\n")
  68.     end for
  69.     puts(1, "\n\n")
  70. end procedure
  71.  
  72. procedure place_queen(sequence queens)
  73. -- place queens on a NxN chess board
  74. -- (recursive procedure)
  75.     row r -- only need to consider one row for each queen
  76.  
  77.     r = length(queens)+1
  78.     if r > N then
  79.     soln = soln + 1
  80.     print_board(queens)
  81.     return
  82.     end if
  83.     for c = 1 to N do
  84.     if not conflict({r,c}, queens) then
  85.         place_queen(append(queens, {r,c}))
  86.     end if
  87.     end for
  88. end procedure
  89.  
  90. place_queen({})
  91.  
  92.  
  93.