朝日新聞2005年11月25日パズル横丁解答

プログラムの実行結果は以下の通り。

1[10][10]⇒[9][12] 3[10][12]⇒[9][11] 2[10][11]⇒[9][13] 1[9][12]⇒[9][14] 4[10][13]⇒[9][12] 
1[10][10]⇒[9][13] 3[10][12]⇒[9][14] 4[10][13]⇒[9][12] 1[9][13]⇒[9][11] 2[10][11]⇒[9][13] 
1[10][10]⇒[11][12] 3[10][12]⇒[11][11] 2[10][11]⇒[11][13] 1[11][12]⇒[11][14] 4[10][13]⇒[11][12] 
1[10][10]⇒[11][13] 3[10][12]⇒[11][14] 4[10][13]⇒[11][12] 1[11][13]⇒[11][11] 2[10][11]⇒[11][13] 
2[10][11]⇒[9][13] 4[10][13]⇒[9][12] 3[10][12]⇒[9][11] 4[9][12]⇒[9][10] 1[10][10]⇒[9][12] 
2[10][11]⇒[9][13] 4[10][13]⇒[10][11] 3[10][12]⇒[9][11] 4[10][11]⇒[9][10] 1[10][10]⇒[9][12] 
2[10][11]⇒[11][13] 4[10][13]⇒[10][11] 3[10][12]⇒[11][11] 4[10][11]⇒[11][10] 1[10][10]⇒[11][12] 
2[10][11]⇒[11][13] 4[10][13]⇒[11][12] 3[10][12]⇒[11][11] 4[11][12]⇒[11][10] 1[10][10]⇒[11][12] 
3[10][12]⇒[9][11] 1[10][10]⇒[9][12] 2[10][11]⇒[9][13] 1[9][12]⇒[9][14] 4[10][13]⇒[9][12] 
3[10][12]⇒[9][11] 1[10][10]⇒[10][12] 2[10][11]⇒[9][13] 1[10][12]⇒[9][14] 4[10][13]⇒[9][12] 
3[10][12]⇒[11][11] 1[10][10]⇒[10][12] 2[10][11]⇒[11][13] 1[10][12]⇒[11][14] 4[10][13]⇒[11][12] 
3[10][12]⇒[11][11] 1[10][10]⇒[11][12] 2[10][11]⇒[11][13] 1[11][12]⇒[11][14] 4[10][13]⇒[11][12] 
4[10][13]⇒[9][11] 2[10][11]⇒[9][10] 1[10][10]⇒[9][12] 4[9][11]⇒[9][13] 3[10][12]⇒[9][11] 
4[10][13]⇒[9][12] 2[10][11]⇒[9][13] 3[10][12]⇒[9][11] 4[9][12]⇒[9][10] 1[10][10]⇒[9][12] 
4[10][13]⇒[11][11] 2[10][11]⇒[11][10] 1[10][10]⇒[11][12] 4[11][11]⇒[11][13] 3[10][12]⇒[11][11] 
4[10][13]⇒[11][12] 2[10][11]⇒[11][13] 3[10][12]⇒[11][11] 4[11][12]⇒[11][10] 1[10][10]⇒[11][12] 
16 件，0.421 秒

座標位置は以下の通り。

最初の行を図解すると以下のようになる。

プログラムのソースは以下の通り。

#include "puzutl.h"

ulong board[20][20];            // 10円玉を配置する盤
struct struct_coinpos {         // 10円玉の位置
  int m_irow, m_icol;
};
const int ncoins = 4;           // 10円玉の個数
struct Coins {
  struct_coinpos p[ncoins];
}; // 配置する10円玉
Coins first;                    // 最初の位置。最初の位置と5回移動した先の位置が重ならないことを確認するため
Coins history[10];              // 10円玉の移動の履歴
int numFind = 0;                // 解の数

void coin_init( struct_coinpos& coin, int irow, int icol) // １枚の10円玉を盤上に配置する
{
  coin.m_irow = irow;
  coin.m_icol = icol;
}

void coins_init( Coins& coins)  // ４枚の10円玉を盤上に配置する
{
  coin_init( coins.p[0], 10, 10);
  coin_init( coins.p[1], 10, 11);
  coin_init( coins.p[2], 10, 12);
  coin_init( coins.p[3], 10, 13);
}

void coin_getpos( const struct_coinpos& coin, int id, int& minrow, int&mincol, int& maxrow, int& maxcol) // 10円玉の廻りの位置を求める
{
  int irow = coin.m_irow, icol = coin.m_icol;
  minrow = min( minrow, irow-1);
  mincol = min( mincol, icol-1);
  maxrow = max( maxrow, irow+1);
  maxcol = max( maxcol, icol+1);
  // 現在の10円玉の位置の廻りに６箇所置ける
  board[irow  ][icol-1] = id;   // 左右
  board[irow  ][icol+1] = id;
  if( irow&1) {
    board[irow-1][icol-1] = id;
    board[irow-1][icol  ] = id;
    board[irow+1][icol-1] = id;
    board[irow+1][icol  ] = id;
  }
  else {
    board[irow-1][icol  ] = id;
    board[irow-1][icol+1] = id;
    board[irow+1][icol  ] = id;
    board[irow+1][icol+1] = id;
  }
}

int coins_getpos( struct_coinpos pos[], Coins coins)  // ４枚の10円玉を配置できる位置を求める
{
  static ulong id = 10;         // 盤を初期化せず使うので,解を出力するとき小さな値を使うので初期値をちょっと大きめに設定する
  ++id;                         // 毎回違う値を盤に書き込む
  int minrow = 100, mincol = 100, maxrow = -1, maxcol = -1;
  for( int i=0; i< ncoins; i++) { // 現在の10円玉の位置の廻りに配置可能
    coin_getpos( coins.p[i], id, minrow, mincol, maxrow, maxcol);
  }
  int numpos = 0;
  // 配置可能な位置を配列に入れる
  for( int irow=minrow; irow <= maxrow; irow++) {
    for( int icol=mincol; icol <= maxcol; icol++) {
      if( board[irow][icol] == id) {
        pos[numpos].m_irow = irow;
        pos[numpos].m_icol = icol;
        numpos++;
      }
    }
  }
  return numpos;
}

YesNo coin_is_setnewpos( struct struct_coinpos pos[], int inewpos, Coins coins, int icoin)  // 新しい位置に配置できるか?
{
  int irow = pos[inewpos].m_irow, icol = pos[inewpos].m_icol;
  // 新しい位置に10円玉が存在してはならない。
  for( int i=0; i< ncoins; i++) {
    if( coins.p[i].m_irow == irow &&
        coins.p[i].m_icol == icol) return NO; // 既に新しい位置には10円玉が配置してあるので，そこには置けない。
  }
  // 新しい位置の廻りに２個の10円玉が無ければならない。
  static ulong id = 0; --id;
  for( i=0; i< ncoins; i++) {   // 残りの３つの10円玉の場所を記録する
    if( icoin == i) continue;   // 異なる10円玉が配置されていなければならない
    board[coins.p[i].m_irow][coins.p[i].m_icol] = id;
  }
  int numneighbor = 0;
  for( i=0; i< ncoins; i++) {   // 残りの３つの10円玉のうち２つが新しい位置の廻りに無ければならない
    if( icoin == i) continue;   // 異なる10円玉が配置されていなければならない
    if( board[irow  ][icol-1] == id) { numneighbor++; board[irow][icol-1] = 0;}
    if( board[irow  ][icol+1] == id) { numneighbor++; board[irow  ][icol+1] = 0;}
    if( irow&1) {
      if( board[irow-1][icol-1] == id) { numneighbor++; board[irow-1][icol-1] = 0;}
      if( board[irow-1][icol  ] == id) { numneighbor++; board[irow-1][icol  ] = 0;}
      if( board[irow+1][icol-1] == id) { numneighbor++; board[irow+1][icol-1] = 0;}
      if( board[irow+1][icol  ] == id) { numneighbor++; board[irow+1][icol  ] = 0;}
    }
    else {
      if( board[irow-1][icol  ] == id) { numneighbor++; board[irow-1][icol  ] = 0;}
      if( board[irow-1][icol+1] == id) { numneighbor++; board[irow-1][icol+1] = 0;}
      if( board[irow+1][icol  ] == id) { numneighbor++; board[irow+1][icol  ] = 0;}
      if( board[irow+1][icol+1] == id) { numneighbor++; board[irow+1][icol+1] = 0;}
    }
  }
  if( numneighbor >= 2) return YES;
  return NO;
}

void print_diff( Coins s, Coins d) 
{
  // sからdへ何をどう移動したかを出力する。
  // 違いは１つしかないはずなので，一つの違いを見つけたら出力する。
  for( int i=0; i< ncoins; i++) {
    if( s.p[i].m_irow != d.p[i].m_irow ||
        s.p[i].m_icol != d.p[i].m_icol) {
      ps( "%d[%d][%d]⇒[%d][%d] ", i+1, s.p[i].m_irow, s.p[i].m_icol, d.p[i].m_irow, d.p[i].m_icol);
    }
  }
}

void print_history( int level) 
{
  numFind++;
  for( int i=0; i< level; i++) {
    print_diff( history[i], history[i+1]);
  }
  ps( "\n");
}

void find( int level, Coins coins);

void move( int level, Coins coins, int icoins, struct_coinpos& newpos)
{
  coins.p[icoins] = newpos;
  if( level > 4) {
    // 横1列に並んでいたらOK
    int irow = coins.p[0].m_irow;
    for( int i=1; i< ncoins; i++) {
      if( irow != coins.p[i].m_irow) return;
    }
    // 最初の位置と重ならない。
    for( irow=0; irow < 20; irow++) for( int icol=0; icol< 20; icol++) board[irow][icol] = 0;
    for( i=0; i< ncoins; i++) {
      board[first.p[i].m_irow][first.p[i].m_icol]++;
      board[coins.p[i].m_irow][coins.p[i].m_icol]++;
    }
    for( irow=0; irow < 20; irow++) for( int icol=0; icol< 20; icol++) if(board[irow][icol] > 1) return;
    history[level] = coins;
    print_history( level);
    return;
  }
  find( level, coins);
}

void find( int level, Coins coins)
{
  struct_coinpos pos[30];       // 4個の10円玉の廻りに6箇所置き場所があるので次に移動できる位置は最大でも24箇所
  history[level] = coins;       // 移動手順を出力するため現在位置を記録する
  int numpos = coins_getpos( pos, coins); // 4つの10円玉を置ける場所を探す
  // 4つの10円玉を実際に新しい位置に置く。
  for( int i=0; i< ncoins; i++) {
    for( int j=0; j< numpos; j++) {
      if( coin_is_setnewpos( pos, j, coins, i)) { // 10円玉を新しい位置に配置できるか?
        move( level+1, coins, i, pos[j]); // 配置できるなら移動する
      }
    }
  }
}

int main( int argc, cstring argv[])
{
  ProcTime pt;
  Coins coins;
  coins_init( coins);           // 10円玉の初期位置を設定する
  first = coins;                // 初期位置を記録する
  find( 0/*level*/, coins);     // 探す
  pt.end();
  ps( "%d 件，%g 秒\n", numFind, pt.sec());
  return 0;
}