#include "puzutl.h"

#define ROWS    4               // 部屋数
#define COLS    4
int mat[ROWS][COLS];            // 1:訪問,0:未訪問
int matcnt[ROWS][COLS];         // 解候補数
int visit[ROWS*COLS];           // 訪問順序
const int rows=4, cols=4;
#define on      1               // 訪問した
#define off     0               // 未訪問
int goalRow = -1, goalCol = -1; // 出口(解が見つかったら設定する)

YesNo exist( int row, int col)  // 未訪問?
{
  if( row < 0) return NO;
  if( row >= rows) return NO;
  if( col < 0) return NO;
  if( col >= cols) return NO;
  if( mat[row][col]) return NO;
  return YES;
}

void find( int level, int row, int col)
{
  mat[row][col] = on;
  visit[level] = row * COLS + col;
  if( level >= rows*cols-1) {
    matcnt[row][col]++;
    mat[row][col] = off;
    if( goalRow == row && goalCol == col) {
      ps( "訪問順序は以下の通り\n");
      int       matvis[ROWS][COLS];
      for( int i=0; i<= level; i++) {
        int row = visit[i]/COLS, col = visit[i]%COLS;
        matvis[row][col] = i+1;
      }
      int row, col;
      for( row=0; row< rows; row++) {
        for( col=0; col< cols; col++) {
          ps( "%2d ", matvis[row][col]);
        }
        ps( "\n");
      }
    }
    return;
  }
  if( exist( row+0, col-1)) {
    find( level+1,row+0, col-1);
  }
  if( exist( row+0, col+1)) {
    find( level+1,row+0, col+1);
  }
  if( exist( row-1, col+0)) {
    find( level+1,row-1, col+0);
  }
  if( exist( row+1, col+0)) {
    find( level+1,row+1, col+0);
  }
  mat[row][col] = off;
}

int main( int argc, cstring argv[])
{
  int row, col;
  find( 0, 3, 1);
  for( row=0; row< rows; row++) {
    for( col=0; col< cols; col++) {
      if( matcnt[row][col]) ps( "Goal[%d][%d] : %d%s\n", row, col, matcnt[row][col], matcnt[row][col]==1?"☆":"");
      if( matcnt[row][col] == 1) { goalRow = row, goalCol = col;}
      matcnt[row][col] = 0;
    }
  }
  find( 0, 3, 1);
  return    0;
}