CでDevquiz２０１１スライドパズル その３

スライドパズルに関するアルゴリズムのサマリー

ソースさらし祭り(?)に参加されている人の解説などを含め今回調べたアルゴリズムを整理したページです。

広く浅く、全体を俯瞰できるようにすることを目標に書いてみます。

 ☆問題の定式化

駒数をKとすると可能な盤面はK！個あり、それらを要素とする集合Sを考える。

Sの各要素は駒を一回移動することで遷移できる要素と繋がっていると考えることで無向グラフとみなすことができる。

与えられた問題面ノードからゴールノードまでの経路探索問題と解釈できる。
なお、Kが３６の場合K!は３．７×１０^３６となり、無限の要素を持つと思って考えていい。

今後、n,g,h,h'を以下の意味で使う。

n：与えられた盤面

g(n)：スタートの盤面からnまでの駒の移動回数

h(n)：nからゴールまでの最短経路の駒の移動回数

h'(n)：h(n)の推定値。（マンハッタンディスタンスなどを利用したnからゴールまでの駒の移動回数の推定値）

 ☆経路探索アルゴリズム：幅探優先探索

駒の移動回数の小さい順に探索していくアルゴリズム。

見つかったノードをキューに入れていく形で実装。

過去の盤面をメモリーに保存するため、メモリーサイズで探索できるノード数が限られる。

http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 ☆経路探索アルゴリズム：深さ優先探索

ノードが途切れるか、ゴールに到達するまで深く探索していき、その後はバックトラック。

スライドパズルのような開いた木の最適解を求めるためには下記のIDDFSやIDA*のような手法を使う。

過去の盤面を保存しないのでメモリー消費は小さい。


http://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 ☆経路探索アルゴリズム：IDA*

深さ優先探索で以下の閾値を設けて探索を行う。

 g(n) + h'(n) <Threshold

ある閾値でゴールが見つからなかった場合は、閾値を徐々に増大させながら探索を繰り返す。

ここでh'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)


この閾値の評価を単に

  g(n) < Threshold

としたものは反復深化深さ優先探索(IDDFS)と呼ばれる。

木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。（深さNに応じてx＾Nでノード数は増大するため、たとえばx=2の場合、高々2倍の演算量にしかならない）


http://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 ☆経路探索アルゴリズム：A*

幅優先のキューをプライオリティキューにして、もっとも推定コストの小さいノードを優先して探索しているアルゴリズム。

推定コストとは

f(n) = g(n) + h'(n)

ここでIDA*同様h'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)

幅優先探索の拡張であるのでメモリが探索深度に応じ指数関数的に消費されていくため、ある程度以上の深度まで探索しようとすると、使われないノードを一旦破棄し必要に応じて再利用（SMA*）が必要になる。

http://ja.wikipedia.org/wiki/A*

 ☆評価関数h'(n)

高得点を得ていたアルゴリズムはほぼA*かIDA*を利用したものだったが、これらのアルゴリズムでは評価関数h'(n)の精度が重要になる。
h'(n)がh(n)に近ければ近いほど演算量は小さくなるので、いかにh(n)に近い関数を見つけるかがとても重要！

以下で説明するようにいくつかの手法が考案されており、これらを組み合わせて使う（もっとも値の大きいh'(n)の値を利用する）こともできる。

 ☆マンハッタンディスタンス（MD)

個々の駒に関してゴール位置への移動回数を計算したもの。

http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2

パターンデータベース（PDB）

前もって特定のパターンとそのパターンのh(n)を計算しておき、それをハッシュ化して保存しておきh'(n)の計算に利用する手法。


http://www.ise.bgu.ac.il/faculty/felner/research/jairpdb.pdf

 ☆ギャップ集合

MDを利用したh'(n)とh(n)とのギャップがいくつであるかに応じたデータベースをあらかじめ作っておく。
探索時にそのDBを参照し、ギャップに応じてMDに値を加算する。


http://www.jstage.jst.go.jp/article/tjsai/26/2/419/_pdf/-char/ja/

 ☆転倒距離

駒の並びを順列と考え、小さい順に並んでいない駒の数（転倒が起こっている回数）を利用

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

 ☆ウォーキングディスタンス

ゴール盤面で各行（または各列）に属している駒が、その盤面でそれぞれの各行（または各列）に何個あるかというパターンをデータベース化したもの。
PDBの一種（？）
４×４くらいまでは有効だが、５×５以上ではデータベースが膨大になり現実的ではない。

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

 ☆最短経路以外の解を求める探索

ここまでは全て最短経路を求めるためのアルゴリズムだが、今回のDevquizの問題は与えられた移動可能駒数に余裕があり、参加者の多くは非最短解を求めるアルゴリズムを考案・採用されていた。

大別すると以下のパターンに分類できる。

 ☆上限を守らない評価関数

上に述べたように任意の盤面nに対し

0 ≦ h'(n) ≦ h(n)

を満たすような評価関数であれば、最短経路である事が保障されますが、この上限をあえて守らない事でより早くゴールにたどり着こうという発想。

具体的には、MD値を各コマに対して足し上げる際に端の駒の重みを大きくしたり、駒の並び順に応じてペナルティスコアを加算したり等。

 ☆段階を置いてゴールに辿りつこうという方法

いきなりゴール面までの探索をする代わりに、途中に中継点を置いて中継点までの探索を行い、中継点からゴールまでの探索を再度行う方法。

私が行った、端優先、ステップ実行はこれにあたる。
（ 端優先、ステップ実行という名前は私が勝手に付けた）

 ☆キューのサイズに上限を設ける方法

A*など幅優先系のアルゴリズムでプライオリティキューのサイズに上限を設け、上限に達したらプライオリティのもっとも低いノードをキューから削除する方法。

 ☆経路探索アルゴリズム：双方向探索

逆方向からも探索する事で演算量を下げる方法。
やり方によっては最適解にもなる。

x^Nがx^(N/2)となり、大幅に演算量を下げることができる。

http://ja.wikipedia.org/wiki/%E5%8F%8C%E6%96%B9%E5%90%91%E6%8E%A2%E7%B4%A2

CでDevquiz２０１１スライドパズル その２

解説1

昨日公開したスライドパズルのソースの解説をしていこうと思います。
まずは特に独自性がありそうな、端優先、ステップ実行と書いたアルゴリズムの解説です。

端優先

１	２	３
４	５	６
７	８	０

このような３X３のブロックなしの問題が与えられた場合、人力で解く際は通常、まず１をそろえて、その次２、３、その次４、７、最後に５、６、８と合わせますよね。

このロジックを実装したアルゴリズムです。

ここで２、３を一緒に合わせるのは２を先に合わせて固定してしまうと３が入らなくなるからですが、これは「ある駒（この場合２の駒）を固定することで1方向にしか移動できなくなる駒（この場合は３の駒）を一緒に合わせる必要がある」という考えで一般化でき、具体的には

recurs_func(　駒A　）{
 駒Aを固定する
 for　(　駒B　∈　Aと隣り合っている駒で1方向にしか動かせない駒　）
　　recurs_func(　駒B　）
}

といった再帰で実現できます。

このロジックはブロックがある場合にも拡張でき、例えば

１	２	３	４
５	６	＝	８
９	A	B	C
D	E	F	０

といったケースにもうまく適応できます。

この場合

{1}
{2,3,4,8}
{5,6}
{9,D}
{AE}
{BCF}

といった形の配列を作成し、上から順番にIDA*を利用して揃えていくという事を行っています。

なお、上からそろえる、左からそろえる、左上（０から遠いところから）揃えると3パターンで試してみましたが、これら３つはほぼ等価で、上からそろえてうまくいくものは、左からでも左上からでもうまくいくし、ダメなものはだめという結果でした。

この理由はダメな場合はこの例の｛2,3,4,8}のように一緒に揃えないといけない駒の数が多いとき、IDA*では現実的な計算量に収まらないという状況のようです。
ここは、マンハッタンディスタンス（MD)に加え並び順も考慮することで改善の余地がありそうだったので時間があればもうちょっと開発したかった部分です。

ステップ実行

一般に、駒の移動回数Nが増えるに従いx^Nのオーダーで計算量が増えていきます。

ここで、xは与えられた問題に依存する1から3の間の実数です。（3より小さいのは上下左右4つの方向のうち1方向は前回の盤面に戻る移動なので省略しているから）移動回数とMDの輪が閾値以下という条件で枝刈りするにしてもNが増えると（閾値が増えると）計算量はどうしても膨大になります。

そこで最短経路解を取りこぼしてでも（移動回数の制限はかなりあまいという事がわかっていたので）強めの枝刈りを考える事になるのですが、ここではたとえば1億ノードとか指定してあげて、そのノード数探索して見つからなかったら、それまでに探索したノード内で最もMDの小さい値を初期ノードとして再探索するという事を行いました。つまり、最小値を持つモード以外すべて枝刈りするという大胆な方法です。

双方向探索と同じようにx^Nをx^(N/2)としてあげようという発想ですね。

この方法のメリットはなんといっても実装が簡単である事。

また、ステップ毎に強めの枝刈りをして深く探索していく方法だとローカルミニマムにとらわれて脱出できないリスクが高くなりますが、この方法だと無駄だと思われるノードに対しても与えられた探索回数までは広く探索を行うので、ローカルミニマムから脱出する可能性が高くなるというメリットもあります。

実際、この方法は強力で単純なIDA*では見つけられなかった問題（計算に時間がかかりすぎた問題）のかなりの数を回答しています。

これらのアルゴリズムの位置づけに関してはこちらの記事を参照してください。

CでDevquiz２０１１スライドパズル

Devquizへの参加記念にソースコードを晒しておきます。

アルゴリズム

１、IDA*
  過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化
２、双方向探索
ゴールから幅優先探索、前方からIDA*を実行しマッチング
実装中に他の方法で万点取れる目途が付いたので中途半端（というかまだ動いていなかった。。）になっています。
３、端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。
４、ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。（それ以外のノードを捨てる）
５、半自動シミュレーション
上記で解けない問題が7問残った。この残った問題を半自動で解くためのヒントを元に解いていくシュミレーター。

*距離関数としてはブロックを考慮したマンハッタンディスタンスを使用。
*２だけはゴールを広げる程度に幅優先でメモリー使ってますが、基本的にはメモリーを消費しない深さ優先をベースに作っています。辿ったノードを記憶しておく幅優先系ではメモリーが厳しいかなと予想してたんですが、A*で大半の問題を解いた人もいるようですね。

excuse

高得点を取る事だけを目的に書いていたプログラムなので、書きかけのコードが入っていたりグローバル変数使いまくりのコードになってます。
きちんと書いて今後公開しますが(気が向いたときw）、一旦提出したそのままのコードをUPします。

150点取れたときの画像(@o@)

実際のソース

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <unistd.h>

#define YOKO_YUSEN
//#define INVD
#define MAXIDTBL 600
#define MAX_STACK_LEVEL 5000
#define MAX_HANPUKU 2000
#define   MIN(a,b)  ( ((a)<(b) ) ? (a) : (b) )
#define   MAX(a,b)  ( ((a)>(b) ) ? (a) : (b) )

int matrix_size;
int matrix_size_x;
int matrix_size_y;
int hanpuku_done;
int step_done;
int shurink;
int shurink_mask;
unsigned long long max_count;
unsigned long long count_hanpuku;
int step_dist;

unsigned long long level_counter[MAX_STACK_LEVEL+1];
int level_max_md_counter[MAX_STACK_LEVEL+1];
int level_min_md_counter[MAX_STACK_LEVEL+1];
int moving_history[MAX_STACK_LEVEL+1];
int mh_cnt;
int simflg;

int pre_result_threshold;
char *pre_result_string;
char *mondai;
char *kaitou;

enum STACK {UP, DOWN};
enum MODE2 {MOVE, HANPUKU, STEP, STEP_TARGET, FIX,UNFIX};

struct MATRIX{
        char mval[40];
        int sp_pos;
};

struct HASH_LIST {
        struct MATRIX *matrix;
        struct HASH_LIST *next;
};

struct HABA_STACK{
        char mval[36];
};

struct Stock_Arr{
        char r;
        char sp_pos;
        char new_pos[4];
        int md;
        int wd;
        int sd;
        int id;
        int id1;
        int id2;
        int inv1;
        int inv2;
};

struct Stock_Arr stock_arr[MAX_STACK_LEVEL+4];

char New_Pos[36][4];

struct HARR{
        int arr[36][36];
        int arr_len[36];;
        int arr_num;
};


struct MATRIX Matrix;
struct MATRIX Matrix_Min;
struct MATRIX Matrix_Parity;
struct MATRIX Matrix_backup;
struct HARR HArr;
int CrrHarrIdx;

int Threshold;
int Pair_Threshold;
int StackPath[MAX_STACK_LEVEL+1];
int StackPath_Min[MAX_STACK_LEVEL+1];
int *IDTBL1;
int *IDTBL2;
int IDTBL3[MAXIDTBL];
int IDTBL4[MAXIDTBL];
int IDTBL5[MAXIDTBL];
int IDTBL6[MAXIDTBL];
int M_Distance[36][36];
int R_Distance[36][36];
int Parity_omote2ura[36];
int Parity_ura2omote[36];
int max_haba_stack;
struct HASH_LIST **hash_table;
struct HASH_LIST *Hash_List;
int stack_cnt,stack_tail;
int hash_cnt;
int haba;
struct MATRIX *haba_stack;
int min_depth;
int mode=1;

enum Dir {U,L,D,R};
int DirectionX[4] = {0, -1, 0, 1};
int DirectionY[4] = {-1, 0, 1, 0};
char Direction[4] = {'U', 'L', 'D', 'R'};


void dump_harr(){
        int i,j;

        printf("arr_num:%d\n",HArr.arr_num);
        for(i=0;i<HArr.arr_num;i++){
                printf("[%d(arr_len:%d) ->",i,HArr.arr_len[i]);
                for(j=0;j<HArr.arr_len[i];j++){
                        printf(" %d",HArr.arr[i][j]);
                }
                printf("]\n");
        }
}

void dump_matrix(struct MATRIX *m){
        int i;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
        for(i=0;i<matrix_size;i++){
                p = m->mval[i];

                if(p > 8){
                        c = p + 'A' - 9;
                } else if(p == -2){
                        c = '=';
                } else if(p == -1){
                        c = '.';
                } else {
                        c = p + '1';
                }
                printf("%c",c);

                if(i%matrix_size_x == matrix_size_x - 1){
                        printf("\n");
                }
        }
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

void dump_matrix2(struct MATRIX *m){
        int i,x,y;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("       ");
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");

        for(y=0;y<matrix_size_y;y++){
                for(x=0;x<matrix_size_x;x++){
                        i = y*matrix_size_x+x;
                        p = m->mval[i];
                        if(p > 8){
                                c = p + 'A' - 9;
                        } else if(p == -2){
                                c = '=';
                        } else if(p == -1){
                                c = '.';
                        } else {
                                c = p + '1';
                        }
                        printf("%c",c);
                }
                printf("       ");
                for(x=0;x<matrix_size_x;x++){
                        i = y*matrix_size_x+x;
                        p = m->mval[i];
                        if(p == -2){
                                c = '=';
                        } else if(i == matrix_size-1){
                                c = '.';
                        } else if(i > 8){
                                c = i + 'A' - 9;
                        } else {
                                c = i + '1';
                        }
                        printf("%c",c);
                }
                printf("\n");
        }

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("       ");
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

void mv_koma(int this_r){
        int sp_pos,new_sp_pos;
        int tgt;

        sp_pos = Matrix.sp_pos;
        new_sp_pos = New_Pos[sp_pos][this_r];
        tgt = Matrix.mval[new_sp_pos];
        Matrix.mval[sp_pos] = tgt;
        Matrix.mval[new_sp_pos] = -1;
        Matrix.sp_pos = new_sp_pos;

}


void make_goal(struct MATRIX *tgt, struct MATRIX *org){
        int i,j;

        for(i=0, j=0; i<matrix_size; i++){
                if(org->mval[i] == -2){
                        tgt->mval[i] = -2;
                } else {
                        tgt->mval[i] = i;
                        j=i;
                }
        }
        tgt->mval[j] = -1;

        tgt->sp_pos = org->sp_pos;

}



void check_matrix(struct MATRIX *m){
        int i;

        for(i=0;i<matrix_size;i++){
                if(m->mval[i] == -1){
                        return;
                }
        }
        printf("ERR: not found space\n");
        fflush(stdout);
        sleep(100);


}

int fix_mval(char p){
        int c;

        if(p > 8){
                c = p + 'A' - 9;
        } else if(p == -2){
                c = '=';
        } else {
                c = p + '1';
        }

        return c;
}


void dump_matrix_parity(struct MATRIX *m){
        int i;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
        for(i=0;i<matrix_size;i++){
                p = m->mval[Parity_omote2ura[i]];

                if(p > 8){
                        c = p + 'A' - 9;
                } else if(p == -2){
                        c = '=';
                } else {
                        c = p + '1';
                }
                printf("%c",c);

                if(i%matrix_size_x == matrix_size_x-1){
                        printf("\n");
                }
        }
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

int comp(const void *a, const void *b)
{
        return R_Distance[matrix_size-1][*(int*)b] - R_Distance[matrix_size-1][*(int*)a];

}

int next_harr_saiki(int *stack_cnt, int *stack, int crr, struct MATRIX *m){
        int px, py, cx, cy,nx,ny;
        int r1,r2;
        int p_cnt;

        m->mval[crr] = -2;
        stack[stack_cnt[0]] = crr;
        stack_cnt[0]++;

        px = crr % matrix_size_x;
        py = crr / matrix_size_x;

        for ( r1 = 0; r1 < 4; r1++ ){
                cx = px + DirectionX[r1];
                cy = py + DirectionY[r1];

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(m->mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                p_cnt=0;
                for(r2 = 0;r2 < 4;r2++){
                        nx = cx + DirectionX[r2];
                        ny = cy + DirectionY[r2];
                        if ( nx < 0 || ny < 0 || nx >= matrix_size_x || ny >= matrix_size_y ){
                                continue;
                        }
                        if(m->mval[ny*matrix_size_x+nx] == -2){
                                continue;
                        }
                        p_cnt++;
                }

                if(p_cnt < 2 || m->mval[matrix_size-1] == -2){
                        next_harr_saiki(stack_cnt, stack, cy*matrix_size_x+cx ,m);
                }
        }
        return 0;
}

int add_harr(int list_len, int *ranked_list, struct MATRIX *mtr){
        int stck[36];
        int cnt,i,j,found;

        cnt = 0;
        next_harr_saiki(&cnt,stck,ranked_list[0],mtr);
        if(cnt <= 0){
                exit(0);
        }

        for(i=0;i<cnt;i++){
                HArr.arr[HArr.arr_num][i] = stck[i];
        }

        HArr.arr_len[HArr.arr_num] = cnt;
        HArr.arr_num++;

        for(i=0;i<cnt;i++){
                found = 0;
                for(j=0;j<list_len;j++){
                        if(found == 1){
                                ranked_list[j-1] = ranked_list[j];
                        } else if(ranked_list[j] == stck[i]){
                                found = 1;
                        }
                }
        }


        return list_len - cnt;
}


void make_harr(struct MATRIX *m){
        int x,y,i,j,list_len;
        int ranked_list[36];
        int ranked_list_tmp[36];
        struct MATRIX tmp_m;

        CrrHarrIdx=0;
        HArr.arr_num = 0;

        for(i=0,j=0;i<matrix_size-1;i++){
                if(m->mval[i] != -2){
                        ranked_list[j++] = i;
                }
        }
        list_len = j;

        if(step_dist == 1){
                /*do nothing*/
        } else if(step_dist == 2){
                for(i=0;i<matrix_size;i++) ranked_list_tmp[i] = ranked_list[i];
                for(x=0;x<matrix_size_x;x++)
                        for(y=0;y<matrix_size_y;y++)
                                ranked_list[y*matrix_size_x+x] = ranked_list_tmp[y*matrix_size_x+x];
        } else {
                qsort(ranked_list,list_len,sizeof(int),comp);
        }

        tmp_m = Matrix;
        while(1){
                if(list_len <= 0){
                        break;
                }

                list_len = add_harr(list_len, ranked_list, &tmp_m);
        }
}

void set_m_distance(){
        int i,j;

        for ( i = 0; i < matrix_size; i++ ){
                for ( j = 0; j < matrix_size; j++ ){
                        M_Distance[i][j] = abs(i/matrix_size_x-j/matrix_size_x) + abs(i%matrix_size_x-j%matrix_size_x);
                }
        }
}


int pair_saiki(int depth, int pre_r,int crr, int end){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int d;

        if ( crr == end ){
                return 1;
        }

        d = M_Distance[crr][end];
        if ( depth + d > Pair_Threshold ){
                return 0;
        }

        px = crr % matrix_size_x;
        py = crr / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                ret = pair_saiki( depth+1, r , cy*matrix_size_x+cx, end);
                if (ret) {

                        return 1;
                }
        }
        return 0;
}


void set_r_distance(struct MATRIX *m){
        int i,j,ret;

        ret = 0;
        for ( i = 0; i < matrix_size; i++ ){
                if(m->mval[i] == -2) continue;
                for ( j = 0; j < matrix_size; j++ ){
                        if(m->mval[j] == -2) continue;
                        for ( Pair_Threshold = M_Distance[i][j]; Pair_Threshold <= MAX_STACK_LEVEL; Pair_Threshold += 2 ){
                                ret = pair_saiki(0, -4,i,j);

                                if ( ret ){
                                        R_Distance[i][j] = Pair_Threshold;
                                        break;
                                }

                        }
                        if(ret < 0){
                                printf("ERR: R_Distance not fund for [%d][%d]",i,j);
                                exit(1);
                        }
                }
        }
}

int inv_distance1(){
        int i,j,inv,val1,val2;

        inv = 0;
        for (i=0; i<matrix_size; i++) {
                val1 = Matrix.mval[i];
                if (val1 == -1) continue;
                if (val1 == -2) val1 = i;
                for (j=i+1; j<matrix_size; j++) {
                        val2 = Matrix.mval[j];
                        if (val2 == -1) continue;
                        if (val2 == -2) val2 = j;
                        if (val2<val1){
                                inv++;
                        }
                }
        }
        return inv;
}


int inv_distance2(){
        int i,j,inv,val1,val2;

        inv = 0;
        for (i=0; i<matrix_size; i++) {
                val1 = Matrix_Parity.mval[i];
                if (val1 == -1) continue;
                if (val1 == -2) val1 = i;
                for (j=i+1; j<matrix_size; j++) {
                        val2 = Matrix_Parity.mval[j];
                        if (val2 == -1) continue;
                        if (val2 == -2) val2 = j;
                        if (val2<val1){
                                inv++;
                        }
                }
        }
        return inv;
}

int i_distance(){
        int inv1,inv2;

        inv1 = inv_distance1();
        inv2 = inv_distance2();
        return IDTBL1[inv1]+IDTBL2[inv2];
}

int m_distance(){
        int md;
        int i;

        md = 0;
        for(i = 0; i < matrix_size; i++){
                if ( Matrix.mval[i] < 0 )continue;
                md += R_Distance[i][(int)Matrix.mval[i]];
        }

        return md;
}

int w_distance(){
        int md;
        int id;

        md = m_distance();
        id = i_distance();

        return MAX(md,id);;
}

int step_distance(){
        int sum;
        int i,j,k;
        char c;

        sum = 0;
        for(i = 0; i < HArr.arr_len[CrrHarrIdx]; i++){
                k = HArr.arr[CrrHarrIdx][i];
                c = k;
                for(j=0;j<matrix_size;j++){
                        if(Matrix.mval[j] == c){
                                sum += R_Distance[j][k];
                        }
                }

        }
        return sum;
}

int check_goal(){
        int i;
        for ( i = matrix_size-2; i >= 0; i-- ){
                if ( Matrix.mval[i] != i && Matrix.mval[i] != -2 ){
                        return 0;
                }
        }
        return 1;
}

int check_step_goal(){
        int i,j;
        for (i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                j = HArr.arr[CrrHarrIdx][i];
                if ( Matrix.mval[j] != j && Matrix.mval[j] != -2){
                        return 0;
                }
        }
        return 1;
}

int heuristic_distance(){


        return 0;
}

int get_r(char *c){
        int this_r;

        if(*c=='U' || *c=='u') this_r = 0;
        else if(*c=='L' || *c=='l') this_r = 1;
        else if(*c=='D' || *c=='d') this_r = 2;
        else if(*c=='R' || *c=='r') this_r = 3;
        else this_r = -1;

        return this_r;
}



int steploop(int pre_depth, int depth, int pre_r){
        int i;
        int this_r;
        int sp_pos,new_sp_pos;
        int stack_dir;
        int crr_depth;
        char *npp;
        int found;
        int tgt;
        int sd;
        int harr_arr_len;

        struct MATRIX tmp;

        harr_arr_len = HArr.arr_len[CrrHarrIdx];

        tmp = Matrix;

        found = 0;
        crr_depth = 0;

        stack_dir = DOWN;
        sp_pos = Matrix.sp_pos;
        stock_arr[crr_depth].sp_pos = sp_pos;


        sd = step_distance();
        if(sd == 0){
                found = 1;
                return 1;
        }
        stock_arr[crr_depth].sd = sd;

        if ( sd > Threshold - crr_depth ){
                return 0;
        }

        memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
        npp = stock_arr[crr_depth].new_pos;

        for(i=0;i<4;i++){
                if(pre_r - i == 2 || i - pre_r == 2){
                        npp[i] = -1;
                        break;
                }
        }

        for(this_r=-1,i=0;i<4;i++){
                if(npp[i] >= 0){
                        this_r = i;
                        break;
                }
        }

        if(this_r >= 0){
                npp[this_r] = -1;
                stack_dir = DOWN;
        } else {
                fprintf(stderr,"ERR11\n");
                return 0;
        }

        while(1){


                if(stack_dir == DOWN){
                        /* use stack_dir, this_r, sp_pos */

                        if(crr_depth >= MAX_STACK_LEVEL){
                                fprintf(stderr, "ERR: crr_depth over\n");
                                return 0;
                        }
                        crr_depth++;

                        if(count_hanpuku > max_count){
                                hanpuku_done = 1;
                                return 0;
                        }
                        count_hanpuku++;

                        stock_arr[crr_depth].r = this_r;
                        new_sp_pos = New_Pos[sp_pos][this_r];
                        stock_arr[crr_depth].sp_pos = new_sp_pos;
                        tgt = Matrix.mval[new_sp_pos];
                        Matrix.mval[sp_pos] = tgt;
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;
                        sd = stock_arr[crr_depth-1].sd;
                        for(i=0;i<harr_arr_len;i++){
                                if(HArr.arr[CrrHarrIdx][i] == tgt){
                                        sd += R_Distance[sp_pos][tgt] - R_Distance[new_sp_pos][tgt];
                                        break;
                                }
                        }

                        if(sd == 0){
                                found = 1;
                                break;
                        }
                        stock_arr[crr_depth].sd = sd;

                        if ( sd > Threshold - crr_depth ){
                                sp_pos = new_sp_pos;
                                stack_dir = UP;
                                continue;
                        }

                        memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
                        npp = stock_arr[crr_depth].new_pos;

                        for(i=0;i<4;i++){
                                if(this_r - i == 2 || i - this_r == 2){
                                        npp[i] = -1;
                                        break;
                                }
                        }

                        if(npp[0] >= 0) this_r = 0;
                        else if(npp[1] >= 0) this_r = 1;
                        else if(npp[2] >= 0) this_r = 2;
                        else if(npp[3] >= 0) this_r = 3;
                        else this_r = -1;

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }


                } else { // UP
                        if(crr_depth == 0){
                                return 0;
                        }
                        crr_depth--;

                        new_sp_pos = stock_arr[crr_depth].sp_pos;
                        Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;

                        npp =  stock_arr[crr_depth].new_pos;
                        for(this_r = -1,i=0;i<4;i++){
                                if(npp[i] >= 0){
                                        this_r = i;
                                        break;
                                }
                        }

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }

                }
        }

        if(found){
                for(i=0;i<crr_depth;i++){
                        StackPath[pre_depth+i] = stock_arr[i+1].r;
                }
                StackPath[pre_depth+i] = 0;
        }

        return 1;
}

int stepsaiki(int depth, int pre_r){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int wd;
        struct MATRIX tmp;

        wd = step_distance();
        if(wd == 0){
                Matrix_backup = Matrix;
                return 1;
        }

        if ( depth + wd > Threshold ){
                return 0;
        }

        count_hanpuku++;
        if(count_hanpuku > max_count){
                return 0;
        }

        px = Matrix.sp_pos % matrix_size_x;
        py = Matrix.sp_pos / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                tmp = Matrix;
                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
                ret = stepsaiki( depth+1, r );
                if (ret) {
                        StackPath[depth] = r;
                        return 1;
                }
                Matrix = tmp;
        }
        return 0;
}

int check_pre_result_path(){
        int i,x;
        char *c;
        int done;
        int px,py,cx,cy;


        c = pre_result_string;
        if(c == NULL || strncmp(c,"not",3)==0){
                printf("not checked\n");

                return 0;
        }

        for(x=0;c[x];x++){

                done = 0;
                for(i=0;i<4;i++){
                        if(Direction[i] == c[x]){
                                done = 1;
                                break;
                        }
                }
                if(done == 0){
                        printf(":ERR0: no direction[%d][%s]\n",x,c);
                        return 0;
                }

                px = Matrix.sp_pos % matrix_size_x;
                py = Matrix.sp_pos / matrix_size_x;
                cx = px + DirectionX[i];
                cy = py + DirectionY[i];

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        printf(":ERR1: bad direction[%d][%s]\n",x,c);
                        return 0;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        printf(":ERR2: bad direction[%d][%s]\n",x,c);
                        continue;
                }

                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
        }
        if ( m_distance() ){
                printf(":ERR3: bad path[%s]\n",c);
                return 0;
        } else {
                printf("%s ok\n",mondai);
                return 1;
        }
}

int check_id(int inv1, int inv2, struct MATRIX *m){

        if( inv1 != inv_distance1()){
                return 0;
        }
        if( inv2 != inv_distance2()){
                return 0;
        }

        return 1;
}

void make_new_pos(struct MATRIX *mtr){
        int px, py, cx, cy,i,r;
        int npos;

        for(i=0;i<matrix_size;i++){
                for(r=0;r<4;r++){
                        px = i % matrix_size_x;
                        py = i / matrix_size_x;

                        cx = px + DirectionX[r];
                        cy = py + DirectionY[r];

                        npos = cy*matrix_size_x+cx;

                        if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        if(Matrix.mval[npos] == -2){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        New_Pos[i][r] = npos;
                }

        }
}

void fix_new_pos(struct MATRIX *mtr){
        int px, py, cx, cy,i,r;
        int npos;

        for(i=0;i<matrix_size;i++){
                for(r=0;r<4;r++){
                        px = i % matrix_size_x;
                        py = i / matrix_size_x;

                        cx = px + DirectionX[r];
                        cy = py + DirectionY[r];

                        npos = cy*matrix_size_x+cx;

                        if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        if(Matrix.mval[npos] == -2){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        New_Pos[i][r] = npos;
                }

        }
}

int hash_func(struct MATRIX *matrix){
        int hash,i;

        hash = 1;
        for(i=0;i<matrix_size;i++){
                hash += 137 + (matrix->mval[i]+13)*i;
        }
        return hash % max_haba_stack;

}

void dump_hash(){
        int i;
        struct HASH_LIST *hlp;

        for(i=0;i<max_haba_stack;i++){
                for (hlp = hash_table[i]; hlp != NULL; hlp = hlp->next){
                        printf("key:%d\n",i);
                        dump_matrix(hlp->matrix);
                }

        }
}

struct MATRIX *get_hash(struct MATRIX *this_matrix, int hash_val){
        int found,i;
        struct HASH_LIST *hlp;
        char *mval;

        if(hash_val < 0){
                hash_val = hash_func(this_matrix);
        }

        for (hlp = hash_table[hash_val]; hlp != NULL; hlp = hlp->next){
                found = 1;
                mval = hlp->matrix->mval;

                /**/
                for(i=0;i<matrix_size;i++){
                        if(mval[i] != this_matrix->mval[i]){
                                found = 0;
                                break;
                        }
                }
                if(found == 1){

                        return hlp->matrix;
                }
        }

        return NULL;
}

int set_hash(struct MATRIX *this_matrix, int this_r){
        int sp_pos,new_sp_pos;
        int tgt;
        struct HASH_LIST *hash_list, *hlp;
        struct MATRIX *m;
        int hash_val;

        hash_list = &Hash_List[hash_cnt];
        memcpy(&haba_stack[stack_tail],this_matrix,sizeof(struct MATRIX));
        this_matrix = &haba_stack[stack_tail];

        sp_pos = this_matrix->sp_pos;
        new_sp_pos = New_Pos[sp_pos][this_r];
        tgt = this_matrix->mval[new_sp_pos];
        this_matrix->mval[sp_pos] = tgt;
        this_matrix->mval[new_sp_pos] = -1;
        this_matrix->sp_pos = new_sp_pos;

        hash_val = hash_func(this_matrix);
        m = get_hash(this_matrix,hash_val);
        if(m != NULL){
                return 1;
        }

        hash_list->matrix = &haba_stack[stack_tail];
        hash_list->next = NULL;
        hash_cnt++;
        stack_tail++;

        if (hash_table[hash_val] == NULL) {
                hash_table[hash_val] = hash_list;
        } else {
                hlp = hash_table[hash_val];
                while (hlp->next != NULL)
                        hlp = hlp->next;
                hlp->next = hash_list;
        }
        return 0;
}

int haba_tansaku(){
        int i;
        struct MATRIX *this_matrix;
        char *npp;

        stack_cnt=0;
        stack_tail=0;

        haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
        if(haba_stack == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }

        hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
        if(hash_table == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }
        bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);

        Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);
        if (Hash_List == NULL) {
                fprintf(stderr, "ERR: cant alloc memmory\n");
                exit(1);
        }

        this_matrix = &haba_stack[stack_tail];
        memcpy(this_matrix,&Matrix,sizeof(struct MATRIX));
        stack_tail++;

        while(stack_cnt < stack_tail){

                this_matrix = &haba_stack[stack_cnt];
                npp = New_Pos[this_matrix->sp_pos];

                for(i=0;i<4;i++){
                        if(npp[i] >= 0){

                                count_hanpuku++;
                                if(count_hanpuku >= max_count){
                                        return 1;
                                }

                                stack_cnt++;
                                if(stack_tail >= max_haba_stack){
                                        return 1;
                                }

                                set_hash(this_matrix,i);
                        }
                }

        }

        return 0;

}
void free_hash(){

        free(hash_table);
        free(haba_stack);
        free(Hash_List);

        hash_table=NULL;
        haba_stack=NULL;
        Hash_List=NULL;

}

int loop(int depth, int pre_r){
        int i;
        int wd;
        int id;
        int md;
        int this_r;
        int sp_pos,sp_pos_p,new_sp_pos;
        int stack_dir;
        int crr_depth;
        char *npp;
        int found;
        int tgt;
#ifdef INVD
        int new_sp_pos_p;
        int val;
        int tgt_p;
#endif
        int inv1,inv2;
        int id1,id2;

        struct MATRIX tmp;
        struct MATRIX tmp_p;
        struct MATRIX *hash_ret;

        tmp = Matrix;
        tmp_p = Matrix_Parity;

        found = 0;
        crr_depth = 0;

        stack_dir = DOWN;
        sp_pos = Matrix.sp_pos;
        stock_arr[crr_depth].sp_pos = sp_pos;
        sp_pos_p = Parity_omote2ura[sp_pos];


        md = m_distance();
        inv1 = inv_distance1();
        inv2 = inv_distance2();
        id1 = IDTBL1[inv1];
        id2 = IDTBL2[inv2];
        id = id1+id2;
        wd = MAX(md,id);
        if(wd == 0){
                found = 1;
                return 1;
        }

        if(haba == 1){
                hash_ret = get_hash(&Matrix, -1);
                if(hash_ret != NULL){
                        return 0;
                }
        }
#ifdef DEBUG
        level_max_md_counter[crr_depth] = md;
        level_min_md_counter[crr_depth] = md;
#endif

        stock_arr[crr_depth].md = md;
        stock_arr[crr_depth].id = id;
        stock_arr[crr_depth].inv1 = inv1;
        stock_arr[crr_depth].inv2 = inv2;
        stock_arr[crr_depth].wd = wd;

        if ( wd > Threshold - crr_depth ){
                return -1;
        }

        memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
        npp = stock_arr[crr_depth].new_pos;

        for(this_r=-1,i=0;i<4;i++){
                if(npp[i] >= 0){
                        this_r = i;
                        break;
                }
        }

        if(this_r >= 0){
                npp[this_r] = -1;
                stack_dir = DOWN;
        } else {
                fprintf(stderr,"ERR11\n");
                return -1;
        }

        while(1){


                if(stack_dir == DOWN){
                        /* use stack_dir, this_r, sp_pos */

                        if(crr_depth >= MAX_STACK_LEVEL){
                                return -1;
                        }

                        crr_depth++;
                        count_hanpuku++;
                        level_counter[crr_depth]++;
                        if(count_hanpuku > max_count){
                                hanpuku_done = 1;
                                if(shurink > 0){
                                        return -1;
                                }
                        }
                        stock_arr[crr_depth].r = this_r;
                        new_sp_pos = New_Pos[sp_pos][this_r];
                        stock_arr[crr_depth].sp_pos = new_sp_pos;
                        tgt = Matrix.mval[new_sp_pos];
                        Matrix.mval[sp_pos] = tgt;
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;
                        md = stock_arr[crr_depth-1].md - R_Distance[new_sp_pos][tgt] +  R_Distance[sp_pos][tgt];
                        if(md > level_max_md_counter[crr_depth]) level_max_md_counter[crr_depth] = md;
                        if(md < level_min_md_counter[crr_depth]){
                                level_min_md_counter[crr_depth] = md;
                                Matrix_Min = Matrix;
                                min_depth = crr_depth;
                                for(i=0;i<crr_depth;i++) StackPath_Min[i] = stock_arr[i+1].r;
                        }

#ifdef INVD
                        sp_pos_p = Parity_omote2ura[sp_pos];
                        new_sp_pos_p = Parity_omote2ura[new_sp_pos];
                        tgt_p = Matrix_Parity.mval[new_sp_pos_p];
                        Matrix_Parity.mval[sp_pos_p] = tgt_p;
                        Matrix_Parity.mval[new_sp_pos_p] = -1;
                        inv1 = stock_arr[crr_depth-1].inv1;
                        inv2 = stock_arr[crr_depth-1].inv2;

                        if(this_r == U){
                                for(i=new_sp_pos+1;i<sp_pos;i++){
                                        if(Matrix.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix.mval[i];
                                        }
                                        if (val > tgt){
                                                inv1++;
                                        } else {
                                                inv1--;
                                        }
                                }
                        } else if(this_r == D){
                                for(i=sp_pos+1;i<new_sp_pos;i++){
                                        if(Matrix.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix.mval[i];
                                        }
                                        if (val > tgt){
                                                inv1--;
                                        } else {
                                                inv1++;
                                        }
                                }
                        } else if(this_r == L){
                                for(i=new_sp_pos_p+1;i<sp_pos_p;i++){
                                        if(Matrix_Parity.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix_Parity.mval[i];
                                        }
                                        if (val > tgt_p){
                                                inv2++;
                                        } else {
                                                inv2--;
                                        }
                                }
                        } else /* R */{
                                for(i=sp_pos_p+1;i<new_sp_pos_p;i++){
                                        if(Matrix_Parity.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix_Parity.mval[i];
                                        }
                                        if (val > tgt_p){
                                                inv2--;
                                        } else {
                                                inv2++;
                                        }
                                }
                        }

                        id1 = IDTBL1[inv1];
                        id2 = IDTBL2[inv2];
                        id = id1+id2;

                        stock_arr[crr_depth].id1 = id1;
                        stock_arr[crr_depth].id2 = id2;
                        stock_arr[crr_depth].inv1 = inv1;
                        stock_arr[crr_depth].inv2 = inv2;
                        wd = MAX(id,md);
                        stock_arr[crr_depth].wd = wd;

                        /**/    md = wd;
#endif

                        if(md == 0){
                                found = 1;
                                break;
                        }
                        stock_arr[crr_depth].md = md;

                        if(haba == 1){
                                hash_ret = get_hash(&Matrix, -1);
                                if(hash_ret != NULL){
                                        found = crr_depth;
                                        break;
                                }
                        }

                        if ( md > Threshold - crr_depth ){
                                sp_pos = new_sp_pos;
                                stack_dir = UP;
                                continue;
                        }

                        memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
                        npp = stock_arr[crr_depth].new_pos;

                        for(i=0;i<4;i++){
                                if(this_r - i == 2 || i - this_r == 2){
                                        npp[i] = -1;
                                        continue;
                                }
                        }

# ifdef YOKO_YUSEN
                        if(npp[1] >= 0) this_r = 1;
                        else if(npp[0] >= 0) this_r = 0;
                        else if(npp[3] >= 0) this_r = 3;
                        else if(npp[2] >= 0) this_r = 2;
                        else this_r = -1;
# else
                        if(npp[0] >= 0) this_r = 0;
                        else if(npp[1] >= 0) this_r = 1;
                        else if(npp[2] >= 0) this_r = 2;
                        else if(npp[3] >= 0) this_r = 3;
                        else this_r = -1;
# endif

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }


                } else {
                        if(crr_depth == 0){
                                return -1;
                        }
                        crr_depth--;

                        new_sp_pos = stock_arr[crr_depth].sp_pos;
                        Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;

#ifdef INVD
                        sp_pos_p = Parity_omote2ura[sp_pos];
                        new_sp_pos_p = Parity_omote2ura[new_sp_pos];
                        Matrix_Parity.mval[sp_pos_p] = Matrix_Parity.mval[new_sp_pos_p];
                        Matrix_Parity.mval[new_sp_pos_p] = -1;
#endif

                        npp =  stock_arr[crr_depth].new_pos;
                        for(this_r = -1,i=0;i<4;i++){
                                if(npp[i] >= 0){
                                        this_r = i;
                                        break;
                                }
                        }

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }

                }
        }

        if(found){
                for(i=0;i<crr_depth;i++){
                        StackPath[i] = stock_arr[i+1].r;
                }
                StackPath[i] = 0;
        }

        Matrix = tmp;
        return found;
}

int saiki(int depth, int pre_r){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int wd;
        struct MATRIX tmp;

        if ( check_goal() ){
                return 1;
        }

        wd = m_distance();
        if ( depth + wd > Threshold ){
                return 0;
        }

        count_hanpuku++;
        if(count_hanpuku > max_count){
                return 0;
        }

        px = Matrix.sp_pos % matrix_size_x;
        py = Matrix.sp_pos / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                tmp = Matrix;
                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
                ret = saiki( depth+1, r );
                if (ret) {
                        StackPath[depth] = r;

                        Matrix = tmp;
                        return 1;
                }
                Matrix = tmp;
        }
        return 0;
}



int HanpukuShinka(){
        int i;
        int sdcnt[3],sdsum[3],max=0,maxi=0;
        count_hanpuku = 0;
        hanpuku_done = 0;
        struct MATRIX matrix_backup, matrix_goal;
        int ret;

        matrix_backup = Matrix;
        if(pre_result_threshold > 0){
                Threshold = pre_result_threshold;
        } else {
                Threshold = m_distance();
        }
        for (ret = 0 ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
                if(haba == 1){
                        make_goal(&matrix_goal,&Matrix);
                        Matrix = matrix_goal;
                        haba_tansaku();
                        Matrix = matrix_backup;

                }
#ifdef DEBUG
                for(i=0;i<MAX_STACK_LEVEL;i++) level_counter[i] = 0;
                for(i=0;i<MAX_STACK_LEVEL;i++) level_max_md_counter[i] = 0;
                for(i=0;i<MAX_STACK_LEVEL;i++) level_min_md_counter[i] = 100000;
#endif
                ret = loop(0, -4);
                if(haba == 1){
                        free_hash();

                        if(ret >= 0){
                                for ( i = 0; i < ret; i++ ) printf("%c",Direction[StackPath[i]]);
                                fflush(stdout);
                                break;
                        }
                }

                if (ret >= 0){
                        for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
                        printf("\n");
                        fflush(stdout);
                        return 1;
                } else {
                        if(hanpuku_done > 0) {
                                if(shurink > 0){
                                        hanpuku_done=0;
                                        count_hanpuku = 0;
                                        Matrix=Matrix_Min;
                                        if(shurink_mask > 0){
                                                for(i=0;i<3;i++){
                                                        max=0;
                                                        maxi=0;
                                                        step_dist = i;
                                                        make_harr(&Matrix);
                                                        sdsum[i] = 0;
                                                        for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
                                                                if(step_distance() == 0){
                                                                        sdsum[i] += HArr.arr_len[i];
                                                                } else {
                                                                        break;
                                                                }
                                                        }
                                                        sdcnt[i] = CrrHarrIdx;

                                                        if(sdsum[i] > max){
                                                                max = sdsum[i];
                                                                maxi = i;
                                                        }
                                                }
                                                step_dist = maxi;
                                                make_harr(&Matrix);

                                                if(shurink_mask > 1 && sdsum[maxi] > 0){
                                                        for(CrrHarrIdx=0;CrrHarrIdx<sdcnt[maxi];CrrHarrIdx++){
                                                                for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                                                                        Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
                                                                }
                                                        }
                                                }
                                        }
                                        Threshold = m_distance();
                                        for ( i = 0; i < min_depth; i++ ) printf("%c",Direction[StackPath_Min[i]]);
                                        shurink--;
                                        continue;
                                }
                                break;
                        }
                }

        }

        if(ret < 2){
                printf(" not found in HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
                fflush(stdout);
                return 0;
        }

        Threshold = m_distance();
        for ( ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
                haba = 0;
                ret = loop(0, -4);
                haba = 1;

                if (ret != 0){
                        for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
                        printf("\n");
                        fflush(stdout);
                        return 1;
                } else {
                        if(hanpuku_done > 0) {
                                break;
                        }
                }
        }

        printf(" not found in HabaYusen & HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
        fflush(stdout);
        return 0;
}

int StepShinka(){
        int i;
        int ret;
        int this_r;
        int pre_depth;

        count_hanpuku = 0;
        this_r = -4;
        pre_depth = 0;
        for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
                ret = 0;
                for ( Threshold = step_distance(); Threshold <= MAX_STACK_LEVEL; Threshold++ ){
                        Matrix_backup = Matrix;
                        ret = steploop(pre_depth, 0, this_r);
                        if ( ret > 0 ){
                                break;
                        }

                        if(count_hanpuku > max_count){
                                break;
                        }
                        Matrix = Matrix_backup;
                }


                if(ret == 0){
                        printf(" not found in StepShinka(count_hanpuku(%lld)) for Threshold(%d),CrrHarrIdx(%d)\n",count_hanpuku,Threshold+1,CrrHarrIdx);
                        fflush(stdout);
                        return 0;
                }



                for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[pre_depth+i]]);
                if(simflg) for ( i = 0; i < Threshold; i++ ) moving_history[mh_cnt++] = StackPath[pre_depth+i];
                pre_depth += Threshold;
                this_r = StackPath[Threshold-1];
                for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                        Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
                }
                fix_new_pos(&Matrix);
        }
        printf("\n");
        fflush(stdout);

        return 1;
}

int get_tgt(char c){

        if(c == '='){
                c = -2;
        } else if('Z' >= c && c >= 'A'){
                c = c - 'A' + 9;
        } else if('z' >= c && c >= 'a'){
                c = c - 'a' + 9;
        } else if('9' >= c && c >= '1'){
                c = c - '1';
        } else if(c == '.' || c == '0'){
                c = -1;
        } else {
                c = -3;
        }
        return c;
}

void sim(){
        int md,i,j;
        char buff[MAXIDTBL];
        int mode2=-1;
        int this_r;
        char *c;
        int tgt;
        struct MATRIX Matrix_org,Matrix_tmp,Matrix_stp;
        int ret;
        char New_Pos_org[36][4];

        Matrix_tmp = Matrix;
        Matrix_org = Matrix;
        memcpy(New_Pos_org,New_Pos,sizeof(New_Pos));
        mh_cnt = 0;
        if(kaitou){
                printf("%s %s\n",mondai,kaitou);
        } else {
                printf("%s\n",mondai);
        }
        printf("\n");
        dump_matrix2(&Matrix);

        if(kaitou){


                c = kaitou;
                while(*c){
                        this_r = get_r(c);
                        if(this_r < 0) continue;

                        if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                mv_koma(this_r);
                                moving_history[mh_cnt++] = this_r;
                        }
                        c++;
                }

                printf("\n");
                dump_matrix2(&Matrix);
        }

        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");

        while(fgets(buff,MAXIDTBL-1,stdin) != NULL){
                for(i=0;buff[i];i++){
                        if(mode == 0){
                                if(i==0){
                                        if(buff[0] == 'c'){
                                                mode = 1;
                                                dump_matrix2(&Matrix);
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                break;
                                        }
                                }
                                if(buff[i] == '\n'){
                                        dump_matrix2(&Matrix);
                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                        break;
                                }
                                this_r = -1;
                                if(buff[i]=='U' || buff[i]=='u') this_r = 0;
                                if(buff[i]=='L' || buff[i]=='l') this_r = 1;
                                if(buff[i]=='D' || buff[i]=='d') this_r = 2;
                                if(buff[i]=='R' || buff[i]=='r') this_r = 3;

                                if(buff[i] == 0x1b && buff[i+1] == '['){
                                        if(buff[i+2] == 'A'){this_r = 0; i+=2;}
                                        if(buff[i+2] == 'B'){this_r = 2; i+=2;}
                                        if(buff[i+2] == 'C'){this_r = 3; i+=2;}
                                        if(buff[i+2] == 'D'){this_r = 1; i+=2;}
                                }

                                if(this_r < 0) continue;



                                if(this_r < 0) continue;
                                if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                        mv_koma(this_r);
                                        moving_history[mh_cnt++] = this_r;
                                }

                                md = m_distance();
                                if(md == 0){
                                        dump_matrix2(&Matrix);
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                        printf("\n");
                                        printf("done\n");
                                        return;
                                }

                        } else { //command mode
                                if(buff[i] == '\n'){
                                        if(mode2 == STEP){
                                                Matrix_stp = Matrix;
                                                ret = StepShinka();
                                                if(ret <=0){
                                                        Matrix = Matrix_stp;
                                                }
                                                md = m_distance();
                                                if(md == 0){
                                                        dump_matrix2(&Matrix);
                                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                        printf("\n");
                                                        printf("done\n");
                                                        return;
                                                }
                                        }

                                        dump_matrix2(&Matrix);
                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                        mode2 = -1;
                                        break;
                                }
                                if(i==0){
                                        if(buff[0] == 'm') {
                                                if(buff[1] == '\n'){
                                                        mode = 0;
                                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                        break;
                                                } else {
                                                        mode2 = MOVE;
                                                }
                                        }else if(buff[0] == 'h') mode2 = HANPUKU;
                                        else if(buff[0] == 's'){
                                                mode2 = STEP;
                                                HArr.arr_num = 1;
                                                HArr.arr_len[0] = 0;
                                        }else if(buff[0] == 'S') mode2 = STEP_TARGET;
                                        else if(buff[0] == 'i'){
                                                printf("mh_cnt:[%d]\n",mh_cnt);
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");

                                        }else if(buff[0] == 'f') mode2 = FIX;
                                        else if(buff[0] == 'F') mode2 = UNFIX;
                                        else if(buff[0] == 'U'){
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");
                                                Matrix = Matrix_org;
                                                Matrix_tmp = Matrix;
                                                memcpy(New_Pos,New_Pos_org,sizeof(New_Pos));
                                                mh_cnt = 0;
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                break;
                                        }else if(buff[0] == 'm'){
                                                mode2 = MOVE;
                                        }else if(buff[0] == 'N'){
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");
                                                return;
                                        }else if(buff[0] == 'b') {

                                        }else {
                                                dump_matrix(&Matrix);
                                                printf("bad command...ignored.\n");
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                break;
                                        }
                                        continue;
                                }
                                if(mode2 == MOVE){
                                        this_r = -1;
                                        if(buff[i]=='U' || buff[i]=='u') this_r = 0;
                                        if(buff[i]=='L' || buff[i]=='l') this_r = 1;
                                        if(buff[i]=='D' || buff[i]=='d') this_r = 2;
                                        if(buff[i]=='R' || buff[i]=='r') this_r = 3;

                                        if(buff[i] == 0x1b && buff[i+1] == '['){
                                                if(buff[i+2] == 'A'){this_r = 0; i+=2;}
                                                if(buff[i+2] == 'B'){this_r = 2; i+=2;}
                                                if(buff[i+2] == 'C'){this_r = 3; i+=2;}
                                                if(buff[i+2] == 'D'){this_r = 1; i+=2;}
                                        }
                                        if(this_r < 0) continue;
                                        if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                                mv_koma(this_r);
                                                moving_history[mh_cnt++] = this_r;
                                        }
                                        md = m_distance();
                                        if(md == 0){
                                                dump_matrix2(&Matrix);
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                printf("done\n");
                                                return;
                                        }

                                }
                                if(mode2 == STEP){
                                        tgt = get_tgt(buff[i]);
                                        if(tgt >= 0){
                                                HArr.arr[0][HArr.arr_len[0]] = tgt;
                                                HArr.arr_len[0]++;
                                        }
                                }
                                if(mode2 == FIX){
                                        tgt = get_tgt(buff[i]);

                                        if(tgt >=0){
                                                if(Matrix.mval[tgt] >= 0){
                                                        Matrix_tmp.mval[tgt] = Matrix.mval[tgt];
                                                        Matrix.mval[tgt] = -2;
                                                }
                                        }
                                }
                                if(mode2 == UNFIX){
                                        tgt = get_tgt(buff[i]);

                                        if(tgt >=0){
                                                if(Matrix_tmp.mval[tgt] >= 0){
                                                        Matrix.mval[tgt] = Matrix_tmp.mval[tgt];
                                                        Matrix_tmp.mval[tgt] = -3;
                                                }
                                        }
                                }


                                //}//for

                }//command mode

        }
}

}
int set_data(char *in_file){
        int i,j;
        char *c,*p,*t;
        static char buf[1024];
        static char str[1024];
        int len;
        static FILE  *fp=NULL;
        int x,y;
        char *ret;

        if(fp == NULL){
                fp = fopen(in_file, "r");

#ifdef INVD
                for(i=0; i<MAXIDTBL; i++){
                        IDTBL3[i] = (i/2);
                        IDTBL4[i] = (i/3) + (i%3);
                        IDTBL5[i] = (i/4) + (i%4)/2;
                        IDTBL6[i] = (i/5) + (i%5)/3 + ((i%5)%3);
                }
#endif

        }
        if(fp == NULL){
                printf("ERR: cant open [%s]\n",in_file);
                exit(0);
        }

        while(1){
                ret = fgets( buf, 1023, fp );
                if(ret == NULL){
                        return 0;
                }

                if(strchr(buf,',')){
                        break;
                }
        }


        len = strlen(buf);
        buf[len-1] = 0;

        if(strstr(buf,"input ")){
                strcpy(str,&buf[6]);
                mondai = &buf[6];
        } else {
                strcpy(str,buf);
                mondai = buf;
        }

        t=strchr(mondai,' ');
        if(t){
                *t++ = 0;
                kaitou = t;
                if((t =strchr(kaitou,' ')) != NULL){
                        *t = 0;
                }
        } else {
                kaitou = NULL;
        }

        // file format
        // [4,5,5G3486F7092C1ADJEHBI:not found in HanpukuShinka for Threshold:201]
        // [6,5,82935=174ABCD=RHTNJKFLI0PQSOGM ULDDRUULLULULLDRURRDDDLURDRDLLUURDRDRULDR]

        str[1] = 0;
        str[3] = 0;
        matrix_size_x = atoi(str);
        matrix_size_y = atoi(&str[2]);
        matrix_size = matrix_size_x * matrix_size_y;

        c = &str[4];

        t = strchr(c,' ');
        if(t){
                *t++ = 0;
                pre_result_string = t;
        } else {
                pre_result_string = NULL;
        }


        if(t){
                p = strchr(t,':');
        } else {
                p = NULL;
        }
        if(p){
                *p++ = 0;
                pre_result_threshold = atoi(p);
        } else {
                pre_result_threshold = 0;
        }


        for ( i = 0; i < matrix_size; i++ ){
                if(c[i] == '='){
                        c[i] = -2;
                } else if(c[i] >= 'A'){
                        c[i] = c[i] - 'A' + 9;
                } else {
                        c[i] = c[i] - '1';
                }
                Matrix.mval[i] = c[i];
                if(c[i] == -1){
                        Matrix.sp_pos = i;
                }
        }


        for(i=0;i<matrix_size;i++){
                x = i % matrix_size_x;
                y = i / matrix_size_x;
                Parity_omote2ura[i] = x*matrix_size_y+y;

                x = i % matrix_size_y;
                y = i / matrix_size_y;
                Parity_ura2omote[i] = x*matrix_size_x+y;
        }

        for(i=0;i<matrix_size;i++){
                j = Matrix.mval[Parity_ura2omote[i]];
                if(j == -1){
                        Matrix_Parity.mval[i] = j;
                } else if(j == -2){
                        Matrix_Parity.mval[i] = j;
                } else {
                        Matrix_Parity.mval[i] = Parity_omote2ura[j];
                }
        }



        if(matrix_size_x == 3) IDTBL1 = IDTBL3;
        if(matrix_size_x == 4) IDTBL1 = IDTBL4;
        if(matrix_size_x == 5) IDTBL1 = IDTBL5;
        if(matrix_size_x == 6) IDTBL1 = IDTBL6;

        if(matrix_size_y == 3) IDTBL2 = IDTBL3;
        if(matrix_size_y == 4) IDTBL2 = IDTBL4;
        if(matrix_size_y == 5) IDTBL2 = IDTBL5;
        if(matrix_size_y == 6) IDTBL2 = IDTBL6;

        set_m_distance();
        set_r_distance(&Matrix);

        make_harr(&Matrix);

        make_new_pos(&Matrix);


        return 1;
}

int main(int ac, char **av){
        char *in;
        int ret;
        int i,cnt;;

        if(ac < 3){
                printf("useage:cmd inputfile how [max_count]\n");
                exit(0);
        }

        in = av[1];
        if(ac >= 4){
                max_count = (long long)atoi(av[3]) * (long long)10000;
        } else {
                max_count = (long long)MAX_HANPUKU * (long long)10000;
        }



        haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
        if(haba_stack == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }

        hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
        if(hash_table == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }
        bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);

        Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);





        while(1){
                ret = set_data(in);
                if(ret == 0){
                        exit(0);
                }

                if(matrix_size_x < 3 || matrix_size_x > 6 || matrix_size_y < 3 || matrix_size_y > 6){
                        continue;
                }

                if(strcmp(av[2],"check") == 0){
                        check_pre_result_path();
                        continue;
                }

                if(strcmp(av[2],"sim") == 0){
                        simflg = 1;
                        sim();
                        continue;
                }

                if(kaitou){
                        for(cnt=0,i=0;kaitou[i];i++){
                                if(kaitou[i] != 'U' && kaitou[i] != 'L' && kaitou[i] != 'D' && kaitou[i] != 'R') cnt++;
                        }
                        if(cnt == 0){

                                printf("input %s %s\n", mondai,kaitou);
                                fflush(stdout);
                                continue;
                        }
                }


                if(strcmp(av[2],"md") == 0){
                        printf("%d\t%s\n",m_distance(),mondai);
                        continue;
                }
                printf("input %s ", mondai);
                fflush(stdout);

                if(strcmp(av[2],"hanpuku") == 0){
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"shurink") == 0){
                        if(ac >= 5){
                                shurink = atoi(av[4]);
                        } else {
                                shurink = 1;
                        }

                        if(ac >=6){
                                shurink_mask = atoi(av[5]);
                        } else {
                                shurink_mask = 0;
                        }
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"haba") == 0){
                        if(ac >= 5){
                                max_haba_stack = atoi(av[4]) * 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
                        } else {
                                max_haba_stack = 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
                        }

                        haba = 1;
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"step") == 0){
                        if(ac >= 5){
                                step_dist = atoi(av[4]);
                        } else {
                                step_dist = 0;
                        }
                        StepShinka();
                }

                if(strcmp(av[2],"matrix") == 0){
                        dump_matrix(&Matrix);
                        continue;
                }

        }
        exit(0);
}