SudokuWiki.org
Strategies for Popular Number Puzzles
Killer String Definitions
As of 9th May 2024 I've created a new Killer Sudoku string definition to transport candidates and solved cells information to the Killer Solver. This will enable exact positions to be sent via a string, not just the starting board as before. The old 'puzzle' definition will continue to work.
This is currently employed on the [Email this Board] feature - best place to copy/paste the new link. I will probably change some of the documentation pages to use this soon.
The normal killer definition remains the same as before in all places and uses. This consists of
This is currently employed on the [Email this Board] feature - best place to copy/paste the new link. I will probably change some of the documentation pages to use this soon.
The normal killer definition remains the same as before in all places and uses. This 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
The new link looks like this example:
Users of the solver may want to know more about this string so that they can duplicate it for their own uses and understand how it works. So I'm presenting the information here.
There are two packed strings of 162 length separated by a comma. The first string contains the cage colours and clues. The second the candidate spread giving us the progress of the puzzle.
The second 162 character string takes each cell on the board and converts the solution or candidates into a sum of bits (1=1, 2=2, 3=4, 4=8, 5=16, 6=32, 7=64, 8=128 and 9=256). A solved cell has one 'candidate' number. Unlike Sudoku the solved cells don't need to be flagged as solved or an original clue. Killer can have single cages and are published with the big number but for the sake of the definition it is a cage clue. But I'm going to continue to shift the cell value by one bit so the code is the same for Sudoku.
A bit of javascript code shows how this is done
Users of the solver may want to know more about this string so that they can duplicate it for their own uses and understand how it works. So I'm presenting the information here.
There are two packed strings of 162 length separated by a comma. The first string contains the cage colours and clues. The second the candidate spread giving us the progress of the puzzle.
The second 162 character string takes each cell on the board and converts the solution or candidates into a sum of bits (1=1, 2=2, 3=4, 4=8, 5=16, 6=32, 7=64, 8=128 and 9=256). A solved cell has one 'candidate' number. Unlike Sudoku the solved cells don't need to be flagged as solved or an original clue. Killer can have single cages and are published with the big number but for the sake of the definition it is a cage clue. But I'm going to continue to shift the cell value by one bit so the code is the same for Sudoku.
A bit of javascript code shows how this is done
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
n = get the cell value or set of candidates as bits
n = (n << 1); // shift to make it similar to the Sudoku definition
h = n.toString(32); // convert to base 32
if (h.length < 2) h = '0' + h; // pad the number if not two digits
s2 += h; // append to string being made
}
For the first string we organise it thus: the maximum number for a cage clue is 45 - since cages cannot exceed a unit size. I'm aware there are Killer variants which have outsized cages or regions but that would be a different solver. The values for the cage colours are 1, 2, 3 and 4. Occasionally a fifth colour is needed so lets reserve 3 bits. Instead of two strings of 81 characters + 162 characters we can pack these into one string. We use three bits to store the colour number and shifting 45 by three bits = 360. So the largest number is 364. We can use the same base 32 as we use for the candidates.
So in the same for loop as above we can add:
for (y = 0; y < 9; y++)
for (x = 0; x < 9; x++) {
same code as above
.
.
// combine clue (max=45) and the shape colour
// colours are 1 to 5 but store as 0 to 4
n = (clue[y][x] << 3) + (shapecol[y][x]-1);
h = n.toString(32); // convert to base 32
if (h.length < 2) h = '0' + h; // pad the number if not two digits
s1 += h; // append to string being made
}
To unpack the strings we do the following
// This splits a string into an array of elements each 2 characters long var colclues_arr = s1.match(/.{1,2}/g); var cands_arr = s2.match(/.{1,2}/g); for (y = 0; y < 9; y++) for (x = 0; x < 9; x++) { // get the candidates out n = parseInt(cands_arr[y * 9 + x], 32); // convert base 32 to decimal Shift by one bit to remove the dummy flag cands[y][x] = n >> 1; // get the clues and shape colours out // first convert base 32 to decimal n = parseInt(colclues_arr[y * 9 + x], 32); // want the first three bits - gives 0 to 4, add 1 shapecol[y][x] = (n & 7) + 1; // shift the bits by 3 to remove the shapes and get the clue clue[y][x] = n >> 3; }
Comments
... 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.