 # 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
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