Killer and KenKen String Definitions 2.0
This page continues the
discussion of packed puzzle strings from Sudoku and Jigsaws. I've been collaborating with
Quintin May a.k.a.
Sasha behind the scenes to come up with a better approach. Here we aim to capture and transport the board and progress in minimal fashion for Killers, KenKen and KenDoku. This page is a very compressed overview of the approach - but enough to explain how. Quintin has created a superb and comprehensive documentation library - and if you intend to code - I recommend you browse the following:
There are also some
Test Strings built into links to each solver.
Version 'A'
The original 'unpacked' killer definition remains the same as before in all places and uses. We recognise that if one is only interested in a definition of the puzzle - then this is still slightly shorter. The 'unpacked' version consists of
- The address https://www.sudokuwiki.org/killersudoku.aspx?bd=
- 81 characters for the colours defining the shapes
- a comma
- 162 characters stating the clues, padded with zeros if necessary. Clues are the sums of the cages and appear once per cage in the top-left most position
It contains the puzzle only, no progress. An example is
Version 'B'
- All puzzles need the ability to store progress - which consists of solved cells and candidates.
- Unlike Sudoku the Clue/solved cell difference is not needed. A single cell cage may be printed with a large number but it is still a cage clue.
- It will be very helpful to include a version header to give vital context for interpreting the data
Let us look at the kind of information we need to pack:
Leave Out | |
Encode | |
|
Prefix |
Clues |
Solved |
Notes |
Boxes |
Cages |
Clue Operands |
Black Cells |
Bytes / Cell |
Killer Sudoku |
L |
No |
Yes |
Yes |
Regular |
Yes |
- |
- |
4 |
Killer Jigsaw |
M |
No |
Yes |
Yes |
Irregular |
Yes |
- |
- |
5 |
KenKen |
K |
No |
Yes |
Yes |
- |
Yes |
4 (+-x/) |
- |
4 |
KenDoku |
D |
No |
Yes |
Yes |
Regular |
Yes |
4 (+-x/) |
- |
4 |
| |
OFF SET |
SHIFTED |
SHIFTED |
SHIFTED |
SHIFTED | |
The commonality of these puzzles are their 'cages'. Cages have clue numbers and a single-cell cage can be expressed as a clue number in it's cage even if the puzzle designer prints it as a large number.
- There can be up to five cage colours so 3 bits needed.
- In 9x9 Killer Sudoku the largest clue number will be 45 (all the numbers summed). 6 bits required to store this.
- In KenKen 6x6 there is hard cap of 999 for clue numbers (at least as I make them). We need 10 bits to store up to 1023. A clue larger than this will abort the encoding. Do send me examples in case they exist in the wild.
- We will continue to store progress in 10 bits to make it similar to the rest of the scheme. That means adding 9 to solved cells and 18 to candidates to get the correct offset
- For Killer Jigsaw we need 9 bits for the box numbers
- Finally, there is advantage to not storing the box pattern for Killer Sudoku. The 4 bits we save gets us over the 5 bytes per cell boundary to 4 bytes per cell.
So lets build a packed Killer and Killer Jigsaw:
unused
| |box |col|clue |cell no |
0 1000 000 001011 1000010001
| byte 1 | byte 2 |byte 3|
We've squeezed all the data into 3 bytes but expressed in a 36 base alphabet this becomes 5 bytes long per cell. For Killer Sudoku the fifth byte will always be zero so we can leave it off.
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
p = [cell box number]; // 0 if Killer Sudoku
p = (p << 3) + [cage colour 0..4]; // shift by 3 and add next value
p = (p << 6) + [cage clue]; // shift by 6 and add next value
n = get the cell value or set of candidates as bits
if( candidates )
n += 18; // offset by 18
else n += 9; // offset by 9
p = (p << 10) + n; // shift by 10 and add next value
h = p.toString(36); // convert to base 36
// pad the number if not 4 or 5 digits
h = h.padStart((jigsaw killer)? 5 : 4, '0');
s += h; // append to string being made
}
To unpack the string (after checking the version is
L9B or
M9B) we do the following
// This splits a string into an array of elements each 4 or 5 characters long
let cArr = astr.substring(3).match((jigsaw) ? /.{1,5}/g /.{1,4}/g );
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
p = parseInt(cArr [y * 9 + x], 36); // convert base 36 to decimal
n = p & 1023; // first 10 bits
if (n <= 18) {
n -= 9; { // removed 'solved cell' offset
// save the number as a solution
} else {
// save the number as a set of candidates
n -= 18;
}
p >>= 10; // remove first 10 bits
[cage clue] = p & 63; // next 6 bits
p >>= 6; // remove next 6 bits
[cage colour] = (p & 7) + 1; // next 3 bits
[box number] = (p >> 3); // last4 bits
// Will be 0 for vanilla Sudoku
}
Here is an example Killer Jigsaw packed up and loaded on a link to the solver:
KenKen 6x6 and KenDoku 6x6 string packing
Lets also look at how KenKen and KenDoku are working with the new scheme.
We're going to do the packing slightly differently than with Killer. The issue is the operands on the clues. We could reserve 2 bits for them but it turns out that for 6x6 KenKen this pushes the cell size into 5 bytes instead of 4. If we use a temporary storage array we can store the operand in the cell to the right (if appropriate) or the cell below (if appropriate). The storage is always in the future of the j and i FOR loop so it will always get picked up. Unpacking we are guaranteed to have an operand and not a clue number if there is a cell above or to the left with the same colour. So both ways only one scan of the board arrays is needed.
We are reserving 10 bits for the clue number which gives a maximum of 1023. If you spot a puzzle in the wild with a clue number greater than this please let me know. Since the board only goes as high as 6 we only need 8 bits to hold the solved cells and candidates.
unused
| |col | clue | cell no |
000 100 0001101001 10001001
| byte 1 | byte 2 | byte 3 |
All the data is again fitting into 3 bytes but expressed in a 36 base alphabet this only requires 4 bytes per cell as the absolute number is smaller than for Killer. To pack KenKen and KenDoku requires the following:
let store = 6x6 array of zeros
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
p = [cage colour 0..4] ; // Start with the cage colour
p <<= 10; // shift 10 bits
if( clue ) {
p += [cage clue]; // add clue
if( cell_to_right_same_colour )
store[y][x+1] = [operator_number];
else if( cell_below_same_colour )
store[y+1][x] = [operator_number];
// else - 1-cell cage, ignore
} else if( store[y][x] != 0 ) {
p += store[y][x]; // operator 1 to 4
}
n = get the cell value or set of candidates as bits
if( candidates )
n += 12; // offset by 12
else n += 6; // offset by 6
p = (p << 8) + n; // shift by 8 and add next value
h = p.toString(36); // convert to base 36
h = h.padStart(4, '0'); // pad the number if not five digits
s += h; // append to string being made
}
To unpack the string (after checking the version is
K6B or
D6B) we do the following
// This splits a string into an array of elements each 4 characters long
let cArr = astr.substring(3).match(/.{1,4}/g);
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
p = parseInt(cArr [y * 9 + x], 36); // convert base 36 to decimal
n = p & 255; // first 8 bits
if (n <= 12) {
n -= 6; { // removed 'solved cell' offset
// save the number as a solution
} else {
// save the number as a set of candidates
n -= 12;
}
p >>= 8; // remove first 8 bits
op = p & 1023; // could be clue or operand
p >>= 10; // remove next 10 bits
[cage colour] = p + 1; // last 3 bits
if( op ) {
if( cell_above_same_colour or cell_left_same_colour ) {
// puts the operand with the clue in the same cell:
if( cell_above_same_colour ) opp[y-1][x] = op;
if( cell_left_same_colour ) opp[y][x-1] = op;
}
else [cage clue] = op; // must be a clue
}
}
Here is an example Killer Jigsaw packed up and loaded on a link to the solver:
Comments
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted - no need to use <p> or <br> tags.
... by: Emma
I thought I'd take the time to understand this page since you took the time to write it. Nice new feature! Your explanation is clear and straightforward, it's nice to have this new Killer string definition that allows transporting candidates.
I have a few questions/potential corrections, and I thought it might help you that I share them.
"The new link looks like this example:"
It's not a valid string definition, right? I mean, the colors, clues and cages are a bit of a mess :)
"(max= 45 << 2 + 4)"
It seems you meant (max= 45 << 3 + 4), i.e. 364 as you explained above, since you added the mysterious and optional 5th color which requires a 3rd digit.
"s1.match(/.{1,2}/g)"
fancy! I'm a javascript noob, and this looks like a magical formula to me :D
"// want both the first three bits"
should you delete the word "both"? I feel like with this 5th color feature which requires a third bit you changed "two" to "three" without removing "both"
"shapecol[y][x] = (n & 7) + 1;"
I'm not sure why you add 1 here.
I mean, (n & 7) gives you the last three bits, isn't it enough?
You created that string without removing 1, didn't you?
n = (clue[y][x] << 3) + shapecol[y][x];
It feels like you want to store colors as 1-5 in the matrices and 0-4 in the string (you probably did it at first to save one bit?), but then maybe "-1" is missing in this n= formula
top-left most > I felt like "top left" is enough, I googled it to check:
https://ell.stackexchange.com/questions/18112/topmost-left-or-top-leftmost
Anyway, I hope my message can help a bit.
Cheers and thanks again for sharing all these puzzles!
Emma
Agggghhh. Sorry to have led you down a rabbit hole. Removed "both" as well.
Yes, n = (clue[y][x] << 3) + (shapecol[y][x]-1); was missing the -1. Was in the code. Good catch.