Main Page - Back
 
From SudokuWiki.org, the puzzle solver's site
breakline

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; 
	}



Article created on 9-May-2024. Views: 1815
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