Futoshiki - klasicky
Po delší době jsem se opět dostal k řešení nějaké hry. Vybral jsem si japonskou logickou hru Futoshiki. Jedná se o relativně mladou hru vymyšlenou na začátku tohoto století s jednoduchými pravidly.
Hraje se na čtvercové desce obvykle s rozměry 5×5 nebo 7×7 políček.
Pravidla by se dala shrnou asi následovně:
- Na políčka se umísťují čísla v rozmězí od 1 do N (N je velikost čtverce)
- V každém řádku a sloupci může být každé číslo pouze jednou (čísla se tedy nesmí opakovat)
- Navíc je mezi některými sousedními políčky (v řádku nebo soupci) definována nerovnost. Vyplněná políčka pak musí splňovat tuto nerovnost
- Při úvodním zadání jsou některá políčka dopředu specifikována. Ty políčka, které je potřeba doplnit, mají hodnotu 0.
Například takto by mohlo vypadat zadání takové hry:
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 Pokusil jsem se postupně vyzkoušet několik postupů, jak bych mohl takovou hru řešit. Zkusil jsem to nejdříve klasickým přístupen, dále pak pomocí Constraint Programming a nakonec s využitím genetických algoritmů. O výsledky mých pokusů bych se s vámi rád podělil.
Zdroj testovacích dat
Protože budu zkoušet několik postupů, vytvořil jsem si nejdříve jeden společný zdroj testovacích dat. Je to jedna třída SampleSource v samostatném modulu. Ta obsahuje několik zadání hry v textové podobě a metody, jak s nimi jednoduše pracovat.
Jednodušší bude asi ukázka, jak s tím zdrojem testovacích vzorků pracuji:
from Futoshiki_DataSource import SampleSource
samples = SampleSource()
Celkový počet vzorků, které mám k dispozici:
print(len(samples))
12
Takto si mohu zobrazit jeden konkrétní vzorek ve zdrojové podobě:
print(*samples.data(3), sep='\n')
0 0<3<0 0 0 0 0 ^ 0>0 0 0 ^ 0 0 0<0
A takto si mohu zjistit velikost hrací desky pro vybraný vzorrek:
print(samples.size(3))
4
Dále mám ještě připravené dvě metody pro detailnější práci se zadáním.
První z nich je metoda pro předání hodnot políček:
print(*samples.grid(3), sep='\n')
[0, 0, 3, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
Dostanu seznam řádků s hodnotami jednotlivých políček.
Druhou metodou je pak seznam všech omezení definovaných v zadání:
print(*samples.constraints(3), sep='\n')
((0, 1), (0, 2)) ((0, 2), (0, 3)) ((1, 0), (2, 0)) ((2, 1), (2, 0)) ((2, 0), (3, 0)) ((3, 2), (3, 3))
Dostanu seznam dvojic souřadnic políček, mezi kterými je definována relace menší. Můžete si zkontrolovat se zdrojovou podobou zadání.
Klasický přístup pomoci backtracking
Asi každého napadne prvním možný způsob řešení, že prostě budu postupně zkoušet všechny možnosti hodnot políček, až mně něco vyjde. Tak to bylo i u mne, a toto je můj nesmělý pokus:
import numpy as np
class GameBoard:
def __init__(self, grid, constraints):
self.size = len(grid)
self.grid = np.array(grid)
self.constraints = constraints
def allowable_values(self, row, col):
if self.grid[row, col]:
return {self.grid[row, col]}
else:
res = set(range(1, self.size + 1))
res -= set(self.grid[row])
res -= set(self.grid[:, col])
min_const = {self.grid[high] for low, high in self.constraints if low == (row, col) and self.grid[high]}
if min_const:
res = {v for v in res if v < min(min_const)}
max_const = {self.grid[low] for low, high in self.constraints if high == (row, col) and self.grid[low]}
if max_const:
res = {v for v in res if v > max(max_const)}
return res
def is_complete(self):
return all((bool(v) for v in self.grid.ravel()))
def is_valid(self):
if not self.is_complete():
return False
for row in range(self.size):
if len(set(self.grid[row])) != self.size:
return False
for col in range(self.size):
if len(set(self.grid[:, col])) != self.size:
return False
for low, high in self.constraints:
if not self.grid[low] < self.grid[high]:
return False
return True
def solve(self, from_index=0):
if from_index < self.grid.size:
row, col = from_index // self.size, from_index % self.size
if self.grid[row, col]:
return self.solve(from_index + 1)
else:
for val in self.allowable_values(row, col):
self.grid[row, col] = val
if self.solve(from_index + 1):
return True
self.grid[row, col] = 0
return False
else:
return True
Vytvořil jsem si třídu GameBoard, do které při vytvoření instance zadám hodnoty políček jako dvourozměrný seznam, a seznam omezení pro vybraná políčka (to jsou ty dvě posledním metody ze zdroje testovacích dat).
Aby se mně s čtvercovou maticí hodnot lépe pracovalo, udělal jsem si z něj pole v numpy.
Dále jsou ve třídě tyto metody:
- is_complete
- Metoda kontroluje, zda již není řešení kompletní. To se pozná tak, že všechna políčka obsahují nějakou kladnou hodnotu.
- is_valid
- Metoda ověří, že je řešení kompletní a zároveň splňuje všechna požadovaná omezení.
- Ověřuje se unikátnost hodnot v řádcích a sloupcích. A dále se ověřuje splnění všech požadovaných relací mezi políčky.
- allowable_values
- Metoda pro zadané souřadnice políčka zjistí množinu hodnot, které se mohou na políčku vyskytovat.
- Pokud je již políčko vyplněno (to je v případě, že hodnota políčka byla specifikována v zadání hry), pak je vrácena množina obsahující pouze tuto hodnotu.
- Jinak začínám s množinou všech hodnot, které jsou povoleny podle rozměru hrací plochy.
- Od této množiny odečítám množiny již známých hodnot v řádku a sloupci.
- Dále projdu množinu všech omezení, ve kterých hledané políčko figuruje na první pozici (musí být menší). Pokud taková množina existuje, pak do výsledného řešení projdou pouze ty hodnoty, které jsou menší než minimum větších políček. Prostě musí být zachována všechna omezení pro dané políčko.
- Obdobně i pro omezení, kde hledané políčko figuruje na druhé pozici (musí být větší). Do výsledku projdou pouze hodnoty, které jsou větší než maximum menších políček.
- solve
- Hlavní výkonná metoda pro řešení. Spouští se rekurzivně a prochází všechna políčka po řádcích. Parametr from_index udává sekvenční pořadí políčka.
- Pokud je políčko vyplněno, pokračuje se v hledání políčka následujícího.
A takto by to mohlo vypadat, pokud provedu řešení jednoho zadání (v tomto případě pro číslo 3):
board = GameBoard(samples.grid(3), samples.constraints(3))
if board.solve():
if board.is_valid():
print(board.grid)
else:
print("SOLUTION IS NOT VALID")
else:
print("FAILED")
[[2 1 3 4] [1 4 2 3] [3 2 4 1] [4 3 1 2]]
Testováním jsem zjistil, že tento způsob mně dává výsledky v rozumém času, pokud je velikost zadaného vzorku maximálně 7×7. Pro větší vzorky již tohle řešení trvá neúměrně dlouho.
Následuje ukázka řešení pro všechny vzorky z testovacích dat s velikostí do 7×7:
def execute(sample):
print(*samples.data(sample), sep='\n')
print('*' * 20)
board = GameBoard(samples.grid(sample), samples.constraints(sample))
if board.solve():
if board.is_valid():
print(board.grid)
else:
print("SOLUTION IS NOT VALID")
else:
print("FAILED")
for i in range(len(samples)):
if samples.size(i) <= 7:
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
********************
[[2 1 5 4 3]
[3 2 4 5 1]
[4 3 2 1 5]
[5 4 1 3 2]
[1 5 3 2 4]]
====================
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]]
====================
FINISHED
A to je dnes vše. Příště se zkusím s hrou Futoshiki popasovat s využitím knihovny pro Constraint Programming.
-
Místo "if from_index < self.size:" má být "if from_index < self.size ** 2:", jinak to někdy skončí moc brzo nedořešené.
Například: [[0 0 0], [0 0<0], [0<0<0]], které má jednoznačné řešení [[2 3 1], [3 1 2], [1 2 3]].
(Mimochodem u matice 2x2 stačí zadat jakoukoli jednu nerovnost a řešení je už jednoznačné, ale v tom případě by ten program ještě fungoval.)
-
Oceňuji zjednodušený funkční kód na hranici rozsahu, jaký se hodí do článku, demonstrující použití backtrackingu, bez implementace dalších poznatků o řešené úloze. Šlo by to samozřejmě zrychlit sledováním, které číslo se vyskytuje pouze jednou v daném řádku nebo sloupci v množinách možných hodnot pro jednotlivá neznámá pole a hned ho dosadit. Dále je možné ořezávat množiny v sousedních polích, mezi kterými je nerovnost A<B, aniž by se hned musely hned zkoušet hodnoty pomocí backtrackingu. Vyloučí se všechny hodnoty A větší nebo rovny max(B) a stejně tak se vyloučí všechny hodnoty B menší nebo rovny max(A). Tímto způsobem lze hned určit v předchozím příkladu celý poslední řádek [1<2<3] dvojí opakovanou aplikací uvedených pravidel, respektive opakováním pravidel, pokud se zmenšil rozsah alespoň jedné množiny. Tím jsou pokryté všechny intuitivní strategie, které jsou mimochodem popsané v radách na https://www.futoshiki.org/ , kromě poslední strategie - naslepo či intuitivně zkoušet možnosti, které lze vyloučit, na což se už hodí backtracking. K němu je pak vhodné si pamatovat celý seznam množin možných hodnot pro jednotlivá pole, aby se po návratu z rekurze nemusely znovu provádět stejné iterace pro ořezání množin.
Server Futoshiki obsahuje zřejmě předgenerovaných 10000 úloh pro každé z šesti velikostí 4x4 až 9x9 a čtyř obtížností. Zkusil jsem výše uvedená vylepšení na prvních 2000 úlohách nejvyšší obtížnosti s velikostí pole 8x8 a s ověřením, že pro každou úlohu existuje jen jedno řešení. Výsledky jsou: průměrná doba řešení byly 3 sekundy, přičemž 20% úloh bylo hotových do 0.1 sekundy, 50% do 0.5 sekundy, 90% do 7 sekund, 99% do 80 sekund a 0.75% úloh neřeším, protože trvaly déle než 100 sekund.
Další možné zlepšení by zřejmě bylo vylučování řady slepých uliček nejdříve v jedné úrovni do šířky, než se bude postupovat do hloubky. Tím se totiž vyřeší problém například v případě většiny vstupních pravidel umístěných ve spodní polovině (viz ukázka s nerovnostmi pod diagonálou zobecnitelná na jakoukoli velikost), zatímco jednoduchý backtracking postupoval shora a příliš narůstal řešený stavový prostor. Krok hledání zřejmých slepých uliček má polynomiální složitost, zatímco backtracking už bude odpovídat něčemu podobného faktoriálu.
O tomhle chci přemýšlet až po dalším dílu.
ČLÁNKY DO MAILU