Python —> puzzel
De getallen 1 t/m 8 moeten in de volgende vorm worden ingevuld (0 staat gelijk aan leeg):
De getallen die elkaar raken moeten minimaal 2 van elkaar verschillen. Dat geldt zowel horizontaal, verticaal als diagonaal. Voorbeeld: de getallen 1 en 2 mogen niet als volgt worden ingevuld.
Backtracking betekent dat je op een slimme manier en gericht de getal-combinaties invult en beoordeelt. Bij deze puzzel kun je linksboven met 1 beginnen. Vervolgens vul je in de cel ernaast een 2 in. Dan wordt al niet meer voldaan aan de eis. Backtracking betekent dat je dan ook niet verder gaat met de volgende cel helemaal links. De 2 wordt vervolgens opgehoogd naar 3. Dat voldoet. In de cel links wordt vervolgens een 2 ingevuld, die niet voldoet. Daarna een wel toegestane 4. Tussenresultaat:
Dit invulproces gaat door. Telkens wordt in een volgende cel het kleinste getal ingevuld dat is toegestaan. Dat gaat lang goed tot:
Er blijft nu nog één getal over, de 7. Die voldoet niet aan de voorwaarden. Nu ga je telkens één cel terug totdat er in die cel een groter getal ingevuld kan worden dat wel voldoet. Het nieuwe startpunt is:
Het proces wordt voortgezet en na 338 stappen blijkt dat vanuit de 1 linksboven geen oplossing gevonden kan worden. Dan zijn er nog 114 stappen nodig om te concluderen dat ook een 2 linksboven niet tot een oplossing gaat leiden. Een 3 leidt wel tot succes en geeft uiteindelijk als oplossing:
Hieronder staan alle processtappen die het algoritme heeft gezet. Een -1 geeft aan dat in die cel geen toegestaan getal mogelijk is en dat backtracking wordt uitgevoerd.
0: 0 0
0 0 0 0
0 0 uitgangssituatie
1: 1 0
0 0 0 0
0 0
2: 1 3
0 0 0 0
0 0
3: 1 3
4 0 0 0
0 0
4: 1 3
4 6 0 0
0 0
5: 1 3
4 6 8 0
0 0
6: 1 3
4 6 8 5
0 0
7: 1 3
4 6 8 5
2 0
8: 1 3
4 6 8 5
2 -1 backtrack
9: 1 3
4 6 8 5
-1 0 backtrack
10: 1 3
4 6 8 -1
0 0 backtrack
11: 1 3
4 6 -1 0
0 0 backtrack
12: 1 3
4 7 0 0
0 0
13: 1 3
4 7 5 0
0 0
14: 1 3
4 7 5 8
0 0
15: 1 3
4 7 5 8
2 0
16: 1 3
4 7 5 8
2 -1 backtrack
17: 1 3
4 7 5 8
-1 0 backtrack
18: 1 3
4 7 5 -1
0 0 backtrack
19: 1 3
4 7 -1 0
0 0 backtrack
20: 1 3
4 8 0 0
0 0
21: 1 3
4 8 5 0
0 0
22: 1 3
4 8 5 7
0 0
23: 1 3
4 8 5 7
2 0
24: 1 3
4 8 5 7
2 -1 backtrack
25: 1 3
4 8 5 7
-1 0 backtrack
26: 1 3
4 8 5 -1
0 0 backtrack
27: 1 3
4 8 6 0
0 0
28: 1 3
4 8 6 -1
0 0 backtrack
29: 1 3
4 8 -1 0
0 0 backtrack
30: 1 3
4 -1 0 0
0 0 backtrack
31: 1 3
5 0 0 0
0 0
32: 1 3
5 7 0 0
0 0
33: 1 3
5 7 -1 0
0 0 backtrack
34: 1 3
5 8 0 0
0 0
35: 1 3
5 8 6 0
0 0
36: 1 3
5 8 6 -1
0 0 backtrack
37: 1 3
5 8 -1 0
0 0 backtrack
38: 1 3
5 -1 0 0
0 0 backtrack
39: 1 3
6 0 0 0
0 0
40: 1 3
6 8 0 0
0 0
41: 1 3
6 8 5 0
0 0
42: 1 3
6 8 5 7
0 0
43: 1 3
6 8 5 7
2 0
44: 1 3
6 8 5 7
2 -1 backtrack
45: 1 3
6 8 5 7
-1 0 backtrack
46: 1 3
6 8 5 -1
0 0 backtrack
47: 1 3
6 8 -1 0
0 0 backtrack
48: 1 3
6 -1 0 0
0 0 backtrack
49: 1 3
7 0 0 0
0 0
50: 1 3
7 5 0 0
0 0
51: 1 3
7 5 8 0
0 0
52: 1 3
7 5 8 6
0 0
53: 1 3
7 5 8 6
2 0
54: 1 3
7 5 8 6
2 -1 backtrack
55: 1 3
7 5 8 6
-1 0 backtrack
56: 1 3
7 5 8 -1
0 0 backtrack
57: 1 3
7 5 -1 0
0 0 backtrack
58: 1 3
7 -1 0 0
0 0 backtrack
59: 1 3
8 0 0 0
0 0
60: 1 3
8 5 0 0
0 0
61: 1 3
8 5 7 0
0 0
62: 1 3
8 5 7 -1
0 0 backtrack
63: 1 3
8 5 -1 0
0 0 backtrack
64: 1 3
8 6 0 0
0 0
65: 1 3
8 6 -1 0
0 0 backtrack
66: 1 3
8 -1 0 0
0 0 backtrack
67: 1 3
-1 0 0 0
0 0 backtrack
68: 1 4
0 0 0 0
0 0
69: 1 4
3 0 0 0
0 0
70: 1 4
3 6 0 0
0 0
71: 1 4
3 6 8 0
0 0
72: 1 4
3 6 8 2
0 0
73: 1 4
3 6 8 2
-1 0 backtrack
74: 1 4
3 6 8 -1
0 0 backtrack
75: 1 4
3 6 -1 0
0 0 backtrack
76: 1 4
3 7 0 0
0 0
77: 1 4
3 7 -1 0
0 0 backtrack
78: 1 4
3 8 0 0
0 0
79: 1 4
3 8 6 0
0 0
80: 1 4
3 8 6 2
0 0
81: 1 4
3 8 6 2
-1 0 backtrack
82: 1 4
3 8 6 -1
0 0 backtrack
83: 1 4
3 8 -1 0
0 0 backtrack
84: 1 4
3 -1 0 0
0 0 backtrack
85: 1 4
5 0 0 0
0 0
86: 1 4
5 7 0 0
0 0
87: 1 4
5 7 -1 0
0 0 backtrack
88: 1 4
5 8 0 0
0 0
89: 1 4
5 8 6 0
0 0
90: 1 4
5 8 6 2
0 0
91: 1 4
5 8 6 2
3 0
92: 1 4
5 8 6 2
3 -1 backtrack
93: 1 4
5 8 6 2
-1 0 backtrack
94: 1 4
5 8 6 -1
0 0 backtrack
95: 1 4
5 8 -1 0
0 0 backtrack
96: 1 4
5 -1 0 0
0 0 backtrack
97: 1 4
6 0 0 0
0 0
98: 1 4
6 8 0 0
0 0
99: 1 4
6 8 -1 0
0 0 backtrack
100: 1 4
6 -1 0 0
0 0 backtrack
101: 1 4
7 0 0 0
0 0
102: 1 4
7 -1 0 0
0 0 backtrack
103: 1 4
8 0 0 0
0 0
104: 1 4
8 6 0 0
0 0
105: 1 4
8 6 -1 0
0 0 backtrack
106: 1 4
8 -1 0 0
0 0 backtrack
107: 1 4
-1 0 0 0
0 0 backtrack
108: 1 5
0 0 0 0
0 0
109: 1 5
3 0 0 0
0 0
110: 1 5
3 7 0 0
0 0
111: 1 5
3 7 -1 0
0 0 backtrack
112: 1 5
3 8 0 0
0 0
113: 1 5
3 8 -1 0
0 0 backtrack
114: 1 5
3 -1 0 0
0 0 backtrack
115: 1 5
4 0 0 0
0 0
116: 1 5
4 7 0 0
0 0
117: 1 5
4 7 3 0
0 0
118: 1 5
4 7 3 8
0 0
119: 1 5
4 7 3 8
-1 0 backtrack
120: 1 5
4 7 3 -1
0 0 backtrack
121: 1 5
4 7 -1 0
0 0 backtrack
122: 1 5
4 8 0 0
0 0
123: 1 5
4 8 3 0
0 0
124: 1 5
4 8 3 7
0 0
125: 1 5
4 8 3 7
6 0
126: 1 5
4 8 3 7
6 -1 backtrack
127: 1 5
4 8 3 7
-1 0 backtrack
128: 1 5
4 8 3 -1
0 0 backtrack
129: 1 5
4 8 -1 0
0 0 backtrack
130: 1 5
4 -1 0 0
0 0 backtrack
131: 1 5
6 0 0 0
0 0
132: 1 5
6 3 0 0
0 0
133: 1 5
6 3 7 0
0 0
134: 1 5
6 3 7 2
0 0
135: 1 5
6 3 7 2
-1 0 backtrack
136: 1 5
6 3 7 -1
0 0 backtrack
137: 1 5
6 3 8 0
0 0
138: 1 5
6 3 8 2
0 0
139: 1 5
6 3 8 2
-1 0 backtrack
140: 1 5
6 3 8 -1
0 0 backtrack
141: 1 5
6 3 -1 0
0 0 backtrack
142: 1 5
6 8 0 0
0 0
143: 1 5
6 8 3 0
0 0
144: 1 5
6 8 3 7
0 0
145: 1 5
6 8 3 7
-1 0 backtrack
146: 1 5
6 8 3 -1
0 0 backtrack
147: 1 5
6 8 -1 0
0 0 backtrack
148: 1 5
6 -1 0 0
0 0 backtrack
149: 1 5
7 0 0 0
0 0
150: 1 5
7 3 0 0
0 0
151: 1 5
7 3 8 0
0 0
152: 1 5
7 3 8 2
0 0
153: 1 5
7 3 8 2
-1 0 backtrack
154: 1 5
7 3 8 -1
0 0 backtrack
155: 1 5
7 3 -1 0
0 0 backtrack
156: 1 5
7 -1 0 0
0 0 backtrack
157: 1 5
8 0 0 0
0 0
158: 1 5
8 3 0 0
0 0
159: 1 5
8 3 7 0
0 0
160: 1 5
8 3 7 2
0 0
161: 1 5
8 3 7 2
-1 0 backtrack
162: 1 5
8 3 7 -1
0 0 backtrack
163: 1 5
8 3 -1 0
0 0 backtrack
164: 1 5
8 -1 0 0
0 0 backtrack
165: 1 5
-1 0 0 0
0 0 backtrack
166: 1 6
0 0 0 0
0 0
167: 1 6
3 0 0 0
0 0
168: 1 6
3 8 0 0
0 0
169: 1 6
3 8 4 0
0 0
170: 1 6
3 8 4 2
0 0
171: 1 6
3 8 4 2
-1 0 backtrack
172: 1 6
3 8 4 -1
0 0 backtrack
173: 1 6
3 8 -1 0
0 0 backtrack
174: 1 6
3 -1 0 0
0 0 backtrack
175: 1 6
4 0 0 0
0 0
176: 1 6
4 8 0 0
0 0
177: 1 6
4 8 3 0
0 0
178: 1 6
4 8 3 -1
0 0 backtrack
179: 1 6
4 8 -1 0
0 0 backtrack
180: 1 6
4 -1 0 0
0 0 backtrack
181: 1 6
5 0 0 0
0 0
182: 1 6
5 3 0 0
0 0
183: 1 6
5 3 8 0
0 0
184: 1 6
5 3 8 2
0 0
185: 1 6
5 3 8 2
-1 0 backtrack
186: 1 6
5 3 8 4
0 0
187: 1 6
5 3 8 4
-1 0 backtrack
188: 1 6
5 3 8 -1
0 0 backtrack
189: 1 6
5 3 -1 0
0 0 backtrack
190: 1 6
5 8 0 0
0 0
191: 1 6
5 8 3 0
0 0
192: 1 6
5 8 3 -1
0 0 backtrack
193: 1 6
5 8 4 0
0 0
194: 1 6
5 8 4 2
0 0
195: 1 6
5 8 4 2
-1 0 backtrack
196: 1 6
5 8 4 -1
0 0 backtrack
197: 1 6
5 8 -1 0
0 0 backtrack
198: 1 6
5 -1 0 0
0 0 backtrack
199: 1 6
7 0 0 0
0 0
200: 1 6
7 3 0 0
0 0
201: 1 6
7 3 8 0
0 0
202: 1 6
7 3 8 2
0 0
203: 1 6
7 3 8 2
5 0
204: 1 6
7 3 8 2
5 -1 backtrack
205: 1 6
7 3 8 2
-1 0 backtrack
206: 1 6
7 3 8 4
0 0
207: 1 6
7 3 8 4
5 0
208: 1 6
7 3 8 4
5 -1 backtrack
209: 1 6
7 3 8 4
-1 0 backtrack
210: 1 6
7 3 8 -1
0 0 backtrack
211: 1 6
7 3 -1 0
0 0 backtrack
212: 1 6
7 4 0 0
0 0
213: 1 6
7 4 8 0
0 0
214: 1 6
7 4 8 2
0 0
215: 1 6
7 4 8 2
-1 0 backtrack
216: 1 6
7 4 8 3
0 0
217: 1 6
7 4 8 3
2 0
218: 1 6
7 4 8 3
2 -1 backtrack
219: 1 6
7 4 8 3
-1 0 backtrack
220: 1 6
7 4 8 -1
0 0 backtrack
221: 1 6
7 4 -1 0
0 0 backtrack
222: 1 6
7 -1 0 0
0 0 backtrack
223: 1 6
8 0 0 0
0 0
224: 1 6
8 3 0 0
0 0
225: 1 6
8 3 -1 0
0 0 backtrack
226: 1 6
8 4 0 0
0 0
227: 1 6
8 4 -1 0
0 0 backtrack
228: 1 6
8 -1 0 0
0 0 backtrack
229: 1 6
-1 0 0 0
0 0 backtrack
230: 1 7
0 0 0 0
0 0
231: 1 7
3 0 0 0
0 0
232: 1 7
3 5 0 0
0 0
233: 1 7
3 5 -1 0
0 0 backtrack
234: 1 7
3 -1 0 0
0 0 backtrack
235: 1 7
4 0 0 0
0 0
236: 1 7
4 -1 0 0
0 0 backtrack
237: 1 7
5 0 0 0
0 0
238: 1 7
5 3 0 0
0 0
239: 1 7
5 3 -1 0
0 0 backtrack
240: 1 7
5 -1 0 0
0 0 backtrack
241: 1 7
6 0 0 0
0 0
242: 1 7
6 3 0 0
0 0
243: 1 7
6 3 5 0
0 0
244: 1 7
6 3 5 2
0 0
245: 1 7
6 3 5 2
8 0
246: 1 7
6 3 5 2
8 -1 backtrack
247: 1 7
6 3 5 2
-1 0 backtrack
248: 1 7
6 3 5 -1
0 0 backtrack
249: 1 7
6 3 -1 0
0 0 backtrack
250: 1 7
6 4 0 0
0 0
251: 1 7
6 4 -1 0
0 0 backtrack
252: 1 7
6 -1 0 0
0 0 backtrack
253: 1 7
8 0 0 0
0 0
254: 1 7
8 3 0 0
0 0
255: 1 7
8 3 5 0
0 0
256: 1 7
8 3 5 2
0 0
257: 1 7
8 3 5 2
-1 0 backtrack
258: 1 7
8 3 5 -1
0 0 backtrack
259: 1 7
8 3 -1 0
0 0 backtrack
260: 1 7
8 4 0 0
0 0
261: 1 7
8 4 -1 0
0 0 backtrack
262: 1 7
8 5 0 0
0 0
263: 1 7
8 5 3 0
0 0
264: 1 7
8 5 3 -1
0 0 backtrack
265: 1 7
8 5 -1 0
0 0 backtrack
266: 1 7
8 -1 0 0
0 0 backtrack
267: 1 7
-1 0 0 0
0 0 backtrack
268: 1 8
0 0 0 0
0 0
269: 1 8
3 0 0 0
0 0
270: 1 8
3 5 0 0
0 0
271: 1 8
3 5 -1 0
0 0 backtrack
272: 1 8
3 6 0 0
0 0
273: 1 8
3 6 4 0
0 0
274: 1 8
3 6 4 2
0 0
275: 1 8
3 6 4 2
-1 0 backtrack
276: 1 8
3 6 4 -1
0 0 backtrack
277: 1 8
3 6 -1 0
0 0 backtrack
278: 1 8
3 -1 0 0
0 0 backtrack
279: 1 8
4 0 0 0
0 0
280: 1 8
4 6 0 0
0 0
281: 1 8
4 6 3 0
0 0
282: 1 8
4 6 3 5
0 0
283: 1 8
4 6 3 5
-1 0 backtrack
284: 1 8
4 6 3 -1
0 0 backtrack
285: 1 8
4 6 -1 0
0 0 backtrack
286: 1 8
4 -1 0 0
0 0 backtrack
287: 1 8
5 0 0 0
0 0
288: 1 8
5 3 0 0
0 0
289: 1 8
5 3 6 0
0 0
290: 1 8
5 3 6 2
0 0
291: 1 8
5 3 6 2
-1 0 backtrack
292: 1 8
5 3 6 4
0 0
293: 1 8
5 3 6 4
-1 0 backtrack
294: 1 8
5 3 6 -1
0 0 backtrack
295: 1 8
5 3 -1 0
0 0 backtrack
296: 1 8
5 -1 0 0
0 0 backtrack
297: 1 8
6 0 0 0
0 0
298: 1 8
6 3 0 0
0 0
299: 1 8
6 3 5 0
0 0
300: 1 8
6 3 5 2
0 0
301: 1 8
6 3 5 2
-1 0 backtrack
302: 1 8
6 3 5 -1
0 0 backtrack
303: 1 8
6 3 -1 0
0 0 backtrack
304: 1 8
6 4 0 0
0 0
305: 1 8
6 4 -1 0
0 0 backtrack
306: 1 8
6 -1 0 0
0 0 backtrack
307: 1 8
7 0 0 0
0 0
308: 1 8
7 3 0 0
0 0
309: 1 8
7 3 5 0
0 0
310: 1 8
7 3 5 2
0 0
311: 1 8
7 3 5 2
-1 0 backtrack
312: 1 8
7 3 5 -1
0 0 backtrack
313: 1 8
7 3 6 0
0 0
314: 1 8
7 3 6 2
0 0
315: 1 8
7 3 6 2
-1 0 backtrack
316: 1 8
7 3 6 4
0 0
317: 1 8
7 3 6 4
-1 0 backtrack
318: 1 8
7 3 6 -1
0 0 backtrack
319: 1 8
7 3 -1 0
0 0 backtrack
320: 1 8
7 4 0 0
0 0
321: 1 8
7 4 6 0
0 0
322: 1 8
7 4 6 2
0 0
323: 1 8
7 4 6 2
-1 0 backtrack
324: 1 8
7 4 6 3
0 0
325: 1 8
7 4 6 3
2 0
326: 1 8
7 4 6 3
2 -1 backtrack
327: 1 8
7 4 6 3
-1 0 backtrack
328: 1 8
7 4 6 -1
0 0 backtrack
329: 1 8
7 4 -1 0
0 0 backtrack
330: 1 8
7 5 0 0
0 0
331: 1 8
7 5 3 0
0 0
332: 1 8
7 5 3 6
0 0
333: 1 8
7 5 3 6
-1 0 backtrack
334: 1 8
7 5 3 -1
0 0 backtrack
335: 1 8
7 5 -1 0
0 0 backtrack
336: 1 8
7 -1 0 0
0 0 backtrack
337: 1 8
-1 0 0 0
0 0 backtrack
338: 1 -1
0 0 0 0
0 0 backtrack
339: 2 0
0 0 0 0
0 0
340: 2 4
0 0 0 0
0 0
341: 2 4
5 0 0 0
0 0
342: 2 4
5 7 0 0
0 0
343: 2 4
5 7 -1 0
0 0 backtrack
344: 2 4
5 8 0 0
0 0
345: 2 4
5 8 6 0
0 0
346: 2 4
5 8 6 1
0 0
347: 2 4
5 8 6 1
3 0
348: 2 4
5 8 6 1
3 -1 backtrack
349: 2 4
5 8 6 1
-1 0 backtrack
350: 2 4
5 8 6 -1
0 0 backtrack
351: 2 4
5 8 -1 0
0 0 backtrack
352: 2 4
5 -1 0 0
0 0 backtrack
353: 2 4
6 0 0 0
0 0
354: 2 4
6 8 0 0
0 0
355: 2 4
6 8 -1 0
0 0 backtrack
356: 2 4
6 -1 0 0
0 0 backtrack
357: 2 4
7 0 0 0
0 0
358: 2 4
7 -1 0 0
0 0 backtrack
359: 2 4
8 0 0 0
0 0
360: 2 4
8 6 0 0
0 0
361: 2 4
8 6 -1 0
0 0 backtrack
362: 2 4
8 -1 0 0
0 0 backtrack
363: 2 4
-1 0 0 0
0 0 backtrack
364: 2 5
0 0 0 0
0 0
365: 2 5
4 0 0 0
0 0
366: 2 5
4 7 0 0
0 0
367: 2 5
4 7 -1 0
0 0 backtrack
368: 2 5
4 8 0 0
0 0
369: 2 5
4 8 -1 0
0 0 backtrack
370: 2 5
4 -1 0 0
0 0 backtrack
371: 2 5
6 0 0 0
0 0
372: 2 5
6 8 0 0
0 0
373: 2 5
6 8 -1 0
0 0 backtrack
374: 2 5
6 -1 0 0
0 0 backtrack
375: 2 5
7 0 0 0
0 0
376: 2 5
7 -1 0 0
0 0 backtrack
377: 2 5
8 0 0 0
0 0
378: 2 5
8 -1 0 0
0 0 backtrack
379: 2 5
-1 0 0 0
0 0 backtrack
380: 2 6
0 0 0 0
0 0
381: 2 6
4 0 0 0
0 0
382: 2 6
4 8 0 0
0 0
383: 2 6
4 8 -1 0
0 0 backtrack
384: 2 6
4 -1 0 0
0 0 backtrack
385: 2 6
5 0 0 0
0 0
386: 2 6
5 8 0 0
0 0
387: 2 6
5 8 4 0
0 0
388: 2 6
5 8 4 1
0 0
389: 2 6
5 8 4 1
-1 0 backtrack
390: 2 6
5 8 4 -1
0 0 backtrack
391: 2 6
5 8 -1 0
0 0 backtrack
392: 2 6
5 -1 0 0
0 0 backtrack
393: 2 6
7 0 0 0
0 0
394: 2 6
7 4 0 0
0 0
395: 2 6
7 4 8 0
0 0
396: 2 6
7 4 8 1
0 0
397: 2 6
7 4 8 1
-1 0 backtrack
398: 2 6
7 4 8 3
0 0
399: 2 6
7 4 8 3
1 0
400: 2 6
7 4 8 3
1 -1 backtrack
401: 2 6
7 4 8 3
-1 0 backtrack
402: 2 6
7 4 8 -1
0 0 backtrack
403: 2 6
7 4 -1 0
0 0 backtrack
404: 2 6
7 -1 0 0
0 0 backtrack
405: 2 6
8 0 0 0
0 0
406: 2 6
8 4 0 0
0 0
407: 2 6
8 4 -1 0
0 0 backtrack
408: 2 6
8 -1 0 0
0 0 backtrack
409: 2 6
-1 0 0 0
0 0 backtrack
410: 2 7
0 0 0 0
0 0
411: 2 7
4 0 0 0
0 0
412: 2 7
4 -1 0 0
0 0 backtrack
413: 2 7
5 0 0 0
0 0
414: 2 7
5 -1 0 0
0 0 backtrack
415: 2 7
6 0 0 0
0 0
416: 2 7
6 4 0 0
0 0
417: 2 7
6 4 -1 0
0 0 backtrack
418: 2 7
6 -1 0 0
0 0 backtrack
419: 2 7
8 0 0 0
0 0
420: 2 7
8 4 0 0
0 0
421: 2 7
8 4 -1 0
0 0 backtrack
422: 2 7
8 5 0 0
0 0
423: 2 7
8 5 -1 0
0 0 backtrack
424: 2 7
8 -1 0 0
0 0 backtrack
425: 2 7
-1 0 0 0
0 0 backtrack
426: 2 8
0 0 0 0
0 0
427: 2 8
4 0 0 0
0 0
428: 2 8
4 6 0 0
0 0
429: 2 8
4 6 -1 0
0 0 backtrack
430: 2 8
4 -1 0 0
0 0 backtrack
431: 2 8
5 0 0 0
0 0
432: 2 8
5 -1 0 0
0 0 backtrack
433: 2 8
6 0 0 0
0 0
434: 2 8
6 4 0 0
0 0
435: 2 8
6 4 -1 0
0 0 backtrack
436: 2 8
6 -1 0 0
0 0 backtrack
437: 2 8
7 0 0 0
0 0
438: 2 8
7 4 0 0
0 0
439: 2 8
7 4 6 0
0 0
440: 2 8
7 4 6 1
0 0
441: 2 8
7 4 6 1
-1 0 backtrack
442: 2 8
7 4 6 3
0 0
443: 2 8
7 4 6 3
1 0
444: 2 8
7 4 6 3
1 -1 backtrack
445: 2 8
7 4 6 3
-1 0 backtrack
446: 2 8
7 4 6 -1
0 0 backtrack
447: 2 8
7 4 -1 0
0 0 backtrack
448: 2 8
7 5 0 0
0 0
449: 2 8
7 5 -1 0
0 0 backtrack
450: 2 8
7 -1 0 0
0 0 backtrack
451: 2 8
-1 0 0 0
0 0 backtrack
452: 2 -1
0 0 0 0
0 0 backtrack
453: 3 0
0 0 0 0
0 0
454: 3 1
0 0 0 0
0 0
455: 3 1
5 0 0 0
0 0
456: 3 1
5 7 0 0
0 0
457: 3 1
5 7 -1 0
0 0 backtrack
458: 3 1
5 8 0 0
0 0
459: 3 1
5 8 6 0
0 0
460: 3 1
5 8 6 4
0 0
461: 3 1
5 8 6 4
2 0
462: 3 1
5 8 6 4
2 -1 backtrack
463: 3 1
5 8 6 4
-1 0 backtrack
464: 3 1
5 8 6 -1
0 0 backtrack
465: 3 1
5 8 -1 0
0 0 backtrack
466: 3 1
5 -1 0 0
0 0 backtrack
467: 3 1
6 0 0 0
0 0
468: 3 1
6 8 0 0
0 0
469: 3 1
6 8 5 0
0 0
470: 3 1
6 8 5 7
0 0
471: 3 1
6 8 5 7
2 0
472: 3 1
6 8 5 7
2 -1 backtrack
473: 3 1
6 8 5 7
-1 0 backtrack
474: 3 1
6 8 5 -1
0 0 backtrack
475: 3 1
6 8 -1 0
0 0 backtrack
476: 3 1
6 -1 0 0
0 0 backtrack
477: 3 1
7 0 0 0
0 0
478: 3 1
7 5 0 0
0 0
479: 3 1
7 5 8 0
0 0
480: 3 1
7 5 8 4
0 0
481: 3 1
7 5 8 4
2 0
482: 3 1
7 5 8 4
2 -1 backtrack
483: 3 1
7 5 8 4
-1 0 backtrack
484: 3 1
7 5 8 6
0 0
485: 3 1
7 5 8 6
2 0
486: 3 1
7 5 8 6
2 -1 backtrack
487: 3 1
7 5 8 6
-1 0 backtrack
488: 3 1
7 5 8 -1
0 0 backtrack
489: 3 1
7 5 -1 0
0 0 backtrack
490: 3 1
7 -1 0 0
0 0 backtrack
491: 3 1
8 0 0 0
0 0
492: 3 1
8 5 0 0
0 0
493: 3 1
8 5 7 0
0 0
494: 3 1
8 5 7 4
0 0
495: 3 1
8 5 7 4
2 0
496: 3 1
8 5 7 4
2 -1 backtrack
497: 3 1
8 5 7 4
-1 0 backtrack
498: 3 1
8 5 7 -1
0 0 backtrack
499: 3 1
8 5 -1 0
0 0 backtrack
500: 3 1
8 6 0 0
0 0
501: 3 1
8 6 -1 0
0 0 backtrack
502: 3 1
8 -1 0 0
0 0 backtrack
503: 3 1
-1 0 0 0
0 0 backtrack
504: 3 5
0 0 0 0
0 0
505: 3 5
1 0 0 0
0 0
506: 3 5
1 7 0 0
0 0
507: 3 5
1 7 -1 0
0 0 backtrack
508: 3 5
1 8 0 0
0 0
509: 3 5
1 8 -1 0
0 0 backtrack
510: 3 5
1 -1 0 0
0 0 backtrack
511: 3 5
6 0 0 0
0 0
512: 3 5
6 1 0 0
0 0
513: 3 5
6 1 7 0
0 0
514: 3 5
6 1 7 2
0 0
515: 3 5
6 1 7 2
4 0
516: 3 5
6 1 7 2
4 -1 backtrack
517: 3 5
6 1 7 2
-1 0 backtrack
518: 3 5
6 1 7 -1
0 0 backtrack
519: 3 5
6 1 8 0
0 0
520: 3 5
6 1 8 2
0 0
521: 3 5
6 1 8 2
4 0
522: 3 5
6 1 8 2
4 -1 backtrack
523: 3 5
6 1 8 2
-1 0 backtrack
524: 3 5
6 1 8 -1
0 0 backtrack
525: 3 5
6 1 -1 0
0 0 backtrack
526: 3 5
6 8 0 0
0 0
527: 3 5
6 8 1 0
0 0
528: 3 5
6 8 1 7
0 0
529: 3 5
6 8 1 7
4 0
530: 3 5
6 8 1 7
4 -1 backtrack
531: 3 5
6 8 1 7
-1 0 backtrack
532: 3 5
6 8 1 -1
0 0 backtrack
533: 3 5
6 8 -1 0
0 0 backtrack
534: 3 5
6 -1 0 0
0 0 backtrack
535: 3 5
7 0 0 0
0 0
536: 3 5
7 1 0 0
0 0
537: 3 5
7 1 8 0
0 0
538: 3 5
7 1 8 2
0 0
539: 3 5
7 1 8 2
4 0
540: 3 5
7 1 8 2
4 6
541: 3 5
7 1 8 2
4 6 eindsituatie, puzzel opgelost
De totale rekentijd bedraagt slechts 0,06 sec. (Windows laptop met i5 1035G1 processor).
Dit algoritme geeft één oplossing. Maar er zijn er meer. Besef namelijk dat de getallen, zowel verticaal als horizontaal gespiegeld kunnen worden. Dat geeft nog 3 andere oplossingen:
Dit blijken ook de enige 4 oplossingen te zijn. Dat is als volgt te beredeneren (vanuit de wetenschap dat een 1 en een 2 geen resultaat geven):
- Beginnen met een 1 of 2 linksboven gaf geen oplossing. Dat betekent dat ook een 7 en een 8 geen resultaat geeft. Immers, de 7 en 8 hebben dezelfde betekenis als de 1 en de 2 (denk aan de symmetrie in de reeks 1 t/m 8).
- Vanwege de symmetrie van de vorm, kunnen 1, 2, 7 en 8 ook niet rechtsboven, linksonder en rechtsonder. Deze 4 getallen moeten dus op de middelste rij.
- Stel dat 1 helemaal links komt te staan, dan kan 2 niet helemaal rechts, omdat 7 en 8 niet naast elkaar mogen.
- Maar de 2 mag uiteraard ook niet op de 2e positie, vlak naast de 1.
- De 2 moet dan wel op de derde positie van links. Je krijgt dan 1/7/2/8 of 1/8/2/7. Maar dan lukt het niet meer om de 3 te plaatsen. Die zou dan altijd aan de 2 grenzen.
- De 1 moet dus wel in het midden. Vanwege de symmetrie moet ook de 8 in het midden. Daarmee is de plek voor 2 en 7 ook bekend: 7/1/8/2.
- De 3 moet dan linksboven of linksonder. De 6 moet rechtsboven of rechtsonder. De 3 en de 6 mogen echter niet op dezelfde rij, omdat de 4 en de 5 dan naast elkaar zouden komen. Dus als de 3 linksboven komt, gaat de 6 naar rechtsonder.
- Tenslotte kan de 4 alleen nog linksonder en de 5 rechtsboven. Hiermee is de eerste oplossing beredeneerd. Dat het er 4 zijn komt omdat in stap 5 de 1 en 8 omgewisseld kunnen worden en in stap 6 twee varianten mogelijk zijn.
Deze redenering toont dat er 4 oplossingen zijn, wetende dat je niet met een 1, 2, 7 of 8 kunt starten. Het is heel logisch dat 1 en 8 centraal moeten staan. Deze hebben maar 1 buur, zodat ze in het midden het minst beperkend zijn. De 2 en de 7 kunnen dan alleen nog maar helemaal links en rechts. De 3, 4, 5 en 6 hebben dan al snel hun plek gevonden.
Om binnen Python de probleem te modelleren wordt de puzzelvorm gemakshalve platgeslagen tot een vector met 8 posities. Met 8 geneste loops kunnen dan de combinaties eenvoudig worden afgelopen. Aan 18 paren van 2 elementen binnen de vector wordt als eis gesteld dat het verschil minimaal 2 moet zijn, mits uiteraard beide elementen een waarde hebben gekregen. Deze 18 komen overeen met het aantal aan elkaar grenzende cellen binnen de puzzelvorm.
De enumeratie-methode vult eerst de hele vector en bepaalt dan of het een oplossing is. Als ervoor wordt gezorgd dat ieder getal maar één keer mag voorkomen, dan gaat het om ruim 40.000 verschillende vectoren. De rekentijd is maar iets langer dan bij backtracking, vanwege het relatief geringe aantal cellen. Als niet wordt geregeld dat binnen de geneste loops ieder getal slechts één keer mag voorkomen, dan zijn er bijna 17 mln. vectoren die beoordeeld moeten worden (8 tot de macht 8; de vector 1/1/1/1/1/1/1/1 komt dan bijvoorbeeld ook voor en wordt pas bij de beoordeling afgewezen). De rekentijd neemt dan aanzienlijk toe, tot zo’n 50 sec.
Mocht u geïnteresseerd zijn in de code, neem dan contact met mij op.