8パズル
C++のプログラミングの勉強をしています。
ネットなどを利用して勉強してるところなんですが、わからないところがあります。
8パズルの探索プログラムなんですがネットで見つけたものは初期値が最初から入ってるものでした。
自分で入力して実行したいのですがそれがうまくいきません。
読み込んでるつもりなのですがメモリに記憶されてないみたいです。
変数がメイン文の中にない場合の入力がわかってないからできないのだと思います。
どなたか下のプログラムを最初に自分で値を入力する方法を教えていただけないでしょうか？？
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define GOAL 2
#define SIZE 9
/* 状態数 (9! / 2) */
#define MAX_STATE 181440
/* 隣接リスト */
const char adjacent[SIZE][5] = {
1, 3,-1,-1,-1,
0, 4, 2,-1,-1,
1, 5,-1,-1,-1,
0, 4, 6,-1,-1,
1, 3, 5, 7,-1,
2, 4, 8,-1,-1,
3, 7,-1,-1,-1,
4, 6, 8,-1,-1,
5, 7,-1,-1,-1,
};
/* キュー */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
/* 同一局面チェックテーブル */
char check_table[MAX_STATE * 2];
/* 初期状態 */
char init_state[SIZE] = {
8, 6, 7, 2, 5, 4, 3, 0, 1
};
char final_state[SIZE] = {
1, 2, 3, 4, 5, 6, 7, 8, 0
};
/* 結果を出力 */
void print_answer( int n )
{
int i, j;
if( n != 0 ) print_answer( prev_state[n] );
for( i = 0; i < 3; i++ ){
for( j = 0; j < 3; j++ ){
printf("%d ", state[n][i * 3 + j] );
}
printf("\n");
}
printf("\n");
}
/* 番号に変換 */
int change_number( char *board )
{
char work[SIZE];
static int fact_table[SIZE] = {
40320, 5040, 720, 120, 24, 6, 2, 1, 0,
};
int j, k, value = 0;
memcpy( work, board, SIZE );
for( j = 0; j < SIZE - 1; j++ ){
value += fact_table[j] * work[j];
for( k = j + 1; k < SIZE; k++ ){
if( work[j] < work[k] ) work[k]--;
}
}
return value;
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1;
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_postion[0] = 7;
prev_state[0] = -1;
check_table[ change_number( init_state ) ] = TRUE;
check_table[ change_number( final_state ) ] = GOAL;
/* キューにデータがある間繰り返す */
while( front < rear ){
int s = space_postion[front];
int i, k, n;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
state[rear][s] = state[rear][n];
state[rear][n] = 0;
space_postion[rear] = n;
prev_state[rear] = front;
k = change_number( state[rear] );
if( check_table[k] == GOAL ){
/* 発見 */
print_answer( rear );
printf("状態数 %d 個\n", rear );
return;
} else if( !check_table[k] ){
/* キューに登録 */
check_table[k] = TRUE;
rear++;
}
}
front++;
}
}
int main()
{
int start, end;
/*
* 静的変数が 0 に初期化される場合は不用だが
* 初期化することは悪いことではない。
*/
memset( check_table, 0 , MAX_STATE * 2 );
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
お礼
回答ありがとうございます。 悔しいのは直線が10本になる置き方そのものはそれほど難しく ないのに、10本が最大だという証明ができない事です。 もしかすると発見が非常に困難ではあるが直線が11本以上になる 置き方があるのでしょうか？
補足
どうも回答は見当たらない様なので、一旦この質問は締め切りと致します。 ありがとうございました。