2017年11月29日 | ブログ記事

数独を解いてみた

kanji

はじめに

初めまして。traP Advent Calender2017/11/29担当のkanjiです。
今回はタイトル通り数独を解いていきたいと思います。と言ってもただ解くだけだとあれなのでプログラムを使って解いていきます。

数独とは

別名ナンプレと言います。知ってる人も多いと思いますが一応知らない人のために説明をします。
が、その前に、今回の記事内で使う用語についていくつか定義しておきたいと思います。


 それでは説明に入りましょう。まず、数独はパズルゲームで、以下のように進めていきます。  はじめにいくつかの数字が入っているプレートが与えられます。このプレートの空白部分に、以下の3つのルールにしたがって数字を埋めていき、全ての空白がうまれば終了です。

言葉だけの説明では難しいので実際に問題を見てみましょう。(実はトップ画像がこの問題になっています)

IMG_0597-1

この問題の場合、例として(9,7)の属する箱に注目します。この箱には1がないのでどこかに一つ1を入れる必要があります。8列目と9列目にはすでに1があるので入りません。7行目にも1があるので入れられないです。すでに数字の入っている部分には入れられないので消去法で(9,7)に1が入ります。

アルゴリズム

それではこれから数独の問題を解くためのアルゴリズムを考えていきましょう。ただし、この方法はあくまで私が考えた方法なので、実際にはもっといい方法があるかもしれません。もっと上手く解ける方法を知っている、もしくは思いついた方は、どうか暖かく見守ってやってください。

ボツ案

簡単に思いつく方法としては全ての数字のパターンを試して矛盾がないものを選ぶ、という方法があります。コンピュータは人間よりはるかに早く計算することができるのでこの方法でもいつかは解き終えることができるでしょう。しかしこれではつまらないし無駄が多すぎるのでこの方法はボツにしました。

採用案

まず数独の問題を解くには当たり前ですが数字を埋めていく必要があります。それをいちいち場合分けしていては無駄になるので、まず入れられる数字が確定する条件を調べてみましょう。
 例であげた問題では(9,7)の数字が1と確定していました。これを考察すれば良さそうです。まず最初に(9.7)の属する箱には1が入っていないのでどこかに1を入れる必要がありました。しかし(9,7)のマスを除いて1が入れられないので(9,7)が1と確定していたのです。
 これを一般化すると、「ある箱に対して、そこにない数字kの入れられる候補地が1つの場合に限り、その候補地の数字がkと定まる」と言えそうです。なんだか当たり前の話ですね。また、数独のルールの類似性を見ればわかりますがこの方法は行、列にも転用できそうです。よって「ある行、列、箱のいずれかに対して、そこにない数字kの入れられる候補地が1つの場合に限り、その候補地の数字がkと定まる」とまとめられそうです。
では次にその候補地の求め方を考えましょう。ある数値kの入れられる候補地は簡単で、次のように求められそうです。

  1. プレートの全てのマスを候補地とする。
  2. k以外の数字の入ったマスを候補地から取り除く。
  3. kの入ったマスの属する行、列、箱に属する全てのマスを候補地から取り除く。
  4. 残ったものがkの入れられる候補地になる。

これで数字が確定する場所を求めることができるようになりました。大体の問題はこれだけでも解けますが中にはこれだけだと解けない問題もあります。
 それが仮置きして解く問題です。この方法はアルゴリズム的に見ればただの場合分けなので、上記の方法を使って確定する場所がない、かつまだ埋められていない場所がある場合には場合分けをすれば良さそうです。
 これでだいぶ無駄が省けました。これよりもさらに無駄を省く、あるいは早く解ける方法があるかもしれませんが私にできたのはここまでなので、説明は終わりにしたいと思います。
 ちなみに例として出した問題を解かせてみた結果がこちらです。
IMG_0596-2

終わりに

今回は数独の問題を解くアルゴリズムを紹介しましたが、読んでみてわかるように実はやってみると割と簡単だったりします。(いいアルゴリズムかどうかは置いといて) 本当に難しいのは問題を解く方ではなく作る方で、解ける(答えが一つに定まる)問題を生成するアルゴリズムはほとんど検討もつきません。数独はこのように単純なルールなのに奥が深く、考えた人はすごいなぁ...と思いました。(小並感
 え?ソースコード?知りませんねそんなもの

明日のAdventCalenderはerukkuさん、kakuoさん、phi16さんです。お楽しみに!

この記事を書いた人
kanji

情報工学系2年で、プログラマーをやってます。 趣味はゲームです。FF14やってる人、一緒に遊びましょう!

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2017年12月27日
Splatoon2~ボムの使い方~
shigurure
2017年12月26日
RustでMCMC(Metropolis-Hasting)
David
2017年12月26日
NinjaFlickerが完成しました
gotoh
2017年12月25日
Project Obelisk [traP Advent Calendar 2017]
nari
2017年12月25日
tobiom
2017年12月25日
ネタがないので迷路を自動生成してみた
tsukatomo

活動の紹介

カテゴリ

タグ