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
|
class PYRAMID2
--
-- Run faster than pyramid.e
--
inherit ANY redefine print_on end;
creation make
feature {NONE}
pyramid: ARRAY2[INTEGER];
used: ARRAY[BOOLEAN]; -- Already used numbers in `pyramid'.
make is
local
size: INTEGER;
do
if argument_count = 0 then
io.put_string("Size of the pyramid %
% (a small number greater than 1) : ");
io.flush;
io.read_integer;
io.put_new_line;
size := io.last_integer;
else
size := argument(1).to_integer;
end;
io.put_string("I am working...%N");
fill(size);
end;
fill(size: INTEGER) is
-- Fill in a `pyramid' of `size' elements.
require
size > 1
do
!!used.make(1, (size+1) * size // 2);
!!pyramid.make(1,size,1,size);
if solution(1) then
print_on(std_output)
else
io.put_string("Sorry I can't find a solution.%N");
end;
end;
put(value, line, column: INTEGER) is
-- Updtate `pyramid' and `used'.
do
used.put(true,value);
pyramid.put(value,line,column);
end;
remove(line,column :INTEGER) is
-- Updtate `pyramid' and `used'.
do
if pyramid.item(line,column) /= 0 then
used.put(false,pyramid.item(line,column));
pyramid.put(0,line,column);
end;
end;
solution(column:INTEGER): BOOLEAN is
-- Search a solution using a back-tracking algorithm.
local
nb, i: INTEGER;
do
if column > pyramid.upper1 then
Result := true;
else
from
nb := used.upper
until
Result or nb = 0
loop
if not used.item(nb) then
Result := fill_column(column,nb)
end;
if not Result then
from
i := pyramid.lower1
until
pyramid.item(i,column) = 0 or else i > pyramid.upper1
loop
remove(i,column);
i := i + 1;
end;
end;
nb := nb - 1;
end;
end;
end;
fill_column(col, val: INTEGER): BOOLEAN is
local
v, i: INTEGER;
do
from
i := 2;
put(val,1,col);
until
i > col or Result
loop
v := (pyramid.item(i-1,col-1)-pyramid.item(i-1,col)).abs
if used.item(v) then
Result := true;
else
put(v,i,col);
i := i + 1;
end;
end;
if Result then
from
until
i < used.lower
loop
remove(i,col);
i := i-1;
end;
Result := false;
else
Result := solution(col+1);
end;
end;
print_on(file: OUTPUT_STREAM) is
-- Display the pyramid to the standart output.
local
line, column: INTEGER;
blanks: STRING;
do
from
file.put_string("%NSolution found : %N");
line := pyramid.lower1;
!!blanks.make(0);
until
line > pyramid.upper1
loop
file.put_string(blanks);
from
column := pyramid.lower2
until
column > pyramid.upper2
loop
if pyramid.item(line,column) /= 0 then
file.put_integer(pyramid.item(line,column));
file.put_string(" ");
end;
column := column + 1;
end;
file.put_new_line;
line := line+1;
blanks.add_last(' ');
end;
end;
end -- PYRAMID2
|
