How to implement this 9 puzzle to check it is solvable or not? Input data looks
ID: 3804669 • Letter: H
Question
How to implement this 9 puzzle to check it is solvable or not?
Input data looks like following
/* This template includes some testing code to help verify the implementation.
Input boards can be provided with standard input or read from a file.
To provide test inputs with standard input, run the program with
java NinePuzzle
To terminate the input, use Ctrl-D (which signals EOF).
To read test inputs from a file (e.g. boards.txt), run the program with
java NinePuzzle boards.txt
The input format for both input methods is the same. Input consists
of a series of 9-puzzle boards, with the '0' character representing the
empty square. For example, a sample board with the middle square empty is
1 2 3
4 0 5
6 7 8
And a solved board is
1 2 3
4 5 6
7 8 0
An input file can contain an unlimited number of boards; each will be
processed separately.
B. Bird - 07/11/2014
M. Simpson - 11/07/2015
*/
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 < 3; i++){
for (int j = 0; j < 3; j++)
System.out.printf("%d ",B[i][j]);
System.out.println();
}
System.out.println();
}
/* Board/Index conversion functions
These should be treated as black boxes (i.e. don't modify them, don't worry about
understanding them). The conversion scheme used here is adapted from
W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time,
Information Processing Letters, 79 (2001) 281-284.
*/
public static int getIndexFromBoard(int[][] B){
int i,j,tmp,s,n;
int[] P = new int[9];
int[] PI = new int[9];
for (i = 0; i < 9; i++){
P[i] = B[i/3][i%3];
PI[P[i]] = i;
}
int id = 0;
int multiplier = 1;
for(n = 9; n > 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 < 9; i++)
P[i] = i;
for (n = 9; n > 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 < 9; i++)
B[i/3][i%3] = P[i];
return B;
}
public static void main(String[] args){
/* Code to test your implementation */
/* You may modify this, but nothing in this function will be marked */
Scanner s;
if (args.length > 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 < 3 && s.hasNextInt(); i++){
for (int j = 0; j < 3 && s.hasNextInt(); j++){
B[i][j] = s.nextInt();
valuesRead++;
}
}
if (valuesRead < 9){
System.out.printf("Board %d contains too few values. ",graphNum);
break;
}
System.out.printf("Attempting to solve board %d... ",graphNum);
long startTime = System.currentTimeMillis();
boolean isSolvable = SolveNinePuzzle(B);
long endTime = System.currentTimeMillis();
totalTimeSeconds += (endTime-startTime)/1000.0;
if (isSolvable)
System.out.printf("Board %d: Solvable. ",graphNum);
else
System.out.printf("Board %d: Not solvable. ",graphNum);
}
graphNum--;
System.out.printf("Processed %d board%s. Average Time (seconds): %.2f ",graphNum,(graphNum != 1)?"s":"",(graphNum>1)?totalTimeSeconds/graphNum:0);
}
}
Explanation / Answer
//A* algorithm(nine puzzle problem)
**********************************************************************************************************************
astar.java
**************************************************************************************************************************
import java.io.*;
class astar
{
public static void main(String args[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int initial_state[][]=new int[3][3];
int to_print[][]=new int[3][3];//Prints the minimum cost solution
int to_swap[][]=new int[3][3];//Array on which transitions are done
int final_state[][]=new int[3][3];
System.out.println(" Enter the initial puzzle...");//Enter the initial puzzle state
int i,j,times=0;
char temp='';
char what_not_to_do='';//To keep track of the previous already taken state
char cur_mov='';//To store the current move
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
initial_state[i][j]=Integer.parseInt(br.readLine());
to_print[i][j]=initial_state[i][j];
to_swap[i][j]=initial_state[i][j];
}
}
System.out.println(" Enter the final puzzle...");//Enter the final puzzle state
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
final_state[i][j]=Integer.parseInt(br.readLine());
}
}
int parent_cost[]=new int[15];//cost of the best solutions
for(i=0;i<15;i++)
{
parent_cost[i]=99;
}
int p_index=0;
int row=0,col=0;
int again=0;
int loops=0;
int m,n,misplace,no_of_misplaced=0,steps,cost;
int same=0,ways;
steps=0;
cost=0;
no_of_misplaced=0;
int misplaced;
char open[]=new char[15]; // options in open list
char close[]=new char[15];//options in closed list
int fn_cost[]=new int[15];
char name[]=new char[15];
char parent_node[]=new char[15];
int parent_ind[]=new int[15];
//Initializing.......
for(i=0;i<15;i++)
{
open[i]='';
close[i]='';
fn_cost[i]=-1;
name[i]='';
parent_node[i]='';
parent_cost[i]=999;
}
open[0]='A';
parent_node[0]='A';
name[0]='A';
parent_ind[0]=0;
//Calculating the cost of the initial entered matrix
// initially to_swap[][] contains initial_state[][]
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if((to_swap[i][j]!=final_state[i][j])&& to_swap[i][j]!=0 )
{
no_of_misplaced++;
int ud=0,lr=0;
misplace=to_swap[i][j];
for(m=0;m<3;m++)
{
for(n=0;n<3;n++)
{
if(final_state[m][n]==misplace )
{
if(i>m)
{
ud=i-m;
}
else
{
ud=m-i;
}
if(j>n)
{
lr=j-n;
}
else
{
lr=n-j;
}
steps+=(ud+lr);
}
}
}
}
}
}
cost=no_of_misplaced+steps;
name[loops]='A';// initially loops=0
System.out.println("Initial state...");
System.out.println(name[loops]+" : ");
for(i=0;i<3;i++)
{
System.out.println();
for(j=0;j<3;j++)
{
System.out.print(initial_state[i][j]+" ");
}
}
//System.out.println("cost : "+cost);
System.out.println("open: "+open[0]);
System.out.println("close: "+close[0]);
close[0]='A';
loops++; //loops=1 now;
parent_cost[0]=cost;
System.out.println("Heuristic f(n) : "+cost);// initially storing cost of the parent
// System.out.println(" loops: "+loops);
//System.out.println(" p_index: "+p_index);
while(again==0)//Keeps iterating until the current state is the final state
{
p_index++; //for first iteration p_index now becomes 1
int top=0,down=0,left=0,right=0;// Keeps tracks of movements
again=0;
//Checking the position of space(i.e. 0) in the initial_state[][]
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(initial_state[i][j]==0)
{
row=i;
col=j;
}
}
}
//for each level iteration, inorder to check whether the cost of present solution is less than the cost of the previous solution
//
if(row==1 && col==1)//Space at the centre of grid
{
ways=4;
}
else if((row==0 && col==0) || (row==0 && col==2)||(row==2 && col==0)||(row==2 && col==2))// Space at any of the corners
{
ways=2;
}
else
{
ways=3;
}
System.out.println(" OPTIONS AVAILABLE: ");
times=0; int mincost=99;
//for each level iteration, inorder to check whether the cost of present solution is less than the cost of the previous solution
//cost and mincost variables are used... mincost=99 for each level iteration
int flag=0;
char temp_char=''; // for storing the temporary solution name
while(times < ways)
{
// System.out.println("loops: "+loops+" ");
name[loops]=(char)('A'+loops);
//close[loops]=name[loops];
steps=0;//No. of vertical and horizontal blocks to be moves to reach the final state position
no_of_misplaced=0;//No of current state numbers that are not in the final state position
same=0;//
cost=0;//To evaluate cost of each solution
if( (top==0) && (row==1 || row==2) && what_not_to_do!='u' ) // To move the space upwards
{
to_swap[row][col]=initial_state[row-1][col];
to_swap[row-1][col]=0;
top=1;
// Upward movement has already been done
}
else if((down==0)&&(row==0 || row==1) && what_not_to_do!='d' )//To move the space downwards
{
to_swap[row][col]=initial_state[row+1][col];
to_swap[row+1][col]=0;
down=1; // Downward movement has already been done
}
else if((left==0)&&(col==1 || col==2) && what_not_to_do!='l' )// To move the space leftwards
{
to_swap[row][col]=initial_state[row][col-1];
to_swap[row][col-1]=0;
left=1;//Left movement done
}
else if((right==0) && (col==0 || col==1) && what_not_to_do!='r')// To move the space rightwards
{
to_swap[row][col]=initial_state[row][col+1];
to_swap[row][col+1]=0;
right=1;//right movement done
}
// To check what was the exact current movement
if(top==1 &&down==0 && left==0 && right==0)
cur_mov='u';
else if(top==1 &&down==1 && left==0 && right==0)
cur_mov='d';
else if(top==1 &&down==1 && left==1 && right==0)
cur_mov='l';
else if(top==1 &&down==1 && left==1 && right==1)
cur_mov='r';
//always moves down
if(top==0 &&down==1 && left==0 && right==0)
cur_mov='d';
else if(top==0 && down==1 && left==0 && right==1)
cur_mov='r';
else if(top==0 &&down==1 && left==1 && right==0)
cur_mov='l';
else if(top==0 &&down==1 && left==1 && right==1)
cur_mov='r';
else if(top==0 &&down==0 && left==0 && right==1)
cur_mov='r';
else if(top==0 &&down==0 && left==1 && right==0)
cur_mov='l';
else if(top==0 &&down==0 && left==1 && right==1)
cur_mov='r';
else if(top==1 &&down==0 && left==0 && right==1)
cur_mov='r';
else if(top==1 &&down==0 && left==1 && right==0)
cur_mov='l';
else if(top==1 &&down==0 && left==1 && right==1)
cur_mov='r';
else if(top==1 &&down==1 && left==0 && right==1)
cur_mov='r';
//To calculate cost of the solution:
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if((to_swap[i][j]!=final_state[i][j])&& to_swap[i][j]!=0 )
{
no_of_misplaced++;
int ud=0,lr=0;
misplace=to_swap[i][j];
for(m=0;m<3;m++)
{
for(n=0;n<3;n++)
{
if(final_state[m][n]==misplace )
{
if(i>m)
{
ud=i-m;
}
else
{
ud=m-i;
}
if(j>n)
{
lr=j-n;
}
else
{
lr=n-j;
}
steps+=(ud+lr);
}
}
}
}
}
}
cost=no_of_misplaced+steps;
System.out.println(" ");
System.out.println(name[loops]);
for(i=0;i<3;i++)
{
System.out.println();
for(j=0;j<3;j++)
{
System.out.print(to_swap[i][j]+" ");
}
}
System.out.println("Heuristic f(n) : "+cost);
//Checking if this cost values is less than the minimum cost value
if(cost<mincost)
{
//This state has to be printed... Hence to_print[][] gets the values of to_swap[][]
mincost=cost;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
to_print[i][j]=to_swap[i][j];
}
}
temp_char=name[loops];
//currently to_print[][] gets the value of the best solution and initial_state[][] has the parent[][] array
// The below conditions make it possible that the previous state is not repeated....
if(cur_mov=='u')
temp='d';
else if(cur_mov=='d')
temp='u';
else if(cur_mov=='l')
temp='r';
else if(cur_mov=='r')
temp='l';
}
//Restoring default values for finding out next solution
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
to_swap[i][j]=initial_state[i][j];
}
}
times++;
loops++;
}// End of inner while()
parent_cost[p_index]=mincost;//stores the cost of the first good solution
parent_node[p_index]=temp_char;
what_not_to_do=temp;
//printing the best solution...
//current calculated best soln in parent_cost[p_index] and parent cost is [p_index-1];
System.out.println(" Best Node... ");
if(parent_cost[p_index]<parent_cost[p_index-1])
{
System.out.println();
System.out.println(parent_node[p_index]+":");
close[p_index]=parent_node[p_index];
//current best soln. is better than parent soln.
System.out.println();
for(i=0;i<3;i++)
{
System.out.println();
for(j=0;j<3;j++)
{
System.out.print(to_print[i][j]+" ");
}
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
initial_state[i][j]=to_print[i][j];
to_print[i][j]=initial_state[i][j];
to_swap[i][j]=initial_state[i][j];
}
}
parent_node[p_index]=name[loops-1];
}
else
{
System.out.println(" ");
System.out.println(temp_char+" ");
//again parent is evaluated
close[p_index]=parent_node[p_index-1];
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
to_print[i][j]=initial_state[i][j];
to_swap[i][j]=initial_state[i][j];
}
}
for(i=0;i<3;i++)
{
System.out.println();
for(j=0;j<3;j++)
{
System.out.print(to_print[i][j]+" ");
}
}
}
//To check if the chosen matrix is equivalent to the final matrix
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(to_print[i][j]==final_state[i][j])
{
same++;
}
}
}
if(same!=9)
{
//Then prepare for the next level iteration
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
initial_state[i][j]=to_print[i][j];
to_print[i][j]=initial_state[i][j];
to_swap[i][j]=initial_state[i][j];
}
}
again=0;
}
else
{
System.out.println(" Goal reached...");
again=1;
}
int u=0;
int yy;
for(i=0;i<15;i++)// name[] indexes
{
yy=0;
for(j=0;j<15;j++)// close[] indexes
{
if(name[i]==close[j])
yy++;
}
if(yy==0)
{
open[u]=name[i];
u++;
}
}
System.out.println(" open list : ");
for(i=0;i<15;i++)
{
System.out.print(open[i]+" ");
}
System.out.println(" close list : ");
for(i=0;i<15;i++)
{
System.out.print(close[i]+" ");
}
j=0;
u=0;
}//end of outer while()
}//end main()
}//End class()
**********************************************************************************************************************************
OUTPUT:
[ccoew@localhost ~]$ gedit astar.java
[ccoew@localhost ~]$ javac astar.java
[ccoew@localhost ~]$ java astar
Enter the initial puzzle...
1
0
3
4
2
6
7
5
8
Enter the final puzzle...
1
2
3
4
5
6
7
8
0
Initial state...
A :
1 0 3
4 2 6
7 5 8 open: A
close:
Heuristic f(n) : 6
OPTIONS AVAILABLE:
B
1 2 3
4 0 6
7 5 8 Heuristic f(n) : 4
C
0 1 3
4 2 6
7 5 8 Heuristic f(n) : 8
D
1 3 0
4 2 6
7 5 8 Heuristic f(n) : 8
Best Node...
B:
1 2 3
4 0 6
7 5 8
open list :
C D
close list :
A B
OPTIONS AVAILABLE:
E
1 2 3
4 5 6
7 0 8 Heuristic f(n) : 2
F
1 2 3
0 4 6
7 5 8 Heuristic f(n) : 6
G
1 2 3
4 6 0
7 5 8 Heuristic f(n) : 6
H
1 2 3
4 0 6
7 5 8 Heuristic f(n) : 4
Best Node...
E:
1 2 3
4 5 6
7 0 8
open list :
C D F G H
close list :
A B E
OPTIONS AVAILABLE:
I
1 2 3
4 5 6
0 7 8 Heuristic f(n) : 4
J
1 2 3
4 5 6
7 8 0 Heuristic f(n) : 0
K
1 2 3
4 5 6
7 0 8 Heuristic f(n) : 2
Best Node...
J:
1 2 3
4 5 6
7 8 0
Goal reached...
open list :
C D F G H I K
close list :
A B E J
***************************************************************************************************************************
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.