Implementing a C Program for NxN Sliding Tile Puzzle Solvability

This project provides a C code implementation to determine the solvability of an NxN sliding tile puzzle. The program analyzes the input puzzle and the desired end goal to check for solvability based on the number of inversions required to reach the goal state. It reads input from stdin, performs error checks on the puzzle entries, and validates if the puzzle forms a valid NxN configuration. The program then calculates the number of inversions and applies the solvability conditions based on the grid width and the position of the blank tile. The result, either "solvable" or "unsolvable," is printed to the output. The code includes functions to check for perfect squares, blank tile existence, number of entries, inversions, and blank position, ensuring a comprehensive solvability check. Desklib offers this assignment solution along with other study resources for students.

Solvability on NxN Puzzle
C code Program

Introduction
An NxN puzzle has in existence for generations. This type of puzzle requires that a play slide
values into a blank space until an end goal is achieved. The dimensions of the puzzle have to be
same; for example a 2x2, 3x3, and 4x4. Conventionally a sliding NxN puzzle uses numbers from
1 to (NxN) – 1, and a single empty space (Markovitch, 2014). For a 4x4 puzzle, the game’s board
has 15 tiles numbered 1 to 15, and an empty space. One can slide four adjacent tiles into the
empty space if the space is at the center for an 8 or 15-puzzle.
In the field of academics, the 8-puzzle (3x3) and the 15-puzzle (4x4) have over the years been
used as a testing domain for heuristic search techniques (Bischoff et al., 2013). Unlike other tests
that requires developing an algorithm to solve the puzzle, this report presents a program that
checks if a given puzzle is solvable, given a puzzle and an end-goal.
Solvability of an NxN puzzle
For any given puzzle, it is possible to check whether it can be solved or not without actually
solving it. For a 3x3 puzzle, checking its solvability requires one to determine the number of
inversions required to achieve a goal state. Theoretically, it’s impossible to solve a 3x3 puzzle if
the input state of the puzzle has an odd number of inversions. In this case, an inversion is formed
when a pair of the tiles in a puzzle is in reverse order; in reference to a goal state. For example if
the goal state is to have numbers; 1, 2, 3 in that order, then an inversion is required if the initial
state of the board has the numbers in the order; 2, 1, 3; here, (2, 1) forms an inversion.
Calculating number of inversions
Considering a board like the one below, if the board was to be laid out in a single row, then the
solvability of the board would be tested by first checking the number of inversions required. As
discussed, an inversion occurs when a higher valued tile precedes another tile with lower number
value.
Figure 1 and 2 Example of a 15-puzzle board.
In the above board, the number 12 at index 0 of the board requires 11 inversions to reach the end
goal; since numbers 1 – 11 comes before 12. To count all the inversions on the sample board
above, we would take one number after another and place it at the end goal position as we count
the number of moves or inversions; then total all the inversions.

To calculate the total inversions for figure 1 board, the procedure is as outlined below;
 Take the first number (12) and count number of inversions to place it at the right position
assuming the end goal is to have 1 to 15 in ascending order. This gives us 11 inversions
 Number 1 requires no inversions as it is the smallest
 Number 10 requires 8 inversions
 Number 7 requires 4 inversions
 Number 11 requires 6 inversions
 Number 4 requires 1 inversion
 The number 14 requires 6 inversions
 Number 5 requires 1 inversion
 Number 9 requires 3 inversions
 Number 5 requires 4 inversions
 Number 8 requires 2 inversions
 Number 13 requires 2 inversions
 And Finally Number 6 will require 1 inversion.
The total inversions are: 11 + 0 + 8 + 4 + 6 + 1 + 6 + 1 + 3 + 4 + 2 + 2 + 1 = 49
inversions
To determine if the above puzzle is solvable, we apply the conditions;
 For a puzzle whose grid width is odd, the puzzle is solvable if the inversions are even.
 For a puzzle with an even grid width, and the blank space falls on an even row – when
counted from the bottom – then the puzzle is solvable if the total number of inversions is
odd
 For a situation where the width is even, but the blank falls on an odd row – counted from
bottom – then the puzzle is solvable if the inversions are even
The solvability formula is therefore;
 “( (grid width odd) && (#inversions even) ) || ( (grid width even) && ((blank on odd
row from bottom) == (#inversions even)) )”
Implementation
The program developed in this assignment checks if a given puzzle is solvable or not. The
program reads the inputs from stdin and performs the evaluation. The basic flow of the program
is as follows;
 Start the program
 Read in the puzzle and the end goal
 Check for errors in the puzzle entries

o Check for whether the number of tiles forms an NxN puzzle
o Check if the puzzle has any missing value
o Check if the blank is present
o Check if other unwanted values are present
 If the entry has an error, print an error message into the output file
 else if no errors;
o check if solvable
o print out solvable into a file
1. #include "boardADT.c"
2.
3. typedef struct BOARD board;
4. int isPerfectSquare(int n);
5. int bExists(char *board);
6. int getNumberOfEntries(char *board);
7. int getInversions(char *board, int n ) ;
8. int findBPosition(char *board, int n) ;
9. int isSolvable(char *board, int n) ;
1. #define MAX_N 32
2.
3. struct
4. {
5. int N;
6. char *initialState;
7. char *endGoal;
8. } BOARD;
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4.
5.
6. int main(int argc, char *argv[]) {
7. printf("Welcome to programming");
8.
9. char *initialBoard;
10. char *endGoal;
11. size_t bufsize = 32;
12. size_t characters;
13.
14. initialBoard = (char *)malloc(bufsize * sizeof(char));
15. endGoal = (char *)malloc(bufsize * sizeof(char));
16. if( initialBoard == NULL)
17. {
18. perror("Unable to allocate buffer for the initial board state");
19. exit(1);
20. }

21. printf("\n");
22.
23. gets(initialBoard);
24. gets(endGoal);
25.
26. int inversitons = getInversions(initialBoard);
27. //total tiles for the board
28. int n = getNumberOfEntries(initialBoard);
29. //check if board is N by N
30.
31.
32. if (isPerfectSquare(n) == 1) {
33. //check if blank tile exists
34. if(bExists(initialBoard)){
35.
36. int xy = isSolvable(initialBoard, n) ;
37.
38. if(xy == 0){
39. printf("\nstart: %s \n",initialBoard);
40. printf("goal : %s \n",endGoal);
41. printf("solvable \n");
42. }else{
43. printf("\nstart: %s \n",initialBoard);
44. printf("goal : %s \n",endGoal);
45. printf("unsolvable \n");
46. }
47.
48.
49. }else{
50. printf("The board does not have a blank tile");
51. exit(1);
52. }
53. }else {
54. printf("The board is not an NxN board");
55. exit(1);
56. }
57. return 0;
58. }
59.
60.
61.
62. int getInversions3(int arr[],int n)
63. {
64. int i,j;
65. int inv_count = 0;
66. for ( i = 0; i < n - 1; i++)
67. {
68. for ( j = i + 1; j < n; j++)
69. {
70. // count pairs(i, j) such that i appears
71. // before j, but i > j.
72. if (arr[j] && arr[i] && arr[i] > arr[j])
73. inv_count++;
74. }
75. }
76. return inv_count;
77. }
78.
79.
80.
81.

82.
83. /**
84. This function checks if a board in an NxN board
85. it returns 1 if the board is a perfect square
86. or 0 otherwise
87. */
88. int isPerfectSquare(int n)
89. {
90. double a = sqrt(n);
91. double c = a * a ;
92.
93. if(c == n){
94. return 1;
95. }
96.
97. return 0;
98. }
99.
100. /**
101. * The function checks if b exists in a string
102. that represents the board
103. */
104. int bExists(char *board){
105. int n=1,i=0;
106.
107. for(i=0;i<=strlen(board);i++)
108. {
109. if(board[i] =='b'){
110. return 1;
111. }
112.
113. if(board[i]=='\0')
114. break;
115. }
116. return 0;
117. }
118.
119.
120. /**
121. * This functions takes in the string
122. and calculates the number of values in the string
123. */
124. int getNumberOfEntries(char *board)
125. {
126. int n=1,i=0;
127.
128. for(i=0;i<=strlen(board);i++)
129. {
130. if(board[i]!=' '){
131.
132. }
133. else{
134. n++;
135. }
136. if(board[i]=='\0')
137. break;
138. }
139. return n;
140. }
141.
142.

143. int myinversitions (char *board, int n){
144.
145. int i, j;
146. int inv_count = 0 ;
147.
148. for(i = 0; i < strlen(board); i++){
149. for ( j = i + 1; j < strlen(board); j++)
150. {
151.
152.
153. }
154. }
155.
156. }
157.
158. int getInversions(char *board, int n )
159. {
160. int i,j;
161. int inv_count = 0;
162. for (i = 0; i < n; i++)
163. {
164. for ( j = i + 1; j < n; j++)
165. {
166. // count pairs(i, j) such that i appears
167. // before j, but i > j.
168.
169. if (board[j] && board[i] && board[i] > board[j])
170. inv_count++;
171. }
172. }
173. return inv_count;
174. }
175.
176.
177. int findBPosition(char *board, int n)
178. {
179. int i;
180. int N = (int)sqrt(n);
181. // start from bottom-right corner of matrix
182. for ( i = N - 1; i >= 0; i--)
183. if (board[i] == 'b')
184. return N - i;
185. }
186.
187.
188. int isSolvable(char *board, int n)
189. {
190. int N = (int)sqrt(n);
191. int invCount = getInversions(board, n ) ;
192. // If grid is odd, return 1 if inversion
193. // count is even.
194. if (N & 1)
195. return !(invCount & 1);
196.
197. else // grid is even
198. {
199. int pos = findBPosition(board, n);
200. if (pos & 1)
201. return !(invCount & 1);
202. else
203. return invCount & 1;

204. }
205. }
Testing:

References
Bischoff, B., Nguyen-Tuong, D., Markert, H., & Knoll, A. (2013, November). Solving the 15-
Puzzle Game Using Local Value-Iteration. In SCAI (pp. 45-54).
Markovitch, S. (2014), Selective Experience: Generating Solvable Problems with Increasing
Levels of Difficulty.