ジグザグワーズを人間ぽく解いてみました

はじめに

　ジグザグワーズも再帰で解けないかなと挑戦してみましたが、プログラムは動いたけど、雑誌の問題は場合の数が多すぎて終わらない、使い物にならないという結果になった。そこで、今回は、再帰ではなく人間ぽく解いてみた。ただし、パターンの削除で追い詰めるは人間はやらないので、そこらへんは異なる。【結果】前回、再帰で３時間でも収束しなかった雑誌の問題を約0.1秒で解くことができた。プログラムの全文掲載は懸賞問題など雑誌に影響が出る可能性を考慮し非公開とした。

ジグザグワーズの例題とマス番号、ワード番号の割り付け

　パネル番号は左上マスから右マスへ右端にきたら次段の左端マスへ順番に振る（黒字）。ワードの初期マス位置に「ワード番号,一文字目」形式で記載（青字）

プログラム環境

Python 3.11
PyCharm 2023.2 (Community Edition)
Build #PC-232.8660.197, built on July 26, 2023

プログラムのクラス構成

問題入力フォーマット

問題の入力フォーマットは以下のように定義した

t,例題　piyokiti作  # t,タイトル
s,yoko,4            # s,yoko,横のマス数
s,tate,4            # s,tate,縦のマス数
1,面目一新,2        # ワード番号(1～),ワード,ワードの初期マス位置
2,生真面目,5
3,地方新聞,8
4,女子大生,12
5,記念写真,15

パターンの作成

　ワードと初期配置から置ける可能性のあるパターンをすべて作成する。
例題図の「1,面目一新」であれば、(2,1,0,4), (2,3,7,6),など今回
パターンは再帰処理（深さ優先探索）で作成し直した。
以下は、例題のワード「1,面目一新」の初期のインスタンス変数とマス6のパターン配布時のインスタンス変数の例

class Word:
        self._id = 0
        self._word = "面目一新"
        self._word_num = 4
        self._first_position = 2
        self._patterns = [(2, 6, 10, 14), (2, 6, 10, 9), (2, 6, 10, 11), (2, 6, 7, 3), (2, 6, 7, 11), (2, 1, 0, 4), (2, 3, 7, 11), (2, 3, 7, 6)]
class Masu:
        self._id = 6
        self._syoki = 0  # 問題のワード番号に対応 1, 2, 3, ･･･ 0は指定なし
        self._valid = False
        self._moji = ""
        self._next = [2, 10, 5, 7] # 隣のマスid
        self._patterns = {(2, 6, 10, 14): (0, '面目一新', '目'), (2, 6, 10, 9): (0, '面目一新', '目'), (2, 6, 10, 11): (0, '面目一新', '目'), (2, 6, 7, 3): (0, '面目一新', '目'), (2, 6, 7, 11): (0, '面目一新', '目'), (2, 3, 7, 6): (0, '面目一新', '新'), (5, 1, 2, 6): (1, '生真面目', '目'), (5, 9, 10, 6): (1, '生真面目', '目'), (5, 6, 2, 1): (1, '生真面目', '真'), (5, 6, 2, 3): (1, '生真面目', '真'), (5, 6, 10, 14): (1, '生真面目', '真'), (5, 6, 10, 9): (1, '生真面目', '真'), (5, 6, 10, 11): (1, '生真面目', '真'), (5, 6, 7, 3): (1, '生真面目', '真'), (5, 6, 7, 11): (1, '生真面目', '真'), (8, 9, 10, 6): (2, '地方新聞', '聞'), (15, 11, 7, 6): (4, '記念写真', '真'), (15, 11, 10, 6): (4, '記念写真', '真'), (15, 14, 10, 6): (4, '記念写真', '真')}

解法アプローチ

　解法アプローチは原則としてワードが持つパターンを処理し、その結果を反映させる。反映手段は以下の３種類

1. 文字を確定する
2. パターンから存在不可能なパターンを削除する
3. 仮定を適用する(try_and_error)

文字の確定手法

V101 問題で指定された文字の確定

例題におけるマス2の「1,面」など 問題で指定された文字を確定する

V102 ワードが進む先が１マスに確定

　※「確定マス」「未確定マス」の表記は以降省略

「大願成就」の「願」の置き場所はマスAだけ
【実装概要】パターンをインデックス毎にスライスし、同一マスIDだったら確定する

    Class Word:
    def sameid_slicing(self, masul):
        slice_index = [[] for _ in range(self._word_num)]
        for pat in self._patterns:
            for i, mi in enumerate(pat):
                slice_index[i].append(mi)
        for i, sid in enumerate(slice_index):
            if i == 0:  # 先頭は確定済み
                continue
            if len(set(sid)) == 1:  # 全て同じマスid
                if masul[sid[0]].set_valid(self._word[i]):
                    zigzag_logger.info(f"V102,{sid[0]},{self._word[i]}")

※　理解のためだけに、所属するクラスを"Class Word"などと記載

V103 マスに入る可能性がある文字がすべて同じ文字である

マスAに到達できるワードは「7,組織的変化」と「11,化学的変化」だけで文字は「化」
【実装概要】WordクラスからMasuクラスへパターンを配布し、マス内の文字が同じあれば確定する

    Class Masu:
    def set_pattern(self, pattern, word):
        if pattern not in self._patterns:
            self._patterns[pattern] = word  # word:=(id, "花鳥風月", "花")

    def determine_1moji(self):
        if self._valid:
            return False
        mojis = [self._patterns[pat][2] for pat in self._patterns]
        if len(set(mojis)) == 1 and not self._valid:
            if self.set_valid(mojis[0]):
                zigzag_logger.info(f"V103,{self._id},{mojis[0]}")
            return True
        return False

V104 マスに到達できるワードが一つ

マスAに到達できるワードは「44,多次元配列」だけ
【実装概要】マスの保持するパターン一つだけなら確定とする

    Class Masu:
    def determine_1pattern(self):
        if self._valid:
            return False
        if len(self._patterns) == 1:
            for pat in self._patterns:
                for i, mi in enumerate(pat):
                    if mi == self._id and not self._valid:
                        moji = self._patterns[pat][1][i]
                        if self.set_valid(moji):
                            zigzag_logger.info(f"V104,{self._id},{moji}")
                        break
            return True
        else:
            return False

V105 ワードが持つパターンが一つだけである

V104と同じだがV104はクラスMasu内パターンが一つの場合であり、V105はクラスWord内パターンが一つの場合である
【実装概要】ワードの保有するパターンが一つであれば確定する

    def valid_only_one_pattern(self, masul, code):
        if len(self._patterns) == 1:
            for i, mi in enumerate(self._patterns[0]):
                if masul[mi].set_valid(self._word[i]):
                    zigzag_logger.info(f"{code},{mi},{self._word[i]}")

V106 一つのパターンで二つのマスを排他的に占有する

ピンクマスのように「34,整数同士」の「数」と「士」がループして決められない場合がある。ピンクマスでそのパターン以外のワード「50,無量大数」の「数」がピンクマスで「数」を共有しているならば、その文字でマスを確定する
【実装概要】

1. ワードの持つパターンをスライシングして排他状態を検知する
2. そのマスに当該ワード以外のワードが存在するかチェックし、あれば確定する

    Class Solve:
    def exclusive_1pattern(self):
        for w in self.wordl:
            ex = w.exclusive_1pattern()
            if ex:
                #  ex:=((117, 135), ("力", "位")), im(index, moji):= [(117,"力")]
                im = self.masul[ex[0][0]].get_moji_except_exclusive([w.get_i()], ex[1])
                im += self.masul[ex[0][1]].get_moji_except_exclusive([w.get_i()], ex[1])
                if len(set(im)) == 1:
                    if self.masul[im[0][0]].set_valid(im[0][1]):
                        zigzag_logger.info(f"V106,{im[0][0]},{im[0][1]}")
                elif len(set(im)) == 2:
                    if im[0][0] != im[1][0] and im[0][1] != im[1][0]:
                        if self.masul[im[0][0]].set_valid(im[0][1]):
                            zigzag_logger.info(f"V106,{im[0][0]},{im[0][1]}")
                        if self.masul[im[1][0]].set_valid(im[1][1]):
                            zigzag_logger.info(f"V106,{im[1][0]},{im[1][1]}")
                else:
                    rpats = self.masul[ex[0][0]].get_patterns_except_1pair(ex[1])
                    for rp in rpats:
                        self.wordl[rp[0]].remove_patterns([rp[1]], f"R206")
    
    Class Word:
    def exclusive_1pattern(self):
        sp = self.slicing_patterns()
        for j, spj in enumerate(sp):
            for i, spi in enumerate(sp):
                if i < j:
                    if len(spi) == 2 and spi == spj:
                        return spi, (self._word[i], self._word[j])
        return False

    Class Masu:
        def get_moji_except_exclusive(self, wids, mojis):
        im = []
        for pat in self._patterns:
            if self._patterns[pat][2] in mojis:
                if self._patterns[pat][0] not in wids:
                    im.append((self._id, self._patterns[pat][2]))
        return im

V107 二つのパターンで二つのマスを排他的に占有する

V106と同様な状況が二つのワード「5,千客万来」、「6,顧客管理」で発生する場合がある。この場合もV106と同様に「20,給水管」の「管」がピンクマスで重なるなら、確定する
【実装概要】

1. マスに配布したパターンから可能性のあるワードのペアを抽出し、ワードのペアのパターンを各々スライシングし、同じマスIDの組を持つならば、排他的占有候補とする
2. 候補のなかから、マスIDの組の長さが2で文字が異なるものを「二つのパターンで二つのマスを排他的に占有している」とする
3. 排他マスに当該ワード以外のワードが存在するかチェックし、あれば確定する

    Class Solve:
    def exclusive_2patterns(self):
        wid_pairs = self.get_wid_pairs(half=True)
        for wp in wid_pairs:
            sp1 = self.wordl[wp[0]].slicing_patterns()
            sp2 = self.wordl[wp[1]].slicing_patterns()
            for sp in sp1:
                if sp not in sp2:
                    continue
                if len(sp) != 2:
                    continue
                moji1 = self.wordl[wp[0]].get_char(sp1.index(sp))
                moji2 = self.wordl[wp[1]].get_char(sp2.index(sp))
                if moji1 == moji2:
                    continue
                # ２文字で、２マスを占有 43:花/物, 45:花/物
                mojis = (moji1, moji2)
                im1 = self.masul[sp[0]].get_moji_except_exclusive(wp, mojis)
                im2 = self.masul[sp[1]].get_moji_except_exclusive(wp, mojis)
                if len(set(im1)) == 1 and not im2:
                    if self.masul[im1[0][0]].set_valid(im1[0][1]):
                        zigzag_logger.info(f"V107,{im1[0][0]},{im1[0][1]}")
                elif len(set(im2)) == 1 and not im1:
                    if self.masul[im2[0][0]].set_valid(im2[0][1]):
                        zigzag_logger.info(f"V107,{im2[0][0]},{im2[0][1]}")
                else:
                    rpats = self.masul[sp[0]].get_patterns_except_2pair(wp, mojis)
                    rpats += self.masul[sp[1]].get_patterns_except_2pair(wp, mojis)
                    if rpats:
                        for rp in rpats:
                            self.wordl[rp[0]].remove_patterns([rp[1]], f"R207,{rp[0]}")

    def get_wid_pairs(self, half=False):
        wid_pairs = []
        for m in self.masul:
            if m.is_valid():
                continue
            wids = set(m.get_wids())
            for w1 in wids:
                for w2 in wids:
                    if half:
                        if w1 < w2:
                            if (w1, w2) not in wid_pairs:
                                wid_pairs.append((w1, w2))
                    else:
                        if w1 != w2:
                            if (w1, w2) not in wid_pairs:
                                wid_pairs.append((w1, w2))
        return wid_pairs

パターンの削除手法

R201 ワードの持つパターンの中に、ワード外の文字を持つものがあれば削除する

マスAは「V102 ワードの進む先が１マスに確定」に該当し、「願」となる。「5,地方自治体」の持つパターンの中でマスAを含むものを削除する
【実装概要】
パターンの中で確定している文字を特定し、ワードの該当文字でなければ削除する

    def cutpattern_with_diffchar(self, masul):
        rpats = []
        for pat in self._patterns:
            for i, mi in enumerate(pat):
                if masul[mi].is_valid():
                    if masul[mi].get_moji() != self._word[i]:
                        rpats.append(pat)
                        break
        self.remove_patterns(rpats, f"R201,{self._id}")

R202 すべての文字が確定しているパターンがある場合、それ以外のパターンを削除する

「1,大願成就」が持つパターンの中に、パターン１：図の大願成就、パターン２：大願成Aの２パターンあれば、パターン２を削除する
【実装概要】

1. 含まれるすべて文字が確定しており、ワードの文字と一致しているパターンを検索
2. 一致パターン以外のパターンを削除する

    def cutpattern_without_valid(self, masul):
        if len(self._patterns) == 1:
            return
        for pat in self._patterns:
            if all([masul[mi].is_valid() and masul[mi].get_moji() == self._word[i]
                    for i, mi in enumerate(pat)]):
                for pat1 in self._patterns:
                    if pat1 != pat:
                        zigzag_logger.info(f"R202,{self._id},{pat1}]")
                self._patterns = [pat]
                break

R203 パターンが他のワードの行先をブロックしている

ピンクマスの「方」と「治」で「1,大願成就」の行方をブロックしている
【実装概要】
マスを通るワードのペアをすべて抽出し、ペアの一方のワードからパターンを選んだ時に、相手方のワードの持つパターンがすべてブロックされている場合、ブロックしているパターンを削除する

    Class Solve:
    def blocking_other_words_way(self):

        def is_blocking(block_pattern, wp):  # w.id pair
            block = []
            for pat2 in self.wordl[wp[1]].get_patterns():
                is_block = False
                for mi2 in pat2:
                    if mi2 in block_pattern:
                        c1 = self.wordl[wp[1]].get_char(pat2.index(mi2))
                        c2 = self.wordl[wp[0]].get_char(block_pattern.index(mi2))
                        if c1 != c2:  # blockしている
                            is_block = True
                            break
                block.append(is_block)
            if all(block):
                return True
            return False

        wid_pairs = self.get_wid_pairs()
        rpats = []
        for pair in wid_pairs:
            for pat1 in self.wordl[pair[0]].get_patterns():
                if is_blocking(pat1, pair):
                    rpats.append((pair, pat1))
        if rpats:
            for rp in rpats:
                self.wordl[rp[0][0]].remove_patterns([rp[1]], f"R203,{rp[0][0]},{rp[0][1]}")

    def get_wid_pairs(self, half=False):
        wid_pairs = []
        for m in self.masul:
            if m.is_valid():
                continue
            wids = set(m.get_wids())
            for w1 in wids:
                for w2 in wids:
                    if half:
                        if w1 < w2:
                            if (w1, w2) not in wid_pairs:
                                wid_pairs.append((w1, w2))
                    else:
                        if w1 != w2:
                            if (w1, w2) not in wid_pairs:
                                wid_pairs.append((w1, w2))
        return wid_pairs

R204 そのワードしか占有しないマスがある

マスAに入る文字がワード「11,大願成就」だけだった場合、ワード内でマスAを含まないパターンを削除する
【実装概要】

1. マスに含まれるワードが一つかチェックする
2. 一つであれば、ワード内のそのマスを含まないパターンを削除する

    Class Solve:
    def basic(self):
        for m in self.masul:
            wid = m.detect_1word()
            if wid:
                self.wordl[wid[0]].cutpattern_without_1word_masu(self.masul, m.get_i())
    Class Word:
    def cutpattern_without_1word_masu(self, masul, mi):
        rpats = []
        for pat in self._patterns:
            if mi not in pat:
                rpats.append(pat)
        if rpats:
            for pat in rpats:
                self._patterns.remove(pat)
                zigzag_logger.info(f"R204,{self._id},{pat}")
    Class Masu:
    def detect_1word(self):
        if self._syoki:
            return False
        wid = [self._patterns[pat][0] for pat in self._patterns]
        wid = list(set(wid))
        if len(wid) == 1:
            return wid
        return False

R205 パターンを選ぶとどのワードもたどり着けないマスが発生する

「13,一酸化炭素」のパターンの中でBマスを通るパターンを選ぶと、マスAに何も入れることができない（デッドマス）
【実装概要】

1. ブロックする可能性があるマスを抽出する
2. マスAがデッドマスかチェックし、当該パターンを削除する

    Class Solve
    def blocked_masu(self):

        # マス(cmi)に配布されているパターンのすべてが行先がない
        def become_dead_masu(bw, bpat, cmi):
            go_through = []
            for pat2 in self.masul[cmi].get_patterns():
                is_passing = True
                for mi2 in pat2:
                    if self.masul[mi2].is_valid():
                        continue
                    if mi2 in bpat:
                        moji1 = bw.get_char(list(bpat).index(mi2))
                        moji2 = self.masul[mi2].p_get_char_mi(pat2, mi2)
                        if moji1 != moji2:
                            is_passing = False
                            break
                go_through.append(is_passing)
            if not any(go_through):  # 一つも通過できるパターンがなければ、dead_masu
                return True
            return False

        for w in self.wordl:
            for pat in w.get_patterns():
                # ブロックする可能性のあるマスを抽出する
                candidates = []
                for mi in pat:
                    if self.masul[mi].is_valid():
                        continue
                    for pat1 in self.masul[mi].get_patterns():
                        for mi1 in pat1:
                            if not self.masul[mi1].is_valid():
                                if mi1 not in pat and mi1 not in candidates:
                                    candidates.append(mi1)
                # ブロックされているかどうか判定
                for mi in candidates:
                    if become_dead_masu(w, pat, mi):
                        w.remove_patterns([pat], f"R205,{w.get_i()},{mi}")

R206 一つのパターンで二つのマスを排他的に占有している

「34,整数同士」が二つのピンクマスを排他的に占有している場合、ピンクマスを通る「34,整数同士」以外のワードのパターンを削除する
【実装概要】
V106の分岐で確定しない場合は、ピンクマスを通る他のワードのパターンをすべて削除する
プログラムはV106参照

R207 二つのパターンで二つのマスを排他的に占有している

緑のマスは「万／管」で排他的になる場合がある。「5,千客万来」、「10,顧客管理」以外のワードのパターンの中で緑のマスを通るパターンがあれば削除する
【実装概要】
V107の分岐で確定しない場合は、緑のマスを通る他のワードのパターンをすべて削除する
プログラムはV107参照

トライアンドエラー(try_and_error)

解答が行き詰まった場合、論理的には完全に正しいと言えないが、かなり確率高いのでそのワードを置いて解き進めることがある。当然間違えていると消しゴムで消す。その工程をトライアンドエラーとして実装した。
【実装概要】

1. 文字の確定候補、ワードパターンの削除候補を探索し、最も可能性の高い候補を選ぶ
2. 文字、パターンをバックアップし、候補の試行後、論理的な解決手法をぶん回して、様子を見る
3. 前項の判定結果 => 処理
   1. 最後まで解けた場合 => 終了
   2. エラーがassertされた場合 => 文字、ワードパターンをリストアして、別の候補を試行
   3. また行き詰まった場合 => 次の候補を試行

    Class Zigzag:
    def try_and_error(self):
        while True:
            candidates = self.solve.collect_candidate("rank_a")
            if not candidates:
                candidates = self.solve.collect_candidate("rank_b")
            if not candidates:
                candidates = self.solve.collect_candidate("rank_c")
            for ca1 in candidates:
                self.solve.backup()
                self.solve.exec_candidate(ca1)
                result = self.solve_logical_loop()
                if result == "完了":
                    break
                elif result == "継続":
                    break
                elif result == "エラー":
                    self.solve.restore()  # 遭遇しなかっため未デバック
            else:
                continue
            if result == "完了":
                break

トライアンドエラーの候補

トライアンドエラーの候補のなかで、確率が高そうなものから A,B,Cとランク付けを実施した。

H301A 余分にマスを消費している(rank_A)

「33,眉目秀麗」の「目」がマスAにあるパターンがない訳ではないが、出題者としては美しくないので解消する事を考えるだろう。
【実装概要】
ワードのパターンをスライスし、「前後のインデックスが確定している、かつ、確定と非確定の文字を同時に持つ」インデックスを探索する

    Class Word:
    def spend_masu(self, masul):
        candidates = []
        if len(self._patterns) == 1:
            return candidates
        # 確定文字数が同じなら終了
        valid_num = []
        for pattern in self._patterns:
            valid_num.append(len([mi for mi in pattern if masul[mi].is_valid()]))
        valid_num = set(valid_num)
        if len(valid_num) == 1:
            return candidates
         mi = ()
        slp = self.slicing_patterns()
        for i, sp in enumerate(slp):
            if i == 0 or i == len(slp) - 1:
                continue
            if len(sp) != 2:
                continue
            if len(slp[i - 1]) != 1:
                continue
            if not masul[slp[i - 1][0]].is_valid():
                continue
            if len(slp[i + 1]) != 1:
                continue
            if not masul[slp[i + 1][0]].is_valid():
                continue
            if masul[sp[0]].is_valid() and not masul[sp[1]].is_valid():
                mi = (i, sp[1])
                break
            elif not masul[sp[0]].is_valid() and masul[sp[1]].is_valid():
                mi = (i, sp[0])
                break
            else:
                continue
        if not mi:
            return candidates
        rpats = []
        for pat in self._patterns:
            if pat[mi[0]] == mi[1]:
                rpats.append(pat)
        candidates.append(["H301A", self._id, rpats])
        return candidates

H302 ワードを構成しそうな文字が近くにある

「33,地方自治体」のワードの内、「方」と「自」がいかにも続いてワードを構成しているように見えるが、正確には方がマスAに抜ける可能性もわずかながら存在する
【実装概要】
距離、ワードを構成する文字ではないかと思われる文字（候補文字）数、問題が漢字仮名混じりかどうかでランクを判定
※　距離は、ワード内で確定文字と候補文字の間の文字数とした。「地方自治体」で「地」と候補文字「方」であれば距離0、「地」と候補文字「自」であれば距離1

1. 距離0、前図の「方」「自」など候補文字が２文字以上 => H302A ランクA
2. 距離0、候補文字が１文字で漢字、漢字仮名混じり問題 => H302A ランクA
3. 距離0、候補文字が１文字、漢字のみの問題 => H302B ランクB
4. 距離1以上、漢字のみの問題 => H302B ランクB

    Class Word:
    def prefer_more_valid_pattern(self, masul, kanamajiri):

        def count_valid_masu(pat1):
            return len([mi for mi in pat1 if masul[mi].is_valid()])

        if len(self._patterns) == 1:
            return []
        vcount = []
        for pat in self._patterns:
            vcount.append(count_valid_masu(pat))
        if len(set(vcount)) == 1:
            return []
        slpattern = self.slicing_patterns()
        # ワードの一部と推定される確定文字の特定と距離の算定
        distance = 0
        mojis = []
        for i, slp1 in enumerate(slpattern):
            slp = [masul[sp].is_valid() for sp in slp1]
            if not all(slp) and any(slp):
                mojis.append(self._word[i])
            elif not any(slp):
                if not mojis:
                    distance += 1
        candidates = []
        max1 = max(vcount)
        cans = [pat for pat in self._patterns if count_valid_masu(pat) < max1]
        if distance == 0:
            if len(mojis) > 1:
                candidates.append(["H302A", self._id, cans])
            else:
                if kanamajiri:
                    if any([self.is_kanji(moji) for moji in mojis]):
                        candidates.append(["H302A", self._id, cans])
                    else:
                        candidates.append(["H302B", self._id, cans])
                else:
                    candidates.append(["H302A", self._id, cans])
        else:
            if not kanamajiri:
                candidates.append(["H302B", self._id, cans])
        return candidates

H303 二つのワードが持つ同じ文字が未確定マス上で重なる

図のマスAは、「4,先客万来」の「万」と「9,百万長者」の「万」が重なる確率が高い
【実装概要】
二つのワードにより同一の文字が配置されるマスを検知し、
漢字仮名混じり問題であれば、H303A Aランク、漢字問題の場合は、H303C Cランクの候補とする

    Class Solve:
    def duplicate_kanji_masu(self):
        kanji = regex.compile(r'\p{Script=Han}+')
        kanji_dup = []
        for m in self.masul:
            duplicate_masu = m.detect_duplication()
            if duplicate_masu:
                if kanji.findall(duplicate_masu[0][2]):
                    kanji_dup.append(duplicate_masu)
        # 背反の漢字マスがある場合、候補から削除
        # dup:(58, (252, 253, 236, 235, 218, 217), 'れ')
        rdup = []
        for i1, dup1 in enumerate(kanji_dup):
            for i2, dup2 in enumerate(kanji_dup):
                if i1 < i2:
                    if dup1[0][2] == dup2[0][2]:
                        wi1 = [du1[0] for du1 in dup1]
                        wi2 = [du2[0] for du2 in dup2]
                        if set(wi1) == set(wi2):
                            if dup1 not in rdup:
                                rdup.append(dup1)
                            if dup2 not in rdup:
                                rdup.append(dup2)
        candidates = []
        for dup in kanji_dup:
            if dup not in rdup:
                if self.mondai.kanamajiri:
                    candidates.append(["H303A", dup])
                else:
                    candidates.append(["H303C", dup])
        return candidates
    Class Masu:
    def detect_duplication(self):
        dup = []
        if self._valid:
            return dup
        # 2ワード重なりのみ
        for i1, pat1 in enumerate(self._patterns):
            moji1 = self._patterns[pat1][2]
            wi1 = self._patterns[pat1][0]
            for i2, pat2 in enumerate(self._patterns):
                if i1 < i2:
                    moji2 = self._patterns[pat2][2]
                    wi2 = self._patterns[pat2][0]
                    if moji1 == moji2 and wi1 != wi2:
                        if (wi1, pat1, moji1) not in dup:
                            dup.append((wi1, pat1, moji1))
                        if (wi2, pat2, moji2) not in dup:
                            dup.append((wi2, pat2, moji2))
        return dup

結果、考察など

例題のログアウト

S101は状態監視:確定文字6, 残パターン数39と表記、確定文字が16となると完了となる

M101,E:/PROGRAM/puzzle/zigzag/mondai/Q10.txt
M102,例題　piyo999作
M103,4,4
M104,5
M105,1,面目一新,2
M105,2,生真面目,5
M105,3,地方新聞,8
M105,4,女子大生,12
M105,5,記念写真,15
V101,1,2,面
V101,2,5,生
V101,3,8,地
V101,4,12,女
V101,5,15,記
A101,0,(2, 6, 10, 14)
A101,0,(2, 6, 10, 9)
A101,0,(2, 6, 10, 11)
A101,0,(2, 6, 7, 3)
A101,0,(2, 6, 7, 11)
A101,0,(2, 1, 0, 4)
A101,0,(2, 3, 7, 11)
A101,0,(2, 3, 7, 6)
A101,1,(5, 1, 0, 4)
A101,1,(5, 1, 2, 6)
A101,1,(5, 1, 2, 3)
A101,1,(5, 9, 13, 14)
A101,1,(5, 9, 10, 6)
A101,1,(5, 9, 10, 14)
A101,1,(5, 9, 10, 11)
A101,1,(5, 4, 0, 1)
A101,1,(5, 6, 2, 1)
A101,1,(5, 6, 2, 3)
A101,1,(5, 6, 10, 14)
A101,1,(5, 6, 10, 9)
A101,1,(5, 6, 10, 11)
A101,1,(5, 6, 7, 3)
A101,1,(5, 6, 7, 11)
A101,2,(8, 4, 0, 1)
A101,2,(8, 9, 13, 14)
A101,2,(8, 9, 10, 6)
A101,2,(8, 9, 10, 14)
A101,2,(8, 9, 10, 11)
A101,3,(12, 13, 9, 5)
A101,3,(12, 13, 9, 10)
A101,3,(12, 13, 14, 10)
A101,4,(15, 11, 7, 3)
A101,4,(15, 11, 7, 6)
A101,4,(15, 11, 10, 6)
A101,4,(15, 11, 10, 14)
A101,4,(15, 11, 10, 9)
A101,4,(15, 14, 10, 6)
A101,4,(15, 14, 10, 9)
A101,4,(15, 14, 10, 11)
A101,4,(15, 14, 13, 9)
V102,13,子
R201,4,(15, 14, 13, 9)
try_num:0 ===================
S101,6,39                      # S101は状態監視:確定文字6, 残パターン数39
R201,1,(5, 9, 13, 14)
R201,2,(8, 9, 13, 14)
try_num:1 ===================
S101,6,37
try_num:2 ===================
S101,6,37
R203,0,4,(2, 6, 10, 11)
R203,1,4,(5, 9, 10, 11)
R203,1,4,(5, 6, 10, 11)
R203,2,4,(8, 9, 10, 11)
R203,0,3,(2, 6, 10, 9)
R203,1,3,(5, 9, 10, 6)
R203,1,3,(5, 9, 10, 14)
warning:R203,1,3,(5, 9, 10, 11)
R203,1,3,(5, 6, 10, 9)
R203,2,3,(8, 9, 10, 6)
R203,2,3,(8, 9, 10, 14)
warning:R203,2,3,(8, 9, 10, 11)
R203,4,3,(15, 11, 10, 9)
R203,4,3,(15, 14, 10, 9)
V102,4,方
V102,0,新
V102,1,聞
V103,9,大
R204,3,(12, 13, 14, 10)
S101,10,24
R203,0,4,(2, 6, 7, 11)
R201,0,(2, 1, 0, 4)
R201,1,(5, 1, 0, 4)
R201,1,(5, 1, 2, 6)
R201,1,(5, 1, 2, 3)
R201,1,(5, 4, 0, 1)
R201,1,(5, 6, 2, 1)
R202,3,(12, 13, 9, 10)]
S101,10,16
R207,1,(5, 6, 10, 14)
R207,1,(5, 6, 7, 3)
R207,1,(5, 6, 7, 11)
R203,0,1,(2, 6, 10, 14)
R203,0,1,(2, 6, 7, 3)
R203,0,1,(2, 3, 7, 6)
R203,4,0,(15, 11, 7, 6)
R203,4,0,(15, 11, 10, 6)
R203,4,1,(15, 11, 7, 3)
V102,3,目
V102,7,一
V102,11,新
V102,6,真
V102,10,写
R201,4,(15, 11, 10, 14)
R201,4,(15, 14, 10, 11)
V105,14,念
S101,16,5

解答時間

例題に雑誌から入力した問題(11-16)を加えて解答時間は以下の通りでした。

問題	パネル	ワード数	難易度	処理時間(s)	備考
10	4×4	5		0.003	例題（自作）
11	17×17	77	★★★★	0.081	再帰処理で3Hオバー
12	10×10	32	★★★	0.011
13	17×17	95	★★★★	0.177
14	17×17	70	★★★★★	6.228	漢字仮名混じり
15	17×17	92	★★★★	6.024
16	17×17	80	★★★	0.064

　再帰処理でオバーフローした問題11を短時間で解くことができた。
問題を増やすたびに、未確定のマスが増えていく状態だったので、まだ、解決手段は尽くしていないかもしれないと思ったが、たぶん、トライアンドエラーを加えたことである程度解けるようになっていることを期待し、問題なく一発で解けた16番で打ち切った。ジグザグワーズは奥がまだ深くて掘れていないことを認識している。
pythonに慣れるという目標を達成したので、他のこともやってみたいし、一区切りということで発表する。
次はせっかくなのでGUIの勉強しようかな？

未解決、懸念事項

1. 試行錯誤(try_and_error)で仮定した文字、削除パターンが外れた場合をデバックできていない　⇒　適切なデバック環境が構築できなかったので、現象にぶち当たるまで保留
2. クラスのインスタンス変数にアンダーバーを２個つけてプライベート化したときに、ブレークポイントを設定できない場合がある。⇒ プログラムに間違いがあるのか、pythonバージョンアップすれば治るのか、pycharmの問題なのか、原因不明、はまると長そうなので保留
3. セッター、ゲッターでセッター側を参照してくれない場合がある。⇒　上記と同様な理由で保留
4. 問題数が少ないため解けない問題にまだあたりそう　⇒　気分が乗った時に問題を増やす
5. 関数内部に関数を配置した方が、処理時間が早くなる　⇒　時間短縮を試してみたくなったら調査

感謝

　面白い問題を頑張って世に出してくださった皆様に感謝。また、pythonで分からないことを私にもわかるようにまとめて解説を載せてくれた「note.nkmk.me」に感謝。Qiitaにもいっぱい解説あったけど、不明なつぼが合わないと理解が難しいんだよね。