朝日新聞2005年2月5日のパズルパーク問題

問題

8x8のマトリックスがある。以下のルールで赤と黒で升を色分けする。

隣接する最大8個の升と自分自身を合わせた9個の升のうち4個を赤にする。

解答への道(ヒント)

一見コンピュータで解くことが出来そうな問題。しかし問題レベルは「易」。問題の意味さえ判ればプログラムを組まずとも直ぐに解けてしまうので今回はプログラムはなし。

4隅の升は隣接する升が自身を含め4個しかないので全て赤になることが判る。

後は一直線でしょ。

(2005.02.11)本日は休日なので，プログラムを作って解いてみた。プログラムを作っても20分も掛からなかった。それだけ簡単だってこと。

まずは8x8のマトリックスと色を定義する。

const int RED   = 1;
const int BLACK = 2;
int mat[8][8];
struct struct_undefrowcol {
  int m_row;
  int m_col;
};

メイン関数は以下のような感じ。

  cstring colorstr[] = { "？", "□", "■"};
  decided( 0, 0, RED);
  for( int row=0; row< 8; row++) {
    for( int col=0; col< 8; col++) {
      ps( "%s", colorstr[mat[row][col]]);
    }
    ps( "\n");
  }

[0,0]は赤だと判るので，[0,0]を赤に設定し，後は芋蔓式に色を決めていく。

肝となるdecided()は以下のような感じ。

void decided( int row, int col) 
{
  struct_undefrowcol undefRowCol[8];
  int cntRed, cntBlack, cntUndef, i;
  countColor( row, col, cntRed, cntBlack, cntUndef, undefRowCol); // mat[row][col]の周辺の色を調べる
  switch( cntRed) {
  case 4: // 残りは全て黒
    for( i=0; i< cntUndef; i++) {
      mat[undefRowCol[i].m_row][undefRowCol[i].m_col] = BLACK;
    }
    for( i=0; i< cntUndef; i++) {
      decided( undefRowCol[i].m_row, undefRowCol[i].m_col);
    }
    break;
  case 3: // 残りが1なら全て赤,2以上なら確定できず
  case 2: 
  case 1:
  case 0:
    if( cntUndef == 4-cntRed) {
      for( i=0; i< cntUndef; i++) {
        mat[undefRowCol[i].m_row][undefRowCol[i].m_col] = RED;
      }
      for( i=0; i< cntUndef; i++) {
        decided( undefRowCol[i].m_row, undefRowCol[i].m_col);
      }
    }
    break;
  default:
    pe( "Program ERROR\n");
    break;
  }
}

countColor()はmat[row][col]の周辺の色を調べる以下のような関数。

void countColor( int row, int col, int& cntRed, int& cntBlack, int& cntUndef, struct_undefrowcol undefRowCol[])
{
  cntRed = cntBlack = cntUndef = 0;
  getcolor( row-1, col-1, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row-1, col+0, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row-1, col+1, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row  , col-1, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row  , col+0, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row  , col+1, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row+1, col-1, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row+1, col+0, cntRed, cntBlack, cntUndef, undefRowCol);
  getcolor( row+1, col+1, cntRed, cntBlack, cntUndef, undefRowCol);
}

getcolor()はmat[row][col]の色が赤ならcntRedをカウントアップし，黒ならcntBlackをカウントアップし，まだ色が決まっていなければcntUndefをカウントアップして，undefRowCol[]に座標値を記録する以下のような関数。

void getcolor( int row, int col, int& cntRed, int& cntBlack, int& cntUndef, struct_undefrowcol undefRowCol[])
{
  if( row < 0 || row >= 8) return;
  if( col < 0 || col >= 8) return;
  int color = mat[row][col];
  if( color == RED) cntRed++;
  else if( color == BLACK) cntBlack++;
  else { undefRowCol[cntUndef].m_row = row; undefRowCol[cntUndef].m_col = col; cntUndef++;}
}

解速度

即