ジグザグワーズを再帰で解こうとしたら、時間かかり過ぎ

はじめに

　スケルトンパズルを再帰でイライラさせられていた雑誌に載っていた問題が解けたので、調子に乗ってジグザグワーズも再帰で解けないかなと挑戦してみました。結果、プログラムは動いたけど、雑誌の問題は場合の数が多すぎて終わらない。使い物にならない。

ジグザグワーズの例題とルール

　例題は自作です。

ルール

1. リストのワードですべてのマスを埋める
2. ワードの一文字目がパズルの同じ番号に入る
3. ワードにある同じ文字は共有できる
4. 番号は左上から右へ右端から次段の左端へ順番に振る

プログラムの前準備

1. パネル（マス集合）のマスに左上から番号(0,1,･･･)を振る
2. 先頭マスの位置をリストのワードと紐づける
3. 作業効率優先でマスとワードのクラスを作成する

プログラムの作成

環境

netに情報が多そうなpythonを選定、
Pycharmを入れて確認(昔に比べれば天国)
PyCharm 2023.2 (Community Edition)
Build #PC-232.8660.197, built on July 26, 2023

置くことが可能なワードのパターンを作成する

　ワードが置ける形状を作成する
下は"面目一新"の二文字目を右側に置いた場合のワードが置ける形状を表示したもの。

４文字の場合の実現パターンは「"右上左","右上上","右上右","右右上","右右右"
"右右下","右下右","右下下","右下左"」の９パターンで上下左右あるので全部で３６パターン、先頭マスの位置によりさらに制約があるのでパターン数は減るはず。
とりあえず、テーマとしている再帰を使って作成
条件は隣にマスがあるかどうか、36x4=144パターンが64パターンに削減されてました。

    def makePattern(self, masul):
        pat = [self.firstPosition]
        self.genPat(masul, 0, pat)

    def genPat(self, masul, n, pat):
        if n == self.word_num - 1:
            self.pattern.append(copy.copy(pat))
            return
        for branch in "上下左右":
            m = masul[pat[-1]].getTonariMasu(branch)
            if m is not None:
                if not m in pat:
                    pat.append(m)
                    self.genPat(masul, n + 1, pat)
                    pat.pop(-1)
        return

※getTonariMasuは隣のマスがあれば番号、なければNoneを返す

最終的なプログラム

# coding: utf-8
import time
import copy

PanelYoko = 4
PanelTate = 4
# [単語, 先頭マス位置] 左上から0・・・と割り付け
WordList = [["面目一新", 2], ["生真面目", 5], ["地方新聞", 8], ["女子大生", 12], ["記念写真", 15]]

class Masu:
    def __init__(self, n):
        self.id = n
        self.moji = None

    def getTonariMasu(self, branch):
        if branch == "上":
            return self.id - PanelYoko if self.id // PanelYoko > 0 else None
        elif branch == "下":
            return self.id + PanelYoko if self.id // PanelYoko < (PanelTate - 1) else None
        elif branch == "左":
            return self.id - 1 if self.id % PanelYoko != 0 else None
        elif branch == "右":
            return self.id + 1 if self.id % PanelYoko < (PanelYoko - 1) else None


class Word:
    def __init__(self, word):
        self.word = word[0]
        self.word_num = len(self.word)
        self.firstPosition = word[1] # 単語の最初の位置
        self.preMoji = [''] * self.word_num # 以前のマスに含まれる文字
        self.pattern = []

    def makePattern(self, masul):
        pat = [self.firstPosition]
        self.genPat(masul, 0, pat)

    def genPat(self, masul, n, pat):
        if n == self.word_num - 1:
            self.pattern.append(copy.copy(pat))
            return
        for branch in "上下左右":
            m = masul[pat[-1]].getTonariMasu(branch)
            if m is not None:
                if not m in pat:
                    pat.append(m)
                    self.genPat(masul, n + 1, pat)
                    pat.pop(-1)
        return

    def possible(self, masul, branch):
        for i in range(self.word_num):
            if masul[branch[i]].moji is not None:
                if masul[branch[i]].moji != self.word[i]:
                    return False
        return True

    def ahead(self, masul, branch):
        for i in range(self.word_num):
            self.preMoji[i] = masul[branch[i]].moji
            masul[branch[i]].moji = self.word[i]

    def back(self, masul, branch):
        for i in range(self.word_num):
            masul[branch[i]].moji = self.preMoji[i]

def solve(masul, wordl, n):
    if n == len(wordl):
        return True
    for branch in wordl[n].pattern:
        if wordl[n].possible(masul, branch):
            wordl[n].ahead(masul, branch)
            if solve(masul, wordl, n + 1):
                return True
            wordl[n].back(masul, branch)
    return False

def main():
# 初期化
    masul = []
    for n in range(PanelYoko*PanelTate):
        masul.append(Masu(n))
    wordl = []
    for w in WordList:
        wordl.append(Word(w))
        masul[w[1]].moji = w[0][0]
    # 適合パターン作成、事前の枝刈り
    for w in wordl:
        w.makePattern(masul)

#    解決
    start = time.time()
    solve(masul, wordl,  0)
    end = time.time()

    print(f'time: {end - start:.3f}s')
    line = ""
    for j in range(len(masul)):
        line += masul[j].moji
        if j % 4 == 3:
            print(line)
            line = ""

if __name__ == '__main__':
    main()

結果

time: 0.001s
新聞面目
方生真一
地大写新
女子念記

【考察】思ったより遅い

　雑誌に載っていた17x17マスの77ワードのジグザグワーズでは３時間かけても収束しなかった
　原因として考えられるのは以下の通り

1. 本人の技量不足 「クラス利用」、「組み方に問題がある」など
   　深さ方向をマスではなくて、ワードにしたのがいけなかったかも？
2. 場合の数が多すぎて再帰アプローチが解法として適切でない
3. python + pycharmが重い（便利な分C++などに比べると。。。）
   　
   でも、まずは適切な時間で解ける例題作成が最優先か、１分位のが欲しい