yoshのブログ

日々の発見や所感を述べます。

数独の解き方 紙と鉛筆の限界

2009-11-27 08:07:34 | パズル
新聞などによく出題されていますように9X9の升目に数字を埋めるパズルが数独です。これを解くのはかなり難しいものです。ここでは、紙と鉛筆でできる正統的な解法を説明します。(主に原理の説明です。)これから数字を埋める升目を未決定升と言うことにします。未決定升のすべて対して、入ることが可能な数値を選び出して、小さい数から先に書き出します。1か2か3が候補の場合は123と書きます。

a. この時、書き出した数が1桁であれば、この升にはこの数値が入ります。
b. 同じ行(または列または3X3のブロック)において、その升にのみ入ることが可能な数
がある場合にはその数値が入ります。(三行・三列だけに着目する手法と類似しています。)
c. 同じ行(または列または3X3のブロック)の中に、2つの升に12と12があった時、(二国同盟と仮称します)2つの升には1と2が配分され、この行の他の未決定升に1と2は入れません。
d. 同じ行(または列または3X3のブロック)の3つの升に3種類の数値があった時、(三国同盟と仮称します)例えば123,12,23や12,23,31など。3つの升には1と2と3が配分され、この行の他の未決定升に1と2と3は入れません。
e. 同じ行(または列または3X3のブロック)の中のn個の升にn種の数字のみがあった時
(n国同盟と仮称します)n個の升には、これらのn種の数字が配分され、この行の他の未決定升にn種の数字は入れません。

以上のa.b.c.d.eを繰り返し実行して変更の余地が無くなったら終了です。大抵の問題は上記のa.b.c.d.eの繰り返しにより解くことができます。
しかし、この段階で、どうしても9X9の升目全部に数字を埋めることができなければ、この問題は超難問であり、紙と鉛筆で解けるのはここまでです。

さらに先に進むためにはコンピューター・プログラミングを援用する必要があります。
これはかなり手間がかかるので、シンプルに実行することを目指して、現在私はそのプログラムの構想を練っているところです。
コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« 天野宗歩と「四香同視」 | トップ | 全国藩校サミット »
最新の画像もっと見る

コメントを投稿

パズル」カテゴリの最新記事