☆お絵描きロジックのプログラムでの... 投稿者:アルゴリズム ID:cySXE |
|
お絵描きロジックのプログラムでの解き方(1つの提案)
始めに【おことわり】 管理人さんへ: それなりの長文(150行程度)になります。迷惑であればお声がけ下さい。 このコーナーの愛読者様へ:小難しく難解な話?で申し訳ありません。コメントは歓迎します。
「どんな問題でも解きたい」との思いから自作プログラムにチャレンジしているのですが難しい。インターネット検索で「これは、」と思えるプログラム化に適した記事を見つけることが出来ませんでした。(「理解できなかった」を含む) パズルの解き方は手品のタネ明かしと似てオープンにすることはタブーかもしれません。知的財産でもあるし、、、、 マニアックなので非常に少数と思いますが、「個人でプログラム作りをしていて私と同じように悩んでいる人がいるかも」と思い解き方の1つを提案します。もしかしたら超難問を人力で解いている神レベルの人は似たような考え方を使っているかもしれません。また、特定の人には周知の事実かもしれません。 老い先長くないと思ったら何か残したくなって・・・ 以下、断定的な表現もありますがあくまでも個人の主観です。また、誤字・脱字は勿論のこと誤った記載の可能性もあると思います。真偽はご自身でご確認ください。 《つづく》
|
| ◇Re: お絵描きロジックのプログラム... 投稿者:アルゴリズム ID:cySXE |
|
|
左詰め・右詰めデータの作成は多少複雑なので後に回します。とりあえず、新たな■や□の発見方法を説明します。 (注)下記の「塗りつぶし開始位置」とは、左詰めでは塗りつぶす左端を、右詰めでは塗りつぶす右端を示します。 上記(2024/01/29 No.6629の図)、鍵=2,3,3,4の「4」個を例にすれば @新たな■発見について 鍵番号「4」の値「4」が入る可能性があるx位置は左詰めの塗りつぶし開始位置(x=20)から右詰めの塗りつぶし開始位置(x=25)に限定されます。従って重なったx=22,23は■が確定します。 別の云い方をすれば、右詰めの塗りつぶし終了位置から左詰めの終了位置までは■が確定します。 A新たな□発見について 鍵番号「3」の左端はx=16、鍵番号「2」(鍵番号「3」の一つ前)の右端はx=13なのでx=14〜15に■は入りません。従ってx=14〜15は□が確定します。 鍵番号「2」の左端はx=9ですが、1つ前の鍵番号の右端がありません。この場合1つ前の鍵番号の右端は欄外の「7」と想定します。 ここでは例示できていませんが鍵番号「5」(実在する?鍵番号+1)のチェックも必要です。この場合も鍵番号「5」の左端は欄外ですが「26」を想定します。 次の例ならイメージし易いと思います。 鍵=5の1個、マスは15×15 x位置 123456789012345 現在のマスデータ ・・・・・・・■・■・・・・・ 左詰めデータ ・・・・・■■■■■・・・・・ 右詰めデータ ・・・・・・・■■■■■・・・ 検討後のマスデータ □□□□□・・■■■・・□□□ 《つづく》
|
| ◇Re: お絵描きロジックのプログラム... 投稿者:アルゴリズム ID:cySXE |
|
|
最初で最後(たぶん)のプログラムらしいことを一つ(プログラムに興味ない方は適当に読み飛ばして下さい) 上記(2024/01/30 No.6630の図)、"鍵=5の「1」個"で■,□を求めるプログラム例。 左詰め、右詰めデータを求めた後の処理です。鍵の値、左詰データ、右詰めデータは一次元の配列変数です。 鍵番号(m): 0, 1, 2 → 実際の鍵は「1」個だけですが、前後を想定します。 鍵の値 : *, 5, * → "*"は使用しないので何でもよい 左詰めデータ: *, 6,16 → 塗りつぶし開始位置を示す。"*"は使用しないので何でもよい 右詰めデータ: 0,12, * → 塗りつぶし開始位置を示す。"*"は使用しないので何でもよい 言語は何でも良いのですが、私はExcelVBAのN88-Basic(死語)類似部分プラスα程度しか知らないので・・・
For m=m1 To m2 'm1=一番左の未確定の鍵番号、m2=一番右の未確定の鍵番号。上記例ではm1=m2=1 For x= 右詰めデータ(m)-鍵の値(m)+1 To 左詰めデータ(m)+鍵の値(m)-1:GoSub ■確定処理:Next 'm1〜m2の処理 For x= 右詰めデータ(m-1)+1 To 左詰めデータ(m)-1 :GoSub □確定処理:Next 'm1〜m2の処理 Next For x= 右詰めデータ(m-1)+1 To 左詰めデータ(m)-1 :GoSub □確定処理:Next 'm2+1の処理
(注)上記の「確定処理」は確定マスを含まなければ実行しないので If 文がありません。(確定処理の中にはあります) (注)詰データを塗りつぶし開始位置としましたが多少の変更で塗りつぶし終了位置でもOKです (注)プロのプログラマーからはマルチステートメントなど、「こんなプログラムはダメ」と怒られます いままでの説明は上の5行の説明でプロローグです。やはりメインは詰データ作りです。 《つづく》
|
| ◇Re: お絵描きロジックのプログラム... 投稿者:アルゴリズム ID:cySXE |
|
|
使っている言葉などのイメージを補足説明します。(x1,x2,m1,m2,範囲内,範囲外などについて) 鍵が 1,2,3,3,2,1 の「6」個、マスが40×40の場合において現在のマスが次の状態なら、 x位置 012345678901234567890123456789012345678901 現在のマスデータ ・□□■□□□■■□□・・・・・・■・・・・・・・・・□・・・・・・・・・・□■□・ x=0,x=41は枠外。欄内はx=11〜37。→ x1=11,x2=37とする x1の左側とx2の右側は確定マスで埋まっている。ただし、x1の1つ左とx2の1つ右は□ m1は未確定の鍵番号で一番小さい。m2は未確定の鍵番号で一番大きい。→ m1=3、m2=5とする。 詰データ作りには範囲内、範囲外という考え方を使っています。 範囲内は塗りつぶすと想定した範囲のことですが、鍵番号「m」の範囲外は次の通り 左詰めの場合:鍵番号「m」の範囲内の右から鍵番号「m+1」の範囲内手前まで。ただし「m=m2」の場合は欄内右端(x2)まで 右詰めの場合:鍵番号「m」の範囲内の左から鍵番号「m-1」の範囲内手前まで。ただし「m=m1」の場合は欄内左端(x1)まで 鍵が3,3,4 で鍵番号「2」の左詰め・右詰めにおける範囲内および範囲外のイメージ(枠内=欄内はx=1〜18) x位置 01234567890123456789 左詰め想定データ ・・■■■・・・・■■■・■■■■・・・ (塗りつぶし開始位置は x=9) ←−→⇔ 範囲内 範囲外 右詰め想定データ ・・・■■■・・・・・■■■・■■■■・ (塗りつぶし開始位置は x=13) ←−−−→←−→ 範囲外 範囲内 詰データ作りは長い話になると思ったのですが、言葉などの説明で全体のおよそ1/3〜1/2が終わりました。《つづく(あと2回)》
|
| ◇Re: お絵描きロジックのプログラム... 投稿者:アルゴリズム ID:cySXE |
|
|
左詰めデータ作成手順(塗りつぶし開始位置データ作成。右詰めは左詰めの逆なので省きます) [初期値設定]:確定マスの存在を無視した左詰めデータを作る。m1-1,m2+1は欄外位置(x1-1,x2+1)とする。 [手順@]:鍵番号をm2→m1の順に左詰めデータの矛盾チェック。 (右詰めではm1→m2の順) [手順@-1]外チェック:範囲外に■があるか、x位置をx2方向からx1方向に向かってチェック(右詰めではx1方向→x2方向) ■があれば矛盾なので塗りつぶし開始位置を矛盾の無い位置に変更 (■が範囲内となる最も左の位置) (複数の■があっても最初に見つけた■位置に対して変更処理) [手順@-2]内チェック:範囲内に□があるか、x位置をx2方向からx1方向に向かってチェック(右詰めではx1方向→x2の方向) □があれば矛盾なので塗りつぶし開始位置を矛盾の無い位置に変更 (□位置+1に変更) (複数の□があっても最初に見つけた□位置に対して変更処理) (注)上記チェックでは違う鍵番号で塗りつぶし範囲が重複することがありますが、とりあえず無視 [手順A]:鍵番号m1→m2の順に塗りつぶし範囲の重複や空白無しをチェック。(右詰めではm2→m1の順) 重複などがあれば1つ後ろの鍵の塗りつぶし開始位置を重複などの無い位置に変更 [手順B]:手順@,Aで塗りつぶし開始位置を変更した場合は手順@に戻る [矛盾チェック]:塗りつぶし範囲が欄外となれば矛盾です。これは、そもそも問題が成立していないか、どこかの過程での仮置き(仮定)が誤りだった場合に生じます。手順@-2およびAで塗りつぶし開始位置を変更した場合はチェックが必要です。
左詰めと右詰めは同一ルーチンを使用しています。プログラムは■□判定の5行を含め約35行ほどでした。 以上が説明の全てです。次は具体例などの補足説明になります。 《つづく(次回最終)》
|
| ◇Re: お絵描きロジックのプログラム... 投稿者:アルゴリズム ID:cySXE |
|
|
参考として前出(2024/01/29 No.6629の図)の例における具体的なループごとの塗りつぶし開始位置の変化などを記します。 鍵=2,3,3,4の4個 ただし鍵番号「1」の値「2」はx=1〜7で確定済。x=7は□が前提→m1=2,m2=4,x1=8,x2=25 x位置 890123456789012345 現在のマスデータ ・・・■・・□・・・■・・・・・・・ ループ回数 : 初回(手順@前) 手順@後 手順A後 鍵番号(m): 0, 1, 2, 3, 4, 5 → 0, 1, 2, 3, 4, 5 → 0, 1, 2, 3, 4, 5 左詰めデータ: *, *, 8,12,16,26 → *, *, 9,15,16,26 → *, *, 9,15,19,26 →変更あり、2回目へ 右詰めデータ: *, 7,16,20,25, * → *, 7,13,20,25, * → *, 7,13,20,25, * →変更あり、2回目へ
ループ回数 :2回目(手順@前) 手順@後 手順A後 鍵番号(m): 0, 1, 2, 3, 4, 5 → 0, 1, 2, 3, 4, 5 → 0, 1, 2, 3, 4, 5 左詰めデータ: 初回の手順A後 → *, *, 9,16,19,26 → *, *, 9,16,20,26 →変更あり、3回目へ 右詰めデータ: 〃 → *, 7,13,20,25, * → *, 7,13,20,25, * →変更なし、終了 数字だけなので逆に分りづらくなった様な ?(数字の位置を合わせられない)
終わりに【感謝】 「もっと分かり易く簡潔に」と思ったのですが難しいですね。 この手法は数々のケース・バイ・ケースのチェックを網羅していますが全てではありません。また、もっと良い方法があるかもしれません。 どの程度時短になるかは「今までケース・バイ・ケースでどこまでチェックしてたか」で違ってきます。全て組み込み済だった場合は時短どころか逆に遅くなる可能性もあります。 今回作った左詰め・右詰めデータを活用すれば他の手法での確定マス発見のヒントに繋がるかもしれません。保証の限りではありませんが、、、 まだまだ課題があります。解けない問題もあるし、そもそもこのサイトの複数解チェックに比べて数倍〜十数倍遅いし、、、、が、楽しんでいます。 管理人さん始め皆様には長々とお付き合い頂きありがとうございました。 《おわり》
|
|