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:

• Source code for library project and top-level entry point:
  https://github.com/BlueAnt1/puzzle-coding
• Documentation:
  https://blueant1.github.io/puzzle-coding/documentation/puzzlecoding/
• Encoding formats reference:
  https://blueant1.github.io/puzzle-coding/documentation/puzzlecoding/encodingformats

There are also some Test Strings built into links to each solver.

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

• 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:

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: