R3 R2 R1
S E N D
+ M O R E
------------------------
= M O N E Y
S,E,N,D,M,O,R,Y in {0,1,2,3,4,5,6,7,8,9}
SEND + MORE = MONEY
R1,R2,R3 in {0,1}
S <> E <> N <> D <> M <> O <> R <> Y
S <> 0
M <> 0
D + E = Y + 10*R1
N + R + R1 = E + 10*R2
E + O + R2 = N + 10*R3
S + M + R3 = O + 10*M
3
S E N D
+ M O R E
-----------------
= M O N E Y
- celem zadania jest takie podstawienie cyfr za litery, aby
równanie było spełnione.
Hetmani
Ograniczenia:
- każda litera odpowiada innej cyfrze
- cyfry początkowe nie mogą być zerem
Rozwiązanie:
9567 + 1085 = 10652
S=9 E=5 N=6 D=7 M=1 O=0 R=8 Y=2
2
Osiem hetmanów: Przegląd zupełny:
- celem zadania jest takie ustawienie 8 hetmanów na szachownicy, - najpierw generujemy rozwiązanie (zastępujemy wszystkie zmienne
by się wzajemnie nie atakowały. stałymi) a następnie testujemy, czy spełnia ono ograniczenia
- w tym konkretnym przypadku musimy wygenerować 4! = 24
permutacje zbioru {1,2,3,4} i każdą z nich sprawdzić
Ograniczenia:
[ ]
- każdy hetman jest w osobnym wierszu / osobnej kolumnie
(czyli nie atakują się w poziomie i w pionie)
- każdy hetman nie atakuje innego hetmana po skosie
1 2 3 4
Rozwiązanie: 2 3 4 1 3 4 1 2 4 1 2 3
Przykładowe rozwiązanie to: [1,5,8,6,3,7,2,4]
3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2
Wszystkich rozwiązań jest 92.
4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1
5 7
[2,4,1,3] [3,1,4,2]
Czterech hetmanów: Metoda nawrotów (standard backtracking):
- dla uproszczenia zostaną pokazane kolejne kroki dla zagadnienia - kolejni hetmani do listy dodawani pojedynczo i na bieżąco
ustawienia czterech hetmanów na planszy 4x4. sprawdzamy, czy ograniczenia są spełnione
Rozwiązanie:
[ ]
Istnieją dwa rozwiązania tego zadania:
[2,4,1,3]
[3,1,4,2]
1 2 3 4
H
H 2 3 4 1 3 4 1 2 4 1 2 3
H
H
2 4 2 3 1 3 2 4 2 3 1 3
H
H
H
H
3 3 2 2
6 8
[2,4,1,3] [3,1,4,2]
H H
H H H H
H H H H
H
H H H H
H
11: BT do 10 12: BT do 10
1 2: BT do 1 3 4: BT do 3 9: BT do 0 10
[ ] [ ]
1 2 3 4 1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3 2 3 4 1 3 4 1 2 4 1 2 3
2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3
3 3 2 2 3 3 2 2
9 11
[2,4,1,3] [3,1,4,2] [2,4,1,3] [3,1,4,2]
H H H H
H H
H H H H H H
H H H H
H H H H H H H
H
5: BT do 1 6 7 8: BT do 6 13 14 15: [2,4,1,3] 16: BT do 0
BT do 13
[ ] [ ]
1 2 3 4 1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3 2 3 4 1 3 4 1 2 4 1 2 3
2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3
3 3 2 2 3 3 2 2
10 12
[2,4,1,3] [3,1,4,2] [2,4,1,3] [3,1,4,2]
H
H H H H H
H
H
H H
H
H
H H H
H
H H H H
H
19: BT do 18
28: BT do 24
17 18 20 25 27
26: BT do 25
[ ] [ ]
1 2 3 4 1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3 2 3 4 1 3 4 1 2 4 1 2 3
2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3
3 3 2 2 3 3 2 2
13 15
[2,4,1,3] [3,1,4,2] [2,4,1,3] [3,1,4,2]
H
H
H H
H H H
H H H
H H
H H H
H H H H
22: BT do 17
21: [3,1,4,2] 23: BT do 0 24
29 30: BT do 29
31: BT do 24 32: BT do 0
BT do 17
[ ] [ ]
1 2 3 4 1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3 2 3 4 1 3 4 1 2 4 1 2 3
2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 1 3
3 3 2 2 3 3 2 2
14 16
[2,4,1,3] [3,1,4,2] [2,4,1,3] [3,1,4,2]