Nem tudod teljesen kitalálni ezt a rejtvényt? Kipróbáltad a nyers erőltetést minden lehetséges kombinációval?
Karácsonykor kaptam ajándékba ezt a puzzle-t, és naivan kidobtam az összes darabot a táblából, amint kinyitottam. Egy okosabb ember valószínűleg lefotózta volna az eredeti megoldást, minden esetre. Mélyen megbánnám ezt a mulasztást a következő órákban, mivel többször is megpróbáltam, de nem sikerült az összes darabot visszatenni a helyére. Sokszor gyötrelmesen közel kerültem, és a 13 darabból 12-t leraktam, mielőtt rájöttem, hogy az utolsó darab lehetetlen beférni.
Nem sokkal ezután barátaim és családtagjaim segítségét kértem, de még az ő közös erőfeszítéseik sem bizonyultak a megtévesztően egyszerű kirakósnak. Végül egy barátom talált egy működő konfigurációt, de a győzelem üresnek tűnt. Ez a rejtvény sokunkat legyőzött, órákat vesztegetve mindenki idejéből. A kíváncsiságtól és a frusztrációtól egyenlő arányban fűtve úgy döntöttem, készítek egy algoritmust, hogy teljesen összetörjem ezt a rejtvényt. Az intuícióm azt súgta, hogy a feladvány nehéz volt, mert valószínűleg csak egyetlen egyedi megoldás létezik. Nem zárhattam ki több tucat vagy több száz megoldás lehetőségét, de valószínűtlennek tűnt. Egy algoritmussal ezt így vagy úgy be tudnám bizonyítani.
A Rejtvény
Csak miután befejeztem az algoritmusomat, és elkezdtem kutatni ehhez a cikkhez, jöttem rá, hogy a kapott játék valami „pentomino-rejtvény” változata. Úgy tűnik, a pentomino az öt egyforma méretű négyzetből álló alakzat neve.
Egy tipikus pentominó-rejtvényben az egyetlen darab a táblán, nos, pentominó. Kirakónk némileg egyedi, mivel egy további 2x2 négyzet alakú darabot is tartalmaz. A fenti ábra elnevezési konvenciójának követése érdekében ezt a darabot mostantól „O quadromino” néven fogom emlegetni.
A különböző darabok különböző fokú bonyolultságot adnak a kirakós játékhoz. Például az O quadrominónak csak egy tájolása van. Nem számít, hogyan forgatjuk vagy fordítjuk, az alakzat tényleges profilja ugyanaz marad. A spektrum másik végén az F pentominónak nyolc lehetséges iránya van.
Ahhoz, hogy megtaláljuk a rejtvény minden lehetséges megoldását, minden egyes darab minden lehetséges átfordítását és elforgatását figyelembe kell vennünk. Ezen összetett állapotok ábrázolása érdekében a táblaábrázolást a fizikai világról a digitálisra állítjuk át.
A tábla
Mind a tábla, mind a darabok adatszerkezetének listás listát választottam. A tábla inicializálása 0 értékkel jelzi az üres négyzeteket. A bábu 1 és 13 közötti értékkel rendelkezik, ami lehetővé teszi, hogy különbséget tudjanak tenni közöttük, amikor a táblára helyezik őket. Két függvényt is írtam a darabok tájolásának manipulálására: az egyik a darabtömbök 90 fokkal az óramutató járásával megegyező irányba történő elforgatására, a másik pedig egy darab Y tengelye mentén történő tükrözésére. Kombináltan minden lehetséges pozíciót létrehozhatnak egy adott darabhoz.
board = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range(8)]
pieces = (
[[1, 1],
[1, 1]],
[[2, 0, 0],
[2, 0, 0],
[2, 2, 2]],
[[0, 3, 0],
[3, 3, 3],
[0, 3, 0]],
[[4, 4, 4, 4, 4]],
...
)
def rotate_piece(piece):
return [list(row[::-1]) for row in zip(*piece)]
def reflect_piece(piece):
return [row[::-1] for row in piece]
Most olyan módszerre van szükségünk, amellyel a játékszabályok megszegése nélkül helyezhetünk el figurákat a táblára. Mielőtt leraknánk egy darabot, két kritériumot kell ellenőriznünk:
- A darab nem lóg le a tábla széléről.
- A darab nem lesz átfedésben a táblán lévő bábukkal.
Mindaddig, amíg mindkét szabály teljesül, legális a darab elhelyezése.
def add_piece(board, piece, start_row, start_col):
piece_width = len(piece[0])
piece_height = len(piece)
legal_move = True
# check if piece is hanging off the edge of the board
if (start_row + piece_height > len(board)) or
(start_col + piece_width > len(board[0])):
legal_move = False
return board, legal_move
changed_squares = []
for i, row in enumerate(piece):
for j, val in enumerate(row):
# only add filled spaces, never take away
if val:
# don't overwrite existing pieces on the board
if board[start_row + i][start_col + j]:
legal_move = False
return board, legal_move
else:
changed_squares.append((start_row + i, start_col + j, val))
new_board = [[val for val in row] for row in board]
for changed_row, changed_col, val in changed_squares:
new_board[changed_row][changed_col] = val
return new_board, legal_move
Ezen a ponton van egy játéktábla, amely pontosan úgy viselkedik, mint a való életben. Csak most, ahelyett, hogy percenként egy tucat kombinációt kellene tesztelnem, olyan szoftvert írhatunk, amely másodpercenként több ezer kombinációt képes kiadni. Ahhoz, hogy ez valósággá váljon, szükségünk van egy algoritmusra, amely képes előállítani az összes lehetséges kártyaállapotot.
Az algoritmus
Úgy döntöttem, hogy a visszalépésnek nevezett, jól bevált megközelítést választom. Ennek a módszernek az az alapötlete, hogy válasszunk, majd később vonjuk vissza, ha az nem megfelelő. A pentomino kirakós játékhoz addig akarunk darabokat letenni a táblára, amíg lehetetlenné válik további darabok elhelyezése. Amikor ez megtörténik, az azért van, mert vagy kifogytunk a darabokból, és megoldottuk a rejtvényt, vagy (sokkal valószínűbb) olyan konfigurációba helyeztük a darabokat, amelyek nem férnek el a táblán. El kell kezdenünk visszavonni néhány korábbi döntést, amikor elérjük ezt a zsákutcát.
Először a legutóbb elhelyezett darabot húzzuk le a tábláról. Ha még nem próbált módon elfér, akkor ebben az új tájolásban tesszük vissza a táblára a darabot, és folytatjuk a további darabok elhelyezését. Ha minden tájékozódást kimerítettünk a darabnál, ismét visszalépünk, és megpróbáljuk ugyanezt a következő, legutóbb elhelyezett darabbal. Ennek az eljárásnak a megismétlése a pentomino puzzle minden lehetséges táblaállapotát létrehozza.
def solve_board(board, pieces):
# piece_positions contains all possible orientations for a given piece
piece_positions = pieces[0]
for position in piece_positions:
# find every place a piece can fit into the board
legal_squares = get_legal_squares(board, position)
for row, col in legal_squares:
# place the piece, repeat with new board
new_board, _ = add_piece(board, position, row, col)
solve_board(new_board, pieces[1:])
Nos, ez elég egyszerű volt. Most hátradőlhetünk, és hagyjuk, hogy az algoritmus a városba menjen, igaz? Sajnos ez nem lesz olyan egyszerű. Több milliárd lehetséges kártyakonfiguráció létezik, és a túlnyomó többség meg sem közelíti a megoldásokat. Ha elképzeljük, mit csinál az algoritmus jelenleg, könnyen beláthatjuk, hogy ideje nagy részét lehetetlen táblakonfigurációkra pazarolja. Például, amikor az X pentominót a tábla bal felső sarkába helyezzük, az algoritmus által végzett munka haszontalan mindaddig, amíg az X pentominót el nem mozdítjuk, mivel a bal felső négyzet nem tölthető ki.
Optimalizálások
Kiderült, hogy a probléma megoldása „egyenesen a Leetcode-problémából származik”. Esetünkben a darabokkal körülvett üres tereket „szigeteknek” tekinthetjük. Meg akarjuk akadályozni, hogy az algoritmus olyan táblákat generáljon, ahol a pentomino nem fér el egy szigeten.
Az egyes szigetek méretének megszámlálásához mélységi keresést használunk. Még több rekurzió! Ez a „szigetszámláló” algoritmus végigpásztázza a táblát, amíg nem talál egy nulla értékű négyzetet. Megjelöli a négyzetet látogatottként, növeli a számlálóváltozót, és rekurzívan hívja magát a négyzet összes szomszédján. A szigetet teljesen felderítették, amikor az algoritmus kifogy a nulla értékű szomszéd négyzetekből, hogy ellenőrizze. A számláló most a sziget méretét tartalmazza. Ha a szigetnek négynél kevesebb négyzete van, a konfiguráció megoldhatatlan, ezért ezt a táblakonfigurációt eldobjuk.
Négy négyzetből álló szigeteket kell engedélyeznünk az O quadromino miatt, ami az egyetlen darab, ami elférne ott. Megkerülhetjük ezt a korlátozást, ha mindig az O quadrominót helyezzük az első helyre. Mivel mindig a táblán van, soha nem kell aggódnunk, hogy helyet találunk neki. Most átállíthatjuk az algoritmust, hogy csak akkor engedélyezze a szigeteket, ha azok öt többszörösei.
def legal_islands(board):
board = [[elem for elem in row] for row in board]
board_height = len(board)
board_width = len(board[0])
island_size = 0
# depth first search on island squares
def island_dfs(row, col):
# break if square is out of bounds or nonzero
if row < 0 or col < 0 or
row >= board_height or col >= board_width or
board[row][col] != 0:
return
island_cells += 1
board[row][col] = "#"
island_dfs(row - 1, col)
island_dfs(row + 1, col)
island_dfs(row, col - 1)
island_dfs(row, col + 1)
for row in range(board_height):
for col in range(board_width):
if board[row][col] == 0:
island_dfs(row, col)
# only allow islands if they're multiples of five
if len(island_cells) % 5 != 0:
return False
island_cells = []
return True
A további számítások kissé lelassíthatják az általános algoritmust, de ezt bőven kompenzálja azáltal, hogy kiküszöböli a rengeteg helytelen útvonalat.
Megoldások
Megnyomtam a Futtatás gombot a megoldómon, és a terminál kimenetére ragasztottam a szememet. Körülbelül 30 másodpercig nem történt semmi, majd hirtelen három egyedi megoldást köpött ki egyszerre. Öt perccel később 34-re emelkedett. Az intuícióm teljesen összeomlott. Világossá vált, hogy a megoldások száma legalább több ezer, ha nem több. Nevetni támadt kedvem, ahogy a számítógép egyre több megoldást talált egy rejtvényre, amit egyszer sem tudtam megoldani.
Eljutottam idáig, és csak tudnom kellett, hogy pontosan hány megoldás létezik. Szerencsére hozzáfértem egy használaton kívüli szerverhez, ahol senki sem bánná, ha rejtvényszimulációkat indítanék el. Még a multiprocessing implementációja mellett is körülbelül egy napig tartott a futás befejezése. De végre megkaptam a választ! 129 168 megoldása van a pentominó rejtvénynek!
Több optimalizálás, kevesebb megoldás
Egy nappal később az jutott eszembe, hogy ennek a rejtvénynek biztosan nincs 129 168 megoldása. Sok megoldott tábla más megoldott táblák elforgatása vagy tükröződése volt, ami azt jelenti, hogy nem igazán egyediek. Az ismétlődések eltávolításához minden táblát „normalizálnunk” kell az összes átalakítás visszavonásához.
A megoldásom az volt, hogy kiválasztok egy szabványos tájolást az F pentominóhoz, és minden táblát addig forgattam/tükröztem, amíg az F pentominó a szokásos tájolásba nem kerül. Ez kiküszöböli a táblák közötti forgás vagy visszaverődés okozta különbségeket, és lehetővé teszi, hogy közvetlenül összehasonlítsuk őket.
Az összes másolat ilyen módon történő eltávolítása után 16 146 valóban egyedi megoldás maradt. Figyelemre méltó, hogy ez pontosan az 1/8-a az eredeti oldatmennyiségnek. Volt egy olyan sejtésem, hogy ez így lesz, de jó érzés volt bebizonyítani.
Ezzel a megközelítéssel megvalósítottam egy végső optimalizálást a megoldások generálásához. Kizárólag olyan táblák generálására szorítkozhatunk, ahol az F pentomino a szokásos tájolásban van. Ez megakadályozza, hogy duplikált táblákat hozzunk létre, és az algoritmus futásidejét a korábbi legjobb 1/8-ára csökkenti.
Végső gondolatok
Biztos vagyok benne, hogy rengeteg további optimalizálási lehetőség van a kódomhoz. Például a szigetkereső algoritmus módosítható úgy, hogy ne engedélyezze a táblán már lévő darabok alakú szigeteket. Még azt is megpróbálhatnám megfejteni a rejtvényt, hogy „úgy, ahogy Donald Knuth tette”. Nem ez lenne az első alkalom, hogy "megvalósítom" az egyik algoritmusát. Egyelőre azonban elégedett vagyok azzal, amim van.
Ha érdekel játszani a pentomino-rejtvényen, vagy egyszerűen csak vacakol a kóddal, az én implementációm "szabadon elérhető a GitHubon". Köszönöm, hogy elolvasta!
