Input and output files: Your program will read in the values for the initial state and goal state from a text file that contains $23$ lines as shown in Figure $2$ below. Lines $1$ to $11$ contain the tile patterns for the three layers of the initial state, with the layers separated by blank lines. Line $12$ is a blank line. Lines $13$ to $23$ contain the three layers of the goal state, with the layers separated by blank lines. n and m are integers that range from $0$ to $26,$ representing the blank position $(0)$ and the tile numbers $(1-26.)$

Your program will produce an output file that contains $28$ lines as shown in Figure $2$ below. Lines $1$ to $23$ contain the tile patterns for the initial state and goal state. You can simply copy lines $1$ to $23$ from the input file to the output file. Line $24$ is a blank line. Line $25$ is the depth level d of the

CS $6613$ Fall $2023$

Project $1$: $26-$Puzzle Problem E$.$ K$.$ Wong

shallowest goal node as found by the A$*$ algorithm $($assume the root node is at level $0.)$ Line $26$ is the total number of nodes N generated in your tree $($including the root node.$)$ Line $27$ contains the solution $($a sequence of actions from root node to goal node$)$ represented by A$$s$.$ The A$$s are separated by blank spaces. Each A is a character from the set $\{$E$,$ W$,$ N$,$ S$,$ U$,$ D$\},$ representing the East, West, North, South, Up and Down movements of the blank position. Line $28$ contains the f$($n$)$ values of the nodes along the solution path, from the root node to the goal node, separated by blank spaces. There should be d number of A values in line $27$ and d$+1$ number of f values in line $28.$

Testing your program: Three input files will be provided on Brightspace for you to test your program. All input files are solvable; i$.$e$.,$ they have solutions.

Recommended languages: Python, C$++/$C or Java. If you would like to use a different language, send me an email first.

Submit on Brightspace:

$$

Your source code file. Put comments in your source code to make it easier for someone else to read your program. Points will be taken off if you do not have comments in your source code.

$$

The output files generated by your program for the input test files.

$$

A PDF file that contains instructions on how to run your program. If your program requires compilation, instructions on how to compile your program should also be provided. Also, copy and paste your outputs and your source code onto the PDF file $($to make it easier for us to grade your project.$)$ This is in addition to the source code file and output files that you have to hand in separately, as described in items $(1)$ and $(2)$ above.

If you work in a team of two, only one partner needs to submit but please write both partners$$ names on the source code and the PDF report.