簡単なプログラム
C# の簡単な例題として、小さなプログラムをいくつか作ってみましょう。プログラムの実行には dotnet-script を使います。detnet-script はスクリプト言語のように C# のプログラムを実行できるので、今回のような小さなプログラムを試してみるのに適しています。dotnet-script のインストールについては拙作のページ C# 入門: はじめに をお読みください。
●FizzBuzz
リスト : FizzBuzz 問題 (fizzbuzz.csx)
void fizzbuzz(int n) {
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) {
Console.Write("fizzbuzz ");
} else if (i % 3 == 0) {
Console.Write("fizz ");
} else if (i % 5 == 0) {
Console.Write("buzz ");
} else {
Console.Write("{0} ", i);
}
if (i % 10 == 0) {
Console.Write("\n");
}
}
Console.Write("\n");
}
// 実行
fizzbuzz(100)
- dotnet-script を使うとスクリプト言語のようにプログラムを実行できる
- このとき、ソースファイルの拡張子は .csx とする
- クラスを定義しなくても、関数だけ定義して実行することができる
- 主要な標準ライブラリは暗黙のうちに using されているようだ
- REPL からプログラムを読み込むときは #load "filename" とする
- コメントは // から行末まで、または /* と */ で囲む
- Console.Write() でデータを表示、文字列 "..." の中の {n} は引数の値に置換される
- たとえば Write("{0} {1} {2}", 10, 20, 30) は 10 20 30 と表示される
$ dotnet script fizzbuzz.csx 1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17 fizz 19 buzz fizz 22 23 fizz buzz 26 fizz 28 29 fizzbuzz 31 32 fizz 34 buzz fizz 37 38 fizz buzz 41 fizz 43 44 fizzbuzz 46 47 fizz 49 buzz fizz 52 53 fizz buzz 56 fizz 58 59 fizzbuzz 61 62 fizz 64 buzz fizz 67 68 fizz buzz 71 fizz 73 74 fizzbuzz 76 77 fizz 79 buzz fizz 82 83 fizz buzz 86 fizz 88 89 fizzbuzz 91 92 fizz 94 buzz fizz 97 98 fizz buzz
●数値積分
リスト : 中点則で円周率を求める (midpoint.csx)
double midpoint(int n) {
double w = 1.0 / n;
double s = 0.0;
for (int i = 1; i <= n; i++) {
double x = (i - 0.5) * w;
s += 4.0 / (1.0 + x * x);
}
return s * w;
}
// 実行
Console.Write("{0}\n", midpoint(10000));
$ dotnet script midpoint.csx 3.141592654423134
●平均値と標準偏差
リスト : 平均値と標準偏差 (meansd.csx)
// 乱数で生成した身長のデータ
double[] height = {
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3
};
// 平均値
double mean(double[] xs) {
double s = 0.0;
foreach(double x in xs) {
s += x;
}
return s / xs.Length;
}
// 標準偏差
double sd(double[] xs) {
double m = mean(xs);
double s = 0.0;
foreach(double x in xs) {
s += (x - m) * (x - m);
}
return Math.Sqrt(s / xs.Length);
}
// 実行
Console.WriteLine("mean = {0}", mean(height));
Console.WriteLine("sd = {0}", sd(height));
- System.Linq には合計値を求めるメソッド Sum() や平均値を求めるメソッド Average() など便利なメソッドが用意されている
$ dotnet script meadsd.csx mean = 150.62699999999998 sd = 6.433472701426501
●パスカルの三角形
リスト : パスカルの三角形 (pascal.csx)
// 2 次元配列バージョン
void pascal(int n) {
int[,] table = new int[n, n];
table[0, 0] = 1;
table[1, 0] = 1;
table[1, 1] = 1;
for (int i = 2; i < n; i++) {
table[i, 0] = 1;
for (int j = 1; j < i; j++ ) {
table[i, j] = table[i - 1, j - 1] + table[i - 1, j];
}
table[i, i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
Console.Write("{0} ", table[i, j]);
}
Console.Write("\n");
}
}
// 1 次元配列版
void pascal1(int n) {
double[] table = new double[n];
for (int i = 0; i < n; i++) table[i] = 1;
Console.WriteLine("{0}", table[0]);
Console.WriteLine("{0} {1}", table[1], table[2]);
for (int i = 2; i < n; i++) {
for (int j = i - 1; j > 0; j--) {
table[j] += table[j - 1];
}
// 表示
for (int j = 0; j <= i; j++) {
Console.Write("{0} ", table[j]);
}
Console.Write("\n");
}
}
// 実行
pascal(15);
pascal1(15);
$ dotnet script pascal.csx 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
●素数
リスト : 素数 (単純版, prime.csx)
bool checkprime(int n, int[] ps, int size) {
for (int i = 0; i < size; i++) {
int p = ps[i];
if (p * p > n) break;
if (n % ps[i] == 0) return false;
}
return true;
}
void primes(int n) {
int[] ps = new int[n + 1];
int size = 0;
ps[size++] = 2;
for (int i = 3; i <= n; i += 2) {
if (checkprime(i, ps, size))
ps[size++] = i;
}
for (int i = 0; i < size; i++)
Console.Write("{0} ", ps[i]);
Console.WriteLine("");
}
// 実行
primes(500);
$ dotnet script prime.csx 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
●素因数分解
リスト : 素因数分解 (factor.csx)
void factorization(int n) {
int c = 0;
while (n % 2 == 0) {
n /= 2;
c++;
}
if (c > 0) Console.Write("({0}, {1}) ", 2, c);
for (int i = 3; i * i <= n; i += 2) {
c = 0;
while (n % i == 0) {
n /= i;
c++;
}
if (c > 0) Console.Write("({0}, {1}) ", i, c);
}
if (n > 1) Console.Write("({0}, {1}) ", n, 1);
Console.WriteLine("");
}
// 実行
factorization(24);
factorization(12345678);
factorization(123456789);
factorization(1234567890);
factorization(1111111111);
$ dotnet script factor.csx (2, 3) (3, 1) (2, 1) (3, 2) (47, 1) (14593, 1) (3, 2) (3607, 1) (3803, 1) (2, 1) (3, 2) (5, 1) (3607, 1) (3803, 1) (11, 1) (41, 1) (271, 1) (9091, 1)
●順列と組み合わせ
リスト : 順列と組み合わせ (perm.csx)
// 配列の表示
void PrintArray(int[] ps) {
foreach(int p in ps) Console.Write("{0} ", p);
Console.WriteLine("");
}
// 順列の生成
void PermSub(int n, int[] ps, bool[] visited) {
if (n == ps.Length)
PrintArray(ps);
else {
for (int i = 1; i <= ps.Length; i++) {
if (visited[i]) continue;
ps[n] = i;
visited[i] = true;
PermSub(n + 1, ps, visited);
visited[i] = false;
}
}
}
// 1 から n までの順列を表示
void Permutations(int n) {
PermSub(0, new int[n], new bool[n + 1]);
}
// 組み合わせの生成
void CombSub(int n, int r, int m, int[] comb) {
if (r == 0)
PrintArray(comb);
else if (n == r) {
for (int i = r; i > 0; i--) comb[m++] = i;
PrintArray(comb);
} else {
CombSub(n - 1, r, m, comb);
comb[m] = n;
CombSub(n - 1, r - 1, m + 1, comb);
}
}
// 1 から n までの数字から r 個を選ぶ組み合わせを表示
void Combinations(int n, int r) {
CombSub(n, r, 0, new int[r]);
}
// 実行
Permutations(3);
Permutations(4);
Combinations(5, 3);
$ dotnet script perm.csx 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 3 2 1 4 2 1 4 3 1 4 3 2 5 2 1 5 3 1 5 3 2 5 4 1 5 4 2 5 4 3
●小町算
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。ただし、1 の前に - 符号はつけないものとします。
例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
リスト : 小町算 (komachi.csx)
enum OP {Plus = 10, Minus};
void PrintExpr(int[] expr, int m) {
Console.Write("{0}", expr[0]);
for (int i = 1; i < m; i += 2) {
if (expr[i] == (int)OP.Plus)
Console.Write(" + ");
else
Console.Write(" - ");
Console.Write("{0}", expr[i + 1]);
}
Console.WriteLine(" = 100");
}
int CalcExpr(int[] expr, int m) {
int a = expr[0];
for (int i = 1; i < m; i += 2) {
if (expr[i] == 10)
a += expr[i + 1];
else
a -= expr[i + 1];
}
return a;
}
void Komachi(int n, int[] expr, int m) {
if (n == 10) {
if (CalcExpr(expr, m) == 100) {
PrintExpr(expr, m);
}
} else {
expr[m] = (int)OP.Plus;
expr[m + 1] = n;
Komachi(n + 1, expr, m + 2);
expr[m] = (int)OP.Minus;
expr[m + 1] = n;
Komachi(n + 1, expr, m + 2);
int save = expr[m - 1];
expr[m - 1] = save * 10 + n;
Komachi(n + 1, expr, m);
expr[m - 1] = save;
}
}
void main() {
int[] expr = new int[17];
expr[0] = 1;
Komachi(2, expr, 1);
}
// 実行
main();
- enum は列挙型の定義 enum 型名 {名前1 = 値1, ... }
- 値1 を省略すると 0 から始まる
- 列挙型を整数に変換するには明示的なキャストが必要
- (int)OP.Plus で Plus を 10 に変換する
$ dotnet script komachi.csx 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 123 + 4 - 5 + 67 - 89 = 100 123 + 45 - 67 + 8 - 9 = 100 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100 123 - 45 - 67 + 89 = 100
●N Queens Problem
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。詳しい説明は拙作のページ Puzzle DE Programming N Queens Problem をお読みください。
リスト : N Queens Problem の解法 (nqueens.csx)
int count;
void PrintBoard(int[] board) {
foreach(int x in board) Console.Write("{0} ", x);
Console.WriteLine("");
}
bool Attack(int[] board, int x, int n) {
for (int i = 1; n >= 0; i++, n--) {
int q = board[n];
if (q + i == x || q - i == x) return true;
}
return false;
}
void nqueens(int[] board, bool[] used, int n) {
if (n == board.Length) {
count++;
PrintBoard(board);
} else {
for (int x = 1; x <= board.Length; x++) {
if (used[x] || Attack(board, x, n - 1)) continue;
board[n] = x;
used[x] = true;
nqueens(board, used, n + 1);
used[x] = false;
}
}
}
void main() {
for (int size = 4; size <= 8; size++) {
count = 0;
nqueens(new int[size], new bool[size + 1], 0);
Console.WriteLine("count = {0}", count);
}
}
// 実行
main();
$ dotnet script nqueens.csx 2 4 1 3 3 1 4 2 count = 2 1 3 5 2 4 1 4 2 5 3 2 4 1 3 5 2 5 3 1 4 3 1 4 2 5 3 5 2 4 1 4 1 3 5 2 4 2 5 3 1 5 2 4 1 3 5 3 1 4 2 count = 10 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 5 3 1 6 4 2 count = 4 1 3 5 7 2 4 6 1 4 7 3 6 2 5 1 5 2 6 3 7 4 ・・省略・・ 7 2 4 6 1 3 5 7 3 6 2 5 1 4 7 4 1 5 2 6 3 7 5 3 1 6 4 2 count = 40 1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 1 7 4 6 8 2 5 3 ・・・省略・・・ 8 2 5 3 1 7 4 6 8 3 1 6 2 5 7 4 8 4 1 3 6 2 7 5 count = 92
●騎士の巡歴
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。今回は 5 行 5 列の盤面でナイトの移動経路の総数を求めるプログラムを作ります。
盤面は 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
リスト : 騎士の巡歴 (knight.csx)
// 移動
int[] dx = new int[8] {1, 2, 2, 1, -1, -2, -2, -1};
int[] dy = new int[8] {-2, -1, 1, 2, 2, 1, -1, -2};
int count = 0;
// 盤面の表示
void PrintBoard(int [,] board) {
for (int i = 2; i < 7; i++) {
for (int j = 2; j < 7; j++) {
Console.Write("{0} ", board[i, j]);
}
Console.WriteLine("");
}
Console.WriteLine("");
count++;
}
void Solver(int n, int x, int y, int[,] board) {
if (n > 25)
PrintBoard(board);
else
for (int i = 0; i < 8; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (board[x1, y1] == 0) {
board[x1, y1] = n;
Solver(n + 1, x1, y1, board);
board[x1, y1] = 0;
}
}
}
void main() {
var board = new int[9, 9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (i < 2 || i > 6 || j < 2 || j > 6)
board[i, j] = 1; // 壁
}
}
board[2, 2] = 1;
Solver(2, 2, 2, board);
Console.WriteLine("{0}", count);
}
// 実行
main();
配列 dx は騎士の x 方向の変位、配列 dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 board は盤面を表します。関数 main() で壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
関数 Solver() は引数として手数 n と騎士の座標 x, y を受け取ります。まず、n が 25 よりも大きくなったかチェックします。そうであれば、騎士はすべてのマスを訪れたので、PrintBoard() で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で dx と dy の要素を取り出して x と y の値に加え、Solver() を再帰呼び出しします。再帰呼び出しから戻ってきたら、board[x1, y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
$ dotnet script knight.csx 1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 ・・省略・・ 1 16 11 6 3 10 5 2 17 12 15 22 19 4 7 20 9 24 13 18 23 14 21 8 25 304
●ナンバープレース
リスト : ナンバープレースの解法 (numplace.csx)
const int size = 9;
const int wsize = 3;
// 縦横枠の確認
bool Check(int[,] board, int x, int y, int n) {
for (int i = 0; i < size; i++) {
if (board[x, i] == n || board[i, y] == n) return false;
}
int x1 = (x / wsize) * wsize;
int y1 = (y / wsize) * wsize;
for (int i = 0; i < wsize; i++) {
for (int j = 0; j < wsize; j++) {
if (board[x1 + i, y1 + j] == n) return false;
}
}
return true;
}
// 盤面の表示
void PrintBoard(int[,] board) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
Console.Write("{0} ", board[i, j]);
}
Console.WriteLine("");
}
}
// 深さ優先探索
void Solver(int x, int y, int[,] board) {
if (y == size)
PrintBoard(board);
else if (x == size)
Solver(0, y + 1, board);
else if (board[x, y] != 0)
Solver(x + 1, y, board);
else {
for (int n = 1; n <= size; n++) {
if (Check(board, x, y, n)) {
board[x, y] = n;
Solver(x + 1, y, board);
board[x, y] = 0;
}
}
}
}
void main() {
// 問題 (出典: 数独 - Wikipedia の問題例)
int[,] board = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9},
};
PrintBoard(board);
Console.WriteLine("--------------------");
Solver(0, 0, board);
}
// 実行
main();
$ dotnet script numplace.csx 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 -------------------- 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
●ラテン方陣
「ラテン方陣」は数独の枠の条件を無くした方陣です。ラテン方陣の定義を 参考文献 より引用します。
『ラテン方陣を一般的にいうなら、n 行 n 列の正方形の枡に n 種類の記号を n 個ずつ配列して、各行各列に記号の重複のないものを n 次のラテン方陣というのです。』
このラテン方陣をパズルに応用したものが数独というわけです。
簡単な例を示しましょう。3 次のラテン方陣は次に示す 12 通りになります。
1 2 3 1 2 3 1 3 2 1 3 2 2 1 3 2 1 3
2 3 1 3 1 2 2 1 3 3 2 1 1 3 2 3 2 1
3 1 2 2 3 1 3 2 1 2 1 3 3 2 1 1 3 2
標準形
2 3 1 2 3 1 3 1 2 3 1 2 3 2 1 3 2 1
1 2 3 3 1 2 1 2 3 2 3 1 1 3 2 2 1 3
3 1 2 1 2 3 2 3 1 1 2 3 2 1 3 1 3 2
図 : 3 次のラテン方陣
この中で、最初の行と列の要素を昇順に並べたものを「標準形」といいます。3 次のラテン方陣の場合、標準形は 1 種類しかありません。ラテン方陣は任意の行を交換する、または任意の列を交換してもラテン方陣になります。3 次のラテン方陣の場合、標準形から行または列を交換することで、残りの 11 種類のラテン方陣を生成することができます。
今回は標準形ラテン方陣の総数を求めるプログラムを作ります。
リスト : ラテン方陣 (latin.csx)
int count;
bool Check(int[,] board, int x, int y, int n) {
for (int i = 0; i < board.GetLength(0); i++) {
if (board[x, i] == n || board[i, y] == n) return false;
}
return true;
}
void PrintBoard(int[,] board) {
int size = board.GetLength(0);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
Console.Write("{0} ", board[i, j]);
}
Console.WriteLine("");
}
Console.WriteLine("");
}
void Solver(int x, int y, int[,] board) {
int size = board.GetLength(0);
if (y == size)
count++; // PrintBoard(board);
else if (x == size)
Solver(0, y + 1, board);
else if (board[x, y] != 0)
Solver(x + 1, y, board);
else {
for (int n = 1; n <= size; n++) {
if (Check(board, x, y, n)) {
board[x, y] = n;
Solver(x + 1, y, board);
board[x, y] = 0;
}
}
}
}
void main() {
for (int size = 3; size <= 7; size++) {
var board = new int[size, size];
for (int i = 0; i < size; i++) {
board[i, 0] = i + 1;
board[0, i] = i + 1;
}
DateTime s = DateTime.Now;
count = 0;
Solver(1, 1, board);
DateTime e = DateTime.Now;
Console.WriteLine("count = {0}", count);
Console.WriteLine("{0}", e - s);
}
}
// 実行
main();
プログラムは簡単なので説明は割愛します。実行結果は次のようになりました。
$ dotnet script latin.csx count = 1 00:00:00.2606751 count = 4 00:00:00.0000131 count = 56 00:00:00.0002618 count = 9408 00:00:00.0588682 count = 16942080 00:02:43.4218331 $ dotnet script -c Release latin.csx count = 1 00:00:00.2987160 count = 4 00:00:00.0000210 count = 56 00:00:00.0001775 count = 9408 00:00:00.0209643 count = 16942080 00:00:54.6900533 実行環境 : Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
単純なプログラムなので実行時間は遅いですね。高次の標準形ラテン方陣の総数は、簡単に求めることができない非常にハードな問題だといわれています。興味のある方は挑戦してみてください。
-- 参考文献 --------
大村平, 『数理パズルのはなし』, 日科技連出版社, 1998
大村平, 『数理パズルのはなし』, 日科技連出版社, 1998
●マスターマインド
「マスターマインド」は 0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6, 2, 8, 1] : 正解 --------------------------------- 1: [0, 1, 2, 3] : cows 2 : bulls 0 2: [1, 0, 4, 5] : cows 1 : bulls 0 3: [2, 3, 5, 6] : cows 2 : bulls 0 4: [3, 2, 7, 4] : cows 0 : bulls 1 5: [3, 6, 0, 8] : cows 2 : bulls 0 6: [6, 2, 8, 1] : cows 0 : bulls 4 図 : マスターマインドの動作例
今回はマスターマインドを解くプログラムを作ることにします。
●推測アルゴリズム
このゲームは 10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6, 2, 8, 1] が正解の場合
[0, 1, 2, 3] => bulls = 0, cows = 2
[0, 1, 2, 3] と比較する
--------------------------------------------------------
[0, X, X, X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1, 0, 3, 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1, 0, 4, 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1, 0, 4, 5] => bulls = 0, cows = 1
次は、[0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0, 1, 2, 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0, X, X, X] というコードは [0, 1, 2, 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1, 0, 3, 4] というコードを考えてみます。[0, 1, 2, 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1, 0, 3, 4] と [0, 1, 2, 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1, 0, 4, 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しないコードを選択すればいいわけです。
●プログラム
リスト : マスターマインドの解法 (master.csx)
class Query {
public int Bulls { get; set; }
public int Cows { get; set; }
public int[] Code { get; set; }
public Query(int b, int c, int[] code) {
Bulls = b;
Cows = c;
Code = (int[])code.Clone();
}
}
const int SIZE = 4;
List<Query> query = new List<Query>();
List<int[]> perms = new List<int[]>();
// 順列の生成
void MakePerm(int n, bool[] used, int[] ps) {
if (n == SIZE)
perms.Add((int[])ps.Clone());
else
for (int i = 0; i < 10; i++) {
if (used[i]) continue;
used[i] = true;
ps[n] = i;
MakePerm(n + 1, used, ps);
used[i] = false;
}
}
// Bulls を数える
int CountBulls(int[] xs, int[] ys) {
int b = 0;
for (int i = 0; i < SIZE; i++) {
if (xs[i] == ys[i]) b++;
}
return b;
}
// 同じ数字を数える
int CountSameNumber(int[] xs, int[] ys) {
int c = 0;
foreach(int x in xs) {
foreach(int y in ys) if (x == y) c++;
}
return c;
}
// 矛盾しないかチェックする
bool CheckQuery(int[] code) {
foreach(Query q in query) {
int b = CountBulls(q.Code, code);
int c = CountSameNumber(q.Code, code) - b;
if (b != q.Bulls || c != q.Cows) return false;
}
return true;
}
// コードの表示
void PrintCode(int[] code) {
foreach(int x in code) Console.Write("{0} ", x);
}
// マスターマインドの解法
void Solver(int[] answer) {
query.Clear();
foreach(int[] code in perms) {
if (CheckQuery(code)) {
int b = CountBulls(answer, code);
int c = CountSameNumber(answer, code) - b;
query.Add(new Query(b, c, code));
Console.Write("{0}: ", query.Count);
PrintCode(code);
Console.WriteLine(" bulls = {0}, cows = {1}", b, c);
if (b == 4) {
Console.WriteLine("Good Job!!");
break;
}
}
}
}
void main() {
MakePerm(0, new bool[10], new int[SIZE]);
Solver(new int[SIZE] {9,8,7,6});
Solver(new int[SIZE] {9,4,3,1});
}
// 実行
main();
●実行結果
$ dotnet script master.csx 1: 0 1 2 3 bulls = 0, cows = 0 2: 4 5 6 7 bulls = 0, cows = 2 3: 5 4 8 9 bulls = 0, cows = 2 4: 6 7 9 8 bulls = 0, cows = 4 5: 8 9 7 6 bulls = 2, cows = 2 6: 9 8 7 6 bulls = 4, cows = 0 Good Job!! 1: 0 1 2 3 bulls = 0, cows = 2 2: 1 0 4 5 bulls = 0, cows = 2 3: 2 3 5 4 bulls = 0, cows = 2 4: 3 4 0 6 bulls = 1, cows = 1 5: 3 5 6 1 bulls = 1, cows = 1 6: 6 5 0 2 bulls = 0, cows = 0 7: 7 4 3 1 bulls = 3, cows = 0 8: 8 4 3 1 bulls = 3, cows = 0 9: 9 4 3 1 bulls = 4, cows = 0 Good Job!!
●経路の探索
図 : 経路図
リスト : 経路の探索 (keiro.csx)
enum Node {A = 0, B, C, D, E, F, G, S};
// 隣接リスト
Node[][] adjacent = new Node[(int)Node.S][] {
new Node[2] {Node.B, Node.C}, // A
new Node[3] {Node.A, Node.C, Node.D}, // B
new Node[3] {Node.A, Node.B, Node.E}, // C
new Node[3] {Node.B, Node.E, Node.F}, // D
new Node[3] {Node.C, Node.D, Node.G}, // E
new Node[1] {Node.D}, // F
new Node[1] {Node.E}, // G
};
// 経路の表示
void PrintPath(List<Node> path) {
foreach(Node x in path) Console.Write("{0} ", x);
Console.WriteLine("");
}
// 深さ優先探索
void DepthFirstSearch(List<Node> path, Node goal) {
Node x = path[path.Count - 1];
if (x == goal) {
PrintPath(path);
} else {
foreach(Node n in adjacent[(int)x]) {
if (!path.Contains(n)) {
path.Add(n);
DepthFirstSearch(path, goal);
path.RemoveAt(path.Count - 1);
}
}
}
}
// 幅優先探索
void BreadthFirstSearch(Node start, Node goal) {
var que = new List<List<Node>>();
que.Add(new List<Node>(new Node[1] {start}));
while (que.Count > 0) {
var path = que[0];
que.RemoveAt(0);
Node x = path[path.Count - 1];
if (x == goal) {
PrintPath(path);
} else {
foreach(Node n in adjacent[(int)x]) {
if (!path.Contains(n)) {
var newPath = new List<Node>(path);
newPath.Add(n);
que.Add(newPath);
}
}
}
}
}
// 反復深化
void Dfs(int limit, List<Node> path, Node goal) {
Node x = path[path.Count - 1];
if (path.Count == limit) {
if (x == goal) {
PrintPath(path);
}
} else {
foreach(Node n in adjacent[(int)x]) {
if (!path.Contains(n)) {
path.Add(n);
Dfs(limit, path, goal);
path.RemoveAt(path.Count - 1);
}
}
}
}
void IdSearch(Node start, Node goal) {
for (int limit = 1; limit <= (int)Node.S; limit++) {
List<Node> path = new List<Node>(new Node[1] {start});
Console.WriteLine("----- {0} -----", limit);
Dfs(limit, path, goal);
}
}
void main() {
List<Node> path = new List<Node>();
path.Add(Node.A);
Console.WriteLine("Depth First Search");
DepthFirstSearch(path, Node.G);
Console.WriteLine("Breadth First Search");
BreadthFirstSearch(Node.A, Node.G);
Console.WriteLine("IdSearch");
IdSearch(Node.A, Node.G);
}
// 実行
main();
$ dotnet script keiro.csx Depth First Search A B C E G A B D E G A C B D E G A C E G Breadth First Search A C E G A B C E G A B D E G A C B D E G IdSearch ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- A C E G ----- 5 ----- A B C E G A B D E G ----- 6 ----- A C B D E G ----- 7 -----
初版 2016 年 9 月
改訂 2022 年 2 月 12 日
改訂 2022 年 2 月 12 日