Skip to content

Instantly share code, notes, and snippets.

@KevinWang15

KevinWang15/solver.html

Last active May 2, 2025 12:22
Show Gist options
  • Save KevinWang15/d0b984b973c4258e37f8b46400778faf to your computer and use it in GitHub Desktop.
Save KevinWang15/d0b984b973c4258e37f8b46400778faf to your computer and use it in GitHub Desktop.
Download ZIP
Rush-Hour Solver
Raw
solver.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Rush-Hour Solver</title>
<style>
body{font-family:system-ui,Arial,sans-serif}
#garage{position:relative;width:254px;height:254px;margin-bottom:1rem}
#board{display:grid;grid-template-columns:repeat(6,40px);grid-template-rows:repeat(6,40px);gap:2px}
.cell{width:40px;height:40px;background:#ddd}
.car{position:absolute;display:flex;justify-content:center;align-items:center;
color:#fff;font-weight:700;border-radius:4px;font-size:.8rem;user-select:none}
#controls{margin:8px 0}
button{margin-right:4px;padding:4px 10px}
pre{background:#f5f5f5;padding:6px;overflow:auto;max-height:240px}
</style>
</head>
<body>
<h2>Parking-Garage Solver</h2>
<div id="garage"><div id="board"></div></div>
<div id="controls">
<button id="prevBtn">◀ Prev</button>
<button id="nextBtn">Next ▶</button>
<span id="stepInfo"></span>
</div>
<details open>
<summary>Full list of moves produced by the solver</summary>
<pre id="log"></pre>
</details>
<script>
// ---------- problem definition -------------------------------------------------
const cars = [
{car:"red", position:[[0,2],[1,2]]},
{car:"1", position:[[0,3],[0,4]]},
{car:"2", position:[[0,5],[1,5],[2,5]]},
{car:"3", position:[[1,3],[2,3]]},
{car:"4", position:[[1,4],[2,4]]},
{car:"5", position:[[2,0],[2,1],[2,2]]},
{car:"6", position:[[3,0],[3,1]]},
{car:"7", position:[[3,3],[4,3]]},
{car:"8", position:[[3,4],[3,5]]},
{car:"9", position:[[4,0],[5,0]]},
{car:"10", position:[[4,1],[4,2]]},
{car:"11", position:[[5,3],[5,4],[5,5]]},
];
// constants
const W=6,H=6,EXIT_ROW=2;
const order=cars.map(c=>c.car);
// ---------- helper tables (orientation & length) ------------------------------
const orient={}, length={};
cars.forEach(c=>{
orient[c.car]= c.position[0][1]===c.position[1][1] ? 'H' : 'V';
length[c.car]= c.position.length;
});
// ---------- anchor utilities ---------------------------------------------------
function makeAnchors(arr){
const a={};
arr.forEach(c=>{
if(orient[c.car]==='H'){
a[c.car]=[Math.min(...c.position.map(p=>p[0])),c.position[0][1]];
}else{
a[c.car]=[c.position[0][0],Math.min(...c.position.map(p=>p[1]))];
}
});
return a;
}
const start=makeAnchors(cars);
const keyOf=a=>order.map(id=>a[id].join(',')).join('|');
// ---------- occupancy & moves --------------------------------------------------
function occupied(a){
const o={};
order.forEach(id=>{
const [x,y]=a[id];
for(let k=0;k<length[id];k++){
const cell=orient[id]==='H'?[x+k,y]:[x,y+k];
o[cell.join(',')]=id;
}
});
return o;
}
function movesFor(id,a,o){
const [x,y]=a[id], res=[];
if(orient[id]==='H'){
// left
for(let nx=x-1;nx>=0 && !o[[nx,y].join(',')];nx--) res.push([nx-x,'left']);
// right
for(let nx=x+length[id];nx<W && !o[[nx,y].join(',')];nx++) res.push([nx-(x+length[id]-1),'right']);
}else{
// up
for(let ny=y-1;ny>=0 && !o[[x,ny].join(',')];ny--) res.push([ny-y,'up']);
// down
for(let ny=y+length[id];ny<H && !o[[x,ny].join(',')];ny++) res.push([ny-(y+length[id]-1),'down']);
}
return res;
}
function apply(a,id,d){
const b=JSON.parse(JSON.stringify(a));
if(orient[id]==='H') b[id][0]+=d; else b[id][1]+=d;
return b;
}
function isGoal(a){
const [x,y]=a.red;
return y===EXIT_ROW && x+length.red-1===W-1;
}
// ---------- breadth-first search ----------------------------------------------
function solve(){
const Q=[start], parent=new Map(), how=new Map();
parent.set(keyOf(start),null);
while(Q.length){
const cur=Q.shift();
if(isGoal(cur)) return {parent,how,goal:cur};
const occ=occupied(cur);
for(const id of order){
for(const [d,dir] of movesFor(id,cur,occ)){
const nxt=apply(cur,id,d), k=keyOf(nxt);
if(!parent.has(k)){
parent.set(k,keyOf(cur)); how.set(k,[id,d,dir]); Q.push(nxt);
}
}
}
}
return null;
}
const {parent,how,goal}=solve(); // ⇦ runs instantly in this small puzzle
const path=[];
for(let k=keyOf(goal);parent.get(k);k=parent.get(k)) path.push(how.get(k));
path.reverse(); // now path[i] = [car,delta,dir]
// ---------- debugging log ------------------------------------------------------
document.getElementById('log').textContent=
path.map((m,i)=>`${i+1}. Move car ${m[0]} ${m[2]} ${Math.abs(m[1])}`).join('\n');
// ---------- visual board -------------------------------------------------------
const board=document.getElementById('board');
for(let y=0;y<H;y++) for(let x=0;x<W;x++){
board.appendChild(Object.assign(document.createElement('div'),{className:'cell'}));
}
const colors={red:'red'};
function colour(id){
if(!colors[id]) colors[id]=`hsl(${~~(Math.random()*360)},60%,35%)`;
return colors[id];
}
const garage=document.getElementById('garage');
const carEls={};
function draw(a){
Object.values(carEls).forEach(el=>el.remove());
for(const id of order){
const [x,y]=a[id], el=document.createElement('div');
el.className='car'; el.textContent=id; el.style.background=colour(id);
el.style.left=`${x*42}px`; el.style.top=`${y*42}px`;
el.style.width =orient[id]==='H'?`${length[id]*40+(length[id]-1)*2}px`:'40px';
el.style.height=orient[id]==='V'?`${length[id]*40+(length[id]-1)*2}px`:'40px';
garage.appendChild(el); carEls[id]=el;
}
}
// ---------- stepper controls ---------------------------------------------------
let step=-1;
function refresh(){
let a=makeAnchors(cars);
for(let i=0;i<=step;i++){
if(i<0||i>=path.length) break;
const [id,d]=path[i]; a=apply(a,id,d);
}
draw(a);
document.getElementById('stepInfo').textContent=
`Step ${step+1} / ${path.length}`;
}
document.getElementById('nextBtn').onclick=()=>{if(step<path.length-1){step++;refresh();}};
document.getElementById('prevBtn').onclick=()=>{if(step>=0){step--;refresh();}};
refresh(); // initial board
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment