8-puzzle JavaScript: solve and replay a witness

Select the code and use your copy shortcut. Changes in this preview are temporary.

<!doctype html>
<html lang="en-US"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1"><title>8-puzzle JavaScript: solve and replay a witness</title><style>:root{--paper:#f6f3fc;--ink:#302c43;--accent:#65478f;--surface:#fff;--border:#d8cee5;--wash:#eee7f6;--muted:#5e526e;--title:system-ui,sans-serif;--radius:12px;--buttonText:#fff}*{box-sizing:border-box}body{margin:0;background:var(--paper);color:var(--ink);font:17px/1.65 system-ui,sans-serif}main{max-width:980px;margin:auto;padding:24px 26px 48px}header{margin-bottom:20px;border-bottom:2px solid var(--accent);padding-bottom:16px}h1{font:700 clamp(28px,5vw,42px)/1.18 var(--title);margin:0 0 10px;letter-spacing:-.025em}h2{font-size:23px;line-height:1.35;margin:24px 0 12px}h3{font-size:19px}p{margin:0 0 16px}.eyebrow{font-size:16px;color:var(--accent);font-weight:700;margin:0 0 5px}.grid{display:grid;grid-template-columns:repeat(2,minmax(0,1fr));gap:22px}.panel{background:var(--surface);border:1px solid var(--border);border-radius:var(--radius);padding:22px;min-width:0;margin-bottom:20px}label{display:block;font-weight:650;margin-bottom:14px}input,textarea,select{display:block;font:inherit;line-height:1.5;width:100%;min-width:0;color:var(--ink);background:var(--surface);border:1px solid var(--accent);border-radius:5px;padding:9px 11px;margin-top:5px}textarea{resize:vertical}button{font:650 16px/1.5 system-ui;min-height:44px;padding:9px 16px;color:var(--buttonText);background:var(--accent);border:1px solid var(--accent);border-radius:5px;cursor:pointer;margin:4px 6px 4px 0}button[aria-pressed=true]{outline:3px solid var(--accent);outline-offset:2px}button:disabled{opacity:.55;cursor:default}:focus-visible{outline:3px solid #b86d10;outline-offset:3px}.result{border-left:4px solid var(--accent);background:var(--wash);padding:15px;margin:16px 0;white-space:pre-line;overflow-wrap:anywhere;font-weight:600}.result:empty{display:none}pre{font:16px/1.55 ui-monospace,Consolas,monospace;background:var(--wash);padding:16px;white-space:pre-wrap;overflow-wrap:anywhere;border:1px solid var(--border);border-radius:5px}code{overflow-wrap:anywhere}.note{font-size:16px;color:var(--muted)}.row{border-bottom:1px solid var(--border);padding:12px 0}.row strong{display:block}table{width:100%;border-collapse:collapse;font-size:16px;table-layout:fixed}th,td{padding:10px 8px;text-align:left;border-bottom:1px solid var(--border);overflow-wrap:anywhere}th{background:var(--wash)}a{color:var(--accent);overflow-wrap:anywhere}footer{border-top:1px solid var(--border);padding-top:16px;font-size:16px;color:var(--muted)}.tiles{display:grid;grid-template-columns:repeat(3,1fr);gap:8px;max-width:330px}.tile{padding:16px;text-align:center;background:var(--wash);border:1px solid var(--border);font-size:22px}svg,canvas{max-width:100%;height:auto}mark{background:#d5f525;color:#202600}ol,ul{padding-left:24px}li{margin-bottom:9px}[hidden]{display:none!important}@media(max-width:640px){main{padding:18px 16px 36px}.grid{grid-template-columns:1fr;gap:0}.panel{padding:17px}header{padding-bottom:12px;margin-bottom:16px}h1{font-size:29px}th,td{padding:8px 5px}h2{margin-top:18px}}</style></head><body><main><header><p class="eyebrow">Original worked example</p><h1>8-puzzle JavaScript: solve and replay a witness</h1><p>Start [1,2,3,4,5,6,0,7,8]. Goal [1,2,3,4,5,6,7,8,0]. Blank directions name the move.</p></header><section class="panel"><label for="board">Board JSON<textarea id="board" rows="5">[1,2,3,4,5,6,0,7,8]</textarea></label><label for="budget">Maximum expansions: 1–10000<input id="budget" type="number" value="100"></label><button id="solve" type="button">Solve</button><button id="replay" type="button">Replay next</button><div class="result" id="result" role="status" aria-live="polite"></div><pre id="display" tabindex="0"></pre><pre id="witness" tabindex="0"></pre></section><section class="panel"><p>Unit-cost blank swaps only. Manhattan ignores zero. Baseline lower bound 2 and a legal Right, Right witness of length 2 establish the shortest length for this fixture. Changed input invalidates the old witness.</p></section><footer>The bounded local solver makes no universal performance guarantee; a cutoff means unfinished search, not unsolvability. Changes are temporary. No data is sent or saved.</footer></main><script>
(() => {
'use strict';
const $=selector=>document.querySelector(selector);
const on=(selector,handler)=>$(selector).addEventListener('click',handler);
(function(){const goal=[1,2,3,4,5,6,7,8,0],key=b=>b.join(','),h=b=>b.reduce((sum,v,i)=>v?sum+Math.abs(Math.floor(i/3)-Math.floor((v-1)/3))+Math.abs(i%3-(v-1)%3):sum,0);let path=[],moves=[],position=0;function draw(b){$('#display').textContent=[0,3,6].map(i=>b.slice(i,i+3).map(v=>v||'_').join(' ')).join('\n');}function solve(){$('#display').textContent='No current board. Solve the current input.';path=[];moves=[];position=0;$('#witness').textContent='';let start;try{start=JSON.parse($('#board').value);}catch{$('#result').textContent='Invalid board JSON.';return;}if(!Array.isArray(start)||start.length!==9||start.some(v=>!Number.isInteger(v)||v<0||v>8)||new Set(start).size!==9){$('#result').textContent='Invalid board: nine unique integers 0–8 required.';return;}const budget=Number($('#budget').value);if(!Number.isInteger(budget)||budget<1||budget>10000){$('#result').textContent='Enter expansion budget 1–10000.';return;}draw(start);let sequence=0,expansions=0;const frontier=[{b:start,g:0,h:h(start),parent:null,move:null,seq:sequence++}],best=new Map([[key(start),0]]);while(frontier.length){frontier.sort((a,b)=>(a.g+a.h)-(b.g+b.h)||a.h-b.h||(key(a.b)<key(b.b)?-1:key(a.b)>key(b.b)?1:0)||a.seq-b.seq);const n=frontier.shift();if(n.g!==best.get(key(n.b)))continue;if(key(n.b)===key(goal)){let cur=n;while(cur){path.push(cur.b);if(cur.move)moves.push(cur.move);cur=cur.parent;}path.reverse();moves.reverse();for(let i=1;i<path.length;i++){const prev=path[i-1],next=path[i],p=prev.indexOf(0),q=next.indexOf(0);if(Math.abs(Math.floor(p/3)-Math.floor(q/3))+Math.abs(p%3-q%3)!==1||prev.some((v,j)=>j!==p&&j!==q&&v!==next[j]))throw Error('Illegal witness');}$('#result').textContent='Solved: '+n.g+' moves. Initial Manhattan '+h(start)+'. Expansions '+expansions+'. Witness replay checked.';$('#witness').textContent='Blank moves: '+(moves.join(', ')||'(none)');return;}if(expansions>=budget){$('#result').textContent='BudgetExceeded/Unknown after '+expansions+' expansions. No unsolvability claim.';return;}expansions++;const blank=n.b.indexOf(0),row=Math.floor(blank/3),col=blank%3;for(const [dr,dc,move]of [[-1,0,'Up'],[1,0,'Down'],[0,-1,'Left'],[0,1,'Right']]){const r=row+dr,c=col+dc;if(r<0||r>2||c<0||c>2)continue;const next=n.b.slice(),target=r*3+c;[next[blank],next[target]]=[next[target],next[blank]];const g=n.g+1,k=key(next);if(g<(best.get(k)??Infinity)){best.set(k,g);frontier.push({b:next,g,h:h(next),parent:n,move,seq:sequence++});}}}$('#result').textContent='No path after complete frontier exhaustion.';}on('#solve',solve);on('#replay',()=>{if(!path.length){$('#result').textContent='No solved witness available. Solve first.';return;}position=Math.min(path.length-1,position+1);draw(path[position]);$('#result').textContent='Replay '+position+' of '+moves.length+' legal moves. '+(position===moves.length?'Goal reached.':'Next move available.');});['#board','#budget'].forEach(s=>$(s).addEventListener('input',()=>{path=[];moves=[];$('#result').textContent='Input changed. Solve again.';$('#display').textContent='No current board. Solve the current input.';$('#witness').textContent='';}));solve();})();
})();
</script></body></html>