const frames = [{"kind":"grid","caption":"1행 1열 시도","data":{"cols":4,"rows":4,"queens":[],"active":0,"invalid":false}},{"kind":"grid","caption":"1행 퀸 배치","data":{"cols":4,"rows":4,"queens":[0],"active":0}},{"kind":"grid","caption":"2행 1열 시도","data":{"cols":4,"rows":4,"queens":[0],"active":4,"invalid":true}},{"kind":"grid","caption":"2행 2열 시도","data":{"cols":4,"rows":4,"queens":[0],"active":5,"invalid":true}},{"kind":"grid","caption":"2행 3열 시도","data":{"cols":4,"rows":4,"queens":[0],"active":6,"invalid":false}},{"kind":"grid","caption":"2행 퀸 배치","data":{"cols":4,"rows":4,"queens":[0,2],"active":6}},{"kind":"grid","caption":"3행 1열 시도","data":{"cols":4,"rows":4,"queens":[0,2],"active":8,"invalid":true}},{"kind":"grid","caption":"3행 2열 시도","data":{"cols":4,"rows":4,"queens":[0,2],"active":9,"invalid":true}},{"kind":"grid","caption":"3행 3열 시도","data":{"cols":4,"rows":4,"queens":[0,2],"active":10,"invalid":true}},{"kind":"grid","caption":"3행 4열 시도","data":{"cols":4,"rows":4,"queens":[0,2],"active":11,"invalid":true}},{"kind":"grid","caption":"2행으로 되돌아감","data":{"cols":4,"rows":4,"queens":[0],"active":6,"invalid":true}},{"kind":"grid","caption":"2행 4열 시도","data":{"cols":4,"rows":4,"queens":[0],"active":7,"invalid":false}},{"kind":"grid","caption":"2행 퀸 배치","data":{"cols":4,"rows":4,"queens":[0,3],"active":7}},{"kind":"grid","caption":"3행 1열 시도","data":{"cols":4,"rows":4,"queens":[0,3],"active":8,"invalid":true}},{"kind":"grid","caption":"3행 2열 시도","data":{"cols":4,"rows":4,"queens":[0,3],"active":9,"invalid":false}},{"kind":"grid","caption":"3행 퀸 배치","data":{"cols":4,"rows":4,"queens":[0,3,1],"active":9}},{"kind":"grid","caption":"4행 1열 시도","data":{"cols":4,"rows":4,"queens":[0,3,1],"active":12,"invalid":true}},{"kind":"grid","caption":"4행 2열 시도","data":{"cols":4,"rows":4,"queens":[0,3,1],"active":13,"invalid":true}},{"kind":"grid","caption":"4행 3열 시도","data":{"cols":4,"rows":4,"queens":[0,3,1],"active":14,"invalid":true}},{"kind":"grid","caption":"4행 4열 시도","data":{"cols":4,"rows":4,"queens":[0,3,1],"active":15,"invalid":true}},{"kind":"grid","caption":"3행으로 되돌아감","data":{"cols":4,"rows":4,"queens":[0,3],"active":9,"invalid":true}},{"kind":"grid","caption":"3행 3열 시도","data":{"cols":4,"rows":4,"queens":[0,3],"active":10,"invalid":true}},{"kind":"grid","caption":"3행 4열 시도","data":{"cols":4,"rows":4,"queens":[0,3],"active":11,"invalid":true}},{"kind":"grid","caption":"2행으로 되돌아감","data":{"cols":4,"rows":4,"queens":[0],"active":7,"invalid":true}},{"kind":"grid","caption":"1행으로 되돌아감","data":{"cols":4,"rows":4,"queens":[],"active":0,"invalid":true}},{"kind":"grid","caption":"1행 2열 시도","data":{"cols":4,"rows":4,"queens":[],"active":1,"invalid":false}},{"kind":"grid","caption":"1행 퀸 배치","data":{"cols":4,"rows":4,"queens":[1],"active":1}},{"kind":"grid","caption":"2행 1열 시도","data":{"cols":4,"rows":4,"queens":[1],"active":4,"invalid":true}},{"kind":"grid","caption":"2행 2열 시도","data":{"cols":4,"rows":4,"queens":[1],"active":5,"invalid":true}},{"kind":"grid","caption":"2행 3열 시도","data":{"cols":4,"rows":4,"queens":[1],"active":6,"invalid":true}},{"kind":"grid","caption":"2행 4열 시도","data":{"cols":4,"rows":4,"queens":[1],"active":7,"invalid":false}},{"kind":"grid","caption":"2행 퀸 배치","data":{"cols":4,"rows":4,"queens":[1,3],"active":7}},{"kind":"grid","caption":"3행 1열 시도","data":{"cols":4,"rows":4,"queens":[1,3],"active":8,"invalid":false}},{"kind":"grid","caption":"3행 퀸 배치","data":{"cols":4,"rows":4,"queens":[1,3,0],"active":8}},{"kind":"grid","caption":"4행 1열 시도","data":{"cols":4,"rows":4,"queens":[1,3,0],"active":12,"invalid":true}},{"kind":"grid","caption":"4행 2열 시도","data":{"cols":4,"rows":4,"queens":[1,3,0],"active":13,"invalid":true}},{"kind":"grid","caption":"4행 3열 시도","data":{"cols":4,"rows":4,"queens":[1,3,0],"active":14,"invalid":false}},{"kind":"grid","caption":"4행 퀸 배치","data":{"cols":4,"rows":4,"queens":[1,3,0,2],"active":14}},{"kind":"grid","caption":"네 퀸을 모두 놓음","data":{"cols":4,"rows":4,"queens":[1,3,0,2]}}];
const title = "백트래킹 · 4퀸";
const canvas = document.getElementById('stage');
const ctx = canvas.getContext('2d');
const restart = document.getElementById('restart');
const step = document.getElementById('step');
const speed = document.getElementById('speed');
let index = 0, last = performance.now(), width = 300, height = 200;
function colors(){ const s=getComputedStyle(document.documentElement); const v=(key)=>s.getPropertyValue(key).trim(); return {bg:v('--bg'),fg:v('--fg'),muted:v('--muted'),line:v('--line'),surface:v('--surface'),accent:v('--accent'),accent2:v('--accent-2'),accent3:v('--accent-3')}; }
function resize(){ const dpr=Math.min(devicePixelRatio||1,2); width=innerWidth;height=innerHeight;canvas.width=Math.round(width*dpr);canvas.height=Math.round(height*dpr);ctx.setTransform(dpr,0,0,dpr,0,0);draw(); }
function text(value,x,y,color,size=12,align='left'){ ctx.fillStyle=color;ctx.font='600 '+size+'px sans-serif';ctx.textAlign=align;ctx.textBaseline='middle';ctx.fillText(String(value),x,y); }
function line(x1,y1,x2,y2,color,thick=2){ctx.strokeStyle=color;ctx.lineWidth=thick;ctx.beginPath();ctx.moveTo(x1,y1);ctx.lineTo(x2,y2);ctx.stroke();}
function dot(x,y,r,color){ctx.fillStyle=color;ctx.beginPath();ctx.arc(x,y,r,0,Math.PI*2);ctx.fill();}
function draw(){
if(!frames.length)return;
const p=colors(), frame=frames[index], d=frame.data, detail=width>500;
ctx.fillStyle=p.bg;ctx.fillRect(0,0,width,height);
text(title,12,18,p.fg,detail?16:13);text(frame.caption,12,detail?43:39,p.muted,detail?13:10);
text((index+1)+' / '+frames.length,width-12,18,p.muted,10,'right');
const top=detail?62:53, bottom=detail?height-47:height-9, span=Math.max(10,bottom-top), areaW=Math.min(width-22,detail?710:width-22), left=(width-areaW)/2;
if(frame.kind==='graph'){
const nodes=d.nodes, edges=d.edges, positions=Object.fromEntries(nodes.map(n=>[n.id,{x:left+areaW*(.06+.88*n.x),y:top+span*(.11+.78*n.y)}]));
for(const edge of edges){const a=edge[0],b=edge[1],weight=edge[2],key=[a,b].sort().join('-'),pa=positions[a],pb=positions[b];
if(d.hideUnvisited&&(!d.visited.includes(a)||!d.visited.includes(b)))continue;
const chosen=d.selected?.includes(key), active=d.activeEdge===key;ctx.globalAlpha=active||chosen?1:.58;line(pa.x,pa.y,pb.x,pb.y,active?p.accent2:chosen?p.accent:p.muted,active?4:chosen?3:2);ctx.globalAlpha=1;
if(d.directed){const angle=Math.atan2(pb.y-pa.y,pb.x-pa.x),x=pb.x-Math.cos(angle)*(detail?18:13),y=pb.y-Math.sin(angle)*(detail?18:13);line(x-Math.cos(angle-.55)*7,y-Math.sin(angle-.55)*7,x,y,p.muted,1.5);line(x-Math.cos(angle+.55)*7,y-Math.sin(angle+.55)*7,x,y,p.muted,1.5);}
if(weight>0&&!d.hideUnvisited)text(weight,(pa.x+pb.x)/2,(pa.y+pb.y)/2-7,p.muted,10,'center');
}
for(const node of nodes){if(d.hideUnvisited&&!d.visited.includes(node.id))continue;const pt=positions[node.id],selected=d.visited?.includes(node.id),front=d.frontier?.includes(node.id),active=d.active===node.id;let color=active?p.accent2:front?p.accent3:selected?p.accent:p.surface;
if(d.groups){const group=d.groups[nodes.findIndex(n=>n.id===node.id)];color=[p.accent,p.accent2,p.accent3][nodes.findIndex(n=>n.id===group)%3];}
dot(pt.x,pt.y,detail?18:12,color);ctx.strokeStyle=p.line;ctx.lineWidth=1;ctx.stroke();text(node.id,pt.x,pt.y,selected||active||front||d.groups?'#fff':p.fg,detail?13:10,'center');
if(d.distances)text(Number.isFinite(d.distances[node.id])?d.distances[node.id]:'∞',pt.x,pt.y+(detail?29:22),p.muted,10,'center');
}
} else if(frame.kind==='grid'||frame.kind==='table'||frame.kind==='bits'){
const table=frame.kind==='table',bits=frame.kind==='bits';const rows=bits?1:table?d.values.length:d.rows,cols=bits?d.bits.length:table?d.values[0].length:d.cols;
const labelX=table?24:0,labelY=table?18:0,cell=Math.min((areaW-labelX)/cols,(span-labelY)/rows,detail?56:32),ox=left+(areaW-(cols*cell+labelX))/2+labelX,oy=top+(span-(rows*cell+labelY))/2+labelY;
if(table){d.colLabels.forEach((label,c)=>text(label,ox+c*cell+cell/2,oy-10,p.muted,10,'center'));d.rowLabels.forEach((label,r)=>text(label,ox-12,oy+r*cell+cell/2,p.muted,10,'center'));}
for(let r=0;r<rows;r++)for(let c=0;c<cols;c++){const n=r*cols+c,x=ox+c*cell,y=oy+r*cell,active=bits?d.active?.includes(c):table?d.active?.[0]===r&&d.active?.[1]===c:d.active===n,source=table?d.sources?.some(v=>v[0]===r&&v[1]===c):false,visited=bits?d.bits[c]:table?false:d.visited?.includes(n),front=d.frontier?.includes(n),blocked=d.blocked?.includes(n),path=d.path?.includes(n),queen=d.queens?.[r]===c;
ctx.fillStyle=blocked?p.line:active?p.accent2:path||queen?p.accent3:front?p.accent2:visited?p.accent:source?p.accent3:bits&&d.bits[c]?p.accent:p.surface;ctx.fillRect(x+2,y+2,cell-4,cell-4);ctx.strokeStyle=p.muted;ctx.globalAlpha=.42;ctx.strokeRect(x+1,y+1,cell-2,cell-2);ctx.globalAlpha=1;
const value=bits?d.bits[c]:table?d.values[r][c]:queen?'Q':d.start===n?'S':d.goal===n?'G':blocked?'':visited?'·':'';
if(value!==''&&value!==undefined)text(value,x+cell/2,y+cell/2,(active||path||queen||front||visited||bits&&d.bits[c])?'#fff':p.fg,Math.min(13,cell*.43),'center');
if(bits)text(c,x+cell/2,y+cell+11,p.muted,9,'center');
}
} else if(frame.kind==='intervals'){
const rowH=Math.min(31,span/d.intervals.length),unit=(areaW-28)/10,ox=left+10,oy=top+(span-rowH*d.intervals.length)/2;
d.intervals.forEach((it,i)=>{const y=oy+i*rowH;ctx.fillStyle=d.active===i?p.accent2:d.selected.includes(i)?p.accent:p.line;ctx.fillRect(ox+it[0]*unit,y+3,Math.max(5,(it[1]-it[0])*unit-3),rowH-7);text(i+1,ox-5,y+rowH/2,p.muted,10,'right');});
} else if(frame.kind==='ring'){
const cx=width/2,cy=top+span/2,r=Math.min(areaW,span)*.35,loc=(v,rr)=>({x:cx+Math.sin(v*2*Math.PI)*rr,y:cy-Math.cos(v*2*Math.PI)*rr});ctx.strokeStyle=p.muted;ctx.globalAlpha=.6;ctx.lineWidth=2;ctx.beginPath();ctx.arc(cx,cy,r,0,Math.PI*2);ctx.stroke();ctx.globalAlpha=1;
d.keys.forEach((key,i)=>{const point=loc(key,r),server=d.servers.find(s=>s.id===d.owners[i]),dest=loc(server.pos,r);line(point.x,point.y,dest.x,dest.y,d.active===i?p.accent2:p.line,1);dot(point.x,point.y,d.active===i?6:4,d.active===i?p.accent2:p.fg);});
d.servers.forEach((server,i)=>{const point=loc(server.pos,r);dot(point.x,point.y,detail?15:11,[p.accent,p.accent2,p.accent3,p.fg][i]);text(server.id,point.x,point.y,i===3?p.bg:'#fff',11,'center');});
} else if(frame.kind==='points'){
const side=Math.min(areaW,span)-8,ox=(width-side)/2,oy=top+(span-side)/2;ctx.strokeStyle=p.muted;ctx.globalAlpha=.5;ctx.strokeRect(ox,oy,side,side);ctx.globalAlpha=1;ctx.beginPath();ctx.arc(ox,oy+side,side,Math.PI*1.5,0);ctx.strokeStyle=p.muted;ctx.stroke();
d.points.forEach(([x,y])=>dot(ox+x*side,oy+side-y*side,detail?2.5:1.7,x*x+y*y<=1?p.accent:p.accent2));
}
}
function advance(){index=(index+1)%frames.length;draw();}
restart.addEventListener('click',()=>{index=0;last=performance.now();draw();});
step.addEventListener('click',()=>{advance();last=performance.now();});
addEventListener('resize',resize);resize();
function loop(now){const delay=900-Number(speed.value)*140;if(now-last>delay){advance();last=now;}requestAnimationFrame(loop);}requestAnimationFrame(loop);
