-
Notifications
You must be signed in to change notification settings - Fork 0
/
howtobuild.txt
178 lines (110 loc) · 6.29 KB
/
howtobuild.txt
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
SSE4.2 / AVX版 数独solver ビルドおよび実行方法
Copyright (C) 2012-2015 Zettsu Tatsuya (是津達也)
(本ファイルの記述は古いです。sudokusse.md をご参照ください。)
[ビルド環境]
バージョンについては sudokusse.md をご参照ください。
+ Windows 10 64bit版
+ Cygwin 64bit version または Bash on Ubuntu on Windows
- g++
- GNU assembler
- GNU Make
- Ruby
- Perl
MinGW-w64 for 64 bit Windows でもビルドできますが、
CppUnitと合わせてテストをビルドできることは確認していません。
[実行環境]
Cygwin および Perl (バージョンは上記と同じ)
[テスト環境]
CppUnit 1.12.1 (Cygwinのみ, MinGWは未対応)
[ビルド方法]
1. Cygwinコンソールを起動し、ソースファイル一式(sudoku.cpp)のあるディレクトリ
に移動する(以下このディレクトリで作業することを前提とする)。
2. Cygwinコンソールから
make
と入力する。ビルドに成功するとbin/ディレクトリに実行ファイルが2つ生成される。
両実行ファイルの違いは後述する。
sudokusse.exe : 通常版
sudokusse_cells_packed.exe : 一部計算を簡略化したもの
MinGWでビルドするときは、makeの代わりにmingw32-makeを使う。
[SSE4.2とAVXの使い分け]
変数EnableAvxの値が0の場合はSSE4.2, 1の場合はAVXを使用する。
実行時ではなくビルド時に指定するので、Makefileにasの起動オプションとして指定する。
[数独の初期ファイルを用意する]
テキストファイルを用意する。
初期数字が埋まっているマスは、その数字を半角の1から9で書く。空白のマス
は数字以外の任意の表示可能な1byte文字を書く(空白も可)。
<書式1 : 9文字 * 9行>
.3.....4.
.1..97.5.
..25.86..
..3...8..
9....43..
..76....4
..98.54..
.7.....2.
.5..71.8.
横一行のマスは、行の先頭から順に9文字(9byte)を当てはめる。行頭に余分な
文字を書いてはならない。各行の10文字目以降は無視するので、コメントなど
を書いて構わない。
<書式2 : 81文字 * 1行>
.3.....4..1..97.5...25.86....3...8..9....43....76....4..98.54...7.....2..5..71.8.
二行目以降は無視するので、コメントなどを書いて構わない。
[数独を解く]
Cygwinコンソールから
bin/sudokusse.exe 解く回数 < 数独の初期ファイル
と入力して実行する。解く回数を正の整数にすると繰り返し解き、1回解くため
に掛かった最小時間を返す。
解く回数を正の整数にすると、符号を反転させた回数(-5と書いたら5回)だけ
実行する。解く過程を示す以外は、正の数を指定するのと同じである。通常は
-1を指定する。
bin/sudokusse_cells_packed.exe はマスは左上に固まっていると仮定して、
右下のマスを見落とすので、正しい解は出せない。そのためエラーを表示して
終了する。
[解となり得るものを数える]
Cygwinコンソールから
bin/sudokusse.exe 0 < 数独の初期ファイル
と入力して実行すると、何個解があるかだけ表示する。合わせて実行時間を表示する。
bin/sudokusse.exe 0 100 < 数独の初期ファイル
と入力して実行すると、解となり得るものを100個だけ、コンソールに出力する。
101個目以降は出力しない。100の代わりに任意の正の整数を入力すると、
その数だけ列挙する。実行が終わるのは、すべての解を数え上げた後になる。
bin/sudokusse.exe の代わりに、bin/sudokusse_cells_packed.exe を実行すると、
初期マップで埋まっているマスは左上に固まっていると仮定する。つまり
a. 9マスとも埋まっている
b. 左端から埋まってるマスが連続し、その後空白が右端まで連続する
c. 空白だけ
という行が上から順に並ぶ。a,b,cともになくても構わないが、bはないかあっても
1行に限る。
[解となり得るものを数える補助スクリプト]
1．数える時間を計測する
perl sudoku_count.pl 数独の初期ファイル
を実行すると、実行ファイルを変えて繰り返し実行し、その結果をログに出力する。
ログファイル名は、実行日時を基に、SudokuTime_2013_09_27_21_34_56.log
などの名前を自動生成する。無限ループなので、終了するにはCtrl-cを連打する
(一回押しただけでは終了しないことがある)。
2．上記の最小実行時間を探し出す
perl sudoku_search_timelog.pl SudokuTime_2013_09_27_21_34_56.log
と実行すると、上記のログを解析し、各実行ファイル(*.exe)ごとの最小実行
時間を探し出して表示する。ログのファイル名は適宜読みかえること。
[ユニットテスト]
1. 数独を解けるかどうか確認する
perl sudoku_solve_all.pl
と実行すると、data/ 以下にあるテキストファイル(*.txt)を数独初期マップと
みなして解く。解ければ掛かった時間を表示し、解けなければその場で終了する。
2. 関数とアセンブリ言語のマクロをテストする
Cygwinコンソールで、unittest/ サブディレクトリに移動し、
make
と入力する。ビルドに成功するとunittest.exe および
unittest_cells_packed.exe が生成され、テストを実行する。
Makefileが正常終了すれば、テストに成功したと言える。
[出典および謝辞]
1. アルゴリズムの基本と例題(data/*.txt)を下記の書籍から頂きました。
"プログラマのための論理パズル 難題を突破する論理思考トレーニング",
Dennis E. Shasha (著), 吉平 健治 (翻訳), 2009/3, オーム社
2. CppUnitのクラス定義を下記の記事から頂きました。
http://www.atmarkit.co.jp/fdotnet/cpptest/cpptest02/cpptest02_02.html
3. 数独の解となり得るものを数えるというアイデアおよび、本プログラムの
開発において実行時間の比較対象として用いたプログラムは、川合秀実氏に
よるものです。下記の記事をご参照ください。
http://developer.cybozu.co.jp/tech/?p=1692
□