Heliodor 2020/09/26 15:19

SUDOKU

もはや恒例になってしまった、ゲーム開発の役に立つとは思えない話題です。


突然ですが、最近数独やってます。
(数独のルールとか詳しいことはググってください。 https://sudoku.com/ など、適当に遊べるサイトはたくさんあります)

ギガ節約したくてなるべく通信量の少ないゲームをやりたかったのですが、じっくり考えるパズル的なものが良いなと思って手を出したのがきっかけです。


で、そのうち面倒になって自動解答プログラムを作ったんです(ツッコミ禁止)

それで解答プログラムができたら、今度は問題作成プログラムもつくってみたくなるわけですよ。

問題を作るためには、まず正解パターンを作っておかないといけません。そこから数字を削っていって「これ以上削ったら解答できない」ってところまで削ったものがパズルの問題ってことになります(難易度によりますが)



というわけで最初の課題は「正解パターンを作ること」です。
正解パターンというのは勿論

 ・9x9の全てのマスに1~9のどれかが入る
 ・各列には1~9が重複なく入る
 ・各行には1~9が重複なく入る
 ・3x3のブロックには1~9が重複なく入る

のすべての条件を満たす数字の並びですね。とりあえずこの条件を「正解条件」と呼ぶことにします。

で、この正解パターンをどうやったら生成できるのかが最初の課題になります。
もちろん総当たりで試しても良いのですが、あまりに効率が悪すぎるので別の方法を考えることにします。


それで思いついたのは、まずなんでも良いから正解パターンを用意して、「正解条件を崩さないように操作を加え、元と異なるパターンにする」です。これを何回も繰り返せば、そのうち元の正解パターンからは想像もできないようなパターンが出来上がるのではないかと。

この方法で必要なのは元になる「正解パターン」と、それに対する「操作」です。
ですが、何でもよいからとにかく正解パターンを考えろ、というのなら話は割と簡単です。


その理屈ですが、とりあえず

 ・各列には1~9が重複なく入る
 ・各行には1~9が重複なく入る

を満たす9x9個の数字の並びを考えてみます。これはすぐに思いつきます

 123456789
 234567891
 345678912
 456789123
 567891234
 678912345
 789123456
 891234567
 912345678

1行目に1~9まで入れたら、それを1個単位でずらしながら9行目まで埋めていきます。
何のひねりもないんですが、とにかく各行と列に1~9が1個ずつ、という条件は満たしています。
ですが、この状態だと

 ・3x3のブロックには1~9が重複なく入る

の条件を満たしていません。しかしこの条件を満たすのも結構簡単で、1個単位ではなく、3個単位でずらせばよいです
最初の3行は

 123 456 789
 456 789 123
 789 123 456

のようになります。
次の4~6行目には、この1~3行目を1個だけずらした並びを入れます

 234 567 891
 567 891 234
 891 234 567

次の7~9行目には、この4~6行目を1個だけずらした並びを入れます

 345 678 912
 678 912 345
 912 345 678

こうしてできたパターンが

 123 456 789
 456 789 123
 789 123 456

 234 567 891
 567 891 234
 891 234 567

 345 678 912
 678 912 345
 912 345 678

です。この方法を使うと3個区切りの9x9マスのパターンだけでなく、4個区切りの16x16マスとか、10個区切りの100x100マスとか、どんなパターンでも生成できます。もちろん2個区切りの4x4マスなんかも。

あとはこれを元にして正解条件

 ・各列には1~9が重複なく入る
 ・各行には1~9が重複なく入る
 ・3x3のブロックには1~9が重複なく入る

を保ったまま適当な操作を加え、数字の列を乱していきます。






その肝心の操作ですが、まず真っ先に思い付くのは

 ・左右反転
 ・上下反転
 ・回転

ですね。ただ、これは実質何も変わっていないのと同じなので使いものにはなりません。無視します。
で、ほかにどんな操作があるか風呂に入ってタイルを見つめながら考えていたのですが、
結局思いついたのは次の3つでした。

 ・数字の入れ替え
 ・行(列)の入れ替え
 ・行(列)ブロックの入れ替え


順番に説明していきます。




・数字の入れ替え

これはパターン中の、特定の2種類の数字を入れ替えるものです。例えば
1と8を入れ替えるなら、

①23 456 7⑧9
456 7⑧9 ①23
7⑧9 ①23 456

234 567 ⑧9①
567 ⑧9① 234
⑧9① 234 567

345 67⑧ 9①2
67⑧ 9①2 345
9①2 345 67⑧

というパターンは

⑧23 456 7①9
456 7①9 ⑧23
7①9 ⑧23 456


234 567 ①9⑧
567 ①9⑧ 234
①9⑧ 234 567

345 67① 9⑧2
67① 9⑧2 345
9⑧2 345 67①

になります。本当にただ数字を入れ替えただけです(機種依存文字ゴメンナサイ)




・行(列)の入れ替え

2つの行(列)を選んで、それを入れ替えます。

とりあえず2つの列を入れ替えることを例にすると、これは
行を丸ごと入れ替えるだけなので、各行における数字の並びはまったく変化しません。ゆえに

 ・各行には1~9が重複なく入る

という条件は必ず保たれます。

では各列における数字の並びはどうかというと、2か所の数字が入れ替わるだけなので

 ・各列には1~9が重複なく入る

という条件も必ず保たれます。


問題は

・3x3のブロックには1~9が重複なく入る

という条件です。3x3のブロックにおける数字の並びを考えると、
あくまでも「同じブロックの中の数字がシャッフルされるだけ」にしておかないと数字の重複が発生してしまいます。
入れ替える2つの行は、どちらも同じブロックに属していないといけません。
あるブロックの数字を別のブロックに(無条件で)持っていくことはできないのです。
つまり、行の入れ替えで許されるのは

 ・1~3行目から2つの行を選んで入れ替える
 ・4~6行目から2つの行を選んで入れ替える
 ・7~9行目から2つの行を選んで入れ替える

の3パターンだけという事になります。




・行(列)ブロックの入れ替え

行(列)のの入れ替えとだいたい同じ理屈です。3X3ブロックが横に3つ並んでいる部分を「行ブロック」、
縦に3つ並んでいる部分を「列ブロック」としたときに、2つの行(または列)ブロックを、丸ごと入れ替えます。

123 456 789●
456 789 123●
789 123 456●

234 567 891
567 891 234
891 234 567

345 678 912★
678 912 345★
912 345 678★

例えば上のパターンで、一番上の行ブロック(●)と下の行ブロック(★)を入れ替えると

345 678 912★
678 912 345★
912 345 678★

234 567 891
567 891 234
891 234 567

123 456 789●
456 789 123●
789 123 456●

のようになります。




・まとめ

これらをまとめると、正解条件を満たしたままで可能な操作は次の7種類です

・1~9のうち2つの数字をランダムで選び、その2種類の数字を入れ替える
・1~3行目から2行をランダムで選び、入れ替える
・4~6行目から2行をランダムで選び、入れ替える
・7~9行目から2行をランダムで選び、入れ替える
・1~3列目から2列をランダムで選び、入れ替える
・4~6列目から2列をランダムで選び、入れ替える
・7~9列目から2列をランダムで選び、入れ替える

(「行(列)ブロックの入れ替え」はあんまり効果的な乱し方でない気がしたので除外しておきました)

任意の正解パターンを選んで、これらの操作を適当な回数だけ繰り返せば
良い感じに数字の並びを乱していくことができます。



正解パターンさえ得られれば、あとは適当なマスの数字を消していくだけです。
数字の入っているマスを適当に選んで「その数字を消しても正解パターンに辿りつ事ができるか」をチェックし、YESなら消す、NOなら消さないという操作を繰り返します。
(この操作をするためには前提として問題解答プログラムが必要ですが、それについては後日)



例によってこれが何の役に立つか分かりませんが、まあ、適当なミニゲームを組み込むとして、9x9なんてサイズにしないで5x5ぐらいにして(この場合、ブロックは考えない)このうちいくつかの数字がヒントとして出ていて「残りのマスを埋めてみよう!」なんて問題なら気軽にできそうですね。

1  45   12345
23      23451
  512 → 34512
4 1     45123
  2 4   51234

(こんなモノでも初心者にとっては結構悩む問題だと思いますよ)



そもそもこれ、数字である必要はありませんから、例えば〇□△×☆の5種類の記号で埋めるとかにすればカジュアルな見た目になります。

〇  ×☆   〇□△×☆
□△      □△×☆〇
  ☆〇□ → △×☆〇□
× 〇     ×☆〇□△
  □ ×   ☆〇□△×

これならRPGのミニゲームなんかに使えるかなーとも思ったんですが、ルール分からん人にはガチ過ぎるので良くないですね。
(拙者、ミニゲームクリアできなくてゲーム本編放り出す侍)





フォロワー特典は数独の問題作成&回答プログラムのソースコードです。
コンソールウィンドウを開いて printf で表示するというなかなかレトロなヤツです。ハイ。

有料プランの方にはコンパイル済みEXEをお付けします。ビルドの手間が省けます。

フォロワー以上限定無料

まずは無料プランで様子見を。 お気軽にフォローしてみて下さい。

無料

【 500円 】プラン以上限定 支援額:500円

このバックナンバーを購入すると、このプランの2020/09に投稿された限定特典を閲覧できます。 バックナンバーとは?

この記事が良かったらチップを贈って支援しましょう!

チップを贈るにはユーザー登録が必要です。チップについてはこちら

記事のタグから探す

月別アーカイブ

限定特典から探す

記事を検索