import java.util.Scanner; import java.io.File; public class NinePuzzle{ //The total number of possible boards is 9! = 1*2*3*4*5*6*7*8*9 = 362880 public static final int NUM_BOARDS = 362880; /* SolveNinePuzzle(B) Given a valid 9-puzzle board (with the empty space represented by the value 0),return true if the board is solvable and false otherwise. If the board is solvable, a sequence of moves which solves the board will be printed, using the printBoard function below. */ public static boolean SolveNinePuzzle(int[][] B){ /* ... Your code here ... */ return false; } /* printBoard(B) Print the given 9-puzzle board. The SolveNinePuzzle method above should use this method when printing the sequence of moves which solves the input board. If any other method is used (e.g. printing the board manually), the submission may lose marks. */ public static void printBoard(int[][] B){ for (int i = 0; i  1; n--){ s = P[n-1]; P[n-1] = P[PI[n-1]]; P[PI[n-1]] = s; tmp = PI[s]; PI[s] = PI[n-1]; PI[n-1] = tmp; id += multiplier*s; multiplier *= n; } return id; } public static int[][] getBoardFromIndex(int id){ int[] P = new int[9]; int i,n,tmp; for (i = 0; i  0; n--){ tmp = P[n-1]; P[n-1] = P[id%n]; P[id%n] = tmp; id /= n; } int[][] B = new int[3][3]; for(i = 0; i  0){ //If a file argument was provided on the command line, read from the file try{ s = new Scanner(new File(args[0])); } catch(java.io.FileNotFoundException e){ System.out.printf("Unable to open %s ",args[0]); return; } System.out.printf("Reading input values from %s. ",args[0]); }else{ //Otherwise, read from standard input s = new Scanner(System.in); System.out.printf("Reading input values from stdin. "); } int graphNum = 0; double totalTimeSeconds = 0; //Read boards until EOF is encountered (or an error occurs) while(true){ graphNum++; if(graphNum != 1 && !s.hasNextInt()) break; System.out.printf("Reading board %d ",graphNum); int[][] B = new int[3][3]; int valuesRead = 0; for (int i = 0; i 1)?totalTimeSeconds/graphNum:0); } }

1 Programming Assignment The 9-puzzle consists of a square grid containing eight tiles, marked with the numbers 1 through 8. One of the spaces in the grid is empty.The initial state of the puzzle is the configuration below: This is considered to be the 'solved' state of the puzzle and is normally called the 'goal state'. The tiles on the board can be moved horizontally or vertically into the empty space to scramble the ordering of the board, as in the configuration below: 2 6 1 Programming Assignment The 9-puzzle consists of a square grid containing eight tiles, marked with the numbers 1 through 8. One of the spaces in the grid is empty.The initial state of the puzzle is the configuration below: This is considered to be the 'solved' state of the puzzle and is normally called the 'goal state'. The tiles on the board can be moved horizontally or vertically into the empty space to scramble the ordering of the board, as in the configuration below: 2 6