Hlavní navigace

Sliding puzzle - skládání kostiček

14. 1. 2021 21:01 (aktualizováno) Jiří Raška

V rámci procvičování na CodingGame jsem narazil na problém, do jehož řešení jsem dost zabředl. Jedná se o řešení hry Sliding Puzzle, tedy skládání kostiček do správného pořadí s využitím jednoho prázdného místa.

Toto je zadání úkolu

Vlastní bádání nad problémem bylo dost zábavné, proto bych se rád o něj podělil.

Tady si můžete sami připomenout, jak ta hra funguje

Výchozí úvahy o řešení

Budu vycházet z toho, že řeším hru o velikost 3×3 kostičky (ono v zadání je 4×3, ale na řešení to vliv nemá, je to jen jeden z parametrů).

Výchozí stav hry, tedy náhodně poskládané kostičky, můžu reprezentovat jako posloupnost čísel 0 až 8, kdy 0 představuje volné políčko. Posloupnost je poskládaná řazením řádků za sebou. Bylo by pochopitelně možné reprezentovat stav hry jako dvourozměrné pole, ale to by bylo asi komplikovanější na zápis i zpracování.

Konečný stav je ten, kdy jsou všechna čísla v posloupnosti seřazena vzestupně.

Tohle je příklad jednoho možného zadání:


[7, 5, 1, 3, 4, 2, 0, 8, 6]  ==>  [0, 1, 2, 3, 4, 5, 6, 7, 8] 

Pokud bych mohl kostičky libovolně přehazovat, pak by bylo řešení triviální. Nicméně to v tomto případě nejde. Mohu jen posouvat kostičky do volného místa (nebo posouvat volné místo, jak se chcete na to dívat).

Z výchozího stavu se mohu posunout do jednoho z následujících stavů (volné místo mám v levém dolním rohu, takže jej můžu posunout doprava nebo nahoru):


[7, 5, 1, 3, 4, 2, 0, 8, 6]  ->  [[7, 5, 1, 3, 4, 2, 8, 0, 6], [7, 5, 1, 0, 4, 2, 3, 8, 6]] 

A dále mohu vyzkoušet tyto stavy. Posunout se dále, a to vše opakovat, dokud nenajdu cílový stav.

Jak by se to tedy dalo řešit

Pokud budu postupně procházet všechny stavy hry postupným přesouváním kostiček, pak v podstatě procházím strom všech možných stavů a hledám cestu k tomu konečnému stavu.

Kdybych vycházel pouze z předchozí úvahy, pak by se nejednalo o strom: Byl by to graf s cykly, protože se můžu po několika tazích vrátit do stavu, ve kterém jsem již byl. Nicméně docela jednoduchým způsobem se dá zajistit, že se o strom jednat bude. Prostě nebudu pokračovat ve hledávání do stavu, který jsem již dříve navštívil.

Pro řešení se nabízí několik možností, které jsem postupně vyzkoušel:

  • BFS – Breadth-first search
  • DFS – Deep-first search
  • Dijkstra vyhledávací algoritmus
  • A* vyhledávací algoritmus

U posledních dvou metod je možné ještě experimentovat s vyhodnocovacími pravidly a heuristikami.

Takže nakonec z toho vyšlo několik různých variant řešení.

Poznámky k jednotlivým řešením

  1. Ukázalo se, že DFS vyhledávání je hodně pomalé a k výsledku v rozumném čase většinou nevede
  2. Vlastní vyhledávací algoritmus u zbylých tří metod je možné sjednotit do jednoho řešení s prioritní frontou. Výsledné chování pak modifikovat funkcí pro vyhodnocení stavu a výpočet heuristiky (to pro A* algoritmus).

Vlastní řešení

A jdeme na to … nejdříve nějaké společné definice:

In [8]:
import heapq

W, H = 3, 3
MAX_COST = 50

final_state = list(range(W * H))
print(final_state)
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Výkonná část algoritmu

  • pro implementaci prioritní fronty používám modul heapq ze standardní knihovny Python
  • do prioritní fronty vkládám trojici (cena, stav, počet tahů)
  • v zadání hry bylo omezení na maximální počet tahů; tohle omezení je dáno proměnnou _MAXCOST

Výsledkem vyhodnocovací funkce je počet tahů, kterými se dostanu z výchozího stavu do toho cílového.

In [9]:
def solve(initial_state, cost_function):
    q = []
    heapq.heappush(q, (cost_function(initial_state, 0), initial_state, 0))
    visited_states = []
    while q:
        cost, state, moves = heapq.heappop(q)
        if state == final_state:
            return moves
        else:
            for st in next_states(state):
                if st not in visited_states:
                    cost = cost_function(st, moves + 1)
                    if cost <= MAX_COST:
                        heapq.heappush(q, (cost, st, moves + 1))
        visited_states.append(state)
    return None

Pomocné funkce

Pro běh hlavního algoritmu potřebuji pomocnou funkci, která mně vrátí všechny možné následující stavy pro zadaný stav:

In [10]:
def next_states(state):
    i = state.index(0)
    res = []

    # UP
    if i - W >= 0:
        st = state[:]
        st[i], st[i - W] = st[i - W], st[i]
        res.append(st)
    # DOWN
    if i + W < W * H:
        st = state[:]
        st[i], st[i + W] = st[i + W], st[i]
        res.append(st)
    # LEFT
    if i % W - 1 >= 0:
        st = state[:]
        st[i], st[i - 1] = st[i - 1], st[i]
        res.append(st)
    # RIGHT
    if i % W + 1 < W:
        st = state[:]
        st[i], st[i + 1] = st[i + 1], st[i]
        res.append(st)
    return res

Funkce pro vyhodnocení ceny

Výběr vyhodnocovací funkce rozhodne o variante použitého algoritmu, takže pro:

BFS algoritmus

Tady to bude velice jednoduché, neboť stavy řešíme v pořadí, v jakém jsme na ně narazili při průchodu stromem v jednotlivých úrovních.

In [11]:
def cost_bfs(state, moves):
    return moves

Dijkstra algoritmus

Pro vyhodnocení, jak „dobrý“ je zadaný stav, použiji počet rozdílných políček proti cílovému stavu. Při řešení bych tedy měl upřednostnit ty stavy, které jsou nejvíce podobné cílovému stavu.

In [12]:
def cost_tiles(state, moves):
    return moves + len([(x, y) for x, y in zip(state, final_state) if x != y])

A* algoritmus

Do vyhodnocení ceny řešení zahrnu počet tahů, které jsem potřeboval k dosažení tohoto stavu, a heuristiku, kterou odhadnu počet tahů do cílového stavu.

Jako heuristiku použiji Manhattan vzdálenost všech kostiček proti cílovému stavu.

In [13]:
def cost_a_asterisk(state, moves):
    dist = 0
    for i1, val in enumerate(final_state):
        i2 = state.index(val)
        x1, y1 = i1 % W, i1 // H
        x2, y2 = i2 % W, i2 // H
        dist += abs(x1 - x2) + abs(y1 - y2)
    return moves + dist

Testování

A teď bych již měl mít vše, co potřebuji pro testování jednotlivých variant řešení.

Připravil jsem si testovací vzorky, na kterých zkusím jednotlivé algoritmy a vyhodnocovací funkce. Dále budu měřit čas, jak dlouho mně trvá vyhledání výsledku.

Testovací vzorky jsem vytvářel náhodným přesouváním kostiček z výchozího stavu. Podle toho, kolik náhodných tahů provedu, dostanu více složité zadání.

V prvním testovacím vzorku jsem udělal 30 náhodných tahů. Vzhledem k tomu, že výsledky pro BFS jsou výrazně horší než pro zbylé dva algoritmy, udělal jsem ještě jednu sadu se 100 náhodnými tahy.

In [14]:
samples_30 = [
[3, 1, 4, 6, 2, 8, 0, 7, 5],
[4, 2, 7, 1, 0, 3, 6, 8, 5],
[2, 6, 0, 1, 3, 5, 7, 8, 4],
[4, 1, 0, 3, 6, 2, 7, 8, 5],
[3, 1, 4, 6, 2, 8, 0, 7, 5],
]

samples_100 = [
[3, 7, 1, 6, 2, 5, 0, 8, 4],
[3, 2, 7, 5, 8, 4, 6, 1, 0],
[3, 5, 0, 6, 7, 1, 2, 8, 4],
[1, 8, 7, 3, 0, 4, 5, 2, 6],
[0, 4, 8, 6, 5, 2, 3, 1, 7],
[0, 1, 7, 6, 3, 2, 8, 4, 5],
]


def timed(func):
    def func_wrapper(*args, **kwargs):
        import time
        start_time = time.time_ns()
        result = func(*args, **kwargs)
        end_time = time.time_ns()
        return result, (end_time - start_time) // 10**6
    return func_wrapper


@timed
def timed_solve(st, f):
    return solve(st, f)


print("*** 1. sample set (30  random moves)", "*"*24)
for sample in samples_30:
    print(sample)
    res = timed_solve(sample, cost_bfs)
    print(f"   BFS:      ==>  moves required: {res[0]:4d},  time consumed: {res[1] / 1000:.03f}")
    res = timed_solve(sample, cost_tiles)
    print(f"   Dijkstra: ==>  moves required: {res[0]:4d},  time consumed: {res[1] / 1000:.03f}")
    res = timed_solve(sample, cost_a_asterisk)
    print(f"   A*:       ==>  moves required: {res[0]:4d},  time consumed: {res[1] / 1000:.03f}")

print()
print("*** 2. sample set (100 random moves)", "*"*24)
for sample in samples_100:
    print(sample)
    res = timed_solve(sample, cost_tiles)
    print(f"   Dijkstra: ==>  moves required: {res[0]:4d},  time consumed: {res[1] / 1000:.03f}")
    res = timed_solve(sample, cost_a_asterisk)
    print(f"   A*:       ==>  moves required: {res[0]:4d},  time consumed: {res[1] / 1000:.03f}")
*** 1. sample set (30  random moves) ************************
[3, 1, 4, 6, 2, 8, 0, 7, 5]
   BFS:      ==>  moves required:   14,  time consumed: 1.021
   Dijkstra: ==>  moves required:   14,  time consumed: 0.004
   A*:       ==>  moves required:   14,  time consumed: 0.002
[4, 2, 7, 1, 0, 3, 6, 8, 5]
   BFS:      ==>  moves required:   12,  time consumed: 0.209
   Dijkstra: ==>  moves required:   12,  time consumed: 0.001
   A*:       ==>  moves required:   12,  time consumed: 0.000
[2, 6, 0, 1, 3, 5, 7, 8, 4]
   BFS:      ==>  moves required:   16,  time consumed: 7.465
   Dijkstra: ==>  moves required:   16,  time consumed: 0.013
   A*:       ==>  moves required:   16,  time consumed: 0.001
[4, 1, 0, 3, 6, 2, 7, 8, 5]
   BFS:      ==>  moves required:   12,  time consumed: 0.153
   Dijkstra: ==>  moves required:   12,  time consumed: 0.001
   A*:       ==>  moves required:   12,  time consumed: 0.002
[3, 1, 4, 6, 2, 8, 0, 7, 5]
   BFS:      ==>  moves required:   14,  time consumed: 1.182
   Dijkstra: ==>  moves required:   14,  time consumed: 0.004
   A*:       ==>  moves required:   14,  time consumed: 0.002

*** 2. sample set (100 random moves) ************************
[3, 7, 1, 6, 2, 5, 0, 8, 4]
   Dijkstra: ==>  moves required:   16,  time consumed: 0.015
   A*:       ==>  moves required:   16,  time consumed: 0.003
[3, 2, 7, 5, 8, 4, 6, 1, 0]
   Dijkstra: ==>  moves required:   22,  time consumed: 4.363
   A*:       ==>  moves required:   22,  time consumed: 0.083
[3, 5, 0, 6, 7, 1, 2, 8, 4]
   Dijkstra: ==>  moves required:   20,  time consumed: 0.661
   A*:       ==>  moves required:   20,  time consumed: 0.121
[1, 8, 7, 3, 0, 4, 5, 2, 6]
   Dijkstra: ==>  moves required:   22,  time consumed: 5.387
   A*:       ==>  moves required:   22,  time consumed: 0.035
[0, 4, 8, 6, 5, 2, 3, 1, 7]
   Dijkstra: ==>  moves required:   20,  time consumed: 0.472
   A*:       ==>  moves required:   20,  time consumed: 0.046
[0, 1, 7, 6, 3, 2, 8, 4, 5]
   Dijkstra: ==>  moves required:   18,  time consumed: 0.075
   A*:       ==>  moves required:   18,  time consumed: 0.014

Komentář k testům

Jak se asi dalo očekávat, nejslibnější výsledky dává algoritmus A* s heuristikou počítanou jako Manhattan vzdálenost všech kostiček proti cílovému stavu.

Na Googlu je možné najít další varianty řešení s lepším odhadem potřebných tahů, jako je třeba „Linear conflicts heauristic“.

Řešení pro CodingGame

Jak jsem již psal v úvodu, tenhle problém jsem řešil v rámci cvičení na CodingGame.

To, co mne ještě dost zabavilo, bylo následující pravidlo pro danou hru:


Constraints:

Response time first turn ≤ 1000ms


Jinak řečeno, výsledek jsem potřeboval dostat do jedné sekundy. A to byl dost velký problém.

Některé úpravy, které jsem udělal pro zlepšení rychlosti řešení:

  • Stav hry reprezentuji jako objekt
    • jednotlivá políčka jsou reprezentována jako n-tice
    • porovnání stavů se dělá na základě celého čísla, které získám zřetězením číslic všech políček
  • Tam, kde je to možné, nepoužívám seznam ale generátor
  • Pro vyhodnocení stavu jsem použil heuristiku Manhattan distance s korekcí na  Linear Conflicts
  • Výsledek řešení není počet tahů, ale seznam všech stavů od výchozího do cílového (v odpovědi musím předat seznam tahů, které je potřeba udělat pro vyřešení hry)

No a dále uvádím výsledek svého snažení bez dalších zbytečných komentářů:


import sys
import heapq

W = 4
H = 3

MAX_COST = 50

initial_state = []

for i in range(3):
    for j in input().split():
        x = int(j)
        initial_state.append(x)

class Tiles:
    def __init__(self, seq):
        self.data = tuple(seq)
        self.value = int(''.join(("{0:02d}".format(i) for i in self.data)))

    def __eq__(self, other):
        return self.value == other.value

    def __iter__(self):
        return iter(self.data)

    def __len__(self):
        return len(self.data)

    def __getitem__(self, key):
        return self.data[key]

    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return f"Tiles:[val={self.value}, data={self.data}]"

    def index(self, value):
        return self.data.index(value)

    def next_states(self):
        def swap(data, a, b):
            for i in range(len(data)):
                if i == a:
                    yield data[b]
                elif i == b:
                    yield data[a]
                else:
                    yield data[i]

        i, st = self.data.index(0), []
        if i - W >= 0:
            st.append(Tiles(swap(self.data, i, i - W)))
        if i + W < len(self.data):
            st.append(Tiles(swap(self.data, i, i + W)))
        if i % W - 1 >= 0:
            st.append(Tiles(swap(self.data, i, i - 1)))
        if i % W + 1 < W:
            st.append(Tiles(swap(self.data, i, i + 1)))
        return st

start_state = Tiles(initial_state)
final_state = Tiles(range(W * H))

def get_manhattan_distance(a, b=final_state):
    dist = 0
    for i1, val in enumerate(a):
        if val:
            i2 = b.index(val)
            x1, y1 = i1 % W, i1 // H
            x2, y2 = i2 % W, i2 // H
            dist += abs(x1 - x2) + abs(y1 - y2)
    return dist

def get_linear_conflicts(a):
    rows = (tuple((a[i + j] for j in range(0, W) if i <= a[i + j] < i + W)) for i in range(0, len(a), W))
    conflicts = 0
    for row in rows:
        if not row:
            continue
        min_value = row[0]
        for i in range(len(row)):
            if row[i] < min_value:
                conflicts, min_value = conflicts + 1, row[i]
    return conflicts

def get_linear_distance(a, b=final_state):
    return get_manhattan_distance(a, b) + get_linear_conflicts(a)

def solve_a_asterisk(st, f):
    q = []
    heapq.heappush(q, (f(st), st, []))
    visited = set()
    while q:
        pri, state, prev = heapq.heappop(q)
        prev.append(state)
        visited.add(state.value)
        if state == final_state:
            return prev
        else:
            for t in state.next_states():
                if t.value not in visited:
                    cost = len(prev) + f(t)
                    if cost <= MAX_COST:
                        heapq.heappush(q, (cost, t, prev[:]))
    return []

res = solve_a_asterisk(start_state, get_manhattan_distance)
for m in res[1:]:
    i = m.index(0)
    print(i // W, i % W) 

A to je vše.

Pokud budete chtít experimentovat, pak zde je zdroj článku.

Sdílet