/*
2001/08 リング平方数
coded by Isaku WADA
 ┌────────────────────┐
 │Fig.5のように,1〜15の15個の数│
 │を環状に並べた。すると,隣り合っ    │
 │た2数の和がすべて平方数(ある数の   │
 │二乗になっている数)になった……。   │
 │と思ってよく見たら,1ヵ所平方数    │
 │になっていない(8+9=17)。では, │
 │「1〜NのN個の数を全て1個ずつ使   │
 │って環状に並べ,隣り合う2数の和    │
 │がすべて平方数になる」ものができ    │
 │るのは,Nがいくつのときか。最小    │
 │のNを求めよ。また,そのNでの並    │
 │べ方は,回転・鏡像を除いて何通     │
 │りあるか。               │
 └────────────────────┘

 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │プログラムは結果を記録するための配列x[]を持ちます。回転を削 │
 │除するためにx[0]は1に固定します。             │
 │                              │
 │高速化のため平方数かどうかを判定する配列Square[]も持ちます。│
 │                              │
 │さらに、1〜Nの数字が解の配列に使われたかどうかを記録する配│
 │列flags[]も持ちます。                    │
 │                              │
 │探索は、再帰呼び出しをする関数Sub(n,k)で行います。引数nは、 │
 │リングの大きさNです。引数kは再帰呼び出しの深さです。これは │
 │今まで置いてきた数字の個数でもあります。          │
 │                              │
 │Sub(n,k)は、まだ、N個置き終わっていない場合は、まだ使われて│
 │おらず、かつ、前の数との和が平方数になる数字を探します。見つ│
 │かれば、flags[]に印をつけ、結果の配列x[]に記録し、kを増やし │
 │て再帰呼び出しします。                   │
 │                              │
 │n個置けた場合は、まず、x[n-1]<x[1]かどうかを確かめます。こ │
 │の条件により鏡像を消すことができます。そして、x[0]+x[n-1]が │
 │平方数かどうか確認します。以上の条件を満たしていれば、x[]を │
 │出力してリターンします。                  │
 │                              │
 │プログラムは配列Square[]を作成した後、nを3から、解が見つかる│
 │まで、ひとつずつ大きくしながらSub(n,0)を実行します。    │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │再帰呼び出しを使って、できるだけ単純なソースになるように心が│
 │けました。もっと高速にするための工夫を考えようとしましたが、│
 │思い浮かびませんでした。他の人がどのようなアルゴリズムを考え│
 │るか今から楽しみです。                   │
 └──────────────────────────────┘
 Visual C++,Borland C++,LSI C,Turbo C,gcc で動作確認
*/

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

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#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) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────┐
 │変数・定数の宣言│
 └────────┘*/
#define MAX 39     /* 調べるNの最大値              */
int Square[MAX*2]; /* 平方数かどうかを判定する      */
int Count;         /* 何通りあったか                */
int flags[MAX+1];  /* 既に使用した数なら 1          */
int x[MAX]={1};    /* 結果(先頭を1にして回転を消す) */

/*┌─────────────────┐
 │再帰呼び出しをしながらパズルを解く│
 └─────────────────┘*/
void Sub(int n,int k)
{
    int i;

    if (k==n-1)                /* n 個置けた場合               */
     if (x[1]<x[n-1])          /* この条件により、鏡像を消す   */
      if (Square[1+x[n-1]]) {  /* 最初と最後の和が平方数の場合 */
          printf("(N=%d : %d 通り目)",n,++Count); /* 解の表示  */
          for (i=0;i<n;i++) printf("%3d",x[i]);
          printf("\n"); return;
      }
    for (i=2;i<=n;i++)
     if (flags[i]==0&&Square[x[k]+i]) /* 未使用で平方数の場合 */
     { x[k+1]=i; flags[i]=1; Sub(n,k+1); flags[i]=0; }
}

int main(void)
{
    double StartTime=clock(); int n;

    for (n=0;n*n<MAX*2;n++) Square[n*n]=1;
    for (n=3;n<=MAX&&Count==0;n++) Sub(n,0);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}