|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <stdbool.h>
|
|
|
#include <string.h>
|
|
|
|
|
|
#define N 3 // ???????????????????3x3????
|
|
|
int i,j;
|
|
|
typedef struct Node {
|
|
|
int puzzle[N][N]; // ?洢??????????
|
|
|
struct Node* parent; // ?????????????????·??
|
|
|
int f, g, h; // A*???е? f, g, h ?
|
|
|
} Node;
|
|
|
|
|
|
// ?????μ??????
|
|
|
Node* createNode(int puzzle[N][N]) {
|
|
|
Node* newnode = (Node*)malloc(sizeof(Node));
|
|
|
for(i=0;i<N;i++){
|
|
|
for(j=0;j<N;j++){
|
|
|
newnode->puzzle[i][j]=puzzle[i][j];
|
|
|
}
|
|
|
}
|
|
|
newnode->parent=NULL;
|
|
|
newnode->f=0;
|
|
|
newnode->g=0;
|
|
|
newnode->h=0;
|
|
|
return newnode;
|
|
|
|
|
|
}
|
|
|
|
|
|
// ?????????????????
|
|
|
bool isSamePuzzle(int a[N][N], int b[N][N]) {
|
|
|
//相同则返回true,否则返回false
|
|
|
int flag=0;
|
|
|
for(i=0;i<N;i++){
|
|
|
for(j=0;j<N;j++){
|
|
|
if(a[i][j]!=b[i][j]){
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
void printPuzzle(int puzzle[N][N]) {
|
|
|
for (i = 0; i < N; i++) {
|
|
|
for (j = 0; j < N; j++) {
|
|
|
printf("%d ", puzzle[i][j]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
|
|
int heuristic(Node* current, Node* goal) {
|
|
|
int h = 0;
|
|
|
for (i = 0; i < N; i++) {
|
|
|
for (j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] != goal->puzzle[i][j] && current->puzzle[i][j] != 0) {
|
|
|
h++;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return h;
|
|
|
}
|
|
|
|
|
|
// ??????????????μ?????
|
|
|
Node* move(Node* current, int dir) {
|
|
|
int key_x, key_y;
|
|
|
for (i = 0; i < N; i++) {
|
|
|
for (j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] == 0) {
|
|
|
key_x = i;
|
|
|
key_y = j;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int new_x = key_x, new_y = key_y;
|
|
|
if (dir == 0) {
|
|
|
new_x--;
|
|
|
} else if (dir == 1) {
|
|
|
new_x++;
|
|
|
} else if (dir == 2) {
|
|
|
new_y--;
|
|
|
} else if (dir == 3) {
|
|
|
new_y++;
|
|
|
}
|
|
|
if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N) {
|
|
|
return NULL;
|
|
|
}
|
|
|
Node* newnode = createNode(current->puzzle);
|
|
|
newnode->puzzle[key_x][key_y] = current->puzzle[new_x][new_y];
|
|
|
newnode->puzzle[new_x][new_y] = 0;
|
|
|
return newnode;
|
|
|
}
|
|
|
// A*??????????·??
|
|
|
Node* AStar(Node* start, Node* goal) {
|
|
|
Node* OPEN[1000]; // ?????б???????洢?????????
|
|
|
Node* CLOSED[1000]; // ????б???????洢?????????
|
|
|
int OPEN_SIZE = 0; // ?????б????С
|
|
|
int CLOSED_SIZE = 0; // ????б????С
|
|
|
|
|
|
OPEN[0] = start; // ??????????????????б?
|
|
|
OPEN_SIZE = 1; // ?????б????С?????1
|
|
|
CLOSED_SIZE = 0; // ????б????С?????0
|
|
|
|
|
|
while (OPEN_SIZE > 0) {//??open?б????в???
|
|
|
|
|
|
int min_f = OPEN[0]->f;//???????С??f
|
|
|
int min_index = 0;
|
|
|
// ????????б??о?????Сf?????
|
|
|
for(i=0;i<OPEN_SIZE;i++)
|
|
|
{
|
|
|
if (OPEN[i]->f < min_f) {
|
|
|
min_f = OPEN[i]->f;
|
|
|
min_index = i;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
Node* current = OPEN[min_index]; // ?????????Сf?????
|
|
|
if(isSamePuzzle(current->puzzle,goal->puzzle))
|
|
|
{
|
|
|
return current;
|
|
|
}
|
|
|
// ???????????????????????????
|
|
|
OPEN_SIZE--;
|
|
|
|
|
|
//?????б????С??1???????????б??????????????
|
|
|
|
|
|
|
|
|
//????С f ?????????????б????β???????????????????б??С?
|
|
|
//???????????????б??????
|
|
|
Node* temp = OPEN[min_index];
|
|
|
OPEN[min_index] = OPEN[OPEN_SIZE];
|
|
|
OPEN[OPEN_SIZE] = temp;
|
|
|
|
|
|
//?????????????????б???????б???С??1
|
|
|
CLOSED[CLOSED_SIZE]=current;
|
|
|
CLOSED_SIZE++;
|
|
|
int key = 0;
|
|
|
// ??????????п????λ??
|
|
|
for (i = 0; i < N; i++) {
|
|
|
for (j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] == 0) {
|
|
|
key = i * N + j;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
// ???????????????????
|
|
|
int dir;
|
|
|
for (dir = 0; dir < 4; dir++) {
|
|
|
Node* new_node = move(current, dir);
|
|
|
|
|
|
if (new_node != NULL && !isSamePuzzle(new_node->puzzle, current->puzzle)) {
|
|
|
//????????g??f??h?
|
|
|
int gNew = current->g + 1;
|
|
|
int hNew = heuristic(new_node, goal);
|
|
|
int fNew = gNew + hNew;
|
|
|
|
|
|
bool in_OPEN = false;
|
|
|
int open_index = -1;
|
|
|
// ????????????????б???
|
|
|
int i1;
|
|
|
for (i1 = 0; i1 < OPEN_SIZE; i1++) {
|
|
|
if (isSamePuzzle(new_node->puzzle, OPEN[i1]->puzzle)) {
|
|
|
in_OPEN = true;
|
|
|
open_index = i1;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
bool in_CLOSED = false;
|
|
|
int i2;
|
|
|
for (i2 = 0; i2 < CLOSED_SIZE; i2++) {
|
|
|
if (isSamePuzzle(new_node->puzzle, CLOSED[i2]->puzzle)) {
|
|
|
in_CLOSED = true;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//???y???????????б???????????б???
|
|
|
if (!in_OPEN && !in_CLOSED) {
|
|
|
//??gNew??hNew??fNew????new_nod?????g??h??f????????丸??????????????
|
|
|
new_node->g=gNew;
|
|
|
new_node->h=hNew;
|
|
|
new_node->f=fNew;
|
|
|
new_node->parent=current;
|
|
|
// ????????new_node???????б????????б???С??1
|
|
|
OPEN[OPEN_SIZE]=new_node;
|
|
|
OPEN_SIZE++;
|
|
|
//printf("1");
|
|
|
}
|
|
|
//????????????????б??У????μ? f ???С????????????б????????????????
|
|
|
else if (in_OPEN && fNew < OPEN[open_index]->f) {
|
|
|
OPEN[open_index]=current;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return NULL; // ???
|
|
|
}
|
|
|
|
|
|
// ?????·??
|
|
|
void printPath(Node* final) {
|
|
|
if (final == NULL) {
|
|
|
return;
|
|
|
}
|
|
|
printPath(final->parent); // ?????·??
|
|
|
for (i = 0; i < N; i++) {
|
|
|
if (i%3==0){
|
|
|
printf("-------\n");
|
|
|
}
|
|
|
for (j = 0; j < N; j++) {
|
|
|
printf("%d ", final->puzzle[i][j]);
|
|
|
}
|
|
|
|
|
|
printf("\n");
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//int start[N][N] = {{2, 0, 3}, {1, 8, 4}, {7, 6, 5}};
|
|
|
//int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
|
|
|
|
|
|
int start[N][N] = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
|
|
|
int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
|
|
|
|
|
|
//int start[N][N] = {{2, 8, 3}, {1, 0, 4}, {7, 6, 5}};
|
|
|
//int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
|
|
|
Node* init = createNode(start);
|
|
|
Node* goal = createNode(target);
|
|
|
|
|
|
Node* final = AStar(init, goal);
|
|
|
if (final) {
|
|
|
printf("This problem has a solution:\n");
|
|
|
printPath(final); // ?????·??
|
|
|
} else {
|
|
|
printf("This problem has no solution??\n");
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
|
