1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
class KNIGHT
--
-- The classic KNIGHT problem on a N times N square chessboard.
-- The knight have to pass on all places of the chessboard once
-- a time. For instance, here is solution for a 7 X 7 chesboard,
-- knigth starting at position <1,1> :
--
-- 1 28 37 24 3 26 17
-- 36 39 2 27 18 11 4
-- 29 42 23 38 25 16 9
-- 40 35 30 19 10 5 12
-- 43 22 41 32 15 8 47
-- 34 31 20 45 48 13 6
-- 21 44 33 14 7 46 49
--
inherit ANY redefine print_on end;
creation make
feature
make is
local
size, line, column: INTEGER;
do
if argument_count >= 1 and then argument(1).is_integer then
size := argument(1).to_integer;
end;
if not size.in_range(chess_min,chess_max) then
size := ask("Chess-board size: ",chess_min,chess_max);
end;
if argument_count >= 2 and then argument(2).is_integer then
line := argument(2).to_integer;
end;
if not line.in_range(1,size) then
line := ask("Start line: ",1,size);
end
if argument_count >= 3 and then argument(3).is_integer then
column := argument(3).to_integer;
end;
if not column.in_range(1,size) then
column := ask("Start column: ",1,size);
end;
knight(size,line,column)
end;
feature {NONE}
chess_min: INTEGER is 3;
chess_max: INTEGER is 24;
chessboard: ARRAY2[INTEGER];
nb_tries: INTEGER;
tl: ARRAY[INTEGER] is
once
Result := <<-2,-1,1,2,2,1,-1,-2>>;
end;
tc: ARRAY[INTEGER] is
once
Result := <<1,2,2,1,-1,-2,-2,-1>>;
end;
knight(size, line, column: INTEGER) is
require
size >= 3;
1 <= line;
line <= size;
1 <= column;
column <= size;
do
!!chessboard.make(1,size,1,size);
chessboard.put(1,line,column);
if solution(line,column) then
print_on(std_output);
else
io.put_string("Sorry, there is no solution.%N");
end;
io.put_string("%NNumber of tries : ");
io.put_integer(nb_tries);
io.put_new_line;
end;
solution(line,column:INTEGER):BOOLEAN is
local
value,i : INTEGER;
do
if chessboard.count = chessboard.item(line,column) then
Result := true;
else
from
i := 1;
value := chessboard.item(line,column);
until
Result or else i > 8
loop
Result := try(line+tl.item(i),column+tc.item(i),value);
i := i + 1;
end;
end;
end;
try(line, column, value: INTEGER): BOOLEAN is
-- Try to place the knight by used cross back-tracking method.
do
nb_tries := nb_tries + 1;
if chessboard.valid_index(line,column) then
if chessboard.item(line,column) = 0 then
chessboard.put(value+1,line,column);
Result := solution(line,column);
if not Result then
chessboard.put(0,line,column)
end;
end;
end
end;
ask(s:STRING; min, max: INTEGER):INTEGER is
-- Ask for question `s' until the answer is in range `min' `max'.
local
stop: BOOLEAN;
do
from until stop
loop
io.put_string(s);
io.flush;
io.read_integer;
Result := io.last_integer;
if Result < min then
io.put_string("Value too small.%N");
elseif max < Result then
io.put_string("Value too big.%N");
else
stop := true;
end;
end;
end;
print_on(file: OUTPUT_STREAM) is
-- Display the cheesboard.
local
line,column : INTEGER;
separator : STRING;
do
from
create separator.make_filled(' ',3 * chessboard.upper1 + 1);
separator.fill_with('-');
separator.extend('%N')
file.put_string(separator);
line := chessboard.lower1
until
line > chessboard.upper1
loop
from
column := chessboard.lower2
until
column > chessboard.upper2
loop
if chessboard.item(line,column) < 10 then
file.put_string("| ");
else
file.put_character('|');
end;
file.put_integer(chessboard.item(line,column));
column := column + 1;
end;
file.put_string("|%N");
file.put_string(separator);
line := line + 1;
end;
end;
end -- KNIGHT
|
