こんにちは！システム開発部の平田です。
私は大学でプログラミングを学んでからこの会社に入ったのですが、その際に「数独」パズルをプログラムで解こうとしたことがあり、その思い出をお話しします。
ご存知の方も多いと思いますが、「数独」または「ナンバープレース」と呼ばれる紙やデジタル上で遊ぶパズルがありまして、下記のようなルールをもっています。
1. 空いているマスに、1から縦・横のマス数までのいずれかの数字を入れる
2. 縦・横の各列に、同じ数字が重複して入ってはいけない
3. 太線で囲まれたグループ（以降「ブロック」と呼ぶ）内に、同じ数字が重複して入ってはいけない
一例が下記のようなものです。この問題だと縦横のマス数は9なので1～9の数字を使い、答えのどの縦・横・ブロックでも1～9の数字がひとつずつ使われていることがわかります。これだけのルールでありながら奥が深く、今や世界を代表するパズルのひとつなんですよ。
さて私は大学時代、この数独をプログラムで解くことはできないかと考えました。
例えば下記のような数独の問題があったとしますね。この問題だと縦横のマス数は4なので、1～4の数字を入れることになります。
当時の私は、マス一つ一つへ1から順番に数字をあてはめて、違ったら別の数字を試す、という方法で解けるはずだという発想をしました。
例えば上の問題、左上のマスを(A,a)と表すとします。このマスに、まず数字1を入れてみましょう。同じ行・列・2×2のブロックに数字1はないので、いったんこのマスに数字1を仮決めします。(仮決め＝正しいと仮定する)
下記のようになりました。丸数字が仮の数字です。
次に同じ行の(A,b)を見ると、ここはもう数字2が入っているのでスキップです。(A,c)は空いているので、(A,a)と同じ要領で数字1から試しましょう。
でも数字1はもう同じ行の(A,a)に入れているのでここには入りませんね。数字2も(A,b)にあるのでダメです。数字3なら大丈夫そうなので、数字3を仮決めします。
でも、このまま進めると上の問題は行き詰まることにお気づきでしょうか。次の(A,d)を見ると、同じ行に数字1～3があり、2×2の同じブロック内(B,c)にも数字4があります。つまりこのマスに入れられる数字はないんです。
こんな時は、これまで仮決めした数字がどれか間違っているんですね。なので、直前に仮決めした(A,c)をもう一度考え直しましょう。数字3の次は数字4ですけど、これも同じ列にあるためどの数字も入れられない……。
じゃあそもそもさらに前の(A,a)から間違っているのか！とわかり、(A,a)に戻って次の数字2から再検討……。
こんな考えで数字を入れていけばプログラムでも実装できそうだよね、と私は考えて、学んだばかりのプログラミング言語で挑戦したんです。
二次元配列を使えば問題は表現できるし、1から数字を試すのはループでできます。一度入れた数字を取り除いて次を試すのはバックトラッキングでできそうだ、と。バックトラッキングとはこういった制約がある問題を解く方法のひとつで、再帰処理やスタックという考えで実装できます。
しかし当時の私はオブジェクト指向も半端に理解しているだけの学生でした、上のバックトラッキングの概念をプログラムに落とし込めず、最終的に挑戦は頓挫したのでした。
今となっては既に数独を解くツールや考え方は探せば多数見つかるので、さすがにプログラムでの実装に再挑戦はしないでしょうね……。
でも前述の通りシンプルなルールですし、私のやり方以外にもさまざまなアプローチがあると思います。プログラミングの心得がある方、腕試しに「数独」を解くプログラムの作成に挑戦してみてはいかがでしょうか。