2010/08/02 18:57
2. 数独の解法
数独の解法について考えてみます。一つの区画の九つのマス目には、1から9までの数字のどれかが、重複も抜けもなく入るという単純なルールから、次の解法が導き出せます。
- 各マス目に入る数字として、1から9までが候補となる。
- 区画内に数字の確定したマス目があるとき、確定した数字は、区画内の他のマス目の候補から外す。
- 候補の数が一つだけになったマス目があれば、そのマス目に入る数字が確定する。
- あるマス目の候補が複数あっても、複数の数字のどれかが区画内の他のマス目の候補にない場合は、そのマス目に入る数字が確定する。
解法2は、区画内のマス目には数字の重複がないことから導いたものです。解法3は、マス目には必ず数字が入ることから導いたものです。解法4は、区画内のマス目には1から9までの数字が抜けなく入ることから導いたものです。
上の解法は、手順として1、2、3、4と順番に実行していきます。3と4でマス目に入る数字が確定したら、2に戻って手順を繰り返します。このような手順の一連の流れを「アルゴリズム」と呼びます。この解法で、問題をどこまで解けるのか。実際にプログラムを作成し動かしてみることで、確認したいと思います。
(Sudoku)
2010/08/02 18:57
コメント