ミニゲーム『あかはあかん　しろにしろ』

level3 が解けない・・・ 頭悪いよ・・・・

偶然解けたが、頭がよくなった訳ではないので当然 level4 でまた詰まった・・・

Level3までだと少し物足りなかったのでLevel5まで用意したのですが 難しすぎたでしょうか……(;´･ω･) ちなみに私はクリアするのにLevel5だけでもタッチをした回数が2000回を超えました……(>д<)

ソルバー書きました。 4x4 は解は 4 通りありますが、それ以外の 3x3 .. 8x8 までは一通りしかありませんでした。ビックリ。 でも 9x9 でいきなり 64通りになる。

どこかのサイトではるか昔(普通の数え方で5本の指でぎりぎり数えられるくらい)、 どんな大きさでもだったのかどんな模様でもだったのかは忘れましたが このパズルだと必ず解けるっていうのを読んで衝撃的だったのを思い出して作ってみました(;´･ω･) プロの方だとソルバーってそんなにすぐに作れちゃうんですね……。 初心者だとこのゲームのプログラムを作るのに2週間かかったのに……ううっ……(ﾉД`)ｼｸｼｸ

なんとか自力で4x4の4通りを導けて満足です(*´∀`)=3 64通りはさすがに自力で探す気にはならないですが……

ソルバーは基本的に 1. 未確認の解を一つ作り、「確認済み」とする 2. その解は条件を満たすか? 2-1. yes なら解を出力して終了 2-2. no なら 1 へ という流れになります。 ただこれだと、全数検査することになり、現実的な時間では解けないことが多いから、検査する数を減らす工夫が必要になります。 よくあるのは「バックトラッキング」という手法で 「step 1 で、構成途中の解についても条件判断を行い、満たさなかったら一つ手を戻して、次の手を試す」 というものです。 はっちんさんがその手法で数独ソルバーを作ってました。 https://miiverse.nintendo.net/posts/AYMHAAADAAB2V0fA8NRduw

早速DLしてみました！ 解読してこのパズルのソルバーを私も作ってみたいと思います！ 赤か白か見分けるだけだし、このパズルのソルバーの方が格段に簡単にできるはず……(｀・ω・´)

最初はバックトラックなしの全数検査でもいいと思いますよ。 このメリットは「単純なので実装もデバッグも簡単」という点です。 遅いのは遅いですが、4x4 までなら実用的な時間で全数検査できると思います。 正解のわからない問題を解く時は、まずはバグなく動くコードを書くのが大切で、それを使って正解を書き出してしまいます。 一度正解を入手できたなら、高速化に挑戦した時にその出力が正しいかどうか判断できます。そうでないと「結果が出たけど、正しいかどうかわからない」という事になりかねません。 わからないことがあったら何でも聞いてください。「解をどう表現するか?」とか。可能な範囲でお答えします。がんばってね!!

ありがとうございます！がんばります！ 困った時は、よろしくお願いします……_(._.)_

やっとdefがわかってきたかなぁと思ったら、 オーバーフローで3x3までしか計算できない没ちゃん。 安らかに成仏してください……(-人-) やっぱり解読作業を怠るとヨクナイ！

もうできたんだ!! びっくり!! stack overflow ですよね? 4x4 でも再帰レベルは 15 じゃないかなあ?? (5x5で 24, 6x6 で 36, 7x7で 48) プチコンの再帰レベルは最大 32 くらいまでいけたはず。(増やすように要望は何度か出しています。) 今から(すれちがいのため)お出かけしてきます。 戻ったらコードよく見てみますね! 髪型変えたんですね?? エンジェルリングできてる!!

実はまだ残念ながらまだできてないんです……。失敗作を載せています……。 ここまでにエラーをたくさんだして、やっと出なくなった(ただし3x3まで)ので 画像で一時保存です(ﾉ´∀｀*) 『今まででもっともエラーが出たで賞』受賞作です！ でも、構造を根本的に変えていかないと駄目みたいですね。 お出かけ、お気を付けて！ (もう2時間経ってるので、このコメントをご覧になるのは戻ってからですが……) 髪型は、名前を変えるついでに変えてみました！ 関係ないですが、私はパンテーンのシャンプーのにおいが好きです！

肝心な質問に回答するのを忘れていました！ そうです、stack overflowです。 私の場合、マスの２乗分のスタックを使っているので、すぐに怒られるプログラムになっています……。

solve の最後で return solve(i+1) してるけど、現在の solve の機能は 「ビットパターン I の 1 のビットを全てタッチした時の盤面を ARY0 に返す」 となっていますよね。コメントアウトされてるけど、完成かどうかの判定もしている。ので return sum == a*a とすれば、I を与えたとき、完成するかどうかを返す(非再帰の)判定関数になります。 そこで単純な全数検査ソルバーは for i = 0 to a*a-1 if solve(i) then ? bin$(i) next で完成です。? bin$(i)の代わりに、i を a*a のマトリクス文字列にする p(i) という関数があると ? p(i) ですっきり。

mid$(s$, i, 1) の代わりに s$[i] と書けます。34行はこれでスッキリするでしょう。 もっといい方法は、k = i and (1<<j) です。 1<<j は pow(2, j) と同じです。(ただし j は 0～31 までに限定) and はビットごとの掛け算になります。二進数を表す &b を使って書くと &b0011 and &b0101 = &b0001 になります。行を分けて欠くと &b0011 and &b0101 = &b0001 '共に 1 の桁だけ 1 になる iが &bxxxxxxxxx の時、j が 0,1,.. と変化すると k = i and (1<<0) = i and &b1 = iの一番右の桁(0か1) k = i and (1<<1) = i and &b10 = iの右から2番目の桁 ... となります

この場合 k は 1, 2, 4, .. (または 0)になるので if k==0 ではなく if k!=0 で調べます。 if k then とも書けて、これは if k!=0 と厳密に同じです。

詳しく解説ありがとうございます！ 今日はもう寝てしまうのですが、明日MIKIさんの解説を照らし合わせながら頑張ってみます！

solve の引数に整数をを使う理由は、 - 実行時間が速い - プログラムが簡単 の二点に尽きるのですが、反面 32 bit しかないので 5x5=25 は解けるが、6x6=36 は解けません。 なので、上を目指すなら最初から"0""1"の文字列を与えるようにしておけばいいんだけど、例のスタックの問題があるために、どのみち 6x6 は解けないという・・・ 悩ましいですね。

う～ん、なるほど……。 ということは、以前コメントして頂いた9x9で64通りになるというのはプチコン以外でソルバーを書いたということなのでしょうか？ それともdefを使わなければもっと解けちゃうということなのでしょうか(;´･ω･)

あ、そうなんです。 プチコンでないと書けないもの(スプライト使ったもの等)以外は、まず PC で十分デバッグしてからプチコンに移植するという方法をとる事が多いです。 プチコンに比べると、エディタとデバッグ環境込みで、PC の方が 10 倍くらい開発が捗る感じです。 特にプチコンはデバッグが大変ですよね。PCでの開発(主に C 言語)だと「ステップ実行」といって、プログラムを一行ずつ確認しながら実行できる機能があり、これが大変便利なんです。

一般に、再帰を使ったコードは、再帰を使わないで書くことができます。 やろうとすると非常に大変なんですけどね。 もしやるのであれば、まず再帰版を作ってアルゴリズムの妥当性を確認してから、非再帰版を起こすってのがいいかなあ?? いずれにせよ後ろ向きの解決なんですよね。 プチコンが再帰呼び出しの深度を深くすれば済むところを、 こっちサイドで処理系の穴を回避して面倒なことしなければならないという・・・ (お仕事ではよくある話ですww) 目標が「9x9解けるソルバーを作る」であればそういう努力が必要になりますし、 「バックトラックソルバーを書いてみる」であれば、4x4まででいいんじゃないかな?

なるほど！どうもありがとうございます！ 9x9は今の私にはまだ無謀な目標みたいなので、4x4までのパズルを解けるソルバーの完成を目指して頑張ります！

何度作り直しても5x5以上でオーバーフローになるプログラムにたどり着けない……(むしろラッキー！？) その代わりに私の頭がオーバーフローです(/・ω・)/　【2REEDE4E】 まだ同じ形が回転したものを数えたりしていますが、 とりあえず全部白くなる手を抜き出せるようになりました！

お疲れ様です。 このコードをベースに再帰版書こうと思ったのですが、ちょっとメゲて PC から移植しました。 MK_REDSOLV KEY=8X33F384 さっき打ち込んだばかりでコメント書いてないので、こっちで説明しますね。

探索アルゴリズム 1. 未設定のマスを一つ探す 2. なければ全マス設定済みなので、解を出力して戻る 3. あればそのマスを「設定済み」とする 4-1. そのマスにタッチしない場合を仮定し、解として成立するか(ゴール(全部白)と矛盾がないか)を調べる。 4-2. 成立するなら仮定したまま探索アルゴリズムを呼び出する(成立しないなら何もしない) 5-1. そのマスにタッチした場合を仮定し、解として成立するか調べる。 5-2. 成立するなら仮定したまま探索アルゴリズムを呼び出する(成立しないなら何もしない) 6. 3 のマスを「未設定」に戻す 7. 戻る

プログラム説明 グローバル変数 wx, wy はマスのサイズ、wz=wx*wy です。nsolve は見つけた解の個数をカウントします。 関数 ztst(z,i) は、盤面を表す変数 z について、i 番目のマスが白なら non0 を返します。 関数 zinv(z,i) は、z の i番目のマスを反転した状態の盤面を返します。 マスは左上から右、上から下へ 0,1,2,... と番号が振ってあります。 盤の状態は整数で表します。マス0が白なら 1, マス1が白なら 2, マス2が白なら 4, ... の合計で表します。 例えば 白赤赤白という盤面は 1+0+0+8 = 9 と表現されます。

関数 p(z) は盤面zを見やすく表示するための関数です。文字列を返すので ? p(z) のように使います。 関数 z_op_i(z, i) は、盤面 z に対してマスiをタッチした結果の盤面を返します。 関数 zzero() は全部赤の盤面を返します。 関数 mkdepend(depends[32]) は、全部赤の盤面に対し、マスi(i=0..n-1)をタッチした結果の盤面を depends[i] に返します。 4-1 で解の正当性を調べるとき、そのマスの状態確定しているかどうか調べなければなりません。 あるマスが確定しているのは、自分と周囲4マスが設定済みの場合です。 マスiが依存しているマスを1にしたパターンを depends[i] に設定します。 関数 mkorder は、マスをタッチする順番を決めます。高速化のためであって、本質的ではありません。

関数 guessok(depends[], set, work) は、仮定した盤面 work が解として成立するかを調べます。 マスiが設定済みかどうかは ztst(set, i) で調べます。 成立しないのは: 「マス状態が確定している、かつ、マス状態が赤である」というようなマスが一つでも存在する場合です。 成立しないのはその否定で、全てのマスが「マス状態が未確定、または、マス状態が白」である

関数 red_solver lv, depends[], order[], set, guess, work は探索アルゴリズム本体です。 lv は確定したマスの数 depends は依存関係、order はタッチ順を表す。 set はあるマスが未確定かどうか示す。 guess はあるマスをタッチしているかどうかを示す。これが解の予想値そのものです。 work は全赤盤面に対し guess を適用した場合の盤面を示す。

関数 red_solver_top は、前準備をしてから探索アルゴリズムを呼び出します。 関数 main はこのプログラムのメインループです。 以上です。不明な点があれば何でも聞いてください!

わざわざどうもありがとうございます！ダウンロードして使ってみました！ 5x5も一瞬で表示されて驚きでお口あんぐり状態です……。 こちらで説明して頂いたものを作っていただいたプログラムにコメントで書き加えたので ネット環境がなくてもバッチリ解読できるようになりました！ これで寝てしまう1秒前まで考えていられます(｀ω´)ｸﾞﾌﾌ 疑問ができた際には、またよろしくお願いします_(._.)_

訂正があります。 誤: set はあるマスが未確定かどうか示す。 正: set はあるマスが設定済みかどうか示す。 確定したかどうかを示す変数はなく、都度「依存マス(自分と周囲4マス)が全て設定済みか」調べます。 (関数 guessok() 内) マインスイーパーとかで、「ここに爆弾があると仮定して推論してみよう」とかやりますよね。 このアルゴリズムもあれと同じことで、一マスタッチするかしないかを仮定して、矛盾がなければ次のマスを仮定して・・・と進めて、全マス仮定できたらそれが解、というしくみです。