Advertisement
PhilDrummer

Assignment_8 03 PUZZLE.e

Nov 23rd, 2014
1,099
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. note
  2.     description: "N-queens puzzle."
  3.  
  4. class
  5.     PUZZLE
  6.  
  7. feature -- Access
  8.  
  9.     size: INTEGER
  10.             -- Size of the board.
  11.  
  12.     solutions: LIST [SOLUTION]
  13.             -- All solutions found by the last call to `solve'.
  14.  
  15.     trivial_foundation: SOLUTION
  16.             -- Holds one solution.
  17.  
  18. feature -- Basic operations
  19.  
  20.     solve (n: INTEGER)
  21.             -- Solve the puzzle for `n' queens.
  22.         require
  23.             n_positive: n > 0
  24.         local
  25.             i: INTEGER
  26.         do
  27.             size := n
  28.             create {LINKED_LIST [SOLUTION]} solutions.make
  29.  
  30.                 -- Call feature complete with the trivial foundations.
  31.             from
  32.                 i := 1
  33.             until
  34.                 i > size
  35.             loop
  36.                 if
  37.                     size = 1
  38.                 then
  39.                     create trivial_foundation.make_empty
  40.                     trivial_foundation := trivial_foundation.extended_with (1)
  41.                     solutions.extend (trivial_foundation)
  42.                 else
  43.                     create trivial_foundation.make_empty
  44.                     trivial_foundation := trivial_foundation.extended_with (i)
  45.                     complete (trivial_foundation)
  46.                 end
  47.                 i := i + 1
  48.             end
  49.  
  50.         ensure
  51.             solutions_exists: solutions /= Void
  52.             complete_solutions: across solutions as s all s.item.row_count = n end
  53.         end
  54.  
  55. feature {NONE} -- Implementation
  56.  
  57.     complete (partial: SOLUTION)
  58.             -- Find all complete solutions that extend the partial solution `partial'
  59.             -- and add them to `solutions'.
  60.         require
  61.             partial_exists: partial /= Void
  62.         local
  63.             i: INTEGER
  64.             new_partial: SOLUTION
  65.         do
  66.             from
  67.                 i := 1
  68.             until
  69.                 i > size
  70.             loop
  71.                 if
  72.                     under_attack (partial, i) = false
  73.                 then
  74.                     new_partial := partial.extended_with (i)
  75.                     if
  76.                         new_partial.row_count < size
  77.                     then
  78.                         complete (new_partial)
  79.                     else
  80.                         solutions.extend (new_partial)
  81.                     end
  82.                 end
  83.                 i := i + 1
  84.             end
  85.         end
  86.  
  87.     under_attack (partial: SOLUTION; c: INTEGER): BOOLEAN
  88.             -- Is column `c' of the current row under attack
  89.             -- by any queen already placed in partial solution `partial'?
  90.         require
  91.             partial_exists: partial /= Void
  92.         local
  93.             current_row, row: INTEGER
  94.         do
  95.             current_row := partial.row_count + 1
  96.             from
  97.                 row := 1
  98.             until
  99.                 Result or row > partial.row_count
  100.             loop
  101.                 Result := attack_each_other (row, partial.column_at (row), current_row, c)
  102.                 row := row + 1
  103.             end
  104.         end
  105.  
  106.     attack_each_other (row1, col1, row2, col2: INTEGER): BOOLEAN
  107.             -- Do queens in positions (`row1', `col1') and (`row2', `col2') attack each other?
  108.         local
  109.             temp1, temp2: INTEGER
  110.         do
  111.             temp1 := (col2 - col1)
  112.             temp2 := (row2 - row1)
  113.             if
  114.                 col1 = col2
  115.             then
  116.                 Result := true
  117.             elseif
  118.                 temp1.abs = temp2.abs
  119.             then
  120.                 Result := true
  121.             else
  122.                 Result := false
  123.             end
  124.         end
  125.  
  126. end
Advertisement
RAW Paste Data Copied
Advertisement