I have C++ code that is trying to solve building and implementing a sliding block problem. Here is the Assignment: Part 1 Sliding Brick Puzzle Many of you might have played one or another version of the "sliding brick puzzle" (SBP). In this assignment you will just have to create data structures and functions to represent the game state, and perform the various needed operations such as: determining the set of valid moves, execute the moves or determine whether we have solved the puzzle. A sliding brick puzzle is played on a rectangular w by h board (w cells wide and h cells tall). Each cell in the board can be either free, have a wall, or be the goal. On top of the board (over some of the free cells) there is a set of solid pieces (or bricks) that can be moved around the board. One of the bricks is special (the master brick). A move consists of sliding one of the bricks one cell up, down, left or right. Notice that bricks collide with either walls or other bricks, so we cannot move a brick on top of another. Bricks can only slide, they cannot rotate nor be flipped. To solve the puzzle, we have to find a sequence of moves that allows you to move the master brick on top of the goal cell(s). No other pieces are allowed to be placed on top of the goal cell(s). Here is an illustration of a particular configuration of a SBP (but if you still do not understand how the game works, just see this video, or play the game at one of the links above). Complete this assignment in C/C++: 1.A: State representation In this task, you will write code to represent the game state, load a game state from disk, and display a game state in the screen. Depending on the programming language you choose, you will have to create a class (C++) or just a set of functions (C) for completing this task. We will represent the game state as an integer matrix, as shown in this example: The matrix will have the same dimensions as the game board, and each position in the matrix has the following meaning: -1: represents the goal 0: means that the cell is empty 1: means that there is a wall 2: means that the master brick is on top of this cell any number higher or equal than 3: represents each of the other bricks Thus, as you can see, each piece in the board is assigned an integer: the master brick is assigned number 2, and the other bricks are assigned numbers starting from 3. Write a function that allows you to load a game state from disk. The input to the function should be just the name of the file. The file format that you have to use is the following: w,h, Row 1 of the matrix with values separated by commas, ... Row h of the matrix with values separated by commas, You can use the four included files as examples: SBP-level0.txt, SBP-level1.txt, SBP- level2.txt, SBP-level3.txt. Write a function that outputs the game state on the screen. For example, if you load the file SBP-level0.txt, the display state function must output the following to the screen (pay attention to spaces and newlines) 5,4, 1,-1,-1,1,1, 1,0,3,4,1, 1,0,2,2,1, 1,1,1,1,1, Write a function that clones a state. That is that returns a separate state that is identical to the original one. 1.B: Puzzle Complete Check Write a function that returns true if a given state represent a solved puzzle (i.e. if the master brick is on top of the goal). Notice that checking this is very easy, since you only have to go over the matrix, and see if there is any cell with the value -1. If there is, that means that the puzzle is not solved, if there is not, then the puzzle is solved (since only the master brick can cover the goal cells). For example, your function should return false with SBP-level0.txt, but true with SBP- level0-solved.txt 1.C: Move Generation Since each piece has a unique integer identifier, we will represent moves as a pair (piece,direction). Each piece can only move one cell at a time, in any of the four directions. For example a possible move in the following board is (10,down): Write a function that, given a state and a piece, returns a list of all moves the piece can perform (notice that the list can be empty). If you are using C++, define a class and, if using C, a struct to represent a "move". Feel free to encode the direction (up, down, left, right) however you want. For example, you can use a character to represent direction ('u','d','l','r'), or an integer. That is up to you. Write a function that, given a state, returns all moves that can be performed on a board (that is, the union of the moves that each individual piece can perform). Implement a function 'applyMove' that, given a state and a move, performs the move in that state. Implement a function 'applyMoveCloning' that, given a state and a move, returns a new state, resulting from applying the move (i.e. first clones the state, and then applies the move). 1.D: State Comparison Write a function that compares two states, and returns true if they are identical, and false if they are not. Do so using the simplest possible approach: just iterate over each position in the matrix that represents the state, and compare the integers one by one. If they are all identical, the states are identical, otherwise they are not. 1.E: Normalization Notice that the previous state comparison function has a problem. Consider the following two states: The previous function will consider these two states as different. However, it's quite obvious that the states are equivalent. In order to solve this problem, we are going to define a normal form for a state: If we give an index to each cell on the board starting from the top-left corner and going down row by row from left to right (top-left corner has index 0, the cell right next to it has index 1, etc.), then we can assign an index I(b) to a brick b, as the smallest index of the cells covered by b. Now, a state is in normal form if, for any two bricks (that are not the master brick) with numbers n and m such that n < m, it holds that I(n) < I(m). Write a function that, given a state, transforms it into normal form. See the expected effect of this function in this image: Notice that this is simpler than it seems. It can be done with the following algorithm: int nextIdx = 3; for(i = 0;i < h;i++) { for(j = 0;j < w;j++) { if (matrix[j][i]==nextIdx) { nextIdx++; } else if (matrix[j][i] > nextIdx) { swapIdx(nextIdx,matrix[j][i]); nextIdx++; } } } Where the swapIdx function is: swapIdx(int idx1,int idx2) { for(i = 0;i < h;i++) { for(j = 0;j < w;j++) { if (matrix[j][i]==idx1) { matrix[j][i]=idx2; } else if (matrix[j][i]==idx2) { matrix[j][i]=idx1; } } } } This normalization function will be very useful in the following assignments to compare game states, and see if they are equivalent or not. You can test if your version works with this state SBP-test-not-normalized.txt. Make sure you obtain the same result as in the figure above. 1.F: Random Walks Write a function that, given a state and a positive integer N, performs the steps following: 1) generates all moves that can be executed on the board in its current state, 2) selects one at random, 3) executes it, 4) normalizes the resulting game state, 5) if we have reached the goal, or if we have executed N moves, stops; otherwise, goes back to step (1). Please print both the move and the game state on screen after each iteration of the method. The required output format is discussed below. Part 2 Using the code you wrote for part 1, write: A function that solves a given sliding bricks puzzle using a breadth-first search. A function that solves a given sliding bricks puzzle using a depth-first search. A function that solves a given sliding bricks puzzle using an iterative deepening search Notice that the search space is a graph, so you will have to keep track of all the states visited so far, and make sure your algorithm does not get stuck in loops. When the solution is found, it should be printed to the screen. Print the list of moves required to solve the state, and the final state of the puzzle, for example (pay attention to spaces and newlines): (2,left) (4,down) (3,right) (2,up) (2,up) 5,4, 1,2,2,1,1, 1,0,0,3,1, 1,0,0,4,1, 1,1,1,1,1, Main Function Write a main function that, when the program is run, calls the necessary functions you wrote above in order to accomplish the following: 1. Load the file SBP-level0.txt from the current directory and execute a random walk from 1.F with N=3. The output must be of the form (pay attention to spaces and newlines): 5,4, 1,-1,-1,1,1, 1,0,3,4,1, 1,0,2,2,1, 1,1,1,1,1, (2,left) 5,4, 1,-1,-1,1,1, 1,0,3,4,1, 1,2,2,0,1, 1,1,1,1,1, (2,right) 5,4, 1,-1,-1,1,1, 1,0,3,4,1, 1,0,2,2,1, 1,1,1,1,1, (3,left) 5,4, 1,-1,-1,1,1, 1,3,0,4,1, 1,0,2,2,1, 1,1,1,1,1, 2. Load file SBP-level1.txt from the current directory and display to the screen the solution obtained using breadth-first search in the format specified at the beginning of the Part 2 section, followed by a line of the form: #nodes time length where #nodes is the number of nodes explored, time is the time the search took in seconds and fractions of seconds (e.g., 2.53 for 2 seconds and 53/100) and length is the length of the solution found. 3. Display to the screen the solution for SBP-level1.txt obtained using depth-first search in the format specified at the beginning of the Part 2 section, followed by the line that shows number of nodes explored, time taken and length of the solution. 4. Display to the screen the solution for SBP-level1.txt obtained using iterative deepening search in the format specified at the beginning of the Part 2 section, followed by the line that shows number of nodes explored, time taken and length of the solution. IMPORTANT: write all of the code above to be run from command line and to display its output to the console. Do not create any graphical user interfaces and do not ask the user for any input. To help you with testing, additional files have been provided. Your functions will likely be able to handle SBP- level2.txt, SBP-level3.txt. Using these search strategies, it is unlikely that your program will handle puzzles much larger than those (in next assignment, you will implement much better strategies). In case you want to test out the limits of your program, you can use these more complex puzzles: SBP- bricks-level1.txt, SBP-bricks-level2.txt, SBP-bricks-level3.txt, SBP-bricks-level4.txt, SBP- bricks-level5.txt, SBP-bricks-level6.txt, SBP-bricks-level7.txt. Extra Credit Implement A* search What to Submit All homework for this course must be submitted using Bb Learn. Do not e-mail your assignment to a TA or Instructor. If you are having difficulty with your Bb Learn account, you are responsible for resolving these problems with a TA, an Instructor, or someone from IRT, before the assignment is due. If you have any doubts, complete your work early so that a TA or someone from IRT can help you if you have difficulty. For this assignment, you must submit: Your C/C++ source code, and written documentation for your program, including compilation and execution instructions. The source code must include a Makefile file written for use on tux. Running make must produce an executable named hw1 in the directory where Makefile is. hw1 must implement the main function and associated functions/methods described above. An executable called hw1 that runs on tux. A plain text file called output-hw1.txt and generated on tux (very important!) which shows the output your program generates when run. You can easily generate this file using redirection, e.g.: ./hw1 > output-hw1.txt. Use a compression utility to compress your files into a single file (with a .zip extension) and upload it to the assignment page. Important: Almost all of the rest of your assignments will build on top of this assignment. So, make sure that you do a solid job with its design and implementation. Otherwise, you will have problems in the future. So Here is the Code I have so far: #include #include #include // define constants #define GOAL_CELL -1 #define EMPTY_CELL 0 #define WALL_CELL 1 #define MASTER_CELL 2 // define the possible direction #define TOP 0 #define RIGHT 1 #define BOTTOM 2 #define LEFT 3 // struct that defines the moves of the given piece from the current i,j position struct PossibleMovesOfBrick { // to store number of possible moves int numPossibleMoves; // to store current location int i,j; // to store brick number int brickNumber; // to store the moves int moves[4]; int brickWidth; int brickHeight; }; // to check if this passed i,j value is inside the puzzle int isValidLocation(int i,int j,int w,int h) { if( i>=0 && j>=0 && i return 1; return 0; } // to get the next token int getNextToken(FILE ** fp, char delimiter) { // array to store the number read char number[10]; int index = 0; char c; while( (c=fgetc(*fp)) != delimiter ) { // conintue if space if( isspace(c)) continue; // if end of file return if( c == EOF ) { // the the number[ index ] = '\0'; // get the integer from the char array int i = atoi(number); return i; } // add character number[ index++ ] = c; } // add end of string character number[ index ] = '\0'; // get the integer from the char array int i = atoi(number); return i; } // to read the puzzle into the 2D array passed void readPuzzle(char * filename, int *** puzzle, int * width, int * height ) { // open the file FILE * fp= fopen(filename,"r"); // read width and height int w = getNextToken(&fp,','); *width = w; // the height int h = getNextToken(&fp,','); *height = h; //printf("w : %d h : %d ",w,h); // create puzzle , h is the number of rows *puzzle = (int **)malloc(sizeof(int *) * h); // give memory to each row int i; for( i=0; i { (*puzzle)[i] = (int *)malloc(sizeof(int) * w); } // populate the array int j; for( i=0; i { for( j=0; j { // store the next token in the 2Darray (*puzzle)[i][j] = getNextToken(&fp,','); } } // close the file fclose(fp); } // method to display the board void displayGame(int ** puzzle, int w, int h) { // first, display width and height printf("%d,%d, ",w,h); // then the complete 2D array int j,i; for( i=0; i { for( j=0; j { // store the next token in the 2Darray printf("%d,",puzzle[i][j]); } // change line printf(" "); } } // to clone the state int ** clone(int ** puzzle, int w, int h) { int ** clonePuzzle = (int **)malloc(sizeof(int *) * h); // give memory to each row int i; for( i=0; i { clonePuzzle[i] = (int *)malloc(sizeof(int) * w); } // then the complete 2D array int j; for( i=0; i { for( j=0; j { // store the next token in the 2Darray clonePuzzle[i][j] = puzzle[i][j]; } } // return the clone return clonePuzzle; } // check if the puzzle solved // return 1 - for solved , 0 for not solved int isPuzzleComplete(int ** puzzle, int w, int h) { int j,i; for( i=0; i { for( j=0; j { // if there exists a goal cell - puzzle is not solved if( puzzle[i][j] == GOAL_CELL ) return 0; } } // if no goal cell ,puzzle solved return 1; } // get size of brick void getBrickSize(int i,int j,int w,int h, int * width, int * height,int ** puzzle) { int jj = j; int brickNumber = puzzle[i][j]; while( isValidLocation(i,jj,w,h) && puzzle[i][jj] == brickNumber ) { jj++; } int ii = i; while( isValidLocation(ii,j,w,h) && puzzle[ii][j] == brickNumber ) { ii++; } *width = (jj-j); *height = (ii-i); } // method that return possible moves from the current location void getMovesFromThisLocation(int i,int j,int w,int h, int ** puzzle,struct PossibleMovesOfBrick * m) { // set i,j nand brick value for m m->brickNumber = puzzle[i][j]; m->i = i; m->j = j; m->numPossibleMoves = 0; // check for top if( isValidLocation( i-1,j,w,h) ) { // if thje top of this location is a valid cell and empty - top move is possible if( puzzle[i-1][j] == EMPTY_CELL ) { // add this move to moves m->moves[ m->numPossibleMoves ] = TOP; m->numPossibleMoves += 1; } } // check for right if( isValidLocation( i,j+1,w,h) ) { // if the right of this location is a valid cell and empty - right move is possible if( puzzle[i][j+1] == EMPTY_CELL ) { // add this move to moves m->moves[ m->numPossibleMoves ] = RIGHT; m->numPossibleMoves += 1; } } // check for bottom if( isValidLocation( i+1,j,w,h) ) { // if the bottom of this location is a valid cell and empty - bottom move is possible if( puzzle[i+1][j] == EMPTY_CELL ) { // add this move to moves m->moves[ m->numPossibleMoves ] = BOTTOM; m->numPossibleMoves += 1; } } // check for left if( isValidLocation( i,j-1,w,h) ) { // if the left of this location is a valid cell and empty - left move is possible if( puzzle[i][j-1] == EMPTY_CELL ) { // add this move to moves m->moves[ m->numPossibleMoves ] = LEFT; m->numPossibleMoves += 1; } } } int isMovePossible(int i,int j,int w,int h, int ** puzzle,int move) { if( move == TOP ) { if( isValidLocation( i-1,j,w,h) ) { // if the TOP of this location is a valid cell and empty - TOP move is possible if( puzzle[i-1][j] == EMPTY_CELL ) { return 1; } } } else if( move ==RIGHT ) { if( isValidLocation( i,j+1,w,h) ) { // if the RIGHT of this location is a valid cell and empty - RIGHT move is possible if( puzzle[i][j+1] == EMPTY_CELL ) { return 1; } } } else if( move == BOTTOM ) { if( isValidLocation( i+1,j,w,h) ) { // if the BOTTOM of this location is a valid cell and empty - BOTTOM move is possible if( puzzle[i+1][j] == EMPTY_CELL ) { return 1; } } } else if( move ==LEFT ) { if( isValidLocation( i,j-1,w,h) ) { // if the left of this location is a valid cell and empty - left move is possible if( puzzle[i][j-1] == EMPTY_CELL ) { return 1; } } } return 0; }

int moveGenerated( int brickNumber, struct PossibleMovesOfBrick allMoves[],int numMovesGenerated ) { int i; for(i=0; i { if( allMoves[i].brickNumber == brickNumber ) return 1; } return 0; } int getAllPossibleMovesForTheState(int w,int h, int ** puzzle,struct PossibleMovesOfBrick allMoves[]) { // allMoves is an array of moves // allMoves size is total number of bricks with value > int numMovesGenerated = 0; int j,i; for( i=0; i { for( j=0; j { // no moves for wall or empty cell if( puzzle[i][j] < 2 ) continue; // get brick size int ww; int hh; getBrickSize(i,j,w,h,&ww,&hh,puzzle); if( moveGenerated( puzzle[i][j] ,allMoves,numMovesGenerated)) { continue; } if( hh==1 && ww==1 ) { // get all possible moves from this location struct PossibleMovesOfBrick move; getMovesFromThisLocation(i,j,w,h,puzzle,&move); allMoves[ numMovesGenerated++ ] = move; } else { // if brick size is greater than one struct PossibleMovesOfBrick move; move.i = i; move.j = j; move.brickNumber = puzzle[i][j]; move.numPossibleMoves = 0; move.brickHeight = hh; move.brickWidth = ww; int ii = i + hh - 1; int jj = j + ww - 1; int possible = 1; // check for top moves int k; for( k = j; k<=jj; k++) { if( !isMovePossible(i,k,w,h,puzzle,TOP)) { possible = 0; } } if( possible ) { move.moves[ move.numPossibleMoves ] = TOP; move.numPossibleMoves += 1; } // check for right move possible = 1; for( k = i; k<=ii; k++) { if( !isMovePossible(k,jj,w,h,puzzle,RIGHT)) { possible = 0; } } if( possible ) { move.moves[ move.numPossibleMoves ] = RIGHT; move.numPossibleMoves += 1; } possible = 1; // check for BOTTOM moves for( k = j; k<=jj; k++) { if( !isMovePossible(ii,k,w,h,puzzle,BOTTOM)) { possible = 0; } } if( possible ) { move.moves[ move.numPossibleMoves ] = BOTTOM; move.numPossibleMoves += 1; } // check for LEFT move possible = 1; for( k = i; k<=ii; k++) { if( !isMovePossible(k,j,w,h,puzzle,LEFT)) { possible = 0; } } if( possible ) { move.moves[ move.numPossibleMoves ] = LEFT; move.numPossibleMoves += 1; } if( move.numPossibleMoves > 0 ) allMoves[ numMovesGenerated++ ] = move; } } } return numMovesGenerated; } // for brick of size greater than 1, this will have to be called for all pieces of that brick void applyMove(int ** puzzle, int w, int h, struct PossibleMovesOfBrick moves, int move) { if( moves.brickWidth == 1 && moves.brickWidth == 1) { // get location of the pirece to movex int i = moves.i; int j = moves.j; int x = 0; int y = 0; // choose new location to move if( move == TOP ) { x = i - 1; y = j; printf("Move brick number %d TOP ",moves.brickNumber); } else if( move == RIGHT ) { x = i; y = j + 1; printf("Move brick number %d RIGHT ",moves.brickNumber); } else if( move == BOTTOM ) { x = i + 1; y = j; printf("Move brick number %d BOTTOM ",moves.brickNumber); } else if( move == LEFT ) { x = i; y = j - 1; printf("Move brick number %d LEFT ",moves.brickNumber); } // swap values int temp = puzzle[i][j]; puzzle[i][j] = puzzle[x][y]; puzzle[x][y] = temp; } else { int i = moves.i; int j = moves.j; int x = 0; int y = 0; if( move == TOP ) { int ii = i + moves.brickHeight - 1; int jj = j + moves.brickWidth - 1; int k; for( k = j; k<=jj; k++) { x = i-1; y = k; // swap values int temp = puzzle[i][k]; puzzle[i][k] = puzzle[x][k]; puzzle[x][k] = temp; } printf("Move brick number %d TOP ",moves.brickNumber); } if( move == RIGHT ) { int ii = i + moves.brickHeight - 1; int jj = j + moves.brickWidth - 1; int k; for( k = i; k<=ii; k++) { x = k; y = j+1; // swap values int temp = puzzle[k][j]; puzzle[k][j] = puzzle[k][y]; puzzle[k][y] = temp; } printf("Move brick number %d RIGHT ",moves.brickNumber); } if( move == BOTTOM ) { int ii = i + moves.brickHeight - 1; int jj = j + moves.brickWidth - 1; int k; for( k = j; k<=jj; k++) { x = i+1; y = k; // swap values int temp = puzzle[i][k]; puzzle[i][k] = puzzle[x][k]; puzzle[x][k] = temp; } printf("Move brick number %d BOTTOM ",moves.brickNumber); } if( move == LEFT ) { int ii = i + moves.brickHeight - 1; int jj = j + moves.brickWidth - 1; int k; for( k = i; k<=ii; k++) { x = k; y = j-1; // swap values int temp = puzzle[k][j]; puzzle[k][j] = puzzle[k][y]; puzzle[k][y] = temp; } printf("Move brick number %d LEFT ",moves.brickNumber); } } } int ** applyMoveCloning(int ** puzzle,int w,int h,struct PossibleMovesOfBrick moves, int move) { int ** cl = clone(puzzle,w,h); applyMove(cl,w,h,moves,move); return cl; } // method to compare to states int compareState(int ** stateA,int ** stateB,int w,int h) { int j,i; for( i=0; i { for( j=0; j { if( stateA[i][j] != stateB[i][j] ) return 0; } } return 1; } int getNumberOfBricks(int ** puzzle,int w,int h) { int max = 1; int i,j; for( i=0; i { for( j=0; j { if( puzzle[i][j] > max ) max = puzzle[i][j]; } } return max; }

void swapIdx(int ** puzzle,int h, int w,int idx1,int idx2) { int i,j; for(i = 0;i < h;i++) { for(j = 0;j < w;j++) { if (puzzle[j][i]==idx1) { puzzle[j][i]=idx2; } else if (puzzle[j][i]==idx2) { puzzle[j][i]=idx1; } } } } int ** normalize(int ** puzzle,int w,int h) { int nextIdx = 3; int i,j; for(i = 0;i < h;i++) { for(j = 0;j < w;j++) { if (puzzle[j][i]==nextIdx) { nextIdx++; } else if (puzzle[j][i] > nextIdx) { swapIdx(puzzle,h,w,nextIdx,puzzle[j][i]); nextIdx++; } } } return puzzle; } void randomWalk(int ** puzzle,int w,int h,int N) { int numBricks = getNumberOfBricks(puzzle,w,h); struct PossibleMovesOfBrick moves[ numBricks ]; int complete = 0; int i = 0; while( i< N ) { int numMoves = getAllPossibleMovesForTheState(w,h,puzzle,moves); int r = rand( ) % numMoves; applyMove(puzzle,w,h,moves[r],moves[r].moves[0]); puzzle = normalize(puzzle,w,h); displayGame(puzzle,w,h);

if( isPuzzleComplete(puzzle,w,h)) { complete = 1; break; } i++; } if( complete ) printf("Puzzle completed"); } int main(int argc,char *argv[]) { // to store the puzzle int ** puzzle = NULL; // to store width and height int w,h; readPuzzle(argv[1],&puzzle,&w,&h); displayGame(puzzle,w,h); randomWalk(puzzle,w,h,10); return 0; } I have to figure out why it is getting a segment error when I run it in the required Linux command line enviornment. Can anyone help me solve that and then figure out how to implement the part 2 requirement for depth first search and incorporate it into the program? I was looking at https://www.codeproject.com/articles/368188/ai-sliding-puzzle-solution-analyzer for how to do part 2 but I am just stuck. Any help with these issues would be great. code can be excuted how I do it with "./filename input.txt" as the linux command line. If it helps, here is a sample input file from a text file. 5,4, 1,-1,-1,1,1, 1,0,3,4,1, 1,0,2,2,1, 1,1,1,1,1,