情報基礎13-2のプログラムをMaximaに対応させる

2023/05/13

PCでの閲覧推奨

本来ならばより簡単・ランニングコストに優れたアルゴリズムがあるのだろうが，そんなことを考えていたら終わらない。なので，正直に（ほぼ）総当たり形式で見ていく。

●少しでもコストを減らす
　9+0はできないため，下の段に9がないことは確定。なので，総当たりの際に下の段に９を入れる必要はない。
●C#でのプログラムを，Maxima用に再コーディングする。
　本来のC#のものはページ末に載せてある。理解する必要はなく，あくまで付録程度に（そのため，解説は割愛）。
※プログラム中に出てくる変数 {a, b, c, d, e, f, g, h, i} は，以下の図の各々に対応する。

本来のC#プログラムを，Maxima用に一部書き直したものが，以下。
一部，赤字でコメントあり。解説は次ページ。

for z:1 while (z<9) do(
    e:z,
    for zz:1 while(zz<9) do(
        f:zz,
        for zzz:1 while(zzz<9) do(
            g:zzz,
            for zzzz:1 while(zzzz<9) do(
                h:zzzz,
                for zzzzz:1 while(zzzzz<9) do(
                    i:zzzzz,

                    a:e+f,
                    b:f+g,
                    c:g+h,
                    d:h+i,

                    iiiii:sort([a, b, c, d, e, f, g, h, I]), /*a~iをソート*/
                    
                    for xx:1 while(xx<10) do(
                        if iiiii[xx] # xx then return(1)                
                        elseif xx = 9 then(

                            print(" ", a, b, c, d),
                            print(e, f, g, h, i),
                            print("----------")
                        )
                    )
                )
            )
        )
    )
)$

＞解説

  1. 下の段（e～i）の数を1つずつ試す。（１～８）
    ①○○○○　→　①①○○○　→　①①①○○　→　…………　→　⑧⑧⑧⑧⑧
  2. 下の段が完成したら，上の段を計算。
    Ex） ③⑤⑦⑨
    　　①②③④⑤
  3. これで上の段と下の段が完成。しかし，上の段と下の段では重複する値や1～9以外の値が存在する場合があるため，チェックする必要がある。
    考え方として，求まった9個の値を昇順（sort関数）の配列にする。その値が，｛1, 2, 3, 4, 5, 6, 7, 8, 9｝になっていれば，数字の重複がない＆すべて１～９の間だとわかる。
    Ex） ③⑤⑦⑨　　　→　　　｛1, 2, 3, 3, 4, 5, 5, 7, 9｝≠ {1, 2, 3, 4, 5, 6, 7, 8, 9}
    　　①②③④⑤　　　　　　　　　　　　　　　数字の重複があるので，解ではない。
    Ex） ⑨⑦⑫⑬　　　→　　　｛3, 4, 5, 6, 7, 8, 9, 12, 13｝≠ {1, 2, 3, 4, 5, 6, 7, 8, 9}
    　　⑥③④⑧⑤　　　　　　　　　　　　　　　　１～９以外の数字があるので，解ではない。
    Ex） ④⑤⑧⑦　　　→　　　｛1, 2, 3, 4, 5, 6, 7, 8, 9｝＝ {1, 2, 3, 4, 5, 6, 7, 8, 9}
    ①③⑥②⑤ 数字の重複がない＆すべて１～９の間なので，解である。
    ●これを行うために，for文を利用する。
  4. 求まった解で，重複などがなければ，コンソールに表示。

※本来のC#とは，以下の点を省いたプログラムとなっている。
　・同じ数字除外処理
　・反転重複チェック処理
上記の省いた点は，自分で実装してみるとよい。

＞実行結果

上記プログラムを実行すると，このように表示されるはず。

反転重複処理が実装されていないため，「反転すると同じ」ものがそれぞれ出てくる。

【応用課題】

  1. 解説部１では現在，①①①①①なども処理してしまう（無駄なコストがかかっている）。
    プログラムを修正して，以下の解説がふさわしくなるようなプログラムを作ろう。
    下の段（e～i）の数を1つずつ試す。eから順番に，値を当てはめていく。そのとき，
    ①○○○○　→　①①○○○のようにはならないようにしてある。
    Ex）①○○○○　→　①②○○○　→　①②③○○　→　……　→　⑧⑦⑥⑤④
  2. 解説部３では，実行すると，反転したら重複するものがそれぞれ出てきた。すでに表示したもので，反転すれば重複するなら表示しないようにしよう。 具体的には，以下の解説がふさわしくなるようにプログラムを修正しよう。
    ●これを行うために，for文を利用する。
    　|＿ここで求まった解が，すでに求まっている解を反転させただけかもしれないのでチェックする。
    Ex） ④⑤⑧⑦　　　と　　⑦⑧⑤④　　　　　の場合，後に求まった方は解から除外する
    　　①③⑥②⑤　　　　　⑤②⑥③①
    ●これを行うためには，配列を扱うとよい。

本来のC#プログラム。おまけ。（実行環境はUnity）