C言語関係掲示板

過去ログ

No.128.マインスイーパーの攻略方法


No.740

初投稿です。
投稿者---hiro(2002/01/04 23:26:47)


C言語については全くの無知です。でも今年から学校の授業でC言語が、、、
課題として、「マインスイーパーの攻略方法」をプログラミングせよ、と言うものがだされました。まず始めに何をしていいのかもわからないでいます。
どなたか心優しい人は、教えてもらえないでしょうか?


No.741

Re:初投稿です。
投稿者---ともじ(2002/01/05 11:35:40)


hiroさん、こんにちは。

> 課題として、「マインスイーパーの攻略方法」をプログラミングせよ、
> と言うものがだされました。まず始めに何をしていいのかもわからないでいます。

もう少し課題の条件について詳しく書いていただかないとわかりにくいのですが、
とりあえず、次のように考えてみました。

1.2次元配列で初期データを登録する。
	int panel[H][W] 
		= { { 1, 1, 2,-1, 1},
		    { 1,-1, 3, 2, 2},
		    { 1, 1, 2,-1, 1},
		    { 1, 1, 2, 1, 1},
		    { 1,-1, 1, 0, 0} };
  例えばこのような感じで、地雷(というんですか?)は -1 にする。
  HとWは#defineで宣言しておきます。

2.double型で同じ大きさの危険度を記録する2次元配列を用意する。
	double danger_rank[H][W] = {0};

3.マトリックスの場所に応じて危険度を加算する。
  これは、「4角」と「4角を除いた4辺」と「内部」の計9パターンで
  重み付けが変わってきますよね。
  例えば[0][0]なら
	danger_rank[0][1] += (double)panel[0][0]/3;
	danger_rank[1][1] += (double)panel[0][0]/3;
	danger_rank[1][0] += (double)panel[0][0]/3;
  というように、周囲にあるマスの数で割ってやります。

4.与えられた場所に応じて3.の危険度加算を行っていくと、地雷のある
  場所ほど危険度は1に近づきます。


というように、机上では考えてみたのですが、場所の与え方をどうすれば
いいのか。最初の数回は乱数で与えるとして、あとは危険度の少ないところ
から与えるようにすればいいのでしょうか。ここがちょっと出題条件が
わからないとなんとも言えないところです。


No.742

Re:初投稿です。
投稿者---hiro(2002/01/05 21:16:16)


投稿について、お返事ありがとうございます。
今回の課題は、マインスイーパーの攻略プログラムと言うことで、マインスイーパー自体は、教官の作った(?)ものが与えられています。
簡単に言いますと、盤面が8×8,地雷の数が10と与えられています。
以下がその実物です。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#define W 8 /* 盤面ヨコ */
#define H 8 /* 盤面タテ */
#define N 10 /* 地雷数 */

static int bd[H][W];
static int init_done = 0;
static int nopened = 0;
static int seed = 0;
static int verbose = 0;

#define BD_NONE 0
#define BD_MINE 9
#define BD_OPEN 16

/* 盤面表示関数
左側: 未開マスは表示しない
右側: すべてを表示する
*/

#define CH_MINE 'M'

void print_bd(void)
{
int x, y;
int v;
for(y=0; y<H; y++){
for(x=0; x<W; x++){
v = bd[y][x];
if(v & BD_OPEN){
v &= ~BD_OPEN;
if(v == BD_MINE) putchar(CH_MINE);
else putchar('0' + v);
} else {
putchar('.');
}
putchar(' ');
}
printf(" ");
for(x=0; x<W; x++){
v = bd[y][x] & ~BD_OPEN;
if(v == BD_MINE) putchar(CH_MINE);
else putchar('0' + v);
putchar(' ');
}
putchar('\n');
}
}

/* 盤面初期設定関数群
init_bd
set_mines
count_mines
comp_nmine
is_mine
*/

/* (x, y) に最初の着手あり
その場所を除いて, 残りの63マスの中に合計N個の地雷を埋める
*/
static void set_mines(int x, int y)
{
int i, j;
int n;
int r;

srandom(seed);

for(j=0; j<H; j++){
for(i=0; i<H; i++){
bd[j][i] = BD_NONE;
}
}

bd[y][x] = BD_MINE; /* まず指定マスに地雷を置く - 最後に取り除く */

for(n=0; n<N; ){
r = random();
i = r % W;
j = (r / W) % H;
if(bd[j][i] == BD_NONE){
bd[j][i] = BD_MINE;
n++;
}
}

bd[y][x] = BD_NONE;
}


/* 指定マスが地雷なら 1, それ以外(空白, 盤面外)なら 0 */
static int is_mine(int x, int y)
{
if((0 <= x) && (x < W) && (0 <= y) && (y < H) && (bd[y][x] == BD_MINE)){
return 1;
} else {
return 0;
}
}

/* 盤面の指定マスに対して, 地雷でなければ, 値(開くと得られる数)を計算 */
static int comp_nmine(int x, int y)
{
int r;

if(bd[y][x] == BD_MINE) return BD_MINE;
r = 0;
r += is_mine(x-1, y-1);
r += is_mine(x , y-1);
r += is_mine(x+1, y-1);
r += is_mine(x-1, y );
r += is_mine(x+1, y );
r += is_mine(x-1, y+1);
r += is_mine(x , y+1);
r += is_mine(x+1, y+1);
return r;
}

static void count_mines(void)
{
int x, y;
for(y=0; y<H; y++){
for(x=0; x<W; x++){
bd[y][x] = comp_nmine(x, y);
}
}
}

static void init_bd(int x, int y)
{
set_mines(x, y);
count_mines();
init_done = 1;
nopened = 1;
}

static void endgame(int success)
{
if(success){
if(verbose >= 1) printf("Succeed\n");
exit(64);
} else {
if(verbose >= 1) printf("Failed after %d moves\n", nopened);
exit(nopened);
}
}

/* 着手処理関数
プレーヤが呼び出す
帰り値: 0-8 周囲の地雷数
無 地雷を踏んだ時は帰らない
一度開いたマスを繰返し開いてもエラーにはしない
盤面外を指定した場合, エラーとして異常終了する
*/
int open_sq(int x, int y)
{
int r;

if(verbose >= 2){
printf("open %d %d\n", x, y);
}
if((0 <= x) && (x < W) && (0 <= y) && (y < H)){ /* 盤面内 */
if(init_done == 0){ /* 最初の着手後に盤面を設定する */
init_bd(x, y);
}

r = bd[y][x];
if(r == BD_MINE) endgame(0); /* 地雷を踏んだ */
else if(r & BD_OPEN){ /* すでに開いたマス - ペナルティなし*/
r &= ~BD_OPEN;
} else { /* 未開のマス */
bd[y][x] |= BD_OPEN; /* 既開のしるしづけ */
nopened ++; /* カウント */
if(nopened == W * H - N){
endgame(1);
}
}
} else { /* 盤面外 */
fprintf(stderr, "open_sq: out of board, (x, y) = (%d, %d)\n", x, y);
exit(66);
}
if(verbose >= 3){
print_bd();
}
return r;
}

extern void play(void);

int main(int ac, char **av)
{
char *cp;

cp = getenv("MINE_SEED");
if(cp == 0){
seed = time(NULL) + getpid();
} else {
seed = atoi(cp);
}

verbose = 1;
if(ac >= 2){
verbose = atoi(av[1]);
}
play();
/* 途中で帰ってきてしまった - エラー */
fprintf(stderr, "error: play() returned before endgame\n");
exit(65);
}

関数 void play(void) を定義(と言うか、これが作成しなければならないプログラムらしい)する。また、マスを開く関数として int open_sq(int x,int y) を使うらしい。と言うことはわかっています。んで、自分の作ったものと、上で与えられたものを、いっぺんにコンパイルする、、、となっています。

No.743

Re:初投稿です。
投稿者---kikk(2002/01/06 00:39:04)


ども。


基本的に人間がやるのと同じように解けばいいと思います。
具体的には以下の通り。

1. 地雷が指定された数だけみつかるまで以下を繰り返す
2. そのマスの周囲の地雷の数(以下危険度とする)と、
  周囲の開かれていないマスの数が等しいマスを探す
3. みつかったら、そのマスの周囲の開かれていないマスは
  すべて地雷なので、地雷としてチェックする
4. チェックした各地雷の周囲8マスのうち、開かれている
  マスの危険度を1下げる。危険度0になったらそのマスを
  開く


>関数 void play(void) を定義(と言うか、これが作成しなければならないプログラムらしい)する。また、マスを開く関数として int open_sq(int x,int y) を使うらしい。と言うことはわかっています。んで、自分の作ったものと、上で与えられたものを、いっぺんにコンパイルする、、、となっています。

「いっぺんにコンパイルする」ということから、どうやらplay()は
別ファイルにする必要がるようです。その場合、play()の書いてある
ファイルから見える、盤面の状況を知ることのできる関数はopen_sq()
しかありません(他の関数はstatic)。また、盤面自体もstaticで、
別ファイルからは見えないため、play()のあるファイル中で、独自の
盤面を持つ必要があるでしょう。で、そっちの盤面に、危険度と地雷か
どうかとすでに開いたかを記録していけばOKです。

注意点は、open_sq()を実行することでしか、実際の危険度を調べることが
できないということです。したがって、「つまったらランダムに1つ選ぶ」
という処理が必要になります(例えば、初手が地雷でないことは保証されて
いるようですが、そこの危険度が1以上だと「手詰まり」です)。手詰まりか
どうかを判定するには、上記のアルゴリズムで、1.のループを1周しても
盤面に変化がないかどうかをチェックすればOKです。


1つアドバイスをすると、open_sq()の返り値が0(危険度0)のマスが
みつかったときに、その周囲のマスを、危険度が0の限りどんどん開いて
いく関数をつくると便利だと思います(再帰で書くときれいに書けるかも)。
あると、成功する確率がかなり上がります。というか、この処理をしないと
ほとんど成功しないような気が。。


あと。
しばらく実際にマインスイーパーであそんでみるといいかもしれません。


では。

p.s.
stdinをfreopen()して、盤面の状況(地雷の位置も!)をprint_bd()で取得する
という、強引かつズルイ「裏技」もあるにはありますね。。

戻る


「初心者のためのポイント学習C言語」 Last modified:2002.02.03
Copyright(c) 2000-2002 TOMOJI All Rights Reserved