スケルトンパズル解いてみました

はじめに

　ボケ防止で漢字パズル誌を解いていたら、難読漢字の読みでスケルトンを埋めるというパズルが出題されていて、どうしても間違えて解けない。
なんか解き方が再帰問題だよね！ということで、３０年ぶりくらいにプログラムにチャレンジしました。

スケルトンパズルとは

　以下は本人作成の例題です。

プログラムの前の準備

　以下のように定義して例題に割り付ける

　四角の１マスをMasuと横または縦の連続マスをRenMasuとしてクラスとし、マスには１から２２まで順番にidを振る。
　連続マスは、リストInitialPatternsとして事前に準備する。

プログラム

開発環境

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

スケルトンパズル解法プログラム

skelton.py

# coding: utf-8
import time

Words = ["都会", "面子", "風聞", "一風", "子供会", "都市名", "名調子", "真砂地",
         "女子大生", "地方新聞", "生真面目", "面目一新"]
InitialPatterns = [[1, 5, 9, 12], [2, 3, 4], [5, 6, 7], [2, 7], [4, 8, 11], [10, 11],
                  [12, 13, 14, 15], [13, 16, 19], [10, 15, 17, 21], [19, 20, 21, 22],
                   [17, 18], [18, 22]]
LastMasuID = 22
class Masu:
    def __init__(self, id):
        self.id = id
        self.moji = None

class RenMasu:
    def __init__(self, initailpattern, masul):
        self.word = None
        self.num = len(initailpattern)
        self.masul = []  # 連続マスを構成するマス
        self.pre_masul = []  # 以前の構成マスに含まれる文字
        for m in initailpattern:
            m1 = next((m2 for m2 in masul if m2.id == m), None)
            self.masul.append(m1)
            self.pre_masul.append(None)

    def possible(self, word):
        if len(word) != self.num:
            return False
        m = 0
        for k in word:
            if self.masul[m].moji is not None and self.masul[m].moji != k:
                return False
            m += 1
        return True

    def ahead(self, word):
        self.word = word
        for n in range(self.num):
            self.pre_masul[n] = self.masul[n].moji
            self.masul[n].moji = word[n]

    def back(self):
        self.word = None
        for n in range(self.num):
            self.masul[n].moji = self.pre_masul[n]

def possible(renMasl, n: int, word: str):
    for n1 in range(n):
        if renMasl[n1].word == word:
            return False
    return renMasl[n].possible(word)

def solve(renMasul, n):
    if n >= len(renMasul):
        return True
    for word in Words:
        if possible(renMasul, n, word):
            renMasul[n].ahead(word)
            if solve(renMasul, n + 1):
                return True
            renMasul[n].back()
    return False

def main():
# 初期化
    masul = []
    renMasul = []
    for m in range(LastMasuID):
        masul.append(Masu(m + 1))
    for i in range(len(InitialPatterns)):
        renMasul.append(RenMasu(InitialPatterns[i], masul))
# 解決
    start = time.time()
    solve(renMasul, 0)
    end = time.time()

    print(f'time: {end - start:.3f}s')
    for j in range(len(renMasul)):
        print("({}) {}".format(j, renMasul[j].word))

if __name__ == '__main__':
    main()

再帰関数solveは以下の通り

1.連続マスにリストから単語を割り当てていき、possible関数で成否判定、成功の場合、次の連続マスに進めてsolve関数を呼び出す
2.連続マスを順番に進めていき最後の連続マスを解決した時点で終了

成否関数possibleは以下の通り

連続マスに配置できるかどうかの関数は、possibleとして以下3項で作成
1.その単語が既に連続マスに割り付けられているかどうか
2.連続マスに含まれている文字数と単語の文字数が合致しているか
3.連続マス内のマスに既に含まれている文字と異ならないか

その他

連続マスクラスに進む(ahead)／戻る(back)の関数を設けました。

結果

time: 0.000s
(0) 女子大生
(1) 都市名
(2) 子供会
(3) 都会
(4) 名調子
(5) 面子
(6) 生真面目
(7) 真砂地
(8) 面目一新
(9) 地方新聞
(10) 一風
(11) 風聞

時間を１６桁まで表示してみたが0s、短すぎたか？
冒頭の難読漢字問題（49単語)では16.3s程度、再帰でどのくらい短縮できているかは不明？

躓きポイント

1. 代入後の変数をいじると代入前の値も変化する

　a = [1]で aを変数、[1]をオブジェクトと定義
変数 aなどは参照（オブジェクト[1]へのアドレス(0x2000など)）を持つ
b = aとすると'='は参照の値(0x2000）を代入、bも[1]へのアドレス0x2000を持つ
参照の値渡しというらしい(Qiita調べ)
つまり、変数bにさわると(b.append(1)など) a,bが指しているオブジェクトを
変更することになりaが指している値も変わる
ただし、オブジェクトがイミュータブル(数字、文字など）の場合
例えば、b = 2 の数字の「2」はイミュータブルなので
新規に作成した「2」のオブジェクトのアドレスをbに代入、つまり、aは変化しない

2. 関数アノテーションでListがエラーとなる

　アノテーションにListを使うときは、from typing import Listをインポートする
C++はtypeにやたらと厳しくて訳の分からないtype表現を書かされて泣いた
書かなくていいものは書かない、嫌な思い出が・・・

参考プログラム

　Qiitaに投稿されていた「世界一難しいナンプレを1秒で解く方法」@shinichi1729
を参考にしました感謝