リスト : FizzBuzz 問題
using System;
class FizzBuzz {
static void Main() {
for (int i = 1; i <= 100; 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);
}
Console.Write("\n");
}
}
C>fizzbuzz.exe 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
リスト : 中点則で円周率を求める
using System;
class Test {
static void Main() {
Console.Write("{0}\n", MidPoint(10000));
}
static 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;
}
}
C>midpoint 3.14159265442313
リスト : 平均値と標準偏差
using System;
class Test {
// 平均値
static double Mean(double[] xs) {
double s = 0.0;
foreach(double x in xs) {
s += x;
}
return s / xs.Length;
}
// 標準偏差
static 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);
}
static void Main() {
// 乱数で生成した身長のデータ
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
};
Console.WriteLine("mean = {0}", Mean(height));
Console.WriteLine("sd = {0}", Sd(height));
}
}
C>meansd mean = 150.627 sd = 6.4334727014265
リスト : パスカルの三角形
using System;
class Test {
// 2 次元配列バージョン
static 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 次元配列版
static 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");
}
}
static void Main() {
// Pascal(15);
Pascal1(15);
}
}
C>pascal 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
リスト : 素数 (単純版)
using System;
class Prime {
static 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;
}
static 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("");
}
static void Main() {
Primes(500);
}
}
C>prime 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
リスト : 素因数分解
using System;
class Test {
static 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("");
}
static void Main() {
Factorization(24);
Factorization(12345678);
Factorization(123456789);
Factorization(1234567890);
Factorization(1111111111);
}
}
C>factor (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)
リスト : 順列と組み合わせ
using System;
class Test {
// 配列の表示
static void PrintArray(int[] ps) {
foreach(int p in ps) Console.Write("{0} ", p);
Console.WriteLine("");
}
// 順列の生成
static 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 までの順列を表示
static void Permutations(int n) {
PermSub(0, new int[n], new bool[n + 1]);
}
// 組み合わせの生成
static 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 個を選ぶ組み合わせを表示
static void Combinations(int n, int r) {
CombSub(n, r, 0, new int[r]);
}
static void Main() {
Permutations(3);
Permutations(4);
Combinations(5, 3);
}
}
C>perm 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
リスト : 小町算
using System;
class Test {
enum OP {Plus = 10, Minus};
static 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");
}
static 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;
}
static 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;
}
}
static void Main() {
int[] expr = new int[17];
expr[0] = 1;
Komachi(2, expr, 1);
}
}
C>komachi 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
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。詳しい説明は拙作のページ Puzzle DE Programming N Queens Problem をお読みください。
リスト : N Queens Problem の解法
using System;
class Test {
static int count;
static void PrintBoard(int[] board) {
foreach(int x in board) Console.Write("{0} ", x);
Console.WriteLine("");
}
static 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;
}
static 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;
}
}
}
static 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);
}
}
}
C>nqueens 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
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
●：ナイト (K) が動ける位置 問題
問題 : 騎士の巡歴
このナイトを動かして、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.cs : 騎士の巡歴
//
// Copyright (C) 2016 Makoto Hiroi
//
using System;
class Knight {
// 移動
static int[] dx = new int[8] {1, 2, 2, 1, -1, -2, -2, -1};
static int[] dy = new int[8] {-2, -1, 1, 2, 2, 1, -1, -2};
static int count = 0;
// 盤面の表示
static 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++;
}
static 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;
}
}
}
static 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);
}
}
配列 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 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
C>knight 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
リスト : ナンバープレースの解法
using System;
class Test {
const int size = 9;
const int wsize = 3;
// 縦横枠の確認
static 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;
}
// 盤面の表示
static 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("");
}
}
// 深さ優先探索
static 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;
}
}
}
}
static 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);
}
}
C>numplace 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.cs : ラテン方陣
//
// Copyright (C) 2016 Makoto Hiroi
//
using System;
class Test {
static int count;
static 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;
}
static 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("");
}
static 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;
}
}
}
}
static 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);
}
}
}
プログラムは簡単なので説明は割愛します。実行結果は次のようになりました。
C>latin count = 1 00:00:00.0468000 count = 4 00:00:00 count = 56 00:00:00 count = 9408 00:00:00.0780001 count = 16942080 00:02:07.4990240 実行環境 : Windows 7, Core i7-2670QM 2.20GHz
単純なプログラムなので実行時間は遅いですね。高次の標準形ラテン方陣の総数は、簡単に求めることができない非常にハードな問題だといわれています。興味のある方は挑戦してみてください。
「マスターマインド」は 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.cs : マスターマインドの解法
//
// Copyright (C) 2016 Makoto Hiroi
//
using System;
using System.Collections.Generic;
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();
}
}
class Master {
const int SIZE = 4;
static List<Query> query = new List<Query>();
static List<int[]> perms = new List<int[]>();
// 順列の生成
static 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 を数える
static int CountBulls(int[] xs, int[] ys) {
int b = 0;
for (int i = 0; i < SIZE; i++) {
if (xs[i] == ys[i]) b++;
}
return b;
}
// 同じ数字を数える
static 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;
}
// 矛盾しないかチェックする
static 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;
}
// コードの表示
static void PrintCode(int[] code) {
foreach(int x in code) Console.Write("{0} ", x);
}
// マスターマインドの解法
static 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;
}
}
}
}
static 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});
}
}
C>master 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.cs : 経路の探索
//
// Copyright (C) 2016 Makoto Hiroi
//
/*
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
経路図
*/
using System;
using System.Collections.Generic;
class Test {
enum Node {A = 0, B, C, D, E, F, G, S};
// 隣接リスト
static 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
};
// 経路の表示
static void PrintPath(List<Node> path) {
foreach(Node x in path) Console.Write("{0} ", x);
Console.WriteLine("");
}
// 深さ優先探索
static 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);
}
}
}
}
// 幅優先探索
static 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);
}
}
}
}
}
// 反復深化
static 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);
}
}
}
}
static 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);
}
}
static 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);
}
}
C>keiro 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 -----