詰め将棋の詰みを判定させたい

Question

ある特定の駒を用いて，1手詰め将棋問題を列挙しようと考えています．
攻め手は，金2枚，受け手は玉1枚と残りの駒を持駒としています．
下記のプログラムでは，バックトラック法を用いて，4×4マスに利きを考えずに，駒を並べました．
ある盤面が詰んでいるのか詰んでいないのかを判定して，詰んでいる状態のみを表示したいと考えています．

#include <stdio.h>
#include <stdlib.h>
enum KomaN {GYO, KYO, KEI, GIN, KIN, HSH, KAK, FU};
enum Dir {A_DIR, B_DIR, OWNED_A, OWNED_B};



typedef struct Koma {
  enum KomaN nam;
  int x;
  int y;
  enum Dir dir;
} Koma;

#define BOARD_SIZE 9 
#define MAX_KOMA 38  //最大の持ち駒

int hantei(int dep);
Koma * make_koma(enum KomaN nam, int x, int y, enum Dir dir);
void init();
void printBoard();
int searchTsumi(int dep);


Koma * board[BOARD_SIZE * BOARD_SIZE];  //盤の大きさ
Koma * playerA[MAX_KOMA]; //先手の最大駒
int NkomaA; //先手の持ち駒
Koma * playerB[MAX_KOMA+1]; //後手の最大駒
int NkomaB; //後手の持ち駒
char *kname[] = {"GY", "KY", "KE", "GI", "KI", "HS", "KA", "FU"};

Koma * make_koma(enum KomaN nam, int x, int y, enum Dir dir){
  Koma *pt = malloc(sizeof(Koma));
  pt->nam = nam;
  pt->x = x;
  pt->y = y;
  pt->dir = dir;
  return pt;
}

void init() {
  int i, j;
  for (i = 0; i < BOARD_SIZE; i++){
    for (j = 0; j < BOARD_SIZE; j++){
      board[BOARD_SIZE * i + j] = NULL; //最初はNULLを埋めておく
    }
  }
  NkomaA = 0;
  NkomaB = 37;
}

//表示する
void printBoard() {
  int i, j;
  char *shikiri = "   +--+--+--+--+--+--+--+--+--+";
  printf("  　0  1  2  3  4  5  6  7  8\n");
  printf("%s\n", shikiri);
  for (i = 0; i < BOARD_SIZE; i++) {
    printf("%2d ", i);
    for (j = 0; j< BOARD_SIZE; j++) {
      Koma *pt = board[i * BOARD_SIZE + j];
      if (pt != NULL){
	printf("|%s", kname[pt->nam]);
      } else {
	printf("|  ");
      }
    }
    printf("|\n");
    printf("%s\n", shikiri);  
  }
  printf("\n");
}

int searchTsumi(int dep) {
  int i, j;
  int kk[] = {KIN, KIN, GYO};



  //深さが3になったら
  if (dep >= 3){
    printBoard();
  } else {
    for (i = 0; i < 4; i++) {
      for (j = 5; j < 9; j++) {
	      if (board[i * BOARD_SIZE + j] != NULL) continue;
	      Koma *k = make_koma(kk[dep], i, j, A_DIR);
      	board[i * BOARD_SIZE + j] = k;
	      searchTsumi(dep + 1);
	      board[i * BOARD_SIZE + j] = NULL;
      }
    }
  }
}

/* 詰んでいるかどうかの判定 */
int hantei(int dep) {

  //玉の位置を特定
  for (int i = 0; i < 4; i++) {
      for (int j = 5; j < 9; j++) {
          if(board[i * BOARD_SIZE + j]==GYO){
            kingE = i * BOARD_SIZE + j;
          } 
      }
  }
}

int main() {
  init();
  searchTsumi(0);
  return 0;
}

Comments

[y_waiwai]

で、しつもんはなんでしょうか

[izmktr]

メモリリークがひどいコードですね… 学校の課題でないのならC言語使わないほうがいいのでは…

Answer 1

詰みの状態とは、

1. 王の現在位置と周囲8マス中で空いているマスのすべてで、敵方の駒が移動可能である（筋が効いている）
2. 現在王に対して王手をかけている駒を取ることのできる味方の駒（王自身も含む）がないか、あってもその駒を動かした場合に別の王手が発生する
3. 王に対して王手をかけている駒が香車・飛車・角行の場合、味方の駒を移動させて筋を殺すことができない。もしくは合駒を打つことができない

になるでしょうか。
1は純粋に移動させた局面を構成して（高々9局面です）やればよいですね。
2と3が面倒ですね。どこになら駒が移動できるか、そしてその駒が移動したことによって別の王手が発生しないか、をそれぞれ局面構成して調べる必要があるでしょう。
※ルール上、「盤面上になく、攻め手側の持ち駒でない駒は、すべて受け手側の持ち駒である」ので、合駒が足りなくなることはなさそうですが

Answer 2

ある盤面が詰んでいるのか詰んでいないのかを判定

詰んでいる＝玉側に打つ手がない　なので
ルール上やれる防衛手段(?)が有効か否かを順に調べればよいのでは．

1. とりあえず王手がかかっていなければ詰んでない
2. 王手をかけている駒が１個だけの場合は以下を判定

2-1. 玉ではない味方の駒でそれを取れるなら詰んでない
2-2. 間駒を打てる状態(相手が特定の駒種類であって且つ玉に隣接してない)なら詰んでない
3. 玉が移動できる範囲に，敵の駒が利いてない場所があれば詰んでない

みたいな．

（コード見てないけど，盤面をてきとーに作ってるなら，二歩とかになってないことの判定も別途要るかも？）

Answer 3

詰みとは、玉がどう動いても次に必ず取られてしまう状態にあることです。
玉の周りの8マスを調べて、味方の駒や敵駒の利きで全て埋まっていた場合詰み、
一ヶ所でも移動可能なら詰みではないという処理で出来ると思います。