Puzzle Quest 2 の呪文学習クエスト解法を探索する。幅優先。中断/再開機能付き。理論上は全て解ける。しかし、メモリ等の制限で複雑さが高い問題を解くのは難しい。C言語で作ったほうがよかった。

puzzlequest.py

import datetime
import pathlib
import pickle
import sys


class Board:
    def __init__(self, size_x: int, size_y: int, value: str):
        self._size_x = size_x
        self._size_y = size_y
        self._value = list(value)

    def __eq__(self, a) -> bool:
        return self._size_x == a._size_x and self._value == a._value

    def get_value(self, x: int, y: int) -> str:
        return self._value[self._index(x, y)]

    def set_value(self, x: int, y: int, value: str) -> None:
        self._value[self._index(x, y)] = value

    @property
    def size_x(self) -> int:
        return self._size_x

    @property
    def size_y(self) -> int:
        return self._size_y

    def _index(self, x: int, y: int) -> int:
        return self.size_x * y + x

    def print(self, file=sys.stdout) -> None:
        str = "-" * (self.size_x + 2) + "\n"
        for y in range(self.size_y):
            str = str + "|" + \
                "".join(
                    self._value[y * self.size_x: (y + 1) * self.size_x]) + "|\n"
        str = str + "-" * (self.size_x + 2)
        print(str, file=file)

    def solve(self) -> bool:
        changing = True
        changed = False
        while changing:
            temp_value = self._value.copy()
            changing = False
            # horizontial
            for y in range(self.size_y):
                for x in range(self.size_x - 2):
                    if self.get_value(x, y) == self.get_value(x + 1, y) == self.get_value(x + 2, y) != " ":
                        temp_value[self._index(x, y)] = " "
                        temp_value[self._index(x + 1, y)] = " "
                        temp_value[self._index(x + 2, y)] = " "
                        changing = True
            # vertical
            for x in range(self.size_x):
                for y in range(self.size_y - 2):
                    if self.get_value(x, y) == self.get_value(x, y + 1) == self.get_value(x, y + 2) != " ":
                        temp_value[self._index(x, y)] = " "
                        temp_value[self._index(x, y + 1)] = " "
                        temp_value[self._index(x, y + 2)] = " "
                        changing = True
            # fall
            if changing:
                new_value = list(" " * len(self._value))
                for x in range(self.size_x):
                    new_y = self.size_y - 1
                    for y in range(self.size_y - 1, -1, -1):
                        if temp_value[self._index(x, y)] != " ":
                            new_value[self._index(
                                x, new_y)] = temp_value[self._index(x, y)]
                            new_y -= 1
                self._value = new_value
                changed = True

        return changed

    def swap(self, x: int, y: int, direction: str) -> None:
        if direction == "v":
            new_x = x
            new_y = y + 1
        elif direction == "h":
            new_x = x + 1
            new_y = y
        temp = self.get_value(x, y)
        self.set_value(x, y, self.get_value(new_x, new_y))
        self.set_value(new_x, new_y, temp)

    def is_empty(self) -> bool:
        return self._value == list(" " * (self.size_x * self.size_y))


class LinkedBoard(Board):
    def __init__(self, size_x: int, size_y: int, value: str):
        super().__init__(size_x, size_y, value)
        self.prev = list()
        self.next = list()

    def copy(self):
        return LinkedBoard(self.size_x, self.size_y, self._value)


class Manipulation():
    def __init__(self, index: int, x: int, y: int, direction: str):
        self.index = index
        self.x = x
        self.y = y
        self.direction = direction

    def print(self) -> None:
        print("{index}: ({x}, {y}) {direction}".format(
            index=self.index, x=self.x, y=self.y, direction=self.direction))


class BoardTree():
    def __init__(self) -> None:
        self._tree = list()
        self.index = 0

    def make(self, root_board: LinkedBoard, temporary_file: str) -> None:
        def append_answer(searching_board, x: int, y: int, direction: str) -> bool:
            temp_board = searching_board.copy()
            temp_board.swap(x, y, direction)
            new_board = temp_board.copy()
            changed = new_board.solve()
            if changed:
                registered = False
                for registered_index in range(len(self._tree)-1, -1, -1):
                    if new_board == self._tree[registered_index]:
                        registered = True
                        self._tree[registered_index].prev.append(
                            Manipulation(self.index, x, y, direction))
                        searching_board.next.append(Manipulation(
                            registered_index, x, y, direction))
                        break
                if not registered:
                    new_board.prev.append(Manipulation(
                        self.index, x, y, direction))
                    self._tree.append(new_board)
                    searching_board.next.append(Manipulation(
                        len(self._tree) - 1, x, y, direction))
                    if new_board.is_empty():
                        return True
                    if len(self._tree) % 1000 == 0:
                        print("\n{length}".format(length=len(self._tree)))
                        self._tree[-1].print()
            return False

        self.temporary_file = temporary_file
        self.last_timestamp = datetime.datetime.utcnow()
        if self.index == 0:
            self._tree.append(root_board)
        while self.index < len(self._tree):
            print("{index} / {length}\r".format(index=self.index,
                                                length=len(self._tree)), end="")
            searching_board = self._tree[self.index]
            if len(searching_board.next) == 0:
                for y in range(searching_board.size_y):
                    for x in range(searching_board.size_x - 1):
                        find = append_answer(searching_board, x, y, "h")
                        if find:
                            return
                for y in range(searching_board.size_y - 1):
                    for x in range(searching_board.size_x):
                        find = append_answer(searching_board, x, y, "v")
                        if find:
                            return
            self.index += 1
            if datetime.datetime.utcnow() - self.last_timestamp > datetime.timedelta(seconds=1):
                with open(self.temporary_file, "wb") as f:
                    pickle.dump(self, f)
                self.last_timestamp = datetime.datetime.utcnow()
                print("dumped {datetime}".format(
                    datetime=self.last_timestamp.isoformat(sep=' ')))

    def print(self, file=sys.stdout) -> None:
        def get(a):
            if len(a) == 0:
                return "None"
            else:
                return ",".join(str(x.index) for x in a)

        index = 0
        print("index = {index}".format(index=self.index), file=file)
        for board in self._tree:
            print("No. = {index}".format(index=index), file=file)
            board.print(file)
            print("prev = {prev}, next = {next}".format(
                prev=get(board.prev), next=get(board.next)), file=file)
            index += 1

    def print_answer(self) -> None:
        for index in range(len(self._tree)-1, -1, -1):
            if self._tree[index].is_empty():
                prev = index
                while True:
                    self._tree[prev].print()
                    if len(self._tree[prev].prev) > 0:
                        self._tree[prev].prev[0].print()
                        prev = self._tree[prev].prev[0].index
                    else:
                        break


class BoardSolver():
    def __init__(self, size_x: int, size_y: int, value: str, temporary_file: str):
        self.board = LinkedBoard(size_x, size_y, value)
        if pathlib.Path(temporary_file).exists():
            with open(temporary_file, "rb") as f:
                self.board_tree = pickle.load(f)
                with open("./BoardSolver.log", "w") as wf:
                    self.board_tree.print(wf)
        else:
            self.board_tree = BoardTree()
        self.temporary_file = temporary_file

    def solve(self) -> None:
        self.board_tree.make(self.board, self.temporary_file)
        self.board_tree.print_answer()


def test_board2():
    bs = BoardSolver(8, 8,
                    "   BB   "
                    "   YY   "
                    "   RR   "
                    " B YY B "
                    " Y YR Y "
                    " R RY R "
                    "BY YR YB"
                    "RR RY RR",
                     r"./temporary.dat")
    bs.solve()


if __name__ == '__main__':
    test_board2()