第２話 同じ紙を９枚用意し、それぞれのスレッドが色塗りをする
マルチスレッドプログラミングとは並列プログラミングです。
マルチスレッドプログラミングにとって、これと同じものを９枚用意することは非常に簡単です。
なぜ９枚かと申しますと、９種類の色を塗るからです。
本当は９枚あるので、黒色一色でもよいのですが９つの色を使った方がイメージしやすいと思います。
だだし、今回の例では2が入っていませんので８枚です。
それぞれが何を表しているかわかりますか。
例よって答えは20行下。
は１を入れてはいけないところです。
は３を入れてはいけないところです。
は４入れてはいけないところです。
は５を入れてはいけないところです。
は６を入れてはいけないところです。
は７を入れてはいけないところです。
は８を入れてはいけないところです。
は９を入れてはいけないところです。
１から９まで色を塗ってみてわかることは何も入力しない段階で、
２マスも確定しています。
赤は４に確定します。
黄色は５に確定します。
それぞれに４と５入力すると
どこかの空欄は必ず１つの数字に確定するのです。
第１話でも言いましたが、仮定法でやってきた人にとって新しい世界が見えることでしょう。
そして仮定法=背理法=試行錯誤法でやるより、
圧倒的な達成感を得ることができるのです。
理詰めで解けるようになったら数独・ナンプレは本当に面白いのです。
解き方はわかったけど、コンピュータに人間と同じように考えさせるためにはどうしたらよいの？
ですよね。
魔方陣の自動生成はすべて試行錯誤法でやっていましたから、
どうやったら組み込むことができるのか、２週間も考え込んでしまいました。
１つのコツを組み込むだけで頭が爆発しそうになりました。
それなのに後５つも組み込まないとは、
さすがの私もプログラミングがいやになりそうでした。
ですが、最初のコツを組み込むために考えた色塗りの方法がすべてに有効であることがわかって
理詰め解法エンジンの開発に成功したのです。
色塗りはいかにしたら可能でしょうか。
私はonoff[a][y][x][i]を用意してその問題を解消しました。
座標(y, x)上に0より大きい値が入っている場合
for(char j=0; j<n ;j++){
if(j != x){
onoff[[mondai[A][y][x]-1] ;
}
}
もちろん列とブロックについても同様にしなければなりません。
９色の色を塗り行・列・ブロックの中に１つだけ色が塗ってあるところを探し出して、
その色に対応する数を代入することによって理詰めへの第一歩を踏み出したのです。
コツでいうとライン排除とブロック排除を実現したのです。
第１話へ 第３話へ
トップへ