Sliding Puzzle

File name must be puzzle.c

A 15 Puzzle game is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The object of the puzzle is to place the tiles in order by making sliding moves that use the empty slot.

For example initial board might look like this: see image.

For example initial board might look like this: see image.

In this assignment you are asked to write a program for playing a 15 puzzle game. The game consists of a 4 by 4 board which contains 15 numbers and one empty slot represented by -1 value(Note: When the board is displayed to the user your program should display underscore character'' for the empty slot instead of the -1 value). The initial state of the board is provided as an input to the program. Afterwards, the user can interact with the program through four directional commands "up", "down", "left", and "right" in addition to the "exit" command to end the game. The four directional input commands determine the direction in which the empty slot should move in the game. After each command from the user your program should display the following information:

• The current state of the game board displayed exactly the same way as shown in the example interaction section.
• The number of tiles that are out of position (this count does not include the missing tile).

Your program should continue running as long as the puzzle is not solved or the "exit" command is entered by the user. When the puzzle is solved the program should congratulate the player and end the game. Note: if the initial state entered by the user as already solved board you program should end.

Your program should also alert the user in case of an invalid move or an invalid command.

Your program should continue running as long as the puzzle is not solved or the "exit" command is entered by the user. When the puzzle is solved the program should congratulate the player and end the game.

Note: if the initial state entered by the user as already solved board you program should end.

Your program should also alert the user in case of an invalid move or an invalid command.

An invalid move happens in the case where the empty slot can not be moved in the requested direction because it is outside the bounds of the game board. For example: If the game board look like the following then the "right" command results in an invalid move:

4 1 2 3
5 6 7 11
8 9 10 _
12 13 14 15

In this case the program should display the message "Invalid Move!".

An invalid command is any command the is not "up", "down", "left", "right" or "exit".

You program should at least implement the following:

• void scan_board(int board[SIZE][SIZE])
  • Reads the initial board state from user.
• void print_board (int board[SIZE][SIZE])
  • Prints the game board given as the input parameter.
• int update_board (const char command[], int board[SIZE][SIZE])
  • Updates the board state based on the command.
  • Returns 1 if the update was successful, returns 0 otherwise.
• int check_state(int board[SIZE][SIZE])
  • Checks if the given board is solved.
  • Returns 0 if the given board is solved, otherwise returns the number of tiles that are out of position.

You can have other function in addition to the ones listed above.

Example Interaction 1:

Enter initial board state
1 2 3 4
5 6 7 8
9 10 15 11
13 14 -1 12
1 2 3 4
5 6 7 8
9 10 15 11
13 14 _ 12
Number of tiles out of position: 3
Make a move: up
1 2 3 4
5 6 7 8
9 10 _ 11
13 14 15 12
Number of tiles out of position: 2
Make a move: left
1 2 3 4
5 6 7 8
9 _ 10 11
13 14 15 12
Number of tiles out of position: 3
Make a move: right
1 2 3 4
5 6 7 8
9 10 _ 11
13 14 15 12
Number of tiles out of position: 2
Make a move: right
1 2 3 4
5 6 7 8
9 10 11 _
13 14 15 12
Number of tiles out of position: 1
Make a move: down
Final board state
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _
You Won!

Example Interaction 2:

Enter initial board state
1 2 3 4
5 6 7 8
9 10 15 11
13 14 -1 12
1 2 3 4
5 6 7 8
9 10 15 11
13 14 _ 12
Number of tiles out of position: 3
Make a move: down
Invalid Move!
1 2 3 4
5 6 7 8
9 10 15 11
13 14 _ 12
Number of tiles out of position: 3
Make a move: up
1 2 3 4
5 6 7 8
9 10 _ 11
13 14 15 12
Number of tiles out of position: 2
Make a move: right
1 2 3 4
5 6 7 8
9 10 11 _
13 14 15 12
Number of tiles out of position: 1
Make a move: hey
Invalid Command!
1 2 3 4
5 6 7 8
9 10 11 _
13 14 15 12
Number of tiles out of position: 1
Make a move: right
Invalid Move!
1 2 3 4
5 6 7 8
9 10 11 _
13 14 15 12
Number of tiles out of position: 1