//****************************************************************
// 最短手数が最長となる問題図の探索
//****************************************************************
#include <stdio.h>
#include <stdlib.h>

#define  FALSE    0 // CELL不足
#define  TRUE     1 // 正常終了

// ソルバー
#include "hako10solver.c"

int  BOX[20];
int  MaxSteps;
int  FILE_CODE;

//****************************************************************
// ファイル保存
//****************************************************************
void Save()
{
    int  i;
    char fn[200];
    FILE* fp;

    sprintf_s(fn, 200, "FILE%d.txt", FILE_CODE);
    fopen_s(&fp, fn, "at");

    fprintf(fp, "%d steps.\n", MaxSteps);
    for (i = 0; i < 20; i++) {
        fprintf(fp, "%3d", BOX[i]);
        if (i % 4 == 3) fprintf(fp, "\n");
    }

    fclose(fp);
}
//****************************************************************
// 盤面表示
//****************************************************************
void Display(void)
{
    int  i;

    for (i = 0; i < 20; i++) {
        printf("%3d", BOX[i]);
        if (i % 4 == 3) printf("\n");
    }
}
//****************************************************************
// 盤面生成と最長手数の探索
//****************************************************************
int  Backtrack(int start, int count)
{
    int  i, retc;

    // 探索と結果表示
    if (count > 18) return TRUE;
    if (count == 18) {
        retc = Solve(Rule1, Rule2, BOX);
        if (retc == FALSE) return FALSE;    // CEll不足
        if (retc == SOLVED) {
            if (MinSteps >= MaxSteps) {
                MaxSteps = MinSteps;
                // 結果の表示
                printf("%d ", MaxSteps);
                Save(); // ファイル保存
            }
        }
        return TRUE;
    }

    // 盤面生成(横長ピース)
    for (i = start; i < 20; i++) {
        if (i % 4 == 3) continue;
        if (BOX[i] || BOX[i + 1]) continue;
        BOX[i] = 30;
        BOX[i + 1] = 31;
        Backtrack(i + 2, count + 2);    // 再帰呼び出し
        BOX[i] = 0;
        BOX[i + 1] = 0;
    }

    // 盤面生成(縦長ピース)
    for (i = start; i < 16; i++) {
        if (BOX[i] || BOX[i + 4]) continue;
        BOX[i] = 20;
        BOX[i + 4] = 21;
        Backtrack(i + 1, count + 2);    // 再帰呼び出し
        BOX[i] = 0;
        BOX[i + 4] = 0;
    }

    // 盤面生成(小ピース)
    for (i = start; i < 20; i++) {
        if (BOX[i]) continue;
        BOX[i] = 10;
        Backtrack(i + 1, count + 1);    // 再帰呼び出し
        BOX[i] = 0;
    }
    return TRUE;
}
//****************************************************************
// エントリーポイント
//****************************************************************
int main(void)
{
    int  i, retc;

    // メモリー確保
    if (!MemAlloc()) {
        printf("Out of memory.");
        return 0;
    }

    // 初期化
    for (i = 0; i < 20; i++) BOX[i] = 0;
    FILE_CODE = 0;

    // ルール定義
    Rule1 = 1;  // 連続移動を1手とするか? (Yes:一般的ルール)
    Rule2 = 0;  // 他のピースを押せるか?  (No :一般的ルール)

    // 娘(2×2)の位置
    for (i = 0; i < 13; i++) {
        if (i % 4 > 1) continue;    // 左右反転禁止

        FILE_CODE++;
        MaxSteps = 0;

        BOX[i] = 40;
        BOX[i + 1] = 41;
        BOX[i + 4] = 42;
        BOX[i + 5] = 43;
        printf("\n");
        Display();
        retc = Backtrack(0, 4); // 盤面生成と最短手数の調査
        if (retc == FALSE) {
            printf("Cell不足\n");
            break;
        }
        BOX[i] = 0;
        BOX[i + 1] = 0;
        BOX[i + 4] = 0;
        BOX[i + 5] = 0;
    }

    // メモリー解放
    MemFree();

    return 0;
}