SudokuWiki
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
  • 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
An example is
https://www.sudokuwiki.org/killersudoku.aspx?bd=212112111212112223213331443231221241134412231124133132322122212344411312111411312,171510200026110000000000000000000011000011000017160000001101060000090016110017000900000900001800160800040010160000001100002100001800001800140000080000000000000000

The new link looks like this example:
https://www.sudokuwiki.org/killersudoku.aspx?bd=5o3p01015800005p010001015202025j0101002q4g00310203280002020000010103032920008i0202020201015101014800001r0360015o5i024h003a4k002a000202010202040002002b030101040400,q01u1u1uvuvuvuvuvuq01u1uvuvuvuvuvuvuq05u5uvuvuvuvuvuvu5u5uvuvuvuvuvuvuvu5u5uugugugugugvuvu5u5uvuvuvuvuvuvuvu5uq05uvuvuvuvuvuvu5uq05uvuvuvuvuvuvu5uq05uvuvuvuvuvuvu

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

CommentsTalk

... by: Emma

Friday 17-May-2024
I came accross your sudoku solver a few weeks ago and I already fell in love with your puzzles. Weekly str8ts (with settis and BCA), BX, 1 to 25, I'm hooked.

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
Andrew Stuart writes:
I'm really embarrassed! So I was working with a chap who had a fifth colour in his Killer colour map and I realised that I do cater for this on the input popup - since neither of us have a perfect four-colour map algorithm and it's just simpler to use a fifth colour. So We agreed to expand the number of bits from 2 to 3. I changed all the code and this happened right at the beginning so no one would have been using the old 2 bit version of the definition. But I'd already written the copy for the page - and it was the 2 bit example. I've pasted in his puzzle now.

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.
- [Del]
Emma replies:Monday 20-May-2024
Haha, no worries, thanks for your reply! It was fun to see how this feature works and I'm glad I could participate :)
Add to this Thread
Article created on 9-May-2024. Views: 613
This page was last modified on 9-May-2024.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024
Playwire