Do in Javascript

/* ================ 8-puzzle problem ================ Construct a 3x3 grid, containing one blank(empty) space and one each of tiles labeled 1-8. By exchanging tiles adjacent to the blank space with the blank space, achieve the desired configuration: 1 2 3 8 4 7 6 5

State: { grid : Array(3,3), Integers [0,8] } where grid is a 2D array whose indices correspond to the following grid positions: [0][0] [0][1] [0][2] [1][0] [1][1] [1][2] [2][0] [2][1] [2][2] The value 0 is used to represent the blank space, and 1-8 for the corresponding labeled tiles.

Possible actions: ID | Action ---+---------------------- 1 | Move tile above blank down (i.e., "move" blank up) ---+---------------------- 2 | Move tile below blank up (i.e., "move" blank down) ---+---------------------- 3 | Move tile left of blank right (i.e., "move" blank left) ---+---------------------- 4 | Move tile right of blank left (i.e., "move" blank right) */

////////////////////////////////////////////////////////////////////////////// // Complete the following two functions

//Check if the given state is a goal state //Returns: true if is goal state, false otherwise function is_goal_state(state) { ++helper_eval_state_count; //Keep track of how many states are evaluated (DO NOT REMOVE!) return /***Your code to check for goal state here!***/; }

//Find the list of actions that can be performed from the given state and the new //states that result from each of those actions //Returns: Array of successor objects (where each object has a valid actionID member and corresponding resultState member) function find_successors(state) { ++helper_expand_state_count; //Keep track of how many states are expanded (DO NOT REMOVE!) var successors=[];

/***Your code to generate successors here!***/

//Hint: Javascript objects are passed by reference, so don't modify "state" directy. //Make copies instead: // var newState={ // grid : state.grid.map(x => x.slice(0)) //Deep copy of grid // }; //Remember to make a new copy for each new state you make!

//Hint: Add new elements to the successor list like so: // successors.push({ // actionID : /*ID*/, // resultState : newState // });

return successors; }

////////////////////////////////////////////////////////////////////////////// // Use these functions when developing your A* implementation

//Heuristic functions for the 8-puzzle problem function calculate_heuristic(state) { //Total Manhattan distance heuristic var goal=[ [1, 2, 3], [8, 0, 4], [7, 6, 5] ];

var g_pos=Array(9); var st_pos=Array(9); for(let j=0;j<3;++j) for(let i=0;i<3;++i) { g_pos[ goal[j][i] ]=[j,i]; st_pos[ state.grid[j][i] ]=[j,i]; }

var h=0; for(let i=0;i<9;++i) { h+=Math.abs( st_pos[i][0]-g_pos[i][0] )+Math.abs( st_pos[i][1]-g_pos[i][1] ); } return h; }

/* function calculate_heuristic(state) { //Misplaced tiles heuristic var goal=[ [1, 2, 3], [8, 0, 4], [7, 6, 5] ];

var h=0; for(let j=0;j<3;++j) for(let i=0;i<3;++i) { if(state.grid[j][i]!=goal[j][i]) ++h; } if(h>0) --h; //Account for miscounted blank return h; } */

/* function calculate_heuristic(state) { //Simplest heuristic (h(n)=0) return 0; } */

////////////////////////////////////////////////////////////////////////////// // DO NOT MODIFY BELOW THIS LINE

//Check that state input has valid values, outputs descriptive text if not //Returns: true if input ok function verify_state() { var s=read_state();

var cnt=Array(3).fill(0).map(x => Array(3)); for(let j=0;j<3;++j) for(let i=0;i<3;++i) { var pos="Row "+j+", Col "+i; if(isNaN(s.grid[j][i])) { helper_log_write(pos+" is not a number"); return false; } if(s.grid[j][i] < 0 || s.grid[j][i] > 8) { helper_log_write(pos+" is out of range"); return false; } ++cnt[s.grid[j][i]]; } for(let i=0;i<9;++i) { var val=""+i; if(i==0) val="blank"; if(cnt[i]==0) { helper_log_write("Missing "+val); return false; } if(cnt[i]>1) { helper_log_write("Too many "+val+"s"); return false; } } //Count inversions to see if puzzle is solveable var inv=0; var g=[]; for(let j=0;j<3;++j) for(let i=0;i<3;++i) g.push(s.grid[j][i]); g=g.filter(function(x){return x>0;}); for(let i=0;i<8;++i) for(let j=i+1;j<8;++j) if(g[i]>g[j]) ++inv; if(inv%2==0) { helper_log_write("Not solveable"); return false; } return true; }

//Construct state object from page input //Returns: state object function read_state() { var grid=Array(3).fill(0).map(x => Array(3)); for(let k=0;k<9;++k) { var input=document.getElementById("input_pos"+k); var j=Math.floor(k/3); var i=k%3; if(input.value=="") grid[j][i]=0; else grid[j][i]=parseInt(input.value,10); } return { grid : grid }; }

//Convert state to a DOM object suitable for display on web page //Returns: DOM object function state_to_dom(s) { var html=""; for(let j=0;j<3;++j) { for(let i=0;i<3;++i) { html+=" "; if(s.grid[j][i]==0) html+=" "; else html+=s.grid[j][i]; } html+=" "; } var obj=document.createElement("pre"); obj.innerHTML=html; return obj; }

//Convert action to a DOM object suitable for display on web page //(Providing optional on_state argument may give more detailed description of what is being done to provided state.) //Returns: DOM object function action_to_dom(actionID,on_state) { var obj=document.createElement("p"); var bi,bj; if(on_state!=null) { for(let ij=0;ij<9;++ij) { bj=Math.floor(ij/3); bi=ij%3; if(on_state.grid[bj][bi]==0) break; } } switch(actionID) { case 1: if(on_state==null) obj.innerHTML="Move tile above blank down"; else obj.innerHTML="Move "+on_state.grid[bj-1][bi]+" down"; break; case 2: if(on_state==null) obj.innerHTML="Move tile below blank up"; else obj.innerHTML="Move "+on_state.grid[bj+1][bi]+" up"; break; case 3: if(on_state==null) obj.innerHTML="Move tile left of blank right"; else obj.innerHTML="Move "+on_state.grid[bj][bi-1]+" right"; break; case 4: if(on_state==null) obj.innerHTML="Move tile right of blank left"; else obj.innerHTML="Move "+on_state.grid[bj][bi+1]+" left"; break; default: obj.innerHTML="Invalid action!"; } return obj; }

//Convert state to a unique number (no 2 state objects will have the same number unless they are equivalent). // For use with Javascript Set, since there's no way to override its equivalence check function state_to_uniqueid(state) { var id=0; for(let j=0;j<3;++j) for(let i=0;i<3;++i) { id*=9; id+=state.grid[j][i]; } return id; }