「コンピュータプログラミング」第 3 回課題

課題の内容

黒マスはどこだ（通称：黒どこ）というパズルを扱う。黒どこは，N×N のマスに，次の条件に従って黒マスを入れていくパズルである。

盤面の数字は、その数字から上下左右４方向にまっすぐ進んで、次の黒マスか壁にたどり着くまでの、その数字のマスを含めての白マスの合計である。
数字が入っているマスは黒マスにはならない。必ず白マスになる。
黒マスはタテヨコに連続しない。また、黒マスによって盤面が分断されることはない。

例題（９ｘ９の場合）

解答

黒どこの解き方のヒント

『２』の斜め隣のマスはすべて白マスになる。
大きい数字と小さい数字に注目する。
黒マスの上下左右は必ず白マスになる。
黒マスを置くと盤面を分断（盤面の白マス全体がひとつながりにならない状態）してしまうところも白マスになる
最大限伸ばしきった数と数字とが一致する場合がある。当然これらは全て白マスとなるが、大きい数字ほどその傾向があることに注意。

以下のレベルのいずれか１つを選んで解答せよ。

Level 1：Minimum

９ｘ９の黒どこを出題して遊べるプログラムを作成せよ。以下の点に注意すること。

乱数を用いて、プログラムを実行するたびに異なる問題が生成されるようにする。
適当な面白さになるように、数字の配置を工夫する。
ユーザが黒マスの位置を１つずつ入力すると、間違っていないかを答える。--> 正しいかを答えるのは難しいのでやらなくてもよい。
正解まで入力すると"Congratulations!!　You solved it!!"と出力する。
Give upを入力すると、解答例を出力する。
その他に便利で面白い機能を各自工夫してつくる。表示や入力のユーザ・フレンドリーな機能も結構大切である。

ヒント

まず黒マスを適当に配置する。
適当な場所に正しい数字をおく。
黒マスを除いて問題を作成する。
作った問題には複数の解答があるかもしれないことに注意。そのためユーザの入力に対し正しいかどうかは、この方法では答えられない。

Level 2：Fair

５ｘ５の黒どこの問題を自動的に解答し，すべての解を報告するプログラムを作りなさい。つまり、

与えられた問題を（合理的な時間で）解き，その問題についてのすべての解を報告する。
解がない場合は，「解がない」ことを報告する。

レポートに実行結果として添付するのは，Level 1の要領でランダムに生成したいくつかの問題例とする。

ヒント

白や黒と確定したマスに印をつけていく。
上で説明した「黒どこの解き方のヒント」を実装する。
「ここを黒にするとダメだから白」（逆もあり）という読みも必要。
自分なりの法則を見つけて実装すればポイントが高い。
ある程度白と黒が決まったら、あとは未解決の場所に対して全部の候補を探索する。この部分の候補を十分減らしておかないと効率的に解けないので注意。

Level 3：Ambitious

９ｘ９の黒どこの問題を自動的に解答し， （できるだけすべての）解を報告するプログラムを作りなさい。つまり、

与えられた問題を（合理的な時間で）解き，その問題についてのすべての解を報告する。
解がない場合は，「解がない」ことを報告する。

なお本課題に対しては，q1.txt～q20.txt の問題を自動的に解答するプログラムを作りなさい。実行結果としては、これらのいくつか（５個以上）の解答例を示すこと。さらに自分で入力した問題（解の数が不明なもの）に対しても解答できるとなお良い。ただし、これらの問題には解がただ 1 つしかないことがわかっている。また問題は番号が大きいほど難しいので、それらが解けるほどポイントが高い。

ヒント

Level 2で述べたヒントを参考にすること。最後の段階で全探索する候補をできるだけ減らす努力が必要となる。

またLevel 3 では，「局面の状態を保持し，仮定を置いて解き進める」ことも必要なる。このためにスタック（stack）と呼ばれるデータ構造を使用するとよい。

スタックは，LIFO（Last-In First-Out）型のバッファで，最後にスタックに入れたものが最初に取り出される。スタックにデータを入れる操作をプッシュ（push），スタックからデータを取り出す操作をポップ（pop）という。

たとえば，int 型変数を保持するスタックは，次のようにコーディングされる。

struct stack_elem {
  int data;
  struct stack_elem *prev;
};

struct stack_elem *stack_top = NULL;

/* x をスタックにプッシュする */
int stack_push(int x) {
  struct stack_elem *tmp;

  if ((tmp = (struct stack_elem *)malloc(sizeof(struct stack_elem))) == NULL) {
    fprintf(stderr, "Memory Error!\n");
    exit(-1);
  }
  tmp->data = x;
  tmp->prev = stack_top, stack_top = tmp;

  return x;
}

/* スタックトップにあるデータをポップする */
int stack_pop() {
  struct stack_elem *tmp;
  int x;

  if (stack_top == NULL) {
    fprintf(stderr, "The Stack is Empty.\n");
    exit(-1);
  }
  x = stack_top->data;
  tmp = stack_top, stack_top = stack_top->prev;
  free(tmp);

  return x;
}

この「スタック」を利用したプログラムの例として，「スタックマシン」（stkmacn.c）という計算機をあげておく。スタックマシンは，レジスタを持たない簡単な計算機モデルであり，オペランド（計算対象）をスタックにプッシュしておき，演算はスタック中の値をポップして行う。

ちなみに，スタックを用いて解の探索を行うと「深さ優先探索（depth-first search）」になる。幅優先探索の場合は，局面を保持するデータ構造に，リストまたは多分木を使うことになる（ここでは，これらについての解説は省略する）。

レポートプログラム作成上の注意

Level 2およびLevel 3に対して、以下のように入出力仕様を規定する。

入力は，標準入力（stdin）から行い，与えられたフォーマットで書かれた「問題」を読めるようにしなさい。このとき，ファイルからの入力は，リダイレクションを使用することになる（例：% ./a.out < assign1.txt）。
出力は，標準出力（stdout）に行う（ファイルへ出力する場合は，% ./a.out < assign1.txt > result1.txt のようにリダイレクションを使用する）。ただし，エラーメッセージなどは標準エラー出力（stderr）に出力する。

参考文献など

例題とルールは(c)ニコリから引用

「コンピュータ プログラミング」第 3 回課題