/*
2000/01 クロススクエアドナンバーパズル
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ 普通のクロスワードパズルでは,白マスに文字を入れて,タテ│
 │およびヨコに 2マス以上連続してできた単語が意味のあるものに│
 │なっていなければならない。このクロススクエアドナンバーパズ│
 │ルではちょっと違って,各マスには数字を入れる。そして,タテ│
 │およびヨコに並んだ 2桁以上の数を見ると,すべて相異なる平方│
 │数(ある整数を2乗した数)になっていなければならないのだ。 │
 │Fig. 1 の白マスをすべて埋めて完成してほしい。なお,各平方 │
 │数の最上位の数字には 0(ゼロ)は使えない。また,タテの数は│
 │上から下へ,ヨコの数は左から右へ読むことはいうまでもない。│
 │                             │
 │ Fig.1 クロススクエアド □□□□■□          │
 │     ナンバーパズル  □□■□□□          │
 │              □□□□□■          │
 │              ■□□□□□          │
 │              □□□■□□          │
 │              □■□□□□          │
 └─────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIMIT 9 /* long 型が扱える10進数での最大桁数 */
#define SIZEX 6
#define SIZEY 6

char Map[SIZEY+2][SIZEX+3]=
{ "++++++++",
  "+    + +",
  "+  +   +",
  "+     ++",
  "++     +",
  "+   +  +",
  "+ +    +",
  "++++++++" };

/*
 * clock()
 *
 * clock() をサポートしない MS-DOS コンパイラ用の自前の clock()
 * LSI C-86 試食版でも 1/1000 秒単位の経過時間を返すようになる
 * Visual C++、Borland C++ Builder、UNIX などでは自動的に無視される
 *
 * 最初に clock() を呼び出すと必ず0を返す。
 * 2回目以降は、最初の呼び出しからの経過時間を 1/1000 秒単位で返す
 * 経過時間が24日以上になると−1を返す
 * 閏年も考慮に入れている
 */
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif

#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void)
{
    static int day[12]={0,31,59,90,120,151,181,212,243,273,304,334};
    union REGS t,d; static long Date0=0,Time0=0; long Time1,Date1;

    t.h.ah=0x2c; d.h.ah=0x2a;
    intdos(&t,&t); intdos(&d,&d);
    Time1=t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
    Date1=d.x.cx*365+d.x.cx/4+day[d.h.dh-1]+d.h.dl;
    if ((d.x.cx%4)==0&&d.h.dh<=2) Date1--;
    if (Date0==0)  { Date0=Date1; Time0=Time1; return 0; }
    if (Date1-Date0>=24) return-1;
    return(Date1-Date0)*86400000L+Time1-Time0;
}
#endif

/*┌──────────────────────┐
 │長さが2以上の連続する空白を表す word 構造体│
 └──────────────────────┘*/
typedef struct word
{
    char*ptr[LIMIT];    /* Map[][]上での位置を示すポインタの配列 */
    char backup[LIMIT]; /* 割り当てる以前の Map[][]の状態 */
    char size;          /* ワードの長さ(桁数) */
    struct word*next;   /* リストの次の要素 */
} word;

/*┌──────────────────────┐
 │平方数を文字列化したものを表す square 構造体│
 └──────────────────────┘*/
typedef struct square
{
    char text[LIMIT+1]; /* 平方数を文字列化したもの */
    char used;          /* 使用中なら1、未使用なら0 */
    struct square*next; /* リストの次の要素 */
} square;

word*WordList;           /* 全てのワードを記録するリスト */
square*SqrList[LIMIT+1]; /* 桁数毎の平方数を記録するリスト */
int MaxDigit;            /* 出現したワードの最大桁数 */

/*┌──────────────────────────────┐
 │Map[y][x] から始まるワードを探し、あれば WordList に登録する│
 │横のワードは AddWord(x,y,1,0), 縦のワードは AddWord(x,y,0,1)│
 └──────────────────────────────┘*/
void AddWord(int x,int y,int dx,int dy)
{
   int k; word*p;
   if (Map[y][x]==' '&&Map[y-dy][x-dx]!=' '&&Map[y+dy][x+dx]==' ') {
       for (k=2;Map[y+dy*k][x+dx*k]==' ';k++) ;
       if (k>LIMIT) { printf("長すぎるワードがある\n"); exit(1); }
       if (k>MaxDigit) MaxDigit=k;
       p=(word*)malloc(sizeof(word)); p->size=(char)k;
       for (k=0;k<p->size;k++) p->ptr[k]=&Map[y+dy*k][x+dx*k];
       p->next=WordList; WordList=p;
   }
}

/*┌───────────────────────┐
 │MaxDigit 桁までの平方数を桁数別に全て登録する │
 └───────────────────────┘*/
void MakeSquareList(void)
{
    int k=0; long i,n=1; square*q;
    for (i=0;;i++) {
        if (i*i>=n) if (k==MaxDigit) return; else { k++; n*=10; }
        q=(square*)malloc(sizeof(square)); q->next=SqrList[k];
        SqrList[k]=q; q->used=0; sprintf(q->text,"%ld",i*i);
    }
}

/*┌─────────────────────────┐
 │再帰呼び出しをしながら、ワードに平方数を割り当てる│
 └─────────────────────────┘*/
void SolvePuzzle(word*p)
{
    int i,j,k; square*q;
    if (p==0) { /* 全てのワードを割り当てられたので解を表示 */
        for (i=0;i<SIZEY+2;i++) {
            for (j=0;j<SIZEX+2;j++)
             if (Map[i][j]==' ') printf("  ");
             else if (Map[i][j]=='+') printf("■");
             else printf("%.2s","0123456789"
                         +(Map[i][j]-'0')*2);
            printf("\n");
        }
        return;
    }
    for (q=SqrList[k=p->size];q;q=q->next) if (q->used==0) {
        for (i=0;i<k;i++) /* 割り当てが可能かどうか調べる */
            if (*p->ptr[i]!=' '&&*p->ptr[i]!=q->text[i]) break;
        if (i==k) { /* 割り当てが可能な場合の処理 */
            for (i=0;i<k;i++)
            { p->backup[i]=*p->ptr[i]; *p->ptr[i]=q->text[i]; }
            q->used=1; SolvePuzzle(p->next); q->used=0;
            for (i=0;i<k;i++) *p->ptr[i]=p->backup[i];
        }
    }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    int x,y; clock_t StartTime=clock();
    for (x=1;x<=SIZEX;x++) for (y=1;y<=SIZEY;y++)
    { AddWord(x,y,1,0); AddWord(x,y,0,1); }
    MakeSquareList(); SolvePuzzle(WordList);
    printf("time=%f\n",(clock()-StartTime)/(double)CLOCKS_PER_SEC);
}