#include <stdio.
h>
#include <stdlib.h>
#include <string.h>
#define ROWS 3
#define COLS 3
// Representation of the puzzle state
typedef struct {
int puzzle[ROWS][COLS];
} PuzzleState;
// Node structure to represent a state in the BFS search
typedef struct Node {
PuzzleState state;
struct Node* parent;
} Node;
// Function to print the puzzle state
void printPuzzle(const PuzzleState* state) {
for (int i = 0; i < ROWS; ++i) {
for (int j = 0; j < COLS; ++j) {
printf("%d ", state->puzzle[i][j]);
}
printf("\n");
}
printf("\n");
}
// Function to check if two puzzle states are equal
int isEqual(const PuzzleState* state1, const PuzzleState* state2) {
return memcmp(state1, state2, sizeof(PuzzleState)) == 0;
}
// Function to check if a puzzle state is the goal state (solved)
int isGoalState(const PuzzleState* state) {
static const PuzzleState goalState = {{{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}};
return isEqual(state, &goalState);
}
// Function to find the position of the blank tile (0)
void findBlank(const PuzzleState* state, int* row, int* col) {
for (int i = 0; i < ROWS; ++i) {
for (int j = 0; j < COLS; ++j) {
if (state->puzzle[i][j] == 0) {
*row = i;
*col = j;
return;
}
}
}
*row = -1;
*col = -1; // Blank not found
}
// Function to generate child states from the current state
void generateChildren(const PuzzleState* currentState, PuzzleState children[4]) {
int blankRow, blankCol;
findBlank(currentState, &blankRow, &blankCol);
// Possible moves: left, right, up, down
const int moves[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
for (int i = 0; i < 4; ++i) {
int newRow = blankRow + moves[i][0];
int newCol = blankCol + moves[i][1];
if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS) {
children[i] = *currentState;
children[i].puzzle[blankRow][blankCol] = currentState->puzzle[newRow]
[newCol];
children[i].puzzle[newRow][newCol] = 0;
}
}
}
// Function to perform Breadth-First Search
Node* bfs(const PuzzleState* initialState) {
Node* root = (Node*)malloc(sizeof(Node));
root->state = *initialState;
root->parent = NULL;
Node* queue[10000]; // Assuming a maximum of 10000 nodes
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
Node* current = queue[front++];
if (isGoalState(¤t->state)) {
return current; // Solution found
}
PuzzleState children[4];
generateChildren(¤t->state, children);
for (int i = 0; i < 4; ++i) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->state = children[i];
newNode->parent = current;
int j;
for (j = 0; j < rear; ++j) {
if (isEqual(&queue[j]->state, &newNode->state)) {
free(newNode); // Skip already visited state
break;
}
}
if (j == rear) {
queue[rear++] = newNode;
}
}
}
return NULL; // No solution found
}
// Function to print the solution path
void printSolutionReverse(Node* solutionNode) {
Node* current = solutionNode;
// Store the solution path in an array
Node* solutionPath[10000]; // Assuming a maximum of 10000 nodes
int pathLength = 0;
while (current != NULL) {
solutionPath[pathLength++] = current;
current = current->parent;
}
// Print the solution path in reverse order
for (int i = pathLength - 1; i >= 0; --i) {
printPuzzle(&solutionPath[i]->state);
}
}
int main() {
PuzzleState initialState;
printf("Enter the initial state of the puzzle (0 represents the blank tile):\
n");
for (int i = 0; i < ROWS; ++i) {
for (int j = 0; j < COLS; ++j) {
scanf("%d", &initialState.puzzle[i][j]);
}
}
Node* solutionNode = bfs(&initialState);
if (solutionNode != NULL) {
printf("Solution found:\n");
printSolutionReverse(solutionNode);
} else {
printf("No solution found.\n");
}
// Clean up memory
while (solutionNode != NULL) {
Node* temp = solutionNode;
solutionNode = solutionNode->parent;
free(temp);
}
return 0;
}
