Skip to content

Instantly share code, notes, and snippets.

@killroy42

killroy42/sudoku_p20.js

Last active October 30, 2024 09:31
Show Gist options
  • Save killroy42/558251abf382fcf9684354748bd6a749 to your computer and use it in GitHub Desktop.
Save killroy42/558251abf382fcf9684354748bd6a749 to your computer and use it in GitHub Desktop.
Download ZIP
Solved Sudoku Compactor P81->p20
Raw
sudoku_p20.js
(()=>{
const p20 = (()=>{
const F=[1,1,2,6,24,120,720,5040,40320,362880];
const chrLUT = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~', encNum = n=>chrLUT[n], decNum = c=>chrLUT.indexOf(c);
const sizeMap = [9,6,6,6,6,6,6,6,6,6,3,3,3], bitMap = [19,10,10,10,10,10,10,10,10,10,3,3,3], reBitMap = new RegExp(bitMap.map(n=>`(.{${n}})`).join(''));
const N9 = [...Array(9).keys()], boxLUT = N9.map(b=>N9.map(n=>(~~(b/3)*27+b*3%9)+~~(n/3)*9+n%3)), rowLUT = N9.map(r=>N9.map(c=>r*9+c)), colLUT = N9.map(c=>N9.map(r=>r*9+c));
const getLc = (perm,s=[...perm.keys()])=>perm.map((n,_,a,i=s.indexOf(n))=>(s.splice(i,1),i));
const fromLc = (code,s=[...code.keys()])=>code.map((i,_,a,e=s[i])=>(s.splice(i, 1),e));
const lcToInt = (lc,l=lc.length)=>lc.reduce((int,n,i)=>int+n*F[l-i-1],0);
const intToLc = (int,z=9)=>[...Array(z)].map((_,i,a,c=F[z-i-1],n=Math.floor(int/c))=>(int%=c,n));
const getP = (p,m)=>m.map(i=>p[i]), getB = (p,b)=>getP(p,boxLUT[b]), getR = (p,r)=>getP(p,rowLUT[r]), getC = (p,c)=>getP(p,colLUT[c]);
const deflate = (perm,def)=>perm.map(n=>def.reduce((o,d)=>o-(n>d?1:0),n));
const inflate = (perm,inf)=>perm.map(n=>inf.sort().reduce((o,i)=>o+(o>=i?1:0),n));
const solEnc = (puz,p=puz.split('').map(c=>c-1))=>[
getB(p,0),
...[0,1,2].map(i=>getR(p,i)).map(r=>deflate(r.slice(3,9),r.slice(0,3))),
...[0,1,2,3,4,5].map(i=>getC(p,i)).map(r=>deflate(r.slice(3,9),r.slice(0,3))),
...[3,4,5].map(i=>getR(p,i)).map(r=>deflate(r.slice(6,9),r.slice(0,6))),
]
.map(p=>lcToInt(getLc(p)))
.map((n,i)=>n.toString(2).padStart(bitMap[i],'0')).join('').padEnd(120,'0')
.match(/.{6}/g).map(b=>encNum(parseInt(b, 2))).join('');
const solDec = data => {
let perms = data
.split('').map(decNum).map(n=>n.toString(2).padStart(6,'0'))
.join('').match(reBitMap).slice(1).map((b,i)=>fromLc(intToLc(parseInt(b,2),sizeMap[i])));
let p = [...Array(81)].map(_=>0);
boxLUT[0].forEach((i,n)=>p[i]=perms[0][n]);
[0,1,2].forEach(r=>inflate(perms[r+1],getR(p,r).slice(0,3)).forEach((n,i)=>p[rowLUT[r][i+3]]=n));
[0,1,2,3,4,5].forEach(c=>inflate(perms[c+4],getC(p,c).slice(0,3)).forEach((n,i)=>p[colLUT[c][i+3]]=n));
[3,4,5].forEach(r=>inflate(perms[r+7],getR(p,r).slice(0,6)).forEach((n,i)=>p[rowLUT[r][i+6]]=n));
N9.forEach(i=>p[[6,7,8].find(r=>getR(p,r).slice(0,6).indexOf(i)===-1)*9+[6,7,8].find(c=>getC(p,c).slice(0,6).indexOf(i)===-1)]=i);
return p.map(n =>n+1).join('');
};
const puzEnc = p=>p.replace(/[^0]/g,1).padEnd(84,0).match(/.{6}/g).map(b=>encNum(parseInt(b,2))).join('');
const puzDec = d=>[...d].map(decNum).map(n=>n.toString(2).padStart(6,0)).join('').slice(0,81);
const enc = (s,p)=>solEnc(s)+puzEnc(p);
const dec = (d,s=solDec(d.slice(0,20)))=>[s,puzDec(d.slice(20,34)).split('').map((c,i)=>c^1?0:s[i]).join('')];
return {solEnc,solDec,puzEnc,puzDec,enc,dec};
})();
/*
Encoding order:
111|222|222
111|333|333
111|444|444
---+---+---
567|89a|bbb
567|89a|ccc
567|89a|ddd
---+---+---
567|89a|
567|89a|
567|89a|
In order above:
1. Calculate Lehmer Code for each set of sizes 1x9,9x6,3x3
2. Convert to integer and align to bit sizes 19,10,10,10,10,10,10,10,10,10,3,3,3
3. Join and pad to 120 bits
4. Split into groups of 6 and convert a "safe" character
Reverse to decode
Only "tricky" detail is converting a permutation of 9 elements to a subset of 6 or 3 (inflate/ deflate)
*/
const printP81 = p81 => p81.match(/.{9}/g).map((r,i)=>r.match(/.../g).join(' ')+(i==2||i==5?'\n':'')).join('\n');
const printP = p => printP81(p.map(n =>String(n+1)).join(''));
let p81 = '200000090000000080060053000030060008000070060070000020000000015800020000000001030';
let s81 = '281647593345219687967853142439162758152378469678495321726934815813526974594781236';
console.log('Solution:');
console.log(printP81(s81));
console.log('p20.solEnc:', p20.solEnc(s81));
console.log(printP81(p20.solDec(p20.solEnc(s81))));
console.log('Puzzle:');
console.log(printP81(p81));
console.log('p20.puzEnc:', p20.puzEnc(p81));
console.log(printP81(p20.puzDec(p20.puzEnc(p81)).split('').map((c,i)=>c^1?0:s81[i]).join('')));
console.log('s81:', s81);
console.log('p81:', p81);
console.log('p20.enc(s81,p81):', p20.enc(s81,p81));
console.log('p20.dec(p20.enc(s81,p81)):', ...p20.dec(p20.enc(s81,p81)));
})();
Raw
sudoku_p32_a.js
(()=>{
const
F=[1,1,2,6,24,120,720,5040,40320,362880],
N9 = [...Array(9).keys()],
m1=[9,6,6,6,6,6,6,6,6,6,3,3,3],
m2=m1.map(s=>BigInt(F[s])),
m3='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~',
m4 = [N9.map(b=>N9.map(n=>(~~(b/3)*27+b*3%9)+~~(n/3)*9+n%3)),N9.map(r=>N9.map(c=>r*9+c)),N9.map(c=>N9.map(r=>r*9+c))],
m5 = [[[0],0,0,0],[[0,1,2],1,3,1],[[0,1,2,3,4,5],2,3,4],[[3,4,5],1,6,7]],
encN=n=>m3[n],decN=c=>m3.indexOf(c),ce=(p,t,i)=>m4[t][i].map(i=>p[i]),
def = (perm,def)=>perm.map(n=>def.reduce((o,d)=>o-(n>d?1:0),n)), inf = (perm,inf)=>perm.map(n=>inf.sort().reduce((o,i)=>o+(o>=i?1:0),n)),
getLc = (p,i,a,s=[...p.keys()],l=s.length)=>p.map((n,_,a,i=s.indexOf(n))=>(s.splice(i,1),i)).reduce((r,n,i)=>r+n*F[l-i-1],0),
fromLc = (l,z=9,s=[...Array(z).keys()])=>[...s].map((_,i,a,c=F[z-i-1],n=Math.floor(l/c))=>(l%=c,n)).map((i,_,a,e=s[i])=>(s.splice(i, 1),e)),
smoo = (n,s)=>n.reduce((t,n,i)=>(t+BigInt(n))*BigInt(s[i+1]||1),BigInt(0)),
unsmoo = (n,s,l=s.length,r=[])=>{for(let i=l-1;i>=0;i--)r[i]=Number(n%s[i]),n/=s[i];return r;},
pack = (s81,p81) => {
let s=s81.split('').map(c=>c-1);
return (
smoo(m5.map(([n,t,z])=>n.map(i=>ce(s,t,i)).map(r=>def(r.slice(z,9),r.slice(0,z)))).flat().map(getLc),m2).toString(2)+
p81.replace(/[^0]/g,1)
).padEnd(192,0).match(/.{6}/g).map(b=>encN(parseInt(b,2))).join('');
},
unpack = code => {
let [_,decS,decP] = code.split('').map(c=>decN(c).toString(2).padStart(6,0)).join('').match(/(.{110})(.{81})/);
let perms = unsmoo(BigInt('0b'+decS),m2).map((n,i)=>fromLc(n,m1[i]));
let s = [...Array(81)].map(_=>0);
m5.map(([n,t,z,d])=>n.forEach(r=>inf(perms[r+d],ce(s,t,r).slice(0,z)).forEach((n,i)=>s[m4[t][r][i+z]]=n)));
N9.forEach(i=>s[[6,7,8].find(r=>ce(s,1,r).slice(0,6).indexOf(i)===-1)*9+[6,7,8].find(c=>ce(s,2,c).slice(0,6).indexOf(i)===-1)]=i);
let s81 = s.map(n =>n+1).join(''), p81 = decP.split('').map((c,i)=>c^1?0:s81[i]).join('');
return [s81,p81];
};
[
['281647593345219687967853142439162758152378469678495321726934815813526974594781236',
'200000090000000080060053000030060008000070060070000020000000015800020000000001030'],
['379281654164975283285643719937452168658317492412896375723568941546139827891724536',
'000001000064000280080003010907400000000010000000006305020500040046000820000700000'],
].forEach(([solIn,puzIn])=>{
let packed = pack(solIn,puzIn);
console.log('packed:', packed);
let [solOut,puzOut] = unpack(pack(solIn,puzIn));
console.log(' solIn: ', solIn);
console.log(' solOut:', solOut);
console.log(' solIn === solOut:', solIn === solOut);
console.log(' puzIn: ', puzIn);
console.log(' puzOut:', puzOut);
console.log(' puzIn === puzOut:', puzIn === puzOut);
});
})();
Raw
sudoku_p32_humanable.js
(() => {
// Helpers
const factorial = n => (n <= 0) ? 1 : n * factorial(n - 1);
const removeSymbs = (perm, symbs) => {
// Reduce a permutation by a subset of its symbols
return perm.map(n => symbs.reduce((o, d) => o - (n > d ? 1 : 0), n));
};
const insertSymbs = (perm, symbs) => {
// Inject symbols into permutation at correct positions
return perm.map(n => [...symbs].sort().reduce((o, i) => o + (o >= i ? 1 : 0), n));
};
// Lehmer Code
const createLehmerCode = arr => {
const lc = [], len = arr.length, symbs = [...arr.values()].sort();
for(let i = 0; i < len; i++) {
let idx = symbs.indexOf(arr[i]);
lc.push(idx);
symbs.splice(idx, 1);
}
let int = 0;
for(let i = 0; i < len; i++) int += lc[i] * factorial(len - i - 1);
return int;
};
const integerToLehmerCode = (int, permSize) => {
if(permSize <= 1) return [0];
let multiplier = factorial(permSize - 1);
let digit = Math.floor(int / multiplier);
return [digit].concat(integerToLehmerCode(int % multiplier, permSize - 1));
};
const parseLehmerCode = (int, size) => {
let lc = integerToLehmerCode(int, size);
const res = [], len = lc.length, symbs = [...lc.keys()];
for(let i = 0; i < len; i++) {
let idx = lc[i];
res.push(symbs[idx]);
symbs.splice(idx, 1);
}
return res;
};
// B64 encoding
const Char64Map = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~';
const encodeChar64 = num => Char64Map[num], decodeChar64 = char => Char64Map.indexOf(char);
const bitsToChar64 = bits => bits.match(/.{6}/g).map(bits => encodeChar64(parseInt(bits, 2))).join('');
const char64ToBits = chars => [...chars].map(char => decodeChar64(char).toString(2).padStart(6, 0)).join('');
// BigInt packing
const joinBigInts = (bis, biScales) => bis.reduce((acc, cur, i)=>(acc + cur) * (biScales[i + 1] || 1n), 0n);
const splitBigInt = (bi, biScales) => {
let len = biScales.length, res = [];
for(let i = len - 1; i >= 0; i--) {
res[i] = Number(bi % biScales[i]);
bi /= biScales[i];
}
return res;
};
// Sudoku packing details
const N9 = [0, 1, 2, 3, 4, 5, 6, 7, 8];
const Regions = {
box: N9.map(b => N9.map(n => (Math.floor(b / 3) * 27 + b * 3 % 9) + Math.floor(n / 3) * 9 + n % 3)),
row: N9.map(r => N9.map(c => r * 9 + c)),
col: N9.map(c => N9.map(r => r * 9 + c))
};
const PackOrder = [
{type: 'box', parts: [0], size: 9},
{type: 'row', parts: [0, 1, 2], size: 6},
{type: 'col', parts: [0, 1, 2, 3, 4, 5], size: 6},
{type: 'row', parts: [3, 4, 5], size: 3}
];
const PackScales = PackOrder.flatMap(({type, parts, size}) => parts.map(i => BigInt(factorial(size))));
const getReg = (sol, type, idx) => Regions[type][idx].map(i => sol[i]);
const setReg = (sol, type, idx, vals) => Regions[type][idx].map((idx, i) => sol[idx] = vals[i]);
// Packing Functions
const fillBox9 = sol => {
const rows = [6, 7, 8].map(r => getReg(sol, 'row', r).slice(0, 6)),
cols = [6, 7, 8].map(c => getReg(sol, 'col', c).slice(0, 6));
N9.map(i => [
6 + rows.findIndex(r => r.indexOf(i) === -1),
6 + cols.findIndex(c => c.indexOf(i) === -1),
i
])
.forEach(([row, col, i]) => sol[row * 9 + col] = i);
};
const pack = (s81, p81) => {
let vals = [...s81].map(n => n - 1);
let codes = PackOrder.flatMap(({type, parts, size}) => parts
.map(idx => getReg(vals, type, idx))
.map(perm => removeSymbs(perm.slice(9 - size, 9), perm.slice(0, 9 - size)))
.map(createLehmerCode)
.map(BigInt)
);
let solBits = joinBigInts(codes, PackScales).toString(2);
let puzBits = p81.replace(/[^0]/g, 1);
let jointBits = (solBits + puzBits).padEnd(192,0);
return bitsToChar64(jointBits);
};
const unpack = (packed) => {
let jointBits = char64ToBits(packed),
solBits = jointBits.slice(0, 110),
puzBits = jointBits.slice(110, 191),
sol = [],
codes = splitBigInt(BigInt('0b' + solBits), PackScales);
PackOrder.forEach(({type, parts, size}) => parts.forEach(idx => {
let perm = parseLehmerCode(codes.shift(), size),
symbs = getReg(sol, type, idx).slice(0, 9 - size);
setReg(sol, type, idx, symbs.concat(insertSymbs(perm, symbs)));
}));
fillBox9(sol);
let s81 = sol.map(n => n + 1).join(''),
p81 = [...puzBits].map((b, i) => b === '0' ? b : s81[i]).join('');
return {s81, p81};
};
let s81 = '379281654164975283285643719937452168658317492412896375723568941546139827891724536';
let p81 = '000001000064000280080003010907400000000010000000006305020500040046000820000700000';
console.log('s81:', s81);
console.log('p81:', p81);
let packed = pack(s81, p81);
console.log('packed:', packed);
let unpacked = unpack(packed);
console.log('unpacked:', unpacked);
console.log('unpacked.s81 === s81:', unpacked.s81 === s81);
console.log('unpacked.p81 === p81:', unpacked.p81 === p81);
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment