129 lines
13 KiB
JavaScript
129 lines
13 KiB
JavaScript
// Pure rules / geometry / solver. Each mode receives its own standalone copy.
|
||
export function units(c){return c.shape?c.shape.map(([x,y])=>[c.x+x,c.y+y]):Array.from({length:(c.w||1)*(c.h||1)},(_,i)=>[c.x+i%(c.w||1),c.y+Math.floor(i/(c.w||1))]);}
|
||
export function outlineUnits(c){
|
||
const occupied=new Set(units(c).map(p=>p.join(','))),edges=[];
|
||
for(const [x,y]of units(c))for(const [dx,dy,a,b]of [[0,-1,[x,y],[x+1,y]],[1,0,[x+1,y],[x+1,y+1]],[0,1,[x+1,y+1],[x,y+1]],[-1,0,[x,y+1],[x,y]]])if(!occupied.has((x+dx)+','+(y+dy)))edges.push([a,b]);
|
||
const next=new Map(edges.map(([a,b])=>[a.join(','),b])),start=edges[0][0],points=[start];let at=next.get(start.join(','));
|
||
while(at.join(',')!==start.join(',')){points.push(at);at=next.get(at.join(','));if(points.length>edges.length)throw Error('Invalid block contour');}
|
||
return points.filter((b,i)=>{const a=points[(i+points.length-1)%points.length],d=points[(i+1)%points.length];return (b[0]-a[0])*(d[1]-b[1])!==(b[1]-a[1])*(d[0]-b[0]);});
|
||
}
|
||
export function graph(level){
|
||
const cells=level.cells, ids=new Map(cells.map((c,i)=>[c.id,i]));
|
||
if(ids.size!==cells.length)throw Error('重复格 id');
|
||
const adj=cells.map(()=>[]), occupancy=new Map();
|
||
if(level.geometry!=='hex') for(let i=0;i<cells.length;i++)for(const [x,y]of units(cells[i])){const k=x+','+y;if(occupancy.has(k))throw Error('拼块重叠');occupancy.set(k,i);}
|
||
for(let i=0;i<cells.length;i++)for(let j=i+1;j<cells.length;j++){
|
||
let connected=false;
|
||
if(level.geometry==='hex'){let dq=cells[j].q-cells[i].q,dr=cells[j].r-cells[i].r;connected=[[1,0],[-1,0],[0,1],[0,-1],[1,-1],[-1,1]].some(([a,b])=>a===dq&&b===dr);}
|
||
else connected=units(cells[i]).some(([x,y])=>[[1,0],[-1,0],[0,1],[0,-1]].some(([a,b])=>occupancy.get((x+a)+','+(y+b))===j));
|
||
if(connected){adj[i].push(j);adj[j].push(i);}
|
||
}
|
||
const clues=new Map();for(const c of cells)if(c.clue!==undefined){if(!Number.isInteger(c.clue)||c.clue<1||c.clue>cells.length||clues.has(c.clue))throw Error('数字范围或重复');clues.set(c.clue,ids.get(c.id));}
|
||
return {cells,ids,adj,clues};
|
||
}
|
||
export function constraints(level){
|
||
const result=[];
|
||
for(let i=0;i<(level.relations||[]).length;i++)result.push({key:'relation:'+i,kind:'relation',...level.relations[i]});
|
||
for(let i=0;i<(level.orderChains||[]).length;i++)for(let j=0;j<level.orderChains[i].length-1;j++)result.push({key:'order:'+i+':'+j,kind:'order',from:level.orderChains[i][j],to:level.orderChains[i][j+1]});
|
||
for(let i=0;i<(level.windows||[]).length;i++)result.push({key:'window:'+i,kind:'window',...level.windows[i]});
|
||
for(const c of level.cells)if(c.parity)result.push({key:'parity:'+c.id,kind:'parity',cell:c.id,value:c.parity});
|
||
for(const c of level.cells)if(c.direction)result.push({key:'direction:'+c.id,kind:'direction',cell:c.id,value:c.direction});
|
||
if((level.features||[]).includes('alternation'))result.push({key:'alternation',kind:'alternation'});
|
||
for(let i=0;i<(level.walls||[]).length;i++)result.push({key:'wall:'+i,kind:'wall',edge:level.walls[i]});
|
||
for(let i=0;i<(level.doors||[]).length;i++)result.push({key:'door:'+i,kind:'door',...level.doors[i]});
|
||
for(let i=0;i<(level.gates||[]).length;i++)result.push({key:'gate:'+i,kind:'gate',...level.gates[i]});
|
||
return result;
|
||
}
|
||
export function sideBetween(level,cellId,neighborId){
|
||
const c=level.cells.find(c=>c.id===cellId),n=level.cells.find(c=>c.id===neighborId);const occupied=new Set(units(n).map(p=>p.join(',')));const sides=new Set();for(const [x,y]of units(c))for(const [dx,dy,s]of [[-1,0,'l'],[1,0,'r'],[0,-1,'u'],[0,1,'d']])if(occupied.has((x+dx)+','+(y+dy)))sides.add(s);return sides.size===1?[...sides][0]:null;
|
||
}
|
||
export function directionAt(level,path,k){if(k===0||k===path.length-1)return null;const a=sideBetween(level,path[k],path[k-1]),b=sideBetween(level,path[k],path[k+1]);return a&&b?[a,b].sort().join(''):null;}
|
||
export function doorLatched(door,path){
|
||
for(let i=1;i<path.length;i++)if(door.edge.includes(path[i-1])&&door.edge.includes(path[i])&&(Boolean(door.initialOpen)!==Boolean(i%2)))return true;
|
||
return false;
|
||
}
|
||
export function doorOpen(door,path){return Array.isArray(path)?doorLatched(door,path)||(Boolean(door.initialOpen)!==Boolean(path.length%2)):Boolean(door.initialOpen)!==Boolean(path%2);}
|
||
export const directionNames={lr:'左右直行',du:'上下直行',ru:'上与右拐角',dr:'右与下拐角',dl:'下与左拐角',lu:'左与上拐角'};
|
||
export function edgeBlocked(level,path,a,b,{omit=null}={}){
|
||
for(let i=0;i<(level.walls||[]).length;i++)if(omit!=='wall:'+i&&level.walls[i].includes(a)&&level.walls[i].includes(b))return true;
|
||
for(let i=0;i<(level.doors||[]).length;i++)if(omit!=='door:'+i&&level.doors[i].edge.includes(a)&&level.doors[i].edge.includes(b)&&!doorOpen(level.doors[i],path))return true;
|
||
return false;
|
||
}
|
||
export function violations(level,path,{omit=null,complete=path.length===level.cells.length,ignoreClues=false}={}){
|
||
const positions=new Map(path.map((id,i)=>[id,i+1])),bad=[];
|
||
if(!ignoreClues)for(const c of level.cells)if(c.clue!==undefined){const at=positions.get(c.id);if(at!==undefined&&at!==c.clue||path.length>=c.clue&&path[c.clue-1]!==c.id)bad.push({key:'clue:'+c.id,cells:[c.id,path[c.clue-1]].filter(Boolean),message:'固定数字步号不符'});}
|
||
for(const r of constraints(level)){
|
||
if(r.key===omit)continue;
|
||
let fail=false,where=[];
|
||
if(r.kind==='relation'){
|
||
const a=positions.get(r.from),b=positions.get(r.to);where=[r.from,r.to];
|
||
fail=b!==undefined&&(a===undefined||b-a!==r.delta)||a!==undefined&&b===undefined&&path.length>=a+r.delta;
|
||
}else if(r.kind==='order'){where=[r.from,r.to];fail=positions.has(r.to)&&(!positions.has(r.from)||positions.get(r.from)>positions.get(r.to));}
|
||
else if(r.kind==='window'){where=[r.cell];const p=positions.get(r.cell);fail=p!==undefined?(p<r.min||p>r.max):path.length>=r.max;}
|
||
else if(r.kind==='parity'){where=[r.cell];const p=positions.get(r.cell);fail=p!==undefined&&(p%2===1)!==(r.value==='odd');}
|
||
else if(r.kind==='direction'){where=[r.cell];const p=positions.get(r.cell);fail=p===1||p!==undefined&&p<path.length&&directionAt(level,path,p-1)!==r.value||complete&&p===path.length;}
|
||
else if(r.kind==='alternation'){for(let i=1;i<path.length;i++){const a=level.cells.find(c=>c.id===path[i-1]),b=level.cells.find(c=>c.id===path[i]);if(a.category===b.category){fail=true;where.push(a.id,b.id);}}}
|
||
else if(r.kind==='wall'||r.kind==='door')for(let i=1;i<path.length;i++){if(r.edge.includes(path[i-1])&&r.edge.includes(path[i])&&(r.kind==='wall'||!doorOpen(r,path.slice(0,i)))){fail=true;where=r.edge;}}
|
||
else if(r.kind==='gate')for(let i=1;i<path.length;i++){if(r.edge.includes(path[i-1])&&r.edge.includes(path[i])){const s=positions.get(r.switchCell);if(s===undefined||s>i){fail=true;where=r.edge;}}}
|
||
if(fail)bad.push({key:r.key,cells:where,message:r.kind==='relation'?'相对步差不符':r.kind==='order'?'标记次序不符':r.kind==='window'?'到达窗口不符':r.kind==='parity'?'该格步号奇偶不符':r.kind==='direction'?'进出方向不符':r.kind==='wall'?'永久墙不能穿过':r.kind==='door'?'这一步门是关闭的':r.kind==='gate'?'开关尚未打开此门':'蓝橙颜色必须交替'});
|
||
}
|
||
return bad;
|
||
}
|
||
export function canAppend(level,path,id){
|
||
const g=graph(level);if(path.includes(id)||!g.ids.has(id))return false;
|
||
if(!path.length)return !g.clues.has(1)||g.cells[g.clues.get(1)].id===id;
|
||
const last=path.at(-1);if(edgeBlocked(level,path,last,id))return false;if(!g.adj[g.ids.get(last)].includes(g.ids.get(id)))return false;
|
||
if((level.features||[]).includes('alternation')&&g.cells[g.ids.get(last)].category===g.cells[g.ids.get(id)].category)return false;
|
||
for(const gate of level.gates||[])if(gate.edge.includes(last)&&gate.edge.includes(id)&&!path.includes(gate.switchCell))return false;
|
||
return true;
|
||
}
|
||
export function solve(level,{limit=2,omit=null,ignoreClues=false,prune=true,nodeLimit=Infinity}={}){
|
||
const g=graph(level),n=g.cells.length,results=[],path=[],seen=new Set();let nodes=0;
|
||
const active=constraints(level).filter(r=>r.key!==omit),alternating=active.some(r=>r.kind==='alternation');
|
||
const adj=g.adj.map((a,i)=>a.filter(j=>(!alternating||g.cells[i].category!==g.cells[j].category)&&!active.some(r=>r.kind==='wall'&&r.edge.includes(g.cells[i].id)&&r.edge.includes(g.cells[j].id))));
|
||
const forced=ignoreClues?new Map():g.clues;
|
||
function connected(cur){const reached=new Set([cur]),queue=[cur];for(let k=0;k<queue.length;k++)for(const j of adj[queue[k]])if(!seen.has(j)&&!reached.has(j)){reached.add(j);queue.push(j);}return reached.size===n-path.length+1;}
|
||
function visit(i){if(++nodes>nodeLimit)throw Error('求解节点预算耗尽，不能视为唯一');seen.add(i);path.push(g.cells[i].id);
|
||
const k=path.length;
|
||
if(!violations(level,path,{omit,ignoreClues}).length){
|
||
if(k===n)results.push([...path]);
|
||
else if(!prune||connected(i)){
|
||
const f=forced.get(k+1);let next=adj[i].filter(j=>!seen.has(j)&&(f===undefined||j===f));
|
||
next.sort((a,b)=>adj[a].filter(x=>!seen.has(x)).length-adj[b].filter(x=>!seen.has(x)).length);
|
||
for(const j of next){if(!ignoreClues&&g.cells[j].clue!==undefined&&g.cells[j].clue!==k+1)continue;
|
||
let blocked=edgeBlocked(level,path,g.cells[i].id,g.cells[j].id,{omit});for(const r of active)if(r.kind==='gate'&&r.edge.includes(g.cells[i].id)&&r.edge.includes(g.cells[j].id)&&!path.includes(r.switchCell))blocked=true;
|
||
if(!blocked)visit(j);if(results.length>=limit)break;
|
||
}
|
||
}
|
||
}
|
||
path.pop();seen.delete(i);
|
||
}
|
||
let starts=forced.has(1)?[forced.get(1)]:g.cells.map((_,i)=>i);
|
||
for(const i of starts){if(!ignoreClues&&g.cells[i].clue!==undefined&&g.cells[i].clue!==1)continue;visit(i);if(results.length>=limit)break;}
|
||
return results;
|
||
}
|
||
export function hint(solution,path){let k=0;while(k<path.length&&path[k]===solution[k])k++;if(k<path.length)return {kind:k?'backtrack':'restart',cell:k?path[k-1]:solution[0]};return k===solution.length?{kind:'none'}:{kind:k?'next':'start',cell:solution[k]};}
|
||
export function assertStructure(level){
|
||
const g=graph(level),n=g.cells.length;if(level.features?.includes('direction')&&(level.geometry==='hex'||level.cells.some(c=>c.direction&&units(c).length!==1)))throw Error('方向标记放在方形单位格，可与矩形/异形拼块混用');if(n<3||n>20)throw Error('格数须为3–20');
|
||
if(level.geometry==='hex'){const keys=new Set();for(const c of g.cells){if(!Number.isInteger(c.q)||!Number.isInteger(c.r))throw Error('六边坐标');const key=c.q+','+c.r;if(keys.has(key))throw Error('六边重叠');keys.add(key);}}
|
||
else for(const c of g.cells){if(!Number.isInteger(c.x)||!Number.isInteger(c.y))throw Error('坐标');const u=units(c);if(!u.length||new Set(u.map(p=>p.join(','))).size!==u.length)throw Error('异形重复');const seen=new Set([u[0].join(',')]);for(let changed=true;changed;){changed=false;for(const [x,y]of u)if(!seen.has(x+','+y)&&[[1,0],[-1,0],[0,1],[0,-1]].some(([a,b])=>seen.has((x+a)+','+(y+b)))){seen.add(x+','+y);changed=true;}}if(seen.size!==u.length)throw Error('异形不连通');}
|
||
const reach=new Set([0]),queue=[0];for(let k=0;k<queue.length;k++)for(const j of g.adj[queue[k]])if(!reach.has(j)){reach.add(j);queue.push(j);}if(reach.size!==n)throw Error('盘面不连通');
|
||
if((level.doors||[]).length>1)throw Error('步进门只允许一道门');
|
||
const physicalEdges=[...(level.walls||[]),...(level.doors||[]).map(d=>d.edge)].map(e=>[...e].sort().join('|'));if(new Set(physicalEdges).size!==physicalEdges.length)throw Error('墙门共边重复');
|
||
const pairs=[];
|
||
for(const r of constraints(level)){
|
||
for(const id of [r.cell,r.from,r.to,r.switchCell,...(r.edge||[])].filter(Boolean))if(!g.ids.has(id))throw Error('约束引用不存在');
|
||
if(r.kind==='relation'&&(!Number.isInteger(r.delta)||r.delta<1||r.delta>=n||r.from===r.to))throw Error('步差');
|
||
if(r.kind==='order')pairs.push([r.from,r.to]);
|
||
if(r.kind==='window'&&(!Number.isInteger(r.min)||!Number.isInteger(r.max)||r.min<1||r.max>n||r.max-r.min<2||g.cells[g.ids.get(r.cell)].clue!==undefined))throw Error('窗口需允许至少两个同奇偶步号且不与数字重叠');
|
||
if(r.kind==='parity'&&(!['odd','even'].includes(r.value)||g.cells[g.ids.get(r.cell)].clue!==undefined))throw Error('奇偶字段或同格数字冲突');
|
||
if(r.kind==='direction'&&!Object.keys(directionNames).includes(r.value))throw Error('方向');
|
||
if((r.kind==='wall'||r.kind==='door')&&(r.edge.length!==2||!g.adj[g.ids.get(r.edge[0])].includes(g.ids.get(r.edge[1]))))throw Error('墙或门不在共边');
|
||
if(r.kind==='gate'&&(r.edge.length!==2||!g.adj[g.ids.get(r.edge[0])].includes(g.ids.get(r.edge[1]))))throw Error('门不在共边');
|
||
}
|
||
if((level.gates||[]).length>3||new Set((level.gates||[]).map(r=>r.switchCell)).size!==(level.gates||[]).length)throw Error('最多三门且开关一对一');
|
||
if((level.features||[]).includes('alternation')&&g.cells.some(c=>!['circle','triangle'].includes(c.category)))throw Error('缺少类别');
|
||
function cycle(v,stack=new Set(),done=new Set()){if(stack.has(v))throw Error('先后链循环');if(done.has(v))return;stack.add(v);for(const [a,b]of pairs)if(a===v)cycle(b,stack,done);stack.delete(v);done.add(v);}for(const [a]of pairs)cycle(a);
|
||
return g;
|
||
}
|