News and Updates on X
SudokuWiki.org
Strategies for Popular Number Puzzles

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

Version 'B', 'C'

  • 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 L9B No Yes Yes Regular Yes - - 4
Killer Jigsaw M9B No Yes Yes Irregular Yes - - 5
KenKen K6C No Yes Yes - Yes 4 (+-x/) - 4
KenDoku D6C 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
	}


KenKen 6x6 and KenDoku 6x6 string packing

Lets also look at how KenKen and KenDoku are working with the new scheme.
As of Novemeber 23rd 2024 these puzzles are on version 'C'.

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 11 bits for the clue number which gives a maximum of 2047. If you spot a puzzle in the wild with a clue number greater than this please let me know. To tell the difference between a single candidate and a solved cell we're going to reserve 7 to 12 for a solved cell and add 12 to any bit sum of candidates. So a single candidate '1' will be 13. The largest number in this scheme is 63+12 or 75. It requires 7 bits to hold 75.
unused
|  |col | clue | cell no |
000 100 00101101001 1001001
| 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 <<= 11;  //  shift 11 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 << 7) + n; //  shift by 7 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 K6C or D6C) 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 & 127; // first 7 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 >>= 7; // remove first 7 bits
		op = p & 2047;  // could be clue or operand
		p >>= 11; // remove next 11 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
		}
	}




Comments

Your Name/Handle

Email Address - required for confirmation (it will not be displayed here)

Your Comment

Please enter the
letters you see:
arrow
Enter these letters Remember me


Please ensure your comment is relevant to this article.
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.
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.
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: 3081
This page was last modified on 20-November-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