第２講 試行錯誤法でヒント数０数独の解答を作る（１）
第１話 順列作成プログラム
本講義は、初心者の域を卒業した人を対象としていますが、
それでもいきなり数独解答作成ソフトを作ることを要求したら、
読者は離れていってしまうでしょう。
順を追って開発していくために、
一見数独解答自動生成とはまったく関係がないと思える順列の生成から始めます。
お復習いです。
順列とは何でしたか。
１２３を例にすれば、
１２３，１３２，２１３，２３１，３１２，３２１
が順列でしたね。
ここで新しい名称を導入します。
１からｎまでの順列をｎ次順列と名付けます。
ですから、今挙げた
１２３，１３２，２１３，２３１，３１２，３２１
なら３次順列ということになります。
３次順列自動生成とは、自動的にすべての順列＝６個の順列を発生させることを意味することになります。
いくら順を追って数独解答自動生成を開発していくにしても、
ｎ次順列の生成とは余りにも迂遠に思えますよね。
意外に思われるでしょうが、予想より数独自動生成と遙かに近いのですよ。
本サイトは、更新していなかったので訪問者がかなり減ったとはいえ、
今でも１日に２千から３千のアクセスを頂き、
全盛時の多い日には２万近いアクセスを頂いたことがあります。
このサイトは、魔方陣の研究から始まっています。
そしてそこで中心になっている課題は、魔方陣自動生成でした。
この魔方陣自動生ソフトを改良して数独自動生成ソフトを作り、
「数独自動生成アプリ」「ナンプレ作成ソフト」などで検索するとGoogleでNo.1にランクされ、
今や南信州新聞と下野新聞のナンプレ自動出題アプリとして採用されるに至っているのです。
そして、魔方陣自動生成は・・・
さて、魔方陣と何でしょうか。
それは下のような方陣を指します。
| 7 |
8 |
26 |
27 |
21 |
22 |
| 5 |
6 |
25 |
28 |
23 |
24 |
| 35 |
33 |
19 |
17 |
4 |
3 |
| 36 |
34 |
18 |
20 |
2 |
1 |
| 13 |
16 |
12 |
10 |
29 |
31 |
| 15 |
14 |
11 |
9 |
32 |
30 |
方陣とは正方形という意味です。
どうなっていますか。
よく観察して下さい。
慧眼な方はすぐに気がつきますね。
そうです。
すべての行合計と列合計が同じ１１１になっています。
それだけではありません。
２本の対角線の合計も同じ１１１です。
つまり、すべての行合計・列合計・対角線合計が同じになっている方陣を
魔方陣というのです。
よく魔法陣とか書く人がいますが、誤字です。
魔法の表ではなく魔の方陣なのです。
そして、方陣の一辺が６になっているとき６次魔方陣というのです。
この魔方陣自動生成の研究でブレークスルーとなったのが、
魔方陣自動生成はｎ次順列自動生成を応用すればよいと気づいた時点なのです。
２次元は１次元で表せる！・・・
どういうことでしょうか。
６次魔方陣であれば、３６次順列自動生成を少しいじれば出来るのです。
６次魔方陣は
1,2,3,・・・,34,35,36 1,2,3,・・・,34,36,35 1,2,3,・・・,35,34,36 ・・・
という３６次順列を
| 1 |
2 |
3 |
4 |
5 |
6 |
| 7 |
8 |
9 |
10 |
11 |
12 |
| 13 |
14 |
15 |
16 |
17 |
18 |
| 19 |
20 |
21 |
22 |
23 |
24 |
| 25 |
26 |
27 |
28 |
29 |
30 |
| 31 |
32 |
33 |
34 |
36 |
35 |
| 1 |
2 |
3 |
4 |
5 |
6 |
| 7 |
8 |
9 |
10 |
11 |
12 |
| 13 |
14 |
15 |
16 |
17 |
18 |
| 19 |
20 |
21 |
22 |
23 |
24 |
| 25 |
26 |
27 |
28 |
29 |
30 |
| 31 |
32 |
33 |
34 |
36 |
35 |
| 1 |
2 |
3 |
4 |
5 |
6 |
| 7 |
8 |
9 |
10 |
11 |
12 |
| 13 |
14 |
15 |
16 |
17 |
18 |
| 19 |
20 |
21 |
22 |
23 |
24 |
| 25 |
26 |
27 |
28 |
29 |
30 |
| 31 |
32 |
33 |
34 |
36 |
35 |
・
・
のように２次元上に並べて、すべての行と列と対角線合計が同じになるものだけを、
画面にアウトプットすれば、生成できるのです。
さて、いきなりｎ次順列自動生成では難しいですから、
３次順列を自動生成させる課題から取り組みましょう。
これを実現するプログラムをｆor文とif文を組み合わせて組んでみましょう。
と言っても難しいですから、ヒントを与えます。
第１行目でint a[3], cn = 0;と宣言して進めていくわけですが、
0，1，2と1，2，3が似ているので勘違いしてしまいますが、
0，1，2は部屋番号で、1，2，3はその部屋に入る人です。
１部屋には１人しかはいれませんので、
1，2，3の内１人だけが入れます。
このヒントだけでは難しい人は20行下にさらにヒントをつけくわえますから、
下にスクロールして第２のヒントを見ましょう。
ですが、第一ヒントだけで組んでみてください。
１０分ぐらいやっても見当が付かないときに、２０行下を見てください。
#include<iostream>
using namespace std;
int main() {
int a[3], cn = 0;
for (int i = 1; i < 4; i++) {
・・・; //a[0]に1，2，3と入力
for (int j = 1; j < 4; j++) {
if (j != a[0]) {
・・・; //a[0]とa[1]に同じ数字が入らないときに1，2，3を入力
for (int k = 1; k < 4; k++) {
if (k != a[0] && k != a[1]) {
・・・; //できた順列の個数をカウント
・・・; //a[0]とa[1]とa[2]のすべてに同じ数字入らないときに1，2，3を入力
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・; //コンソールに出力
}
}
}
}
}
cout << "順列の場合の数は" << cn << endl;
cout << "プロジェクト成功" << endl;
return(0);
}
・・・は入る文字数のめあすです。
第１講第５話へ 第２話へ
トップへ
