V předchozím příspěvku jsem se pokusil naprogramovat řešení hry Futoshiki s využitím backtracking. To bylo to první, co mne napadlo. Nicméně jsem se dále pokusil vyzkoušet i jiné přístupy, které by mohly vést k vyřešení takové hry.
Jako alternativní způsob jsem vyzkoušel tzv. Constraint Programming. No, ono to zase až takové programování není. Podstatou je vytvoření nějakého modelu, na který se pak pošle solver. A ten by mně měl najít nějaké nebo všechna řešení, která vyhovují zadanému modelu.
Nechtěl jsem vše programovat rukama, proto jsem použil knihovu Google OR-Tools.
Tento příspěvek shrnuje řešení hry, ke kterému jsem dospěl.
Testovací data mám již připravená ve třídě SampleSource
, takže stačí je jen použít stejně jako v předchozím příspěvku.
from Futoshiki_DataSource import SampleSource
samples = SampleSource()
Jako základ celého řešení je vytvoření modelu hry s využitím připravených nástrojů z knihovny OR-Tools.
from ortools.sat.python import cp_model
Tímto modelem je třída, která je potomkem třídy CpSolverSolutionCallback
.
Vlastní nastavení modelu se děje v metodě __init__
.
class GameBoard(cp_model.CpSolverSolutionCallback):
def __init__(self, grid, constraints):
cp_model.CpSolverSolutionCallback.__init__(self)
self.model = cp_model.CpModel()
self.size = len(grid)
self.grid = []
# variables ...
for i, line in enumerate(grid):
row = []
for j, c in enumerate(line):
if val := c:
row.append(self.model.NewIntVar(val, val, '{0}-{1}'.format(i, j)))
else:
row.append(self.model.NewIntVar(1, self.size, '{0}-{1}'.format(i, j)))
self.grid.append(row)
# row constraints ...
for i in range(self.size):
self.model.AddAllDifferent(self.grid[i])
# column constraints ...
for j in range(self.size):
self.model.AddAllDifferent([self.grid[i][j] for i in range(self.size)])
# un-equality constraints ...
for low, high in constraints:
l0, l1, h0, h1 = *low, *high
self.model.Add(self.grid[l0][l1] < self.grid[h0][h1])
# room for one solution ...
self.solution = None
def OnSolutionCallback(self):
self.solution = [[self.Value(v) for v in row] for row in self.grid]
self.StopSearch()
def solve(self):
cp_model.CpSolver().SearchForAllSolutions(self.model, self)
Vycházím z toho, že každé políčko čtvercové matice bude jedna celočíselná proměnná v modelu. U každé proměnné modelu mohu nastavit její dolní a horní mez hodnot, kterých může nabývat.
V případě, že mám v zadání vyplněnou hodnotu políčka, nastavím dolní i horní mez na tuto hodnotu. Pro proměnné které hledám, nastavím pak rozmezí hodnot 1..N (N je velikost strany čtverce).
Dále musím v modelu zachytit požadavek, že v každém řádku a sloupci může být každá hodnota pouze jednou (jinak řečeno unikátnost hodnot v řádku a soupci).
To udělám tak, že v modelu definuji omezení unikátnosti pro proměnné v řádcích a sloucích. Jedná se o metodu AddAllDifferent
, do které se předá seznam proměnných.
Dále musím nastavit omezení, která jsou definována explicitně v zadání hry.
Procházím tedy všechny constraint a přidávám omezení metodou Add
s logickým výrazem mezi dvěma proměnnými.
A tím mám model hotový. Nakonec jsem si v modelu vytvořil ješte proměnnou solution
, do které uložím konkrétní řešení, až jej najdu.
Ve třídě GameBoard
mám definovány ještě dvě metody:
Metoda OnSolutionCallback se zavolá, když solver najde nějaké řešení. V mém případě si vyzvednu hodnoty všech proměnných a udělám z nich dvourozměrné pole tak, aby to odpovídalo zadání. Výsledek si pak uložím do proměnné solution
.
Následně pak ještě vyvolám zastavení činnosti solveru. To proto, že mne bude zajímat pouze první nalezené řešení.
Metoda solve zajistí vyvolání vlastního solveru nad modelem. To je tedy ta výkonná část celého řešení.
A to je co se týká vytvoření modelu a jeho řešení vše potřebné. Následuje již pouze vyzkoušení, jak to celé funguje.
Nejdříve si připravím kus kódu, kterým spustím model pro jedno zadání hry:
def execute(sample):
print(*samples.data(sample), sep='\n')
print('*' * 20)
board = GameBoard(samples.grid(sample), samples.constraints(sample))
board.solve()
if board.solution:
for row in board.solution:
print(*row)
else:
print("FAILED")
A takto vyzkouším řešení pro všechna vzorová zadání:
for i in range(len(samples)):
execute(i)
print("\n")
print("=" * 20)
print("\n")
print("FINISHED")
1 0 0 0 ******************** 1 2 2 1 ==================== 1<0 ^ v 0>0 ******************** 1 2 2 1 ==================== 0>0 v ^ 0<0 ******************** 2 1 1 2 ==================== 0 0<3<0 0 0 0 0 ^ 0>0 0 0 ^ 0 0 0<0 ******************** 2 1 3 4 1 4 2 3 3 2 4 1 4 3 1 2 ==================== 0>3 5 1 0 0 2 0 5 0 ^ 0 0 0 0 0 0 5 0 3 0 0 4 3 2<0 ******************** 4 3 5 1 2 3 2 4 5 1 5 1 2 4 3 2 5 1 3 4 1 4 3 2 5 ==================== 0>0 5 0 0 0 2 0 0 0 ^ 0 0 0 0 0 0 0 0 3 0 0 0 0 2<0 ******************** 4 3 5 1 2 1 2 3 5 4 3 1 2 4 5 2 5 4 3 1 5 4 1 2 3 ==================== 0 0<0 0<0 ^ 0 0>0 0 0 0 0 0 0 0 0<0 0 0 0 v ^ 0 0 0<0<0 ******************** 5 1 3 2 4 3 5 4 1 2 4 2 1 5 3 2 3 5 4 1 1 4 2 3 5 ==================== 0 3 0>0 0 5 0 v ^ 0 0 0 0 0 0 0 ^ 4 5 0>0 0 2 7 v 0 0 0 0 0 0 0 v v 2 6 0 0 0 1 3 ^ 0 0 0 0 0 0 0 0 2 0 0<0 3<0 ******************** 7 3 4 2 6 5 1 6 1 3 4 5 7 2 4 5 6 3 1 2 7 3 4 7 1 2 6 5 2 6 5 7 4 1 3 1 7 2 5 3 4 6 5 2 1 6 7 3 4 ==================== 0 0 0 0 0 0 0 ^ ^ ^ 0 0 0 0 4<0 0 ^ 0 0 0 0 5 0 0 ^ 0 0 0 0 0 0 0 1 0 0 3>0 0<0 v 6>0 0 0 0>0>0 ^ 0<3>0 0 0 0 7 ******************** 4 2 7 5 1 3 6 7 5 2 1 4 6 3 3 1 4 6 5 7 2 5 6 3 2 7 1 4 1 7 6 3 2 4 5 6 4 5 7 3 2 1 2 3 1 4 6 5 7 ==================== 0 1 0 0 0<0 7<0 ^ v v 0 0 0 0 0<0 0>0 v 0>4 0>7 0<0 3 0 v 0 0 0 0 0 0 0<0 v v 0<6 0 2 0 4 0 0 ^ 0 0 0 0 0 0>0 0 ^ ^ ^ 0 0 0<0 0 0 0 0 0 0 0 0 0 0 0 3 ******************** 2 1 6 3 4 5 7 8 4 7 3 1 6 8 5 2 5 4 8 7 2 6 3 1 7 2 5 8 1 3 4 6 3 6 7 2 8 4 1 5 6 8 1 5 3 7 2 4 1 3 4 6 5 2 8 7 8 5 2 4 7 1 6 3 ==================== 0 8>0 0<0 0 1 0<5 ^ 0 1 0<0 0 0 0 0 0 v 0 0 0<0 0 0 0 0 0 ^ ^ ^ ^ 0 0 0 0 0 0 6<0 0 v v 0 0 0 0 0>0 9 0 0 ^ ^ 7 4 8>0 0 0 0>0>0 v v v 0 0<0 0 0 0 0 0 0 ^ 0 0<0<0 3 0 0 7 1 0 0 4 0 0 0 0>0 7 ******************** 9 8 2 3 6 7 1 4 5 3 1 5 8 9 2 7 6 4 1 7 3 5 2 8 4 9 6 2 5 9 7 4 1 6 8 3 6 3 1 4 7 5 9 2 8 7 4 8 6 1 9 5 3 2 4 6 7 1 8 3 2 5 9 5 2 6 9 3 4 8 7 1 8 9 4 2 5 6 3 1 7 ==================== 0 0<0 0>0 0 0 0>0 v v 0 7 8 0>3 5 0<0<0 ^ 0 0 6 0 0>0 0 0 0 v ^ v 7 0 0 3 0 0 0>0 0 v v 0 3 0 0 0 9 0 0<0 v 0>0 0>0>0 2 0<0 0 v v v 0 0 0<0 0 0<0 0 0 v v 0 0 0 0 0 0 0 0 0 v ^ 0<0 7<0<0 0>0 0 0 ******************** 3 1 2 9 4 8 5 7 6 1 7 8 4 3 5 2 6 9 9 8 6 1 7 3 4 2 5 7 5 1 3 2 6 9 8 4 4 3 5 7 8 9 6 1 2 8 4 9 6 5 2 1 3 7 6 2 4 5 1 7 8 9 3 5 9 3 2 6 1 7 4 8 2 6 7 8 9 4 3 5 1 ==================== FINISHED
A to je dnes vše. Příště vyzkouším, zda by to nešlo řešit s využitím genetických algoritmů.
pracuje na pozici IT architekta. Poslední roky se zaměřuje na integrační a komunikační projekty ve zdravotnictví. Mezi jeho koníčky patří také paragliding a jízda na horském kole.
Přečteno 24 511×
Přečteno 22 960×
Přečteno 18 574×
Přečteno 17 531×
Přečteno 16 786×