読者です 読者をやめる 読者になる 読者になる

thagwen’s blog

現役高校2年生のthagwenの趣味・勉強日記

2017.04.15 JSで数独プログラムを作りたい part1

数独プログラムを作りたい―授業のプログラム―

紹介・企画

皆さん、突然ですが、高校時代、必修情報科科目の「社会と情報」「情報の科学」の2科目のうち、どちらの授業を受けましたか?

僕の通う学校では「情報の化学」です。だから僕の手元には「情報の化学」という教科書があります。その教科書には予想通りVBのプログラムが載っています。


そう…

4*4マスのナンプレ(数独)解決プログラムが!

そして思ったのです。

「9*9マスに拡張して高速化したい。」

と。



教科書のプログラムは4*4マス。これは1~4の数字を適当に並べただけで成立します。ナンプレの面白みがないのです。3*3も同じです。

それからプログラムがクールじゃないです。例えば、関数名が日本語()。プログラムとしては動かないこともないですが、かっこよくはないですよね。それから使える数字を調べるために、いちいち実行を止めて、変数を自ら書き換える必要があります。


学校の授業レベルなんだから、と言われればそれまでです。

しかし、すこしプログラムをかじったことのある身からするとじれったい!是非とも直したい。いや、いっそのこと作っちゃえ!


それがこの企画です。


環境等

使用言語JavaScript
開発期間1週間ぐらい
PCWindows8.1 Core-i3 ノートPC
エディタSublime Text3
ブラウザGoogle Chrome


VBで書き直さないのかって?JavaScriptはそんなに変なメソッドを使わない限り、どこでも実行できます。もちろんこのはてな上でもです。

エディタは恋するテキストエディタ、その名も「Sublime Text」のバージョン3です。

PCは小遣いで買った個人用ノート。中古専門店で安売りされていたものです。

ブラウザはもちろんクローム。え、IEはだめ?IEってブラウザなんですか?すみません、僕の中ではブラウザ認識されていません。


数独とは?定義等

数独(すうどく)は、3×3のブロックに区切られた 9×9の正方形の枠内に1〜9までの数字を入れるペンシルパズルの一つである。「ナンバープレースナンプレ)」とも呼ばれる。
(数独 - Wikipedia)

とりあえず説明しやすいように言葉を定義します。

☆「行」...横列のこと。x軸ということがある。

☆「列」...縦列のこと。y軸ということがある。

☆「グループ」...3*3マスの数字の集合のこと。ブロックというほうが一般的かな?


解き方

一つのマスに注目して、そのマスに入る数字を限定する。
一つの列(または3×3のブロック)に注目して、特定の数字が入るマスを探す。
(数独 - Wikipedia)

これだけです。すごくシンプルなゲームですが、恐ろしく難しく、加えてとーっても深いゲームです。


数独の解法の設計

とりあえず解決ロジックを考えてみます。単純にいえば、機械的に数字のない穴すべてに、全種類の数字を入れていって、最終的に全体を俯瞰して矛盾なくすればいいですよね。全部の数字を、「仮定」として挿入していくわけです。

以下のような問題が与えられたとします。


以下のように全マスに数字を入れていくことによって、


最終的にこういうようになれば良いのです。


ここで、ただやみくもに数字を入れていくだけでは、ヒント数が31(上の問題)の場合、最低でも9^{50}計算しなくてはなりません。この状態ではPCでさえも、解答するまでに相当な時間がかかります。たぶんそれ以前にメモリ不足で実行不能になると思いますが。
※n^{m}とは、nのm乗とするとします。



そこで解法を用いることにします。要するに僕らがナンプレを解くときと同じようにするというわけです。ここではある1マスについて考えてみることにします。

まずは行について考えます。


次に列について考えてみます。


最後にグループについて考えてみます。


そうすると、置ける数字が2通りに確定しましたね。

{(縦)かつ(横)かつ(グループ)かつ(そのパネルに数字がない)} が置ける数字です。

こうすることで最初の1マスに関しては数字が2通り確定しました。このようにうまくいくことはまれですが、これだけでかなりの通り数がなくなります。

これを全マスについて行うようにします。今回はここまで!次回以降にプログラミングしていきます。

いまからプログラムを作っていきますので、この企画の更新はとびとびになりそうです。トライ&エラーな毎日になりますね…。

画像はすべてPowerPointを使って作っています。だから結構時間がかかります。というよりもPowerPointはやっぱりすごい。使い方次第で画像作成も自由だし。透過処理までできてしまう優れもの。


今日の学習

教科 やったこと
国語 センターの改題の[2]
英語 単語 1200個

ほとんどの時間が単語に吸収されました。やっぱりゲームは偉大です。ゲーム形式の単語アプリによって何時間も持続して単語勉強できるという!すごいな。


シリーズ

part1
これです。

part2
thagwen.hatenadiary.jp