ペグ・ソリティアを解く - ペグ・ソリティア盤の生成
Karetta|Cパズルプログラミング-再帰編|ペグ・ソリテアのペグ・ソリティアを解いていきます。
ペグ・ソリティアは、上下左右のペグを1個飛び越すことが出来る。ペグを飛び越えたら飛び越えたペグを消す。という単純なルール。
OO.O.
解いてみると、
OO.O. ..OO. ....O
って感じ。最後の一個は規定した所に到着しなければならない。かなりハマリゲームっす。おもろいっす。
webで遊べるゲームは、
- MazeWorks - Peg Solitaire
- 伝統的な奴。Java
- フラッシュゲーム「ペグソリティア」
- 動く所を限定して遊びやすくした感じ。激しくハマル。問題は自動生成っぽい。Flash
とりあえずルールがわかってきたので、伝統的なペグソリティア盤を作ってみます。目標は、
OOO OOO OOOOOOO OOO.OOO OOOOOOO OOO OOO
こんなん。自分では絶対解けそうに無い感じっす。
さて、伝統的なペグソリティア盤の十字を書くにはどうしたらいいのか・・・。
a,bの範囲の正方形なら、 a < x < b && a < y < bとすれば、正方形が書けます。
十字なら・・・うぅぅん・・・図をかきかき・・・。
あ、a < x < b || a < y < bとすれば、よさげ。x,y座標が2,3,4の時、ペグを置けばいい。
そんなわけで、コーディング。
#include <stdio.h> #include <stdlib.h> #define N 7 #define M 2 enum {EMPTY, BLANK, PEG}; char board[N][N]; void init_board(void) { int x,y; for (y = 0; y < N; y++) for (x = 0; x < N; x++) board[y][x] = (x >= M && x < N - M || y >= M && y < N - M) ? PEG: EMPTY; board[N/2][N/2] = BLANK; } void display(void) { int x,y; for (y = 0; y < N; y++) { for (x = 0; x < N; x++) putchar((board[y][x] == EMPTY) ? ' ' : (board[y][x] == BLANK) ? '.' : 'O'); putchar('\n'); } } int main(void) { init_board(); display(); return EXIT_SUCCESS; }
真ん中に穴を開けて、終了。
% ./peg OOO OOO OOOOOOO OOO.OOO OOOOOOO OOO OOO
小さい盤で考えたくなったりするので、7以外の盤でも対応出来るようにしました。奇数の盤限定です。
ジャンプ出来る所を探ってみます。簡単そうなので自分で解きます。
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 7 #define M 2 enum {EMPTY, BLANK, PEG}; char board[N][N]; void display(void) { int x,y; for (y = 0; y < N; y++) { for (x = 0; x < N; x++) putchar((board[y][x] == EMPTY) ? ' ' : (board[y][x] == BLANK) ? '.' : 'O'); putchar('\n'); } } bool is_exist(int x, int y) { if (x >= 0 && x < N && y >= 0 && y < N) return board[y][x] == PEG; return false; } bool is_blank(int x, int y) { if (x >= 0 && x < N && y >= 0 && y < N) return board[y][x] == BLANK; return false; } void look_around(int x, int y) { if (is_exist(x, y)) { if (is_exist(x, y - 1)) printf(" U"); if (is_exist(x, y + 1)) printf(" D"); if (is_exist(x - 1, y)) printf(" L"); if (is_exist(x + 1, y)) printf(" R"); } } void look_jump(int x, int y) { if (is_exist(x, y)) { printf("(%d, %d)", x, y); if (is_exist(x, y - 1) && is_blank(x, y - 2)) printf(" U"); if (is_exist(x, y + 1) && is_blank(x, y + 2)) printf(" D"); if (is_exist(x - 1, y) && is_blank(x - 2, y)) printf(" L"); if (is_exist(x + 1, y) && is_blank(x + 2, y)) printf(" R"); printf("\n"); } } void search(void) { int x,y; for (y = 0; y < N; y++) for (x = 0; x < N; x++) { // printf("(%d, %d)", x, y); // printf(" %s", (is_exist(x, y))? "OK" : "NG"); // look_around(x, y); look_jump(x, y); // printf("\n"); } } void init_board(void) { int x,y; for (y = 0; y < N; y++) for (x = 0; x < N; x++) board[y][x] = (x >= M && x < N - M || y >= M && y < N - M) ? PEG: EMPTY; board[N/2][N/2] = BLANK; } int main(void) { init_board(); display(); search(); return EXIT_SUCCESS; }
結果は、
OOO OOO OOOOOOO OOO.OOO OOOOOOO OOO OOO ..(色々略 (3, 1) D (1, 3) R (5, 3) L (3, 5) U
4箇所べる所がありそうです。対称性を考えるなら1個解法があると。後は移動させるだけ。
どうやら、ジャンプしてる経路探索と考えれば良さそうだ。やばい楽しい。
計算量がやたら増えるので、ダイヤ型を用意してみました。
任意の図形を書きたいときは、グラフを引っ張って、内側か外側かを判定すればいい。
例えば、y = xのグラフを書いて、
y A / | / | / |/ +------>x
上側か下側かで塗分ける。
ダイヤの場合は4本線を書けばいいから、
void init_board(void) { int x,y; for (y = 0; y < N; y++) for (x = 0; x < N; x++) board[y][x] = (y + N / 2 >= x && y - N / 2 <= x && N / 2 - x <= y && N + N / 2 - x > y)? PEG : EMPTY; board[N/2][N/2] = BLANK; }
O OOO OOOOO OOO.OOO OOOOO OOO O
ダイヤになりました。
