A sliding puzzle is a puzzle that challenges a player to slide flat pieces along certain routes on a k × k board to establish a certain end-configuration. The fifteen puzzle is the oldest type of sliding block puzzle and it was invented by Noyes Chapman in 1880s. It is played on a 4-by-4 grid with 15 square blocks labeled 1 through 15 and a blank square. The goal is to rearrange the blocks so that they are in order, using as few moves as possible. Blocks are permitted to be slid horizontally or vertically into the blank square. Search time for the goal state can be shortened by adding a priority for the direction of the search to proceed. A* algorithm is commonly used as an efficient alternative to find an answer to the sliding puzzle with the minimum number of steps.  you will implement A* algorithm to solve the sliding puzzle problem.

*Data Structures and Algorithm

Sliding (or k 2 − 1) puzzle using A* algorithm

A sliding puzzle is a puzzle that challenges a player to slide flat pieces along certain routes on a k × k board to establish a certain end-configuration. The fifteen puzzle is the oldest type of sliding block puzzle and it was invented by Noyes Chapman in 1880s. It is played on a 4-by-4 grid with 15 square blocks labeled 1 through 15 and a blank square. The goal is to rearrange the blocks so that they are in order, using as few moves as possible. Blocks are permitted to be slid horizontally or vertically into the blank square.

Search time for the goal state can be shortened by adding a priority for the direction of the search to proceed. A* algorithm is commonly used as an efficient alternative to find an answer to the sliding puzzle with the minimum number of steps.  you will implement A* algorithm to solve the sliding puzzle problem.

A* Algorithm 

A* (pronounced A-star) is an informed search algorithm, or a best-first search, formulated in terms of weighted graphs starting from a specific starting node of a graph, and find a path to the given goal node having the smallest cost (least distance, shortest time, etc.). A* maintains a tree of paths originating at the start node and extends those paths one edge at a time until its termination criterion is satisfied. At each iteration of its main loop, A* needs to determine which of its paths to extend based on: i) the cost of the path taken so far and ii)an estimate of the cost required to extend the path towards the goal Thus, A* selects the path that minimizes f(n) = g(n) + h(n), where • n is the next node on the path, • g(n) is the cost of the path from the start node to n, and • h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.

Files to work with:

starter.c

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

int main(int argc, char **argv)
{
FILE *fp_in,*fp_out;

fp_in = fopen(argv[1], "r");
if (fp_in == NULL){
 printf("Could not open a file.\n");
 return -1;
}

fp_out = fopen(argv[2], "w");
if (fp_out == NULL){
 printf("Could not open a file.\n");
 return -1;
}

char *line = NULL;
size_t lineBuffSize = 0;
ssize_t lineSize;
int k;

getline(&line,&lineBuffSize,fp_in);//ignore the first line in file, which is a comment
fscanf(fp_in,"%d\n",&k);//read size of the board
//printf("k = %d\n", k); //make sure you read k properly for DEBUG purposes
getline(&line,&lineBuffSize,fp_in);//ignore the second line in file, which is a comment

int initial_board[k*k];//get kxk memory to hold the initial board
for(int i=0;i<k*k;i++)
 fscanf(fp_in,"%d ",&initial_board[i]);
//printBoard(initial_board, k);//Assuming that I have a function to print the board, print it here to make sure I read the input board properly for DEBUG purposes
fclose(fp_in);

////////////////////
// do the rest to solve the puzzle
////////////////////

//once you are done, you can use the code similar to the one below to print the output into file
//if the puzzle is NOT solvable use something as follows
fprintf(fp_out, "#moves\n");
fprintf(fp_out, "no solution\n");

//if it is solvable, then use something as follows:
fprintf(fp_out, "#moves\n");
//probably within a loop, or however you stored proper moves, print them one by one by leaving a space between moves, as below
for(int i=0;i<numberOfMoves;i++)
 fprintf(fp_out, "%d ", move[i]);

fclose(fp_out);

return 0;

}
 

makefile

SOURCE := main.c
CC := gcc
TARGET := solve

all: $(TARGET)

$(TARGET): $(SOURCE)
$(CC) -o $(TARGET) $(SOURCE)

clean:
rm -f $(TARGET)

3boardEasy.txt

#k
3
#initial state
1 0 3 4 2 6 7 5 8 

3boardEasyOut.txt

moves
2 5 8 

3boardHard.txt

#k
3
#initial state
1 2 8 4 5 0 7 6 3 
 

3boardHardOut.txt

#moves
8 2 5 8 3 6 8 5 2 3 6