9x9(81マス)の数独の問題を解きたい
9x9の81マスが次の条件全てを満たすように空きマスを埋めていく必要がある
- 1列(9x1の9マス)に1~9の各数字が揃う
- 1行(1x9の9マス)に1~9の各数字が揃う
- 1ブロック(3x3の9マス)に1~9の各数字が揃う
このプログラムのアプローチは
- 初期状態として各1ブロック(3x3の9マス)に1~9の各数字が揃うように空きマスに適当な数字を配置する
- 1列(9x1の9マス)内や1行(1x9の9マス)内の不揃いを得点(コスト)として計上する
- 各1ブロック(3x3の9マス)内の中でランダムに選んだ2マスの数字を入れ替えること(2点swap)を繰り返す
- 2点swapを遷移(近傍?)として焼きなまし法(SA)を行いコストを限りなく0に近づけること(最小化)を目指す
- コストが0に至れば数独の問題を解くことに成功、コストを0にできなかったら失敗