/******************************************************************************

                    「スリザーリンク」解法プログラム

         copyright (c) 1996  by T.Mori <mori@forest.dnj.ynu.ac.jp>
	 All right reserved.

	 $Author: mori $
	 $Revision: 2.6 $
	 $Date: 1996/11/11 11:38:32 $


0.はじめに

  このプログラムは森辰則(横浜国大・電子情報工学科)が横浜国立大学電子情
  報工学特別実験のために独自に開発したものです．
  著作権は放棄しませんが，GNU GENERAL PUBLIC LICENSE を適用するものと
  し，このプログラムのいかなる部分の変更・流用も自由とします．
  バグなどがありましたら，上記アドレスまで連絡を頂ければ幸いです．

1.インストールの方法

  普通にCコンパイラでコンパイルして下さい．ただし，ANSI C 準拠のコンパ
  イラが必要です．例えば GNU CC をお持ちでしたら，次のようにします．

  gcc -O -o surilin surilin.c

2.使い方

  このプログラムは以下のように起動します．

  surilin [-a] [-c] [-d] [-r] [-p] [-o 出力ファイル名] [-v] [データファイル名]

      -a                : 全解探索モード
      -c                : バックトラックサーチのまえに解の枝刈
      -d                : 途中結果も表示するデバッグモード
      -r                : プログラム可読出力モード
      -p                : 問題清書モード(解を求めない)
      -o 出力ファイル名 : 出力ファイルの名前
      -v                : バージョンの表示
      ファイル名        : データファイルの名前

  データファイルの名前を省略すると，標準入力からデータファイルが読み込
  まれます．また，出力ファイルを指定しない場合は標準出力に結果が出力されます．


3.データ形式

  このプログラムのデータ形式は次のようになっています．

  <Data>            ::=  <Line>+
  <Line>            ::=  <Comment>|<Data Line>
  <Data Line>       ::=  <Mark>+ '\n'
  <Mark>            ::=  <Number Mark>|<non-Number Mark>
  <Number Mark>     ::=  <Digit>
  <Digit>           ::=  '0'|'1'|'2'|'3'
  <non-Number Mark> ::=  '.'
  <Del>             ::=  <Digit>, <non-Number Mark> 以外の文字
  <Comment>         ::=  '#' <Any Character>* '\n'

  空白文字以外にも'+''=''|' を区切り文字にしてありますので，データをき
  れいに記述することができます．また，行頭に'#'のある行はコメントになり
  ますので，任意の文字を記述できます．
  

  例えば，以下のデータは正しいデータを表します．

      例1)
        #
        # Some comments
        #
	 . (0) .  . (1)
	 . (3) . (1) .
	(2) .  .  . (1)
	 . (3) . (3) .
	(3) .  . (3) .


      例2)
      ###############
      # ニコリ 例題 #
      ###############
      +   +   +   +   +   +
        .   0   .   .   1  
      +   +   +   +   +   +
        .   3   .   1   .  
      +   +   +   +   +   +
        2   .   .   .   1  
      +   +   +   +   +   +
        .   3   .   3   .  
      +   +   +   +   +   +
        3   .   .   3   .  
      +   +   +   +   +   +

******************************************************************************/
#ifndef lint
  static char surilin_version[] = "$Header: /home/forest/mori/src/slilin/RCS/slilin.c,v 2.6 1996/11/11 11:38:32 mori Exp mori $";
#endif 


#include <stdio.h>
#include <malloc.h>

/* booleanの定義 */
#ifndef TRUE
#define TRUE (1)
#define FALSE (0)
#endif

/* 数字マスについての一つの候補のデータ表現 */
struct cand {
  unsigned short line;
  /* unsigned char valid; */
  struct cand *next;
};

/* 数字マスのデータ表現．複数の候補からなる */
struct num_data {
  unsigned char num;
  unsigned char col;
  unsigned char row;
  unsigned char cand_no;
  struct cand *cand;
  unsigned char fixed;
  struct num_data *next;
};

/* ゴミ集め用リスト */
struct num_data_list {
  struct num_data *num_data;
  struct num_data_list *next;
};


/* 解のリスト */
struct board_list {
  unsigned short *line_board;
  struct board_list *next;
};

/* 大域データ */
struct board_list *board_list = NULL;
struct num_data_list *garbage_num_data = NULL;
int found = FALSE;

int height=0;
int width=0;
/* 盤面内のデータ (IDORG 以上は線分(のID)に対応する)*/
#define NO      (0) /* 線が引けないことが決定 */
#define YES     (1) /* 線が引けることが決定 */
#define UNKNOWN	(2) /* そこに線が引けるかどうか 未決定 */
#define IDORG	(3)
#define ID(id)  ((id)>=IDORG)
#define FIXED(id) (((id)==YES) || ((id)==NO) || ((id) >= IDORG))
#define NOTNUM  (4) /* 数字ではないマス */

#define YOKO	(0)
#define TATE	(1)
#define NOTDIR	(2)

#define UNCHANGED (0) /* 変化しなかった */
#define CHANGED (1)   /* 変化した       */

#define Line(b,dir,row,col)	(b)[(dir)*(height+2)*(width+2) + (row)*(width+2)+(col)]
#define Yoko(b,row,col)		Line(b,YOKO,row,col)
#define Tate(b,row,col)		Line(b,TATE,row,col)
#define Num(b,row,col)		(b)[(row)*width+col]
/*                             ↓ 1000000000000(2) */
#define NotLinePat		(010000)
#define GetBit(pat,n)		(((pat)>>(n)) & 1)


/* コマンドライン引数に関連する大域変数 */
FILE *infp = stdin;		/* 入力ファイルポインタ */
FILE *outfp = stdout;		/* 出力ファイルポインタ */
int debug_level = 0;		/* デバッグモードのレベル */
int ans_mode = TRUE;		/* 求解モードのフラグ */
int search_all_mode = FALSE;	/* 全解探索モードのフラグ */
int pruning_mode = FALSE;	/* バックトラックサーチ優先モードのフラグ */
int prog_readable_mode = FALSE;	/* 読み込み可能モードのフラグ */
char *progname;			/* 起動時のプログラム名 */


/* 線分の配置パタン */
unsigned short line_pat_bit[4][64+1];
/* 以下の文字列によるパタンをオリジナルにしているのは人間による保守のため */
/* ビットの順番が逆になっているので注意 */
/* nnnnnnnnnnyy なら 110000000000(2) に対応 */
char *line_pat[4][64+1] = {
  /* 0 */
  {
   "nnnnnnnnnnnn", "nnnnnnnnnnyy", "nnnnnnnnyynn", "nnnnnnnnyyyy",
   "nnnnnnyynnnn", "nnnnnnyynnyy", "nnnnnnyyyynn", "nnnnnnyyyyyy",
   "nnnnyynnnnnn", "nnnnyynnnnyy", "nnnnyynnyynn", "nnnnyynnyyyy",
   "nnnnyyyynnnn", "nnnnyyyynnyy", "nnnnyyyyyynn", "nnnnyyyyyyyy",
   (char *)NULL},
  /* 1 */
  {
   "nnnynynnnnyn","nnnyynnnnnyn","nnnynynnnnny","nnnyynnnnnny",
   "ynnnynnynnnn","ynnnynynnnnn","ynnnnynynnnn","ynnnnyynnnnn",
   "nynnnnnyynnn","nynnnnnynynn","nynnnnynynnn","nynnnnynnynn",
   "nnynnnnnnyyn","nnynnnnnnyny","nnynnnnnynyn","nnynnnnnynny",

   "nnnynynnyyyn","nnnyynnnyyyn","nnnynynnyyny","nnnyynnnyyny",
   "ynnnynnynnyy","ynnnynynnnyy","ynnnnynynnyy","ynnnnyynnnyy",
   "nynnnnnyynyy","nynnnnnynyyy","nynnnnynynyy","nynnnnynnyyy",
   "nnynnnyynyyn","nnynnnyynyny","nnynnnyyynyn","nnynnnyyynny",

   "nnnynyyynnyn","nnnyynyynnyn","nnnynyyynnny","nnnyynyynnny",
   "ynnnynnyyynn","ynnnynynyynn","ynnnnynyyynn","ynnnnyynyynn",
   "nynnyynyynnn","nynnyynynynn","nynnyyynynnn","nynnyyynnynn",
   "nnynyynnnyyn","nnynyynnnyny","nnynyynnynyn","nnynyynnynny",

   "nnnynyyyyyyn","nnnyynyyyyyn","nnnynyyyyyny","nnnyynyyyyny",
   "ynnnynnyyyyy","ynnnynynyyyy","ynnnnynyyyyy","ynnnnyynyyyy",
   "nynnyynyynyy","nynnyynynyyy","nynnyyynynyy","nynnyyynnyyy",
   "nnynyyyynyyn","nnynyyyynyny","nnynyyyyynyn","nnynyyyyynny",

   (char *)NULL},
  /* 2 */
  {
   "nnyynynnnynn","nnyynynnynnn","nnyyynnnnynn","nnyyynnnynnn",
   "ynnynnnynnny","ynnynnnynnyn","ynnynnynnnny","ynnynnynnnyn",
   "yynnynnnynnn","yynnnynnynnn","yynnynnnnynn","yynnnynnnynn",
   "nyynnnynnnyn","nyynnnnynnyn","nyynnnynnnny","nyynnnnynnny",

   "nnyynyyynynn","nnyynyyyynnn","nnyyynyynynn","nnyyynyyynnn",
   "ynnynnnyyyny","ynnynnnyyyyn","ynnynnynyyny","ynnynnynyyyn",
   "yynnynnnynyy","yynnnynnynyy","yynnynnnnyyy","yynnnynnnyyy",
   "nyynyyynnnyn","nyynyynynnyn","nyynyyynnnny","nyynyynynnny",

   "nynynyynnyyn","nynyynynnyyn","nynynyynnyny","nynyynynnyny",
   "nynynynynyyn","nynyynnynyyn","nynynynynyny","nynyynnynyny",
   "nynynyynynyn","nynyynynynyn","nynynyynynny","nynyynynynny",
   "nynynynyynyn","nynyynnyynyn","nynynynyynny","nynyynnyynny",

   "ynynynnynyyn","ynynynnyynyn","ynynynnynyny","ynynynnyynny",
   "ynynynynnyyn","ynynynynynyn","ynynynynnyny","ynynynynynny",
   "ynynnynynyyn","ynynnynyynyn","ynynnynynyny","ynynnynyynny",
   "ynynnyynnyyn","ynynnyynynyn","ynynnyynnyny","ynynnyynynny",
   (char *)NULL},
  /* 3 */
  {"ynyynnynnynn","ynyynnynynnn","ynyynnnynynn","ynyynnnyynnn",
   "yynynnnnynny","yynynnnnynyn","yynynnnnnyny","yynynnnnnyyn",
   "yyynynnnnnny","yyynnynnnnny","yyynynnnnnyn","yyynnynnnnyn",
   "nyyynyynnnnn","nyyynynynnnn","nyyyynynnnnn","nyyyynnynnnn",
   (char *)NULL}
};



/* 関数のプロトタイプ宣言 */
void initialize(void);
struct num_data *read_data(FILE *fp);
int get_one_box(FILE *fp);
unsigned short get_id(void);
void init_data(struct num_data *num_data_ptr, unsigned short **line_board_ptr, unsigned char **num_board_ptr, unsigned short **line_status_ptr);
unsigned short *alloc_line_board(void);
unsigned char *alloc_num_board(void);
void copy_line_board(unsigned short *dst, unsigned short *src);
struct num_data *mk_copy_num_data(struct num_data *ndp);
void free_num_data(struct num_data *ndp);
struct cand *make_cand(int num);
void solver(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *num_data_ptr);
void heuristics_static(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board);
void three_three_E(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col);
void three_three_S(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col);
void three_three_SE(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col);
void three_three_SW(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col);
void set_all_line_status(unsigned short *b, unsigned short mark);
struct num_data *solve(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *num_data_ptr);
struct num_data *prune_candidates(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp);
int fixed_board(unsigned short *line_board);
void sort_num_data(struct num_data **ndp_ptr);
void search_all(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp);
void count_candidate(struct num_data *ndp);
void search_all_1(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp);
void push_board_list(unsigned short *line_board);
void get_lines_on_board(unsigned short *line_board, unsigned char row, unsigned char col,
			unsigned short *line_yes_ptr, unsigned short *line_no_ptr);
void get_lines_on_board_1(unsigned short line, unsigned short *line_yes_ptr, unsigned short *line_no_ptr);
int put_lines_on_board(unsigned short *line_board, unsigned short *line_status,  int row, int col, unsigned short pat_yes, unsigned short pat_no, int msg);
int put_line(unsigned short *line_board, unsigned short *line_status, unsigned char dir, unsigned char row, unsigned char col,
	     unsigned short line,  int msg);
void get_intsect_point_info(unsigned short *line_board, unsigned char row, unsigned char col,
		       unsigned char *n_yes_ptr, unsigned char *n_no_ptr,
		       unsigned short *id_of_yes_ptr,
		       unsigned char *dir_unknown_1_ptr,
		       unsigned char *row_unknown_1_ptr, unsigned char *col_unknown_1_ptr,
		       unsigned char *dir_unknown_2_ptr,
		       unsigned char *row_unknown_2_ptr, unsigned char *col_unknown_2_ptr);
void get_intsect_point_info_1(unsigned short *line_board,
			 unsigned char dir, unsigned char row, unsigned char col,
			 unsigned char *n_yes_ptr, unsigned char *n_no_ptr,
			 unsigned short *id_of_yes_ptr,
			 unsigned char *dir_unknown_1_ptr,
			 unsigned char *row_unknown_1_ptr, unsigned char *col_unknown_1_ptr,
			 unsigned char *dir_unknown_2_ptr,
			 unsigned char *row_unknown_2_ptr, unsigned char *col_unknown_2_ptr);
void get_intsect_point_yes_info(unsigned short *line_board, unsigned char row, unsigned char col,
			   unsigned char *n_yes_ptr, unsigned short *id_of_yes_ptr);
void change_ID(unsigned short *line_board, unsigned short old, unsigned short new);
int other_IDs(unsigned short *line_board, int id);
void delete_invalid_cands(struct num_data *ndp, unsigned short *line_board);
int different_line_board(unsigned short *b1, unsigned short *b2);
void local_loop_check(unsigned short *line_board, unsigned short *line_status_new);
void local_loop_check_1(unsigned short *line_board, unsigned short *line_status_new,  unsigned char dir);
int intsect_point_check(unsigned short *line_board, unsigned short *line_status, unsigned short *line_status_new, unsigned char *num_board, int msg);
void pretty_print_board(FILE *fp, unsigned short *line_board, unsigned char *num_board, int id, int aste, int prog_readable_mode);
void print_yoko_line(FILE *fp, unsigned short yoko, int id, int aste);
void print_tate_line(FILE *fp, unsigned short tate, int id, int aste);
void print_line(FILE *fp, unsigned char dir, unsigned short line, int id, int aste);
unsigned short get_pat_line(unsigned short line_yes, unsigned short line_no, unsigned char n);
void pretty_print_cand(FILE *fp, unsigned short line_yes, unsigned short line_no);
void pretty_print_all_cand(FILE *fp, struct cand *cand);
void usage(void);




/* メイン */
void
main(int argc, char *argv[])
{
  struct num_data *num_data_ptr;
  unsigned short *line_board;
  unsigned char *num_board;
  unsigned short *line_status;
  int c,i;

  extern char *optarg;
  extern int optind,opterr;

  progname = argv[0];

  while ((c=getopt(argc,argv,"dpro:vac")) != EOF) {
    switch (c) {
    case 'd':
      debug_level++;
      if (debug_level > 5) fprintf(stderr, "Debug Level > 5\n");
      break;
    case 'p':
      ans_mode = FALSE;
      break;
    case 'r':
      prog_readable_mode = TRUE;
      break;
    case 'a':
      search_all_mode = TRUE;
      break;
    case 'c':
      pruning_mode = TRUE;
      break;
    case 'o':
      if ((outfp = fopen(optarg,"w")) == (FILE *)NULL) {
	fprintf(stderr, "%s: cannot open the file %s.\n", progname, optarg);
	exit(1);
      }
      break;
    case 'v':
      usage();
      exit(0);
      break;    /* Never reach */
    case '?':
    default:
      usage();
      exit(1);
    }
  }

  switch(argc - optind) {
  case 0:
    break;
  case 1:
    if ((infp = fopen(argv[optind],"r")) == (FILE *)NULL) {
      fprintf(stderr, "%s: %s -- No such file.\n", progname, argv[optind]);
      exit(1);
    }
    break;  /* Never reach */
  default:
    usage();
    exit(1);
  }

  /* 初期設定 */
  initialize();
  /* データ読み込み */
  num_data_ptr = read_data(infp);
  /* データ初期化 */
  init_data(num_data_ptr, &line_board,&num_board,&line_status);

  /* 入力データの表示 */
  if (debug_level > 2){
    pretty_print_board(outfp, line_board, num_board, TRUE, TRUE, TRUE);
    fprintf(outfp,"\n\n");
  }

  if (ans_mode) {
    solver(line_board, line_status, num_board, num_data_ptr);
  }
  else
    pretty_print_board(outfp, line_board, num_board, FALSE, FALSE, prog_readable_mode);

  exit(0);
}


void
initialize(void)
{
  unsigned short bit_pat;
  int i,j,k;

  for(i=0; i<=3; i++) {
    for(j=0; line_pat[i][j] != (char *)NULL ;j++) {
      for(k=11,bit_pat=0; k>=0; k--) {
	bit_pat <<= 1;
	if (line_pat[i][j][k] == 'y')
	  bit_pat |= 1;
      }
      line_pat_bit[i][j] = bit_pat;
    }
    line_pat_bit[i][j] = NotLinePat;
  }
}

#define RETURN (-2)
#define NNMARK (-3)
#define NONUMBER '.'

/* データの読み込み */
struct num_data *
read_data(FILE *fp)
{
  int c;
  struct num_data *num_data_ptr=NULL, *newptr;
  unsigned char row = 0, col = 0;
  
  while ((c = get_one_box(fp)) != EOF) {	/* 1マスのデータを読む */
    if (c >= 0) {				/* 数字ならデータ設定 */
      if (debug_level > 2) fprintf(stderr,"%d",c);
      if ((newptr = (struct num_data *)malloc(sizeof(struct num_data)))
	  == NULL) {
	fprintf(stderr, "malloc error in read_data().\n");
	exit(1);
      }
      newptr->num       = (unsigned char)c;
      newptr->col   	= col;
      newptr->row   	= row;
      newptr->cand_no	= 0;
      newptr->cand	= make_cand(c);
      newptr->fixed	= FALSE;
      newptr->next	= num_data_ptr;

      num_data_ptr = newptr;
      col++;
    } else if (c == RETURN) {
      if (debug_level > 2) fprintf(stderr,"\n");
      if (width <=0)
	width = col;
      else if (col != width && col != 0) {
	fprintf(stderr, "%s: malformed data (at line %d. %d != %d).\n", progname, row+1, col, width);
	exit(1);
      }
      if (col != 0) row++;
      col = 0;
    } else if (c == NNMARK) {
      if (debug_level > 2) fprintf(stderr,".");
      col++;
    }
  }
  height = row;

  return(num_data_ptr);
}


/* コメント，区切り文字を読み飛ばし，1マス分のデータを読む．
 * 値 0〜3	その数字
 *  .		空欄
 */
int
get_one_box(FILE *fp)
{
  int c;
  int comment;

  do {
    comment = FALSE;
    c = getc(fp);
    if (c == '#') {
      comment = TRUE;
      while ((c = getc(fp)) != '\n' && c != EOF)
	;
    }
  } while (comment || !( ('0'<= c && c <= '3') || c == NONUMBER || c == '\n' || c == EOF ));

  if ('0' <= c && c <= '3') {
    c -= '0';
  } else if (c == NONUMBER) {
    c = NNMARK;
  } else if (c == '\n') {
    c = RETURN;
  } else if ( c != EOF ) {
    c = FALSE;
  }

  return(c);
}


/* 線IDの割り当て */
unsigned short
get_id(void)
{
  static unsigned short id = IDORG-1;

  id++;

  if (debug_level > 4) fprintf(stderr,"ID assignment %d\n", id);
  return(id);
}

/* データの初期化 */
void
init_data(struct num_data *num_data_ptr, unsigned short **line_board_ptr, unsigned char **num_board_ptr, unsigned short **line_status_ptr)
{
  int i,j,k;
  struct num_data *nd;

  *line_board_ptr = alloc_line_board();
  *line_status_ptr = alloc_line_board();
  *num_board_ptr  = alloc_num_board();

  for(nd = num_data_ptr; nd != NULL; nd = nd->next) {
    Num(*num_board_ptr, nd->row,nd->col) = nd->num;
  }
}

/* 盤面データの取得 */
unsigned short *
alloc_line_board(void)
{
  unsigned short *b;
  int i,j;

  if ((b = (unsigned short *)malloc(sizeof(unsigned short)*(height+2)*(width+2)*2))
      == NULL) {
    fprintf(stderr, "malloc error in alloc_line_board().\n");
    exit(1);
  }
  for (i=0; i<= height; i++)
    for (j=0; j<= width; j++)
      Yoko(b,i,j) = Tate(b,i,j) = UNKNOWN;

  for (j=0; j<=width; j++)
    Tate(b,0,j)=Tate(b,height+1,j)=NO;

  for (i=0; i<=height; i++)
    Yoko(b,i,0)=Yoko(b,i,width+1)=NO;

  return(b);
}


unsigned char *
alloc_num_board(void)
{
  unsigned char *b;
  int i,j;

  if ((b = (unsigned char *)malloc(sizeof(unsigned char)*width*height))
      == NULL) {
    fprintf(stderr, "malloc error in alloc_num_board().\n");
    exit(1);
  }
  for (i=0; i<height; i++)
    for (j=0; j<width; j++)
      Num(b,i,j) = NOTNUM;

  return(b);
}


/* 盤面データの解放 */
#define Free_line_board(b)	free((char *)b)
#define Free_num_board(b)	free((char *)b)


/* 盤面データのコピー */
void
copy_line_board(unsigned short *dst, unsigned short *src)
{
  int i;

  for (i=(height+2)*(width+2)*2; i>=0 ; i--)
    dst[i] = src[i];
}


struct num_data *
mk_copy_num_data(struct num_data *ndp)
{
  struct num_data *newndp, *tmp_ndp, root_data, *root; 
  struct cand *cand, *newcand, *tmp_cand, root_cand_data, *root_cand;

  root = &root_data;
  root->next = NULL;
  root_cand = &root_cand_data;

  for (newndp = root; ndp != NULL; ndp = ndp->next) {
    if ((tmp_ndp = (struct num_data *)malloc(sizeof(struct num_data)))
	== NULL) {
      fprintf(stderr, "malloc error in mk_copy_num_data().\n");
      exit(1);
    }
    *tmp_ndp = *ndp;
    newndp->next = tmp_ndp;
    newndp = tmp_ndp;
    for (newcand = root_cand,cand=ndp->cand; cand != NULL; cand=cand->next) {
      if ((tmp_cand = (struct cand *)malloc(sizeof(struct cand)))
	  == NULL) {
	fprintf(stderr, "malloc error in mk_copy_num_data().\n");
	exit(1);
      }
      *tmp_cand = *cand;
      newcand->next = tmp_cand;
      newcand = tmp_cand;
    }
    newndp->cand=root_cand->next;
  }

  return root->next;
}


void
free_num_data(struct num_data *ndp)
{
  struct num_data *nextndp;
  struct cand *cand, *nextcand;

  while (ndp != NULL) {
    nextndp = ndp->next;
    cand = ndp->cand;
    while (cand != NULL) {
      nextcand = cand->next;
      free(cand);
      cand = nextcand;
    }
    free(ndp);
    ndp = nextndp;
  }
}
/* 線分パタンの作成 */
struct cand *
make_cand(int num)
{
  struct cand *cand = (struct cand *)NULL;
  struct cand *newcand;
  int i;

  if (num<0 || num>3) {
    fprintf(stderr, "%s: Invalid number %d.\n", progname, num);
    exit(1);
  }

  for (i=0; line_pat_bit[num][i] != NotLinePat; i++) {
    if ((newcand = (struct cand *)malloc(sizeof(struct cand)))
	== NULL) {
      fprintf(stderr, "malloc error in make_cand().\n");
      exit(1);
    }
    newcand->line = line_pat_bit[num][i];

    if (debug_level>4) {
      fprintf(stderr, "\n");
      fprintf(stderr, "num=%d, i=%d\n", num, i);
      pretty_print_cand(stderr, newcand->line, ~(newcand->line));
      fprintf(stderr, "\n");
    }

    /* newcand->valid = TRUE; */
    newcand->next=cand;
    cand=newcand;
  }

  return(cand);
}


/* 求解 */
void
solver(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *num_data_ptr)
{
  /* 静的なヒューリスティックスを適用 */
  heuristics_static(line_board,line_status,num_board);
  if (debug_level) {
    fprintf(stderr, "After applying static heuristics.\n");
    pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
    fprintf(stderr, "Constraint satisfaction starts.\n");
  }

  /* 局所的制約適用 */
  set_all_line_status(line_status, CHANGED);
  num_data_ptr = solve(TRUE, line_board, line_status, num_board, num_data_ptr);

  if (num_data_ptr) {
    if (num_data_ptr == (struct num_data *)TRUE) {
      /* 局所的制約だけで解けた */
      pretty_print_board(outfp, line_board, num_board, FALSE, TRUE, FALSE);
      if (debug_level) {
	fprintf(stderr, "Solved with :\n");
	fprintf(stderr, "    'Static Heuristics'\n");
	fprintf(stderr, "    'Constraint satisfaction'\n");
      }
    } else {
      /* 未解消の部分がある */
      if (debug_level) {
	fprintf(stderr, "Cannot solve only with local constraints.\n");
	pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
      }
      if (pruning_mode) {
	if (debug_level) {
	  fprintf(stderr, "Pruning of contradictory candidates starts.\n");
	}
	/* 配線候補のうち配置しただけで矛盾がわかるものの枝刈 */
	num_data_ptr = prune_candidates(line_board, line_status, num_board, num_data_ptr);
	set_all_line_status(line_status, CHANGED);
	num_data_ptr = solve(TRUE, line_board, line_status, num_board, num_data_ptr);
	
	if (num_data_ptr == (struct num_data *)TRUE) {
	  /* 解けた */
	  pretty_print_board(outfp, line_board, num_board, FALSE, TRUE, FALSE);
	  if (debug_level) {
	    fprintf(stderr, "Solved with :\n");
	    fprintf(stderr, "    'Static Heuristics'\n");
	    fprintf(stderr, "    'Constraint satisfaction'\n");
	    fprintf(stderr, "    'Pruning of contradictory candidates'\n");
	  }
	  return;
	} else if (num_data_ptr) {
	  if (debug_level) {
	    fprintf(stderr, "Cannot solve with pruning of candidates.\n");
	    pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
	  }
	} else {
	  /* 矛盾が生じた．*/
	  fprintf(outfp, "No answer.\n");
	  return;
	}
      }
      /* 未解消の部分がある */
      /* バックトラックによる探索 */
      if (debug_level) {
	fprintf(stderr, "Backtrack search starts.\n");
      }
      if (debug_level > 2)
	search_all(TRUE, line_board, line_status, num_board, num_data_ptr);
      else
	search_all(FALSE, line_board, line_status, num_board, num_data_ptr);
      if (board_list == NULL) {
	/* 矛盾が生じた．*/
	fprintf(outfp, "No answer.\n");
      } else {
	for (; board_list != NULL; board_list = board_list->next) {
	  pretty_print_board(outfp, board_list->line_board, num_board,
			     FALSE, TRUE, FALSE);
	}
	if (debug_level) {
	  fprintf(stderr, "Solved with :\n");
	  fprintf(stderr, "    'Static Heuristics'\n");
	  fprintf(stderr, "    'Constraint satisfaction'\n");
	  if (pruning_mode) {
	    fprintf(stderr, "    'Pruning of contradictory candidates'\n");
	  }
	  fprintf(stderr, "    'Backtrack search'\n");
	}
      }
    }
  } else {
    /* 局所制約に矛盾が生じた．*/
    fprintf(outfp, "No answer.\n");
  }
}

/* 静的ヒューリスティック適用 */
void
heuristics_static(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board)
{
  unsigned char row,col;

  for(row=0; row<height; row++) {
    for(col=0; col<width; col++){
      three_three_E(line_board,line_status,num_board,row,col);
      three_three_S(line_board,line_status,num_board,row,col);
      three_three_SE(line_board,line_status,num_board,row,col);
      three_three_SW(line_board,line_status,num_board,row,col);
    }
  }
}

/* ヒューリスティック ここから */
void
three_three_E(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col)
{
  if (col <= width-2) {
    if (Num(num_board,row,col) == 3 && Num(num_board,row,col+1) == 3) {
      put_line(line_board,line_status,TATE,row+1,col,   YES, TRUE);
      put_line(line_board,line_status,TATE,row+1,col+1, YES, TRUE);
      put_line(line_board,line_status,TATE,row+1,col+2, YES, TRUE);
      put_line(line_board,line_status,TATE,row  ,col+1, NO, TRUE);
      put_line(line_board,line_status,TATE,row+2,col+1, NO, TRUE);
    }
  }
}

void
three_three_S(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col)
{
  if (row <= height-2) {
    if (Num(num_board,row,col) == 3 && Num(num_board,row+1,col) == 3) {
      put_line(line_board,line_status,YOKO,row  ,col+1, YES, TRUE);
      put_line(line_board,line_status,YOKO,row+1,col+1, YES, TRUE);
      put_line(line_board,line_status,YOKO,row+2,col+1, YES, TRUE);
      put_line(line_board,line_status,YOKO,row+1,col,   NO, TRUE);
      put_line(line_board,line_status,YOKO,row+1,col+2, NO, TRUE);
    }
  }
}

void
three_three_SE(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col)
{
  if (row <= height-2 && col <= width-2) {
    if (Num(num_board,row,col) == 3 && Num(num_board,row+1,col+1) == 3) {
      put_line(line_board,line_status,YOKO,row,  col+1, YES, TRUE);
      put_line(line_board,line_status,TATE,row+1,col,   YES, TRUE);
      put_line(line_board,line_status,TATE,row+2,col+2, YES, TRUE);
      put_line(line_board,line_status,YOKO,row+2,col+2, YES, TRUE);
      put_line(line_board,line_status,TATE,row,  col,   NO, TRUE);
      put_line(line_board,line_status,YOKO,row,  col,   NO, TRUE);
      put_line(line_board,line_status,YOKO,row+2,col+3, NO, TRUE);
      put_line(line_board,line_status,TATE,row+3,col+2, NO, TRUE);
    }
  }
}

void
three_three_SW(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, unsigned char row, unsigned char col)
{
  if (row <= height-2 && col >= 1) {
    if (Num(num_board,row,col) == 3 && Num(num_board,row+1,col-1) == 3) {
      put_line(line_board,line_status,YOKO,row,  col+1, YES, TRUE);
      put_line(line_board,line_status,TATE,row+1,col+1, YES, TRUE);
      put_line(line_board,line_status,TATE,row+2,col-1, YES, TRUE);
      put_line(line_board,line_status,YOKO,row+2,col,   YES, TRUE);
      put_line(line_board,line_status,TATE,row,  col+1, NO, TRUE);
      put_line(line_board,line_status,YOKO,row,  col+2, NO, TRUE);
      put_line(line_board,line_status,YOKO,row+2,col-1, NO, TRUE);
      put_line(line_board,line_status,TATE,row+3,col-1, NO, TRUE);
    }
  }
}
/* ヒューリスティック ここまで */


/* 盤面状態の設定 */
void
set_all_line_status(unsigned short *b, unsigned short mark)
{
  int i;

  for (i=(height+2)*(width+2)*2; i>=0 ; i--)
    b[i] = mark;
}


struct num_data *
solve(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *num_data_ptr)
{
  struct num_data *ndp, *ndp2, root;
  unsigned short common_line_yes,common_line_no;
  struct cand *cnd;
  unsigned short *line_board_old;
  unsigned short *line_status_new;
  int i,j;

  if (num_data_ptr == NULL)  return (struct num_data *)TRUE;
  
  line_board_old = alloc_line_board();
  line_status_new = alloc_line_board();


  do {
    copy_line_board(line_board_old, line_board);
    set_all_line_status(line_status_new, UNCHANGED);
    /*
     *   各数字マスについて
     *   該当箇所の確定部分と矛盾する配線候補を破棄する．
     *   候補が無くなってしまった場合は，解なし
     *   すべての配線候補で共通する部分を取り出し，盤面に書き込む
     *   候補が一つしかないものは確定
     *   書き込んだ線分の両端で連接チェック
     *   接続されている線分においてIDを同じものに書き換える．
     */
    for (ndp = num_data_ptr; ndp != NULL; ndp=ndp->next) {

      if (! num_rel_lines_changed(ndp,line_status) ) continue;

      /* 該当箇所の確定部分と矛盾する配線候補を破棄する．*/
      delete_invalid_cands(ndp,line_board);
      if (debug_level > 4) {
	fprintf(stderr, "==========\n");
	fprintf(stderr, "num=%d\n", ndp->num);
	pretty_print_all_cand(stderr, ndp->cand);
	fprintf(stderr, "==========\n");
      }

      if (ndp->cand == NULL) {
        /* 候補が無くなってしまった場合は，解なし．処理終了 */
	if (msg)
	  fprintf(outfp, "No consistent answer at %d (%d,%d)\n", ndp->num, ndp->row, ndp->col);
	return (struct num_data *)FALSE;
      }
      /*  候補が一つしかないものは確定 */
      if (ndp->cand->next == NULL) {
	if (debug_level >2) {
	  fprintf(stderr, "(%d,%d) is fixed.\n", ndp->row, ndp->col);
	}
	ndp->fixed = TRUE;
      }
      /* すべての配線候補で共通する部分を取り出し，*/
      common_line_yes = 07777;
      common_line_no  = 07777;
      for (cnd=ndp->cand; cnd != NULL; cnd = cnd->next) {
	common_line_yes &= cnd->line;
	common_line_no  &= ~(cnd->line);
      }

      if (debug_level > 2) {
	fprintf(stderr, "Common Pattern for %d (%d,%d)\n", ndp->num, ndp->row, ndp->col);
	pretty_print_cand(stderr, common_line_yes, common_line_no);
      }

      /* 盤面に書き込む */
      /* IDの管理ならびにループのチェックも行なう */
      if (!put_lines_on_board(line_board, line_status_new, ndp->row, ndp->col, common_line_yes,common_line_no, msg))
	return (struct num_data *)FALSE;

      if (debug_level > 2) {
	fprintf(outfp,"\n");
	pretty_print_board(outfp, line_board, num_board, TRUE, TRUE, TRUE);
      }
    } /* for */

    /* fixしたマスの情報を取り除く */
    root.next = num_data_ptr;
    ndp2 = &root;
    ndp = ndp2->next = num_data_ptr;
    while (ndp != NULL) {
      if (ndp->fixed) {
	if (debug_level > 2) {
	  fprintf(stderr, "Number %d (%d,%d) is fixed\n", ndp->num, ndp->col, ndp->row);
	}
	ndp2->next = ndp->next;
	free(ndp);
	ndp = ndp2->next;
      } else {
	ndp2 = ndp;
	ndp = ndp->next;
      }
    }
    num_data_ptr = root.next;

    /*
     *   各交点においてそこから伸びる線の数は 0 か 2であるから，
     *   これを利用して線を伸ばす．
     *   UNKNOWN の数が 1 個の場合に可能．
     *     3つ x      → UNKNOWN のところも x
     *     1つ o 2つx → UNKNOWN のところが o
     *     2つ o      → のこりのところが x
     */
    if (!intsect_point_check(line_board,line_status,line_status_new,num_board,msg)) 
      return (struct num_data *)FALSE;

    /*
     *  上記制約チェックで一つも状態変化がおこらなかった場合に，
     *  ローカルループチェックをする．
     *  そして，ローカルループになるところを x にする
     */
    if (! change_line_status(line_status_new))
      local_loop_check(line_board, line_status_new);

    /*
     * 線分の変化情報のコピー
     */
    copy_line_board(line_status, line_status_new);

/*} while (different_line_board(line_board, line_board_old)); */
  } while (change_line_status(line_status));

  /* 盤面が変わらなくなるまで繰り返す */

  Free_line_board(line_board_old);
  Free_line_board(line_status_new);

  if (num_data_ptr == NULL) {
    /* 判断が甘い． 盤面上に UNKNOWN がなくなったら，が本当 */
    if (debug_level > 1) fprintf(stderr, "Solved. (num_data_ptr == NULL)\n");
    return (struct num_data *)TRUE;
  } else {
    if (debug_level > 1) fprintf(stderr, "Not solved. (num_data_ptr != NULL)\n");
    return num_data_ptr;
  }
}

struct num_data *
prune_candidates(unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp)
{
  struct num_data *ndp1,*ndp2,*ndp_new, ndp_root_data, *ndp_root;
  struct cand *cl1, *cl2, root_data, *root;
  unsigned short *line_board_new, *line_board_tmp;

  if (ndp == NULL) return (struct num_data *)NULL;

  line_board_new = alloc_line_board();
  line_board_tmp = alloc_line_board();

  root = &root_data;
  ndp_root = &ndp_root_data;

  count_candidate(ndp);
  sort_num_data(&ndp);
  ndp2 = ndp_root;
  ndp1 = ndp_root->next = ndp;

  found = FALSE;

  while (ndp1 != NULL && (search_all_mode || !found) ) {
    cl2 = root;
    cl1 = root->next = ndp1->cand;
    while(cl1 != NULL) {
      copy_line_board(line_board_tmp, line_board);
      ndp_new = mk_copy_num_data(ndp_root->next);


      if (debug_level>1) {
	int i;

	fprintf(stderr, "Hypothesis at %d (%d,%d)\n",
		ndp1->num, ndp1->row, ndp1->col);
	for (i=0; i<12; i++)
	  fprintf(stderr, "%d|",((cl1->line)>>i & 1));
	fprintf(stderr, "\n");
	pretty_print_cand(stderr, cl1->line, ~(cl1->line));
	fprintf(stderr, "\n");
      }

      set_all_line_status(line_status, UNCHANGED);
      if (put_lines_on_board(line_board_tmp, line_status, ndp1->row, ndp1->col, cl1->line, ~(cl1->line), FALSE)
	  && (ndp_new = solve(FALSE, line_board_tmp,  line_status, num_board, ndp_new))) {
	/* 整合性がある候補 */
	cl2 = cl1;
	cl1 = cl1->next;
	copy_line_board(line_board_new, line_board_tmp);
	if (debug_level>1) {
	  fprintf(stderr, "is OK.\n");
	}
      } else {
	/* 整合性がない候補 */
	cl2->next = cl1->next;
	free(cl1);
	cl1 = cl2->next;
	if (debug_level>1) {
	  fprintf(stderr, "is NG.\n");
	}
      }
      ndp1->cand = root->next;
      if(ndp_new != (struct num_data *)NULL
	 && ndp_new != (struct num_data *)TRUE)
	free_num_data(ndp_new);
    }
    if (ndp1->cand != (struct cand *)NULL
	&& ndp1->cand->next == (struct cand *)NULL) {
      /* 候補が一つしかないマス */
      copy_line_board(line_board, line_board_new);

      /* UNKNOWN がなければ found. 全解探索でないならばループ終了 */
      found = fixed_board(line_board);

      if (debug_level>1) {
	fprintf(stderr, "Pruning goes on...\n");
	pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
      }
      /* そのマスを削除 */
      ndp2->next = ndp1->next;
      ndp1->next = NULL;
      free_num_data(ndp1);
      ndp1 = ndp2->next;
    } else {
      /* 候補が2個以上もしくは0個のマスは残す */
      ndp2 = ndp1;
      ndp1 = ndp1->next;
    }
  }
  Free_line_board(line_board_new);
  Free_line_board(line_board_tmp);

  return ndp_root->next;
}

int
fixed_board(unsigned short *line_board)
{
  int i;
  
  for (i=(height+2)*(width+2)*2; i>=0 ; i--)
    if (line_board[i] == UNKNOWN) return FALSE;

  return TRUE;
}


void
sort_num_data(struct num_data **ndp_ptr)
{
  struct num_data root_data, *root, ans_data, *ans, *ndp1,*ndp2;

  if (*ndp_ptr == NULL) return;

  ans = &ans_data;
  ans->next = *ndp_ptr;
  *ndp_ptr = (*ndp_ptr)->next;
  ans->next->next = NULL;

  while (*ndp_ptr != NULL) {
    ndp2 = ans;
    ndp1 = ans->next;
    while(ndp1 != NULL && ndp1->cand_no < (*ndp_ptr)->cand_no) {
      ndp2 = ndp1;
      ndp1 = ndp1->next;
    }
    ndp2->next = *ndp_ptr;
    *ndp_ptr = (*ndp_ptr)->next;
    ndp2->next->next = ndp1;
  }

  *ndp_ptr = ans->next;
}


void
search_all(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp)
{
  found = FALSE;
  count_candidate(ndp);
  search_all_1(msg, line_board, line_status, num_board, ndp);
}

void
count_candidate(struct num_data *ndp)
{
  struct cand *cand;

  for (; ndp != NULL; ndp=ndp->next) {
    for (cand=ndp->cand,ndp->cand_no = 0; cand != NULL; cand=cand->next)
      (ndp->cand_no)++;
  }
}


void
search_all_1(int msg, unsigned short *line_board, unsigned short *line_status, unsigned char *num_board, struct num_data *ndp)
{
  struct cand *cand;
  unsigned short *line_board_new;
  struct num_data *ndp_new, *ndp_tmp, root_dat, *root, *ndp1, *ndp2, *ndp1min, *ndp2min;
  int i,c,cmin;

  if (ndp == NULL) return;


  root = &root_dat;
  root->next = ndp;

  cmin = 10000; /* 最小値よりも小さい可能性のない数 */
  ndp2 = root;
  ndp1 = root->next;

  for (; ndp1 != NULL; ndp2 = ndp1, ndp1 = ndp1->next) {
    if (ndp1->cand_no < cmin) {
      cmin = ndp1->cand_no;
      ndp2min=ndp2;
      ndp1min=ndp1;
    }
  }
  if (debug_level > 1) {
    fprintf(stderr, "Min. No. of cand = %d\n", cmin);
  }
  ndp2min->next = ndp1min->next; /* ndp1min が候補数最小のものを指し示す */
  ndp = root->next;

  line_board_new = alloc_line_board();
  copy_line_board(line_board_new, line_board);

  for (cand=ndp1min->cand; cand != NULL && (search_all_mode || !found); cand=cand->next) {
    ndp_new = mk_copy_num_data(ndp);
    if (debug_level > 1) {
      fprintf(stderr, "Hypothesis at %d (%d,%d)\n",
	      ndp1min->num, ndp1min->row, ndp1min->col);
      for (i=0; i<12; i++)
	fprintf(stderr, "%d|",((cand->line)>>i & 1));
      fprintf(stderr, "\n");
      pretty_print_cand(stderr, cand->line, ~(cand->line));
      fprintf(stderr, "\n");
    }
    set_all_line_status(line_status,UNCHANGED);
    if (put_lines_on_board(line_board_new, line_status, ndp1min->row, ndp1min->col, cand->line, ~(cand->line), msg)) {
      if (debug_level > 1) {
	fprintf(stderr, "is OK\n");
      }
      ndp_new = solve(msg, line_board_new, line_status, num_board, ndp_new);
      if (debug_level >1 ){
	fprintf(stderr, "After solve in search_all\n");
	pretty_print_board(stderr, line_board_new, num_board, FALSE, TRUE, FALSE);
      }
      if (ndp_new == (struct num_data *)TRUE) {
	if (debug_level >1 ) {
	  fprintf(stderr, "Before push in serach_all\n");
	  pretty_print_board(stderr, line_board_new, num_board, FALSE, TRUE, FALSE);
	}
	push_board_list(line_board_new);
	found = TRUE;
      } else if (ndp_new != NULL) {
	search_all_1(msg, line_board_new, line_status, num_board, ndp_new);
      }
    } else {
      if (debug_level > 1) {
	fprintf(stderr, "is NG\n");
      }
    }
    copy_line_board(line_board_new, line_board);
    if (ndp_new != (struct num_data *)NULL
	&& ndp_new != (struct num_data *)TRUE)
      free_num_data(ndp_new);
  }
  Free_line_board(line_board_new);
}

void
push_board_list(unsigned short *line_board)
{
  struct board_list *bl;

  if ((bl = (struct board_list *)malloc(sizeof(struct board_list)))
      == NULL) {
    fprintf(stderr, "malloc error in push_board_list().\n");
    exit(1);
  }

  bl->line_board = alloc_line_board();
  copy_line_board(bl->line_board,line_board);

  bl->next = board_list;
  board_list = bl;
}


void
get_lines_on_board(unsigned short *line_board, unsigned char row, unsigned char col,
		   unsigned short *line_yes_ptr, unsigned short *line_no_ptr)
{
  *line_yes_ptr = 0;
  *line_no_ptr  = 0;
  get_lines_on_board_1(Line(line_board, YOKO, row+1, col  ), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row+2, col  ), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row+2, col+1), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, YOKO, row+1, col+2), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, YOKO, row,   col+2), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row,   col+1), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row,   col  ), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, YOKO, row,   col  ), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row+1, col  ), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, YOKO, row+1, col+1), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, TATE, row+1, col+1), line_yes_ptr, line_no_ptr);
  get_lines_on_board_1(Line(line_board, YOKO, row,   col+1), line_yes_ptr, line_no_ptr);
}

void
get_lines_on_board_1(unsigned short line, unsigned short *line_yes_ptr, unsigned short *line_no_ptr)
{
  *line_yes_ptr <<= 1;
  *line_no_ptr <<= 1;
  if (ID(line)) {
    *line_yes_ptr |= 1;
  } else if (line == NO) {
    *line_no_ptr |= 1;
  }
}


int
put_lines_on_board(unsigned short *line_board, unsigned short *line_status,
                   int row, int col,
		   unsigned short pat_yes, unsigned short pat_no,  int msg)
{
  if (!(   put_line(line_board,line_status,YOKO,row  , col+1,get_pat_line(pat_yes,pat_no,0),msg)
	&& put_line(line_board,line_status,TATE,row+1, col+1,get_pat_line(pat_yes,pat_no,1), msg)
	&& put_line(line_board,line_status,YOKO,row+1, col+1,get_pat_line(pat_yes,pat_no,2), msg)
	&& put_line(line_board,line_status,TATE,row+1, col  ,get_pat_line(pat_yes,pat_no,3), msg)
	&& put_line(line_board,line_status,YOKO,row  , col  ,get_pat_line(pat_yes,pat_no,4),msg)
	&& put_line(line_board,line_status,TATE,row  , col,  get_pat_line(pat_yes,pat_no,5), msg)
	&& put_line(line_board,line_status,TATE,row  , col+1,get_pat_line(pat_yes,pat_no,6), msg)
	&& put_line(line_board,line_status,YOKO,row,   col+2,get_pat_line(pat_yes,pat_no,7),msg)
	&& put_line(line_board,line_status,YOKO,row+1, col+2,get_pat_line(pat_yes,pat_no,8),msg)
	&& put_line(line_board,line_status,TATE,row+2, col+1,get_pat_line(pat_yes,pat_no,9), msg)
	&& put_line(line_board,line_status,TATE,row+2, col,  get_pat_line(pat_yes,pat_no,10), msg)
	&& put_line(line_board,line_status,YOKO,row+1, col,  get_pat_line(pat_yes,pat_no,11),msg)
	)) return FALSE;

  return TRUE;
}

int
put_line(unsigned short *line_board, unsigned short *line_status, unsigned char dir, unsigned char row, unsigned char col,
	      unsigned short line, int msg)
{
  if (debug_level >2) fprintf(stderr, "put_line(%d, %d, %d, %d, %d)\n", dir, row, col, line, msg);
  if ((ID(Line(line_board, dir, row, col)) && line == NO)
      ||(Line(line_board, dir, row, col) == NO && line == YES)) {
    /* 線配置が矛盾してしまった場合は，解なし．処理終了 */
    if (msg)
      fprintf(outfp, "No consistent answer at dir=%d line (%d,%d)\n", dir, row,col);
    return FALSE;
  }
  /* 配置する必要がない */
  if (ID(Line(line_board, dir, row, col))
      || (Line(line_board, dir, row, col) == NO && line == NO)
      || line == UNKNOWN) return TRUE;
  /* 配置する必要がある */
  if (line == YES) {
    unsigned char n_yes_1, n_yes_2;
    unsigned short id1,id2;

    n_yes_1 = 0; n_yes_2 = 0; id1 = 0; id2 = 0;

    if (dir == YOKO) {
      get_intsect_point_yes_info(line_board, row,   col-1, &n_yes_1, &id1);
      get_intsect_point_yes_info(line_board, row,   col,   &n_yes_2, &id2);
    } else if (dir == TATE) {
      get_intsect_point_yes_info(line_board, row-1, col,   &n_yes_1, &id1);
      get_intsect_point_yes_info(line_board, row,   col,   &n_yes_2, &id2);
    } else {
      fprintf(stderr, "Invalid direction.\n");
      exit(1);
    }

    if (n_yes_1 >1 || n_yes_2 >1) {
      /* 線配置が矛盾してしまった場合は，解なし．処理終了 */
      if (msg)
	fprintf(outfp, "No consistent answer at dir=%d line (%d,%d)\n",dir,row,col);
      return FALSE;
    } else if (n_yes_1 == 1 && n_yes_2 == 1) {
      /* 二つのグループを結ぶ */
      if (id1 == id2) {
	if (other_IDs(line_board, id1)) {
	  /* ローカルループができてしまった．解なし．処理終了 */
	  if (msg)
	    fprintf(outfp, "local loop at dir=%d line (%d,%d)\n",dir,row,col);
	  return FALSE;
	} else {
	  /* 大きなループ．解がみつかった */
	  Line(line_board, dir, row, col) = id1;
	  Line(line_status, dir, row, col) = CHANGED;
	}
      } else {
	/* 小さい方にあわせて，異なる ID のグループをつなぐ */
	if (id1 < id2) {
	  Line(line_board, dir, row, col) = id1;
	  Line(line_status, dir, row, col) = CHANGED;
	  change_ID(line_board, id2,id1);
	} else {
	  Line(line_board, dir, row, col) = id2;
	  Line(line_status, dir, row, col) = CHANGED;
	  change_ID(line_board, id1,id2);
	}
      }
    } else if (n_yes_1 == 1) {  /* 左側だけに接続 */
      Line(line_board, dir, row, col) = id1;
      Line(line_status, dir, row, col) = CHANGED;
    } else if (n_yes_2 == 1) { /* 右側だけに接続 */
      Line(line_board, dir, row, col) = id2;
      Line(line_status, dir, row, col) = CHANGED;
    } else {                       /* 単独の線分 */
      Line(line_board, dir, row, col) = get_id();
      Line(line_status, dir, row, col) = CHANGED;
    }
  } else if (line == NO) {
    Line(line_board, dir, row, col) = NO;
    Line(line_status, dir, row, col) = CHANGED;
  }
  /*  else UNKNOWN Nothing */

  return TRUE;
}


void
get_intsect_point_info(unsigned short *line_board, unsigned char row, unsigned char col,
		       unsigned char *n_yes_ptr, unsigned char *n_no_ptr,
		       unsigned short *id_of_yes_ptr,
		       unsigned char *dir_unknown_1_ptr,
		       unsigned char *row_unknown_1_ptr, unsigned char *col_unknown_1_ptr,
		       unsigned char *dir_unknown_2_ptr,
		       unsigned char *row_unknown_2_ptr, unsigned char *col_unknown_2_ptr)
{
  unsigned short line;

  *n_yes_ptr = 0;
  *n_no_ptr  = 0;
  *dir_unknown_1_ptr = NOTDIR;
  *dir_unknown_2_ptr = NOTDIR;

  get_intsect_point_info_1(line_board, TATE,  row,   col,
			   n_yes_ptr, n_no_ptr,
			   id_of_yes_ptr,
			   dir_unknown_1_ptr, row_unknown_1_ptr, col_unknown_1_ptr,
			   dir_unknown_2_ptr, row_unknown_2_ptr, col_unknown_2_ptr);
  get_intsect_point_info_1(line_board, TATE,  row+1,   col,
			   n_yes_ptr, n_no_ptr,
			   id_of_yes_ptr,
			   dir_unknown_1_ptr, row_unknown_1_ptr, col_unknown_1_ptr,
			   dir_unknown_2_ptr, row_unknown_2_ptr, col_unknown_2_ptr);
  get_intsect_point_info_1(line_board, YOKO,  row,   col,
			   n_yes_ptr, n_no_ptr,
			   id_of_yes_ptr,
			   dir_unknown_1_ptr, row_unknown_1_ptr, col_unknown_1_ptr,
			   dir_unknown_2_ptr, row_unknown_2_ptr, col_unknown_2_ptr);
  get_intsect_point_info_1(line_board, YOKO,  row,   col+1,
			   n_yes_ptr, n_no_ptr,
			   id_of_yes_ptr,
			   dir_unknown_1_ptr, row_unknown_1_ptr, col_unknown_1_ptr,
			   dir_unknown_2_ptr, row_unknown_2_ptr, col_unknown_2_ptr);
}


void
get_intsect_point_info_1(unsigned short *line_board,
			 unsigned char dir, unsigned char row, unsigned char col,
			 unsigned char *n_yes_ptr, unsigned char *n_no_ptr,
			 unsigned short *id_of_yes_ptr,
			 unsigned char *dir_unknown_1_ptr,
			 unsigned char *row_unknown_1_ptr, unsigned char *col_unknown_1_ptr,
			 unsigned char *dir_unknown_2_ptr,
			 unsigned char *row_unknown_2_ptr, unsigned char *col_unknown_2_ptr)
{
  unsigned short line;

  line = Line(line_board,dir,row,col);

  if (ID(line)) {
    *id_of_yes_ptr = line;
    (*n_yes_ptr)++;
  } else if (line == NO) {
    (*n_no_ptr)++;
  } else if (line == UNKNOWN) {
    if (*dir_unknown_1_ptr == NOTDIR) {
      *dir_unknown_1_ptr = dir;
      *row_unknown_1_ptr = row;
      *col_unknown_1_ptr = col;
    } else {
      *dir_unknown_2_ptr = dir;
      *row_unknown_2_ptr = row;
      *col_unknown_2_ptr = col;
    }
  }
}

void
get_intsect_point_yes_info(unsigned short *line_board, unsigned char row, unsigned char col,
			   unsigned char *n_yes_ptr, unsigned short *id_of_yes_ptr)
{
  unsigned char n_no = 0;
  unsigned char dir_unknown_1, row_unknown_1, col_unknown_1;
  unsigned char dir_unknown_2, row_unknown_2, col_unknown_2;

  get_intsect_point_info(line_board, row, col,
		         n_yes_ptr, &n_no,
			 id_of_yes_ptr,
			 &dir_unknown_1, &row_unknown_1, &col_unknown_1,
			 &dir_unknown_2, &row_unknown_2, &col_unknown_2);
}



void
change_ID(unsigned short *line_board, unsigned short old, unsigned short new)
{
  int i,j;

  if (debug_level > 2) fprintf(stderr,"change_ID(%d, %d)\n", old, new);
  for (i=0; i<= height; i++) {
    for (j=0; j<= width; j++) {
      if (Line(line_board,YOKO, i, j)==old) Line(line_board,YOKO, i, j) = new;
      if (Line(line_board,TATE, i, j)==old) Line(line_board,TATE, i, j) = new;
    }
  }
}

int
other_IDs(unsigned short *line_board, int id)
{
  int i,j;

  for (i=0; i<= height; i++) {
    for (j=0; j<= width; j++) {
      if (ID(Line(line_board,YOKO,i,j)) && Line(line_board,YOKO,i,j) != id )
	return(TRUE);
      if (ID(Line(line_board,TATE,i,j)) && Line(line_board,TATE,i,j) != id )
	return(TRUE);
    }
  }

  return(FALSE);
}

int
num_rel_lines_changed(struct num_data *ndp, unsigned short *line_status)
{
  unsigned char row,col;

  row = ndp->row;
  col = ndp->col;

  if ( Line(line_status, YOKO, row+1, col  ) == CHANGED
      || Line(line_status, TATE, row+2, col  ) == CHANGED
      || Line(line_status, TATE, row+2, col+1) == CHANGED
      || Line(line_status, YOKO, row+1, col+2) == CHANGED
      || Line(line_status, YOKO, row,   col+2) == CHANGED
      || Line(line_status, TATE, row,   col+1) == CHANGED
      || Line(line_status, TATE, row,   col  ) == CHANGED
      || Line(line_status, YOKO, row,   col  ) == CHANGED
      || Line(line_status, TATE, row+1, col  ) == CHANGED
      || Line(line_status, YOKO, row+1, col+1) == CHANGED
      || Line(line_status, TATE, row+1, col+1) == CHANGED
      || Line(line_status, YOKO, row,   col+1) == CHANGED )
    return(TRUE);
  return(FALSE);
}


int
intsect_point_rel_lines_changed(unsigned short *line_status, unsigned char row, unsigned char col)
{
 if ( Line(line_status, TATE, row,   col  ) == CHANGED
      || Line(line_status, YOKO, row,   col  ) == CHANGED
      || Line(line_status, TATE, row+1, col  ) == CHANGED
      || Line(line_status, YOKO, row,   col+1) == CHANGED )
    return(TRUE);
  return(FALSE);
}

void
delete_invalid_cands(struct num_data *ndp, unsigned short *line_board)
{
  unsigned short line_on_board_yes,line_on_board_no;
  struct cand *cl1, *cl2, root_data, *root;
  int i,valid;

  get_lines_on_board(line_board, ndp->row, ndp->col, &line_on_board_yes, &line_on_board_no);

  if (debug_level>7) {
    fprintf(stderr, "=========================================\n");
    fprintf(stderr, "Number %d (%d,%d)\n", ndp->num, ndp->row, ndp->col);
    fprintf(stderr, "=========================================\n");
    pretty_print_cand(stderr, line_on_board_yes, line_on_board_no);
    fprintf(stderr, "=========================================\n");
  }

  root = &root_data;
  cl2 = root;
  cl1 = root->next = ndp->cand;
  while(cl1 != NULL) {
    if (debug_level>7) 
      pretty_print_cand(stderr, cl1->line, ~(cl1->line));
    if (line_on_board_yes == (line_on_board_yes & cl1->line)
	&& line_on_board_no == (line_on_board_no & ~(cl1->line))) {
      /* 整合性がある候補 */
      if (debug_level>7) fprintf(stderr, "is valid.\n");
      cl2 = cl1;
      cl1 = cl1->next;
    } else {
      /* 整合性がない候補 */
      if (debug_level>7) fprintf(stderr, "is NOT valid.\n");
      cl2->next = cl1->next;
      free(cl1);
      cl1 = cl2->next;
    }
  }
  ndp->cand = root->next;
  if (debug_level>7) {
    fprintf(stderr, "=========================================\n");
  }
}

/*
 *  二つの盤面データの同値性を調べる
 *  違う時に真になる
 */
int
different_line_board(unsigned short *b1, unsigned short *b2)
{
  int i,j;

  for (i=(height+2)*(width+2)*2; i>=0; i--) {
    if (b1[i] != b2[i]) return(TRUE);
  }

  return(FALSE);
}

int
change_line_status(unsigned short *line_status)
{
  int i;

  for (i=(height+2)*(width+2)*2; i>=0 ; i--)
    if (line_status[i] == CHANGED)
      return TRUE;

  return FALSE;
}

/*
 * ローカルループチェック
 */
void
local_loop_check(unsigned short *line_board, unsigned short *line_status_new)
{
  local_loop_check_1(line_board, line_status_new, YOKO);
  local_loop_check_1(line_board, line_status_new, TATE);
}

void
local_loop_check_1(unsigned short *line_board, unsigned short *line_status_new, unsigned char dir)
{
  int row,col;
  unsigned char n_yes_1, n_yes_2;
  unsigned short id1,id2;

  for(row = 0; row<=height; row++) {
    for(col =0; col<=width; col++) {
      if (Line(line_board,dir,row,col) != UNKNOWN) continue;

      n_yes_1 = 0; n_yes_2 = 0; id1 = 0; id2 = 0;

      if (dir == YOKO) {
	get_intsect_point_yes_info(line_board, row, col-1, &n_yes_1, &id1);
	get_intsect_point_yes_info(line_board, row, col,   &n_yes_2, &id2);
      } else if (dir == TATE) {
	get_intsect_point_yes_info(line_board, row-1, col, &n_yes_1, &id1);
	get_intsect_point_yes_info(line_board, row, col,   &n_yes_2, &id2);
      } else {
	fprintf(stderr, "Invalid direction.\n");
	exit(1);
      }
      if (n_yes_1 == 1 && n_yes_1 == 1
	  && id1 == id2
	  && other_IDs(line_board, id1)) {
	/* 二つのグループを結ぶと，ローカルループができる配置である． */
	/* そこを x にする */
	put_line(line_board,line_status_new,dir,row,col,NO,FALSE);
      }
    }
  }
}

int
intsect_point_check(unsigned short *line_board, unsigned short *line_status, unsigned short *line_status_new, unsigned char *num_board, int msg)
{
  unsigned char row,col, n_yes, n_no;
  unsigned short id;
  unsigned char dir_unknown_1, row_unknown_1, col_unknown_1;
  unsigned char dir_unknown_2, row_unknown_2, col_unknown_2;

  for (row=0; row<= height; row++) {
    for (col=0; col<= width; col++) {
      if (! intsect_point_rel_lines_changed(line_status, row, col)) continue;
      get_intsect_point_info(line_board, row, col,
			     &n_yes, &n_no, &id,
			     &dir_unknown_1, &row_unknown_1, &col_unknown_1,
			     &dir_unknown_2, &row_unknown_2, &col_unknown_2);
      if (n_no == 3) {
	if (n_yes == 1) {
	  /* 袋小路に線が入るのは矛盾 */
	  if (msg)
	    fprintf(outfp, "No consistent answer at point (%d,%d)\n", row,col);
	  return FALSE;
	}
	/* 3方向とも x ならば もう一つのUNKNOWNも x */
	if (debug_level > 4) {
	  fprintf(stderr, "mark no\n");
	  fprintf(stderr, "n_yes = %d, n_no = %d (%d,%d)\n", n_yes, n_no, row, col);
	  pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
	}
	if (!put_line(line_board, line_status_new, dir_unknown_1, row_unknown_1, col_unknown_1, NO, msg))
	  return FALSE;
      }
      if (n_no == 2 && n_yes == 1) {
	/* 2方向 x で一方向 o ならば もう一つのUNKNOWNは o */
	if (debug_level > 4) {
	  fprintf(stderr, "mark yes\n");
	  fprintf(stderr, "n_yes = %d, n_no = %d (%d,%d)\n", n_yes, n_no, row, col);
	  pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
	}
	if (!put_line(line_board, line_status_new, dir_unknown_1, row_unknown_1, col_unknown_1, YES, msg))
	  return FALSE;
      }
      if (n_yes == 2 && n_no != 2) {
	/* 2方向 o ならば，残りのUNKNOWNは x */
	if (debug_level > 4) {
	  fprintf(stderr, "mark no\n");
	  fprintf(stderr, "n_yes = %d, n_no = %d (%d,%d)\n", n_yes, n_no, row, col);
	  pretty_print_board(stderr, line_board, num_board, FALSE, TRUE, FALSE);
	}
	if (dir_unknown_1 != NOTDIR)
	  if (!put_line(line_board, line_status_new, dir_unknown_1, row_unknown_1, col_unknown_1, NO, msg))
	    return FALSE;
	if (dir_unknown_2 != NOTDIR)
	  if (!put_line(line_board, line_status_new, dir_unknown_2, row_unknown_2, col_unknown_2, NO, msg))
	    return FALSE;
      }
    }
  }

  return TRUE;
}


/*
 * 解を清書する．
 */
void
pretty_print_board(FILE *fp, unsigned short *line_board, unsigned char *num_board, int id, int aste, int prog_readable_mode)
{
  int i,j;

  for (i=0; i<height; i++) {
    fprintf(fp,"+");
    for (j=0; j<width; j++) {
      print_yoko_line(fp,Line(line_board,YOKO, i,j+1),id,aste);
      fprintf(fp, "+");
    }
    fprintf(fp,"\n");
    for (j=0; j<width; j++) {
      print_tate_line(fp,Line(line_board,TATE, i+1,j),id,aste);
      if (Num(num_board,i,j) != NOTNUM) 
	fprintf(fp, " %d ", Num(num_board,i,j));
      else
	if (prog_readable_mode)
	  fprintf(fp, " . ");
	else
	  fprintf(fp, "   ");
    }
    print_tate_line(fp,Line(line_board,TATE,i+1,j),id,aste);
    fprintf(fp,"\n");
  }
  fprintf(fp,"+");
  for (j=0; j<width; j++) {
    print_yoko_line(fp,Line(line_board,YOKO,i,j+1),id,aste);
    fprintf(fp, "+");
  }
  fprintf(fp,"\n");
}

void
print_yoko_line(FILE *fp, unsigned short yoko, int id, int aste)
{
  switch (yoko) {
  case YES:
    fprintf(fp, "---");
    break;
  case NO:
    fprintf(fp, "   ");
    break;
  case UNKNOWN:
    if (aste)
      fprintf(fp, " * ");
    else
      fprintf(fp, "   ");
    break;
  default:
    if (ID(yoko)) {
      if (id)
	fprintf(fp, " %c ", yoko-IDORG+'a');
      else
	fprintf(fp, "---");
    } else {
      fprintf(stderr, "%s: Unknown symbol number %d in put_yoko_line.\n",
	      progname, yoko);
      exit(1);
    }
  }

}


void
print_tate_line(FILE *fp, unsigned short tate, int id, int aste)
{
  switch (tate) {
  case YES:
    fprintf(fp, "|");
    break;
  case NO:
    fprintf(fp, " ");
    break;
  case UNKNOWN:
    if (aste)
      fprintf(fp, "*");
    else
      fprintf(fp, " ");
    break;
  default:
    if (ID(tate)) {
      if (id)
	fprintf(fp, "%c", tate-IDORG+'a');
      else
	fprintf(fp, "|");
    } else {
      fprintf(stderr, "%s: Unknown symbol number %d in put_tate_line.\n",
	      progname, tate);
      exit(1);
    }
  }
}


void
print_line(FILE *fp, unsigned char dir, unsigned short line, int id, int aste)
{
  switch (dir) {
  case TATE:
    print_tate_line(fp, line, id, aste);
    break;
  case YOKO:
    print_yoko_line(fp, line, id, aste);
    break;
  default:
    fprintf(stderr, "Undefined direction %d\n", dir);
    exit(1);
  }
}

unsigned short
get_pat_line(unsigned short line_yes, unsigned short line_no, unsigned char n)
{
  if (GetBit(line_yes,n) && GetBit(line_no,n)) {
    fprintf(stderr, "Inconsistent bit pattern %d and %d\n", line_yes, line_no);
    exit(1);
  }

  if (GetBit(line_yes,n))
    return(YES);
  else if (GetBit(line_no,n))
    return(NO);
  else
    return(UNKNOWN);
}

void
pretty_print_cand(FILE *fp, unsigned short line_yes, unsigned short line_no)
{
  fprintf(fp, "    +   +    \n");
  fprintf(fp, "    ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,6-1), FALSE, TRUE);
  fprintf(fp, "   ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,7-1), FALSE, TRUE);
  fprintf(fp, "    ");

  fprintf(fp, "\n");

  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,5-1), FALSE, TRUE);
  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,1-1), FALSE, TRUE);
  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,8-1), FALSE, TRUE);
  fprintf(fp, "+");

  fprintf(fp, "\n");

  fprintf(fp, "    ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,4-1), FALSE, TRUE);
  fprintf(fp, "   ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,2-1), FALSE, TRUE);
  fprintf(fp, "    ");

  fprintf(fp, "\n");

  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,12-1), FALSE, TRUE);
  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,3-1), FALSE, TRUE);
  fprintf(fp, "+");
  print_line(fp, YOKO, get_pat_line(line_yes,line_no,9-1), FALSE, TRUE);
  fprintf(fp, "+");

  fprintf(fp, "\n");

  fprintf(fp, "    ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,11-1), FALSE, TRUE);
  fprintf(fp, "   ");
  print_line(fp, TATE, get_pat_line(line_yes,line_no,10-1), FALSE, TRUE);
  fprintf(fp, "    ");

  fprintf(fp, "\n");

  fprintf(fp, "    +   +    \n");
}

void
pretty_print_all_cand(FILE *fp, struct cand *cand)
{
  for(; cand != NULL; cand=cand->next) {
    fprintf(fp, "\n");
    pretty_print_cand(fp, cand->line, ~(cand->line));
    fprintf(fp, "\n");
  }
}

/* 使い方を表示する */
void
usage(void)
{
  char *rev = "$Revision: 2.6 $";
  char *ver;

  if ((ver = malloc((unsigned)strlen(rev)-9)) 
      == NULL) {
    fprintf(stderr, "malloc error in usage().\n");
    exit(1);
  }
  sscanf(&(rev[1]), "Revision: %s", ver);
  fprintf(stderr, "「スリザーリンク」解法プログラム Ver. %s\n",ver);
  fprintf(stderr, "     Copyright (c) 1996  by T.Mori\n\n");
  fprintf(stderr, "【使い方】\n");
  fprintf(stderr,
	  "%s [-a] [-d ...] [-r] [-p] [-o 出力ファイル名] [-v] [データファイル名]\n\n",
	  progname);
  fprintf(stderr,
	  "      -a                 : 全解探索 (off)\n");
  fprintf(stderr,
	  "      -c                 : バックトラックサーチの前に解の枝刈 (off)\n");
  fprintf(stderr,
	  "                           大きな問題の場合に時間が短縮されることがある\n");
  fprintf(stderr,
	  "      -d                 : 途中結果も表示するデバッグモード (off)\n");
  fprintf(stderr,
	  "                         :   -d の数でデバッグレベルがかわる\n");
  fprintf(stderr,
	  "      -r                 : プログラム可読出力 (off)\n");
  fprintf(stderr,
	  "      -p                 : 問題清書．解を求めない (off)\n");
  fprintf(stderr,
	  "      -o 出力ファイル名  : 出力ファイルの名前 (標準出力)\n");
  fprintf(stderr,
	  "      -v                 : バージョンの表示\n");
  fprintf(stderr,
	  "      データファイル名   : データファイルの名前 (標準入力)\n");
  fprintf(stderr,
	  "                                  (括弧内は省略時の値)\n");
}

/******************************************************************************

	プログラム記述終了

 ******************************************************************************/
