Hlavolam II

... Petr Blahoš, 2. 11. 2018 Python

V minulém díle jsme pomocí OpenCV oskenovali hlavolam a převedli jsme jej do formy, stravitelné pro počítač. Naznačil jsem, že budeme tento hlavolam řešit pomocí počítače. Po rozmyšlení jsem ale došel k závěru, že je to zatím pro to nebohé pachole moc složité (datové struktury, rekurze), takže se věnujeme něčemu jinému, a zde Vám jen předestřu hotové řešení.

Řešení

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


def widen_puzzle(puzzle):
    """
    Adds 10 empty cells (value 0) on each side of the field.
    """
    sz0 = len(puzzle)
    sz1 = sz0 + 20
    out = [[0] * sz1 for i in range(sz1)]
    for i in range(sz0):
        for j in range(sz0):
            out[i + 10][j + 10] = puzzle[i][j]

    return out


DIRS = [
    (-1, 1), (-1, 0), (-1, -1),
    (0, 1),           (0, -1),
    (1, 1),  (1, 0),  (1, -1),
]


def make_border(puzzle):
    """ changes the value to -1 on the puzzle borders. """
    sz = len(puzzle)
    for i in range(5, sz - 5):
        for j in range(5, sz - 5):
            if puzzle[i][j]:
                continue
            for (dx, dy) in DIRS:
                if puzzle[i + dx][j + dy] > 0:
                    puzzle[i][j] = -1
                    break


def deep_solve(puzzle):
    """ Finds all solutions of the puzzle. """
    puzzle = widen_puzzle(puzzle)
    make_border(puzzle)

    path = [(20, 20), ]
    dirs = []
    visited = set()
    follow_path(puzzle, path, dirs, visited)


def follow_path(puzzle, path, dirs, visited):
    """
    Makes one step in every direction from the last point (path[-1])
    one by one, and recursively calls itself to follow the path.
    """
    if not path:
        return
    for (dx, dy) in DIRS:
        (x, y) = path[-1]
        val = puzzle[x][y]
        (xx, yy) = (x + val * dx, y + val * dy)
        if (xx, yy) in visited:
            continue
        visited.add((xx, yy))
        try:
            path.append((xx, yy))
            dirs.append((dx, dy))

            if 0 == puzzle[xx][yy]:
                continue  # outside
            if -1 == puzzle[xx][yy]:
                if puzzle[xx + dx * -1][yy + dy * -1] > 0:
                    print_path(puzzle, path, dirs)
                continue  # border
            follow_path(puzzle, path, dirs, visited)
        finally:
            del dirs[-1]
            del path[-1]


def print_path(puzzle, path, dirs):
    print("%s, " % (dirs, ))


if "__main__" == __name__:
    deep_solve(PUZZLE)

Pár slov:

PUZZLE je to pole, které jsme dostali z algoritmu počítačového vidění v minulém díle.
Nejprve jej rozšíříme o 10 prázdných polí z každé strany. Tím pádem nebudeme při skákání muset hlídat, jestli jsme uvnitř pole, nebo ne.
Dále na hranici doplníme hodnotu -1. Tím pádem, když skočíme a jsme na hodnotě 0, tak jsme venku. Když jsme na hodnotě -1, tak jsme na hranici, což ovšem ještě není jistě řešení.
Když se postavíme na druhé políčko od konce třetího řádku (je tam číslo 3, za ním je 5, tak na tu trojku), a jdeme doleva nahoru, ocitneme se na políčku, které je na hranici, čili vypadá to, že jsme našli řešení. Ale řešení to, jak asi chápete, není.
No a pak už jen začneme uprostřed (funkce deep_solve), připravíme pole s dosavadní cestou (path) a s dosavadními směry (dirs) a zavoláme funkci follow_path, která udělá 1 krok (postupně ve všech směrech) a rekurzivně zavolá sama sebe.
Cestou si ještě ukládáme navštívená políčka, jinak bychom se mohli zacyklit.
Když algoritmus najde řešení, vypíše směry, kterými se postupně má jít. Netvrdím, že ta řešení jsou nejoptimálnější. Vyšla 187 kroků dlouhá.