数独自動生成ソフト開発で学ぶ超初心者のためのC++マルチスレッドプログラミング入門　　
第１講　序章（周辺の説明とプログラミング体験）
第２話 どんな題材がマルチスレッドプログラミングに向いているの？

第１話に続いてマルチスレッドプログラミングはどんな題材に向いているのかを説明しましょう。

向いている題材は将棋・囲碁・数独自動生成などです。

囲碁はルールさえ知りませんので、

将棋を例に説明しましょう。

局面によって変化しますが、プロが見ると有力な手が５,６手あります。

手順前後を考慮に入れなければ、

どの手を指したかによって異なる世界になります。

例えば有力手がA,B,C,D,E,Fだとすると、

その手を指した後６種類の並行世界＝並列世界＝パラレルワールドが現れます。

この場合にはスレッドを６個派生させて、

それぞれのスレッドにおいて局面A,B,C,D,E,Fの解析をさせれば、

効率的に局面の分析が出来ることになります。

並列世界だから並列プログラミングであるマルチスレッドが向いているわけです。

将棋や囲碁以上に向いている題材は、

実は数独自動生成です。

皆さんに体験していただいたソフトはルートスレッド以外に36個の派生スレッドを起動して、

ルートスレッドを含めて37個のスレッドが用意ドンで数独探索を始めます。

それぞれのパラレルワールドは全く別の世界ですから、

相互に影響を与えあうことはありません。

そして37個のスレッドは、すべてに個性を持たせています。

その個性は３つです。

① 問題のタイプ---左右対称・上下対称・点対称・
　　　　　　　　　　　　 左右にも上下にも対称（これは線対称にして点対称であることと同値です）・ハート型
② ヒントになる数字を配置するマスを81マスからランダムに選ぶ＝スタート地点を81マスからランダムに選ぶ
③ ②のスタート地点から何飛びにするかを81と互いに素となる整数の中からランダムに選ぶ

②③は意味が分からない方がいらっしゃると思いますので、

具体例を出しましょう。

１，２，３，４，５の中からスタート地点をランダムに選び、

５（数字の個数）と互いに素である整数を選びそれを飛びとします。

そして右に飛ぶわけですが、右が存在しないときは一番左に戻るというルールにします。

例えば、スタート地点を３として、飛びを２とすると

３→５→２→４→１

５回ですべてを網羅します。

実はすべてを網羅するのは数字の個数と飛びが互いに素なときのみです。

（ａ，ｂ）の最大公約数が１であるとき、ａとｂは互いの素と呼びます。

これはａ/ｂのように分数にした時に、既約分数になるということです。

既約分数とはこれ以上約分できない分数のことです。

例を挙げれば（５，２）が互いに素で（６，２）は互いに素でないということになります。

１，２，３，４，５，６についてスタート地点を３として飛びを２とすると、

３→５→１→３→５→１→・・・

無限回やっても３と５と１しか網羅できないことがお分かりかと思います。

２と４と６が落ちてしまうわけです。

（ａ，ｂ）が互いに素なときはどんな大きい整数であってもａ回ですべてを網羅するわけです。

例えば、（81，５（飛び））のときも任意にスタート地点を選んでも81回ですべてを網羅します。

スタート地点を６として考えると

６→11→16→21→・・・

この後は皆さんがご自分で確かめてください。

81回ですべてを網羅します。

数独とどこが関係するのと、

お怒りの方もいらっしゃるかもしれませんが、

大いに関係します。

私の開発した数独自動生成は、

（ａ，ｂ）が互いに素なときはどんな大きい整数であってもａ回ですべてを網羅するという性質を

使って数独を生成しています。

81と互いに素である整数ならば、81回ですべてを網羅することを発見したことによって

数独自動生成が可能になったと言ってもよいほどです。

さて、マルチスレッドに話題を戻しましょう。

① 問題のタイプ---左右対称・上下対称・点対称・
　　　　　　　　　　　　 左右にも上下にも対称（これは線対称にして点対称であることと同値です）・ハート型
② ヒントになる数字を配置するマスを81マスからランダムに選ぶ＝スタート地点を81マスからランダムに選ぶ
③ ②のスタート地点から何飛びにするかを81と互いに素となる整数の中からランダムに選ぶ

この３つの個性を持つスレッドが用意ドンで数独の探索を始めるわけですが、

6，480倍もの速さを実現したものはこの個性によるのではないかと、考えています。

個性の異なる37個のスレッドが数独探索をして、

発見すると他のスレッドに発見したということを報告して、

すべての派生スレッドが強制的に終了させられて、

ルートスレッドがCSVファイルに結果をまとめているわけです。

個性の異なる37個のスレッドが数独を探索することが驚異的な速さを実現できた原因ではないかと

推察しています。

ですから、数独自動生成はマルチスレッドに向いているわけです。


第１話へ　第３話へ

トップへ