/*
2000/09 オールナイトパズル
coded by Isaku WADA
 ┌──────────────────────────────┐
 │チェスのナイト(騎士)は,将棋の桂馬と違って8方向に跳べる。 │
 │ このナイトを8×8のチェス盤に以下のふたつの条件で置く。   │
 │                              │
 │1)すべての空所がどれかのナイトの効き筋(跳べるところ)にな │
 │  っていること。2個以上のナイトから効いていてもかまわない │
 │2)ナイト同士は互いに効き筋にいない             │
 │                              │
 │ これをできるだけ少ない数のナイトで実現したい,      │
 │ 何個のナイトが必要だろうか。               │
 │ そのとき,全体を回転したものや鏡像のものは別の解はしないと│
 │ すると,何通りの置き方があるか。配置図を添えてお答えいただ│
 │ きたい。                         │
 └──────────────────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ データ構造は8×8の1次元配列(マップ)で表現します。壁は│
 │使いません。その代わりに、全ての位置について、跳べる場所の│
 │数と位置を、あらかじめ配列に格納します。配列を使うことによ│
 │り、少し速くなります。                  │
 │                             │
 │ 探索は、再帰呼び出しをしながら、ひとつずつナイトを小さい│
 │位置から順に置いてゆきます。小さい位置に空白がある場合、次│
 │に置くナイトの配置に上限を設けることができます。なぜなら、│
 │仮に、その上限を超えてナイトを置くと、さらに次以降のナイト│
 │は必ず、前のナイトよりも大きな位置に置かれるので、空白を埋│
 │めることが不可能になるからです。上限を設けることにより、飛│
 │躍的に高速になります。さらに処理を高速化するために、あらか│
 │じめ、この上限を空白の位置に対応付けて、配列に格納します。│
 │                             │
 │ 探索中に空白の数が0になれば、その時のマップを、解の候補│
 │とします。そして、過去の解の回転と鏡像をチェックします。も│
 │し、新しいものであればリストに登録します。        │
 │                             │
 │ 探索を始めるときに、ナイトは8×8=64人まで置けると仮│
 │定します(これを最大人数と呼びます)。そして、最大人数よりも│
 │小さな解が見つかるたびに最大人数を小さいものに更新します。│
 │同時に古い解はリストから削除します。探索中に、最大人数と配│
 │置した人数の差(つまり、残り人数)に9をかけたものよりも、空│
 │白の数が多い場合は探索を打ち切ります。この打ち切りにより、│
 │少し高速になります。                   │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・感想                          │
 │                             │
 │ 空白に対応した上限を設ける前は、実行時間が4時間を越えて│
 │いました。たった1つの工夫で約4千倍も速くなり驚きました。│
 │また、回転と鏡像をできるだけシンプルに排除するのに苦労しま│
 │した。今回のプログラムも移植性にこだわって作成しました。 │
 └─────────────────────────────┘
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SX 8 /* チェス盤の横方向の大きさ */
#define SY 8 /* チェス盤の縦方向の大きさ */
#define IS_KNIGHT  9 /* ナイトがいる場合 Map[] が取る値 */

/* clock() をサポートしない MS-DOS コンパイラ用の clock()
LSI C-86 試食版でも 1/1000 秒単位の経過時間を返すようになる
Visual C++、Borland C++ Builder、UNIX 等では自動的に無視される
最初は0を返し、2回目以降は最初からの経過時間を返す */
#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};
    static long Date0,Time0; long Time1,Date1; union REGS t,d;
    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*365L+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; /* 24日以上経過すると-1を返す */
    return(Date1-Date0)*86400000L+Time1-Time0;
}
#endif

typedef unsigned char uchar;
typedef struct list { char map[SX*SY]; struct list*next; } list;
int   MaxKnight=SX*SY;     /* ナイトの最大人数 */
char  NumOfSite[SX*SY];    /* 移動できる場所の数 */
uchar SiteTable[SX*SY][8]; /* 移動できる場所の絶対位置 */
uchar ForLimit[SX*SY];     /* for ループの枝刈り用の上限 */
list *ListHead;            /* 解のリストへのポインタ */

/*┌───────────────────┐
 │盤の各位置から移動できる場所を計算する│
 └───────────────────┘*/
void InitSiteTable(void)
{
    static short RelativeX[8]={1,2,-1,-2, 2, 1,-2,-1};
    static short RelativeY[8]={2,1, 2, 1,-1,-2,-1,-2};
    int x,y,NewX,NewY,n,i,j;

    for (i=y=0;y<SY;y++) for (x=0;x<SX;x++,i++) {
        for (n=j=0;j<8;j++) {
            NewX=x+RelativeX[j]; NewY=y+RelativeY[j];
            if (NewX<0||NewX>=SX||NewY<0||NewY>=SY) continue;
            SiteTable[i][n++]=(uchar)(NewY*SX+NewX);
        }
        NumOfSite[i]=(char)n;
    }
}

/*┌──────────────────┐
 │for ループの枝刈り用の上限を計算する│
 └──────────────────┘*/
void InitForLimit(void)
{
    int x,y,i;

    for (i=y=0;y<SY;y++) for (x=0;x<SX;x++,i++)
        if (y==SY-1)      ForLimit[i]=(uchar)i;
        else if (y==SY-2)
             if (x>SX-3)  ForLimit[i]=(uchar)(i+SX-2);
             else         ForLimit[i]=(uchar)(i+SX+2);
        else if (x==SX-1) ForLimit[i]=(uchar)(i+2*SX-1);
             else         ForLimit[i]=(uchar)(i+2*SX+1);
}

/*┌─────────────┐
 │回転や鏡像があれば1を返す│
 └─────────────┘*/
int CheckMap(char*Map,int a,int b,int c,int d)
{
    list*p; int x,y,i;

    for (p=ListHead;p;p=p->next)
    {
        for (i=x=y=0;i<SX*SY;i++)
         if (p->map[x*a+(SX-1-x)*b+y*c+(SY-1-y)*d]!=Map[i]) break;
         else if (++x==SX) { x=0; y++; } 
        if (i==SX*SY) return 1;
    }
    return 0;
}

/*┌─────────────────┐
 │回転と鏡像を排除し、Map を記録する│
 └─────────────────┘*/
void AppendMap(char*Map,int NumOfKnight)
{
    list*p,*q; int i;

    if (NumOfKnight==MaxKnight) {
        if (CheckMap(Map,0,1,0,SX)) return; /*回転180*/
        if (CheckMap(Map,0,1,SX,0)) return; /*鏡像0*/
        if (CheckMap(Map,1,0,0,SX)) return; /*鏡像180*/
#if SX == SY
        if (CheckMap(Map,SX,0,0,1)) return; /*回転90*/
        if (CheckMap(Map,0,SX,1,0)) return; /*回転270*/
        if (CheckMap(Map,0,SX,0,1)) return; /*鏡像90*/
        if (CheckMap(Map,SX,0,1,0)) return; /*鏡像270*/
#endif
    } else { /* 古い解の削除 */
        for (p=ListHead;p;) { q=p->next; free(p); p=q; }
        ListHead=0; MaxKnight=NumOfKnight;
    }
    p=(list*)malloc(sizeof(list));
    if (p==0) { printf("malloc()が失敗しました\n"); exit(1); }
    for (i=0;i<SX*SY;i++) p->map[i]=Map[i];
    p->next=ListHead; ListHead=p;
}

/*┌──────────────────────────────┐
 │ナイトを Map に置く。再帰呼び出しにより複数置くことができる │
 └──────────────────────────────┘*/
void sub(void)
{
    static char Map[SX*SY];       /* チェス盤の状態 */
    static int  StartPos;         /* ナイトを置ける一番若い位置 */
    static int  NumOfKnight;      /* ナイト数の累計 */
    static int  NumOfSpace=SX*SY; /* 空白の数 */
    int pos,limit,i;

    if (NumOfSpace==0) { AppendMap(Map,NumOfKnight); return; }
    for (i=0;;i++) if (Map[i]==0) break;
    limit=ForLimit[i];
    for (pos=StartPos;pos<=limit;pos++)
     if (Map[pos]==0) {
         for (i=NumOfSite[pos]-1;i>=0;i--) {
             int index=SiteTable[pos][i];
             if (Map[index]==0) NumOfSpace--;
             Map[index]++; /* 効いている場所の Map を増やす */
         }
         NumOfSpace--; NumOfKnight++;
         if ((MaxKnight-NumOfKnight)*9>=NumOfSpace) {
             Map[pos]=IS_KNIGHT; StartPos=pos+1;
             sub(); Map[pos]=0;
         }
         NumOfKnight--; NumOfSpace++;
         for (i=NumOfSite[pos]-1;i>=0;i--) {
             int index=SiteTable[pos][i];
             Map[index]--; /* 効いている場所の Map を戻す */
             if (Map[index]==0) NumOfSpace++;
         }
     }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    double StartTime=clock(); list*p; int count=0,i,x;

    InitSiteTable(); InitForLimit(); sub();
    for (p=ListHead;p;p=p->next) { /* 解の表示 */
        for (x=i=0;i<SX*SY;i++) {
            printf("%.2s","012345678●"+p->map[i]*2);
            if (++x==SX) { printf("\n"); x=0; }
        }
        printf("\n"); count++;
    }
    printf("ナイトの人数=%d   解の数=%d  ",MaxKnight,count);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
}