Hetmani – cd.
2
Czterech hetmanów
:
- dla uproszczenia zostan
ą
pokazane kolejne kroki dla zagadnienia
ustawienia czterech hetmanów na planszy 4x4.
Rozwi
ą
zanie
:
Istniej
ą
dwa rozwi
ą
zania tego zadania:
[2,4,1,3]
H
H
H
H
[3,1,4,2]
H
H
H
H
3
Przegl
ą
d zupełny
:
- najpierw generujemy rozwi
ą
zanie (zast
ę
pujemy wszystkie zmienne
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
ć
3 4 2 4 2 3
4 3 4 2 3 2
2 3 4
1
3 4 1 4 1 3
4 3 4 1 3 1
1 3 4
2
2 4 1 4 1 2
4 2 4 1 2 1
1 2 4
3
2 3 1 3 1 2
3 2 3 1 2 1
1 2 3
4
[ ]
[2,4,1,3] [3,1,4,2]
4
Metoda nawrotów (standard backtracking)
:
- kolejni hetmani do listy dodawani pojedynczo i na bie
żą
co
sprawdzamy, czy ograniczenia s
ą
spełnione
2 4 2 3
3
2 3 4
1
1 3
3
1 3 4
2
2 4
2
1 2 4
3
2 3 1 3
2
1 2 3
4
[ ]
[2,4,1,3] [3,1,4,2]
5
Forward checking
:
- kolejni hetmani do listy dodawani pojedynczo i na bie
żą
co
sprawdzamy, czy ograniczenia s
ą
spełnione (standard backtracking)
oraz uaktualniamy domeny hetmanów, usuwaj
ą
c z nich warto
ś
ci
niedozwolone (propagacja ogranicze
ń
) i sprawdzamy, czy która
ś
z domen nie jest pusta
2
3 4
1
1
3
4
2
4
2
1
3
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
6
H
1
H
H
2: BT do 1
H
H
3
4: BT do 0
H
H
H
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
H
H
X
X
X
X
X
X
X
X
X
X
X
X
H
H
X
X
X
X
X
X
X
X
X
X
X
X
H
X
2
3 4
1
1
3
4
2
4
2
1
3
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
7
5
H
H
H
6
H
H
H
7
H
H
H
H
8: [2,4,1,3]
BT do 0
H
H
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
2
3 4
1
1
3
4
2
4
2
1
3
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
8
9
H
H
H
10
H
11
H
H
12: [3,1,4,2]
BT do 0
H
H
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
H
X
H
X
X
X
X
X
X
X
X
X
H
X
X
H
X
H
2
3 4
1
1
3
4
2
4
2
1
3
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
9
H
13
H
H
H
14
H
15: BT do 13
H
H
H
H
16: BT do 0
H
H
H
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
2
3 4
1
1
3
4
2
4
2
1
3
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
10
Looking Ahead + Forward checking
:
- kolejni hetmani do listy dodawani pojedynczo i na bie
żą
co:
sprawdzamy, czy ograniczenia s
ą
spełnione (standard backtracking),
uaktualniamy domeny hetmanów i sprawdzamy czy s
ą
niepuste
(forward checking), oraz sprawdzamy, czy domeny hetmanów
nieustawionych nie zawieraj
ą
wył
ą
cznie ustawie
ń
niebezpiecznych
3 4
1
1
3
4
2
4
2
1
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
11
H
1
H
H
2: BT do 1
H
H
3: BT do 0
4
H
H
H
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
H
H
X
X
X
X
X
X
X
X
X
X
X
X
H
H
X
X
X
X
X
X
X
X
X
X
X
X
H
X
3 4
1
1
3
4
2
4
2
1
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
H
H
X
X
X
X
X
X
X
X
X
X
X
X
A
A
H
X
X
X
X
X
X
X
X
X
12
5
H
H
H
6
H
H
H
H
8
H
H
7: [2,4,1,3]
BT do 0
H
X
X
X
X
X
X
X
X
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
3 4
1
1
3
4
2
4
2
1
3
1 2
4
[ ]
[2,4,1,3] [3,1,4,2]
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
X
X
X
X
X
X
X
X
X
X
H
X
H
X
H
H
X
X
X
X
X
X
X
X
X
