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

Sudoku String Definitions

As of 18th January 2023 I'm employing a new Sudoku string definition to transport information about the board and candidates. This is currently employed on the
  • [Email this Board] feature - best place to copy/paste the new link
  • The [Import a Sudoku] will accept the new 162 character string as well as the normal 81
  • The transport of the solver board to the Sudoku Player does so using the new definition.
  • I will probably change some of the printable pages to use this soon.
  • As an example of it's usefulness I have changed the "Load example" links on the X-Wing page to precisely go to the correct position
Thus the new link looks like this example:
https://www.sudokuwiki.org/sudoku.htm?bd=vu4804032o1508g080030k10o888882647046888g06828060k10029k260b90478go003g0g95090b0b6a2c00g0bcg038ga8g9ao1506601oh847063a2ag288gg8g0626c082c2k20b159818920k9ag9462044

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.

The normal 81 character sudoku definition remains the same as before in all places and uses.

The new 162 character string takes each cell on the board and converts the clue or solution to a bit (1=1, 2=2, 3=4, 4=8, 5=16, 6=32, 7=64, 8=128 and 9=256). This allows a spread of candidates to be summed as a set of bit values. To really pack the information numbers are converted to base 32. The twist with the new definition is I wanted to also transport a flag to state if a number was a clue or solved cell. This is done by shifting the bits by one and setting the last bit as 1 for clue, 0 for not.

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
// shift to make room for one more bit
n = (n << 1) + (clue(y, x) ? 1 : 0);
h = n.toString(32); // convert to base 32
if (h.length < 2) h = '0' + h; // pad the number if not two digits
s += h; // append to string being made
}

To unpack a string we do the following
// This splits a string into an array of elements each 2 characters long 
var narr = theString.match(/.{1,2}/g); 
for (y = 0; y < 9; y++)
	for (x = 0; x < 9; x++) {
		n = parseInt(narr[y * 9 + x], 32); // convert base 32 to decimal
		clue(y, x) = (n & 1) ? 1 : 0; // extract the clue flag
		n = n >> 1; Shift the bits to remove the flag
		if (bit_count(n) == 1) { 
			// save the number as a clue or solution
		} else {
			// save the number as a set of candidates
		}
	}

The largest possible value in a cell, the sum of all numbers 1 to 9, is 511. Shifted left one bit this becomes 1022. Add the clue flag to make 1023. Converted to base 32 this becomes "vv". (However, since a cell with multiple candidates cannot be a clue, 1022 is the maximum value - which is "vu"). So no cell value will exceed 2 "digits" in this scheme. Hence it makes sense to use a fixed length definition rather than one with delimiters.

Any problems or questions, let me know in the comments below



Comments

CommentsTalk

... by: Sasha

Monday 27-Nov-2023
This algorithm inadvertently solves Naked Singles. The representation for a clue or solution is the same as a set containing a single candidate (bit_count(n) == 1).

If you encode a board containing a cell with a single candidate & then decode it, the candidate is solved.
Andrew Stuart writes:
This is true. I am wondering if that is a problem or not.
Sasha replies:Friday 11-Oct-2024
Because this is meant to be an interchange format for sharing & discussing Sudoku boards this loss of fidelity just didn't sit right. I've taken your algorithm & tweaked it a bit to solve this data loss. With your algorithm we run out of bits due to the doubling for the clue flag. Rather than doubling, I use offsets.

When encoding:
- empty cell: "00"
- value: zero padded base32(value)
- clue: zero padded base32(clue + 10)
- candidates: base32(base10(candidate bit pattern) + 20)

When decoding we deal with numeric ranges. Translate the base32 character pair to base 10:
0: empty cell
1...9: value
11...19: clue = value - 10
otherwise: candidates = decode bits (value - 20)

Still 2 characters per cell but with full fidelity.
Add to this Thread

... by: tebo

Thursday 8-Jun-2023
I entered the Sudoku String below into "Import a Sudoku", and the Puzzle rendered on the Board is exactly as I intended. I clicked "Solve Path" and Step 1 indicates Elimination of Candidates that are already Eliminated. So, I think your solver backed up a couple steps from the current State.

I'm trying to determine which Strategy handles the almost Deadly Pattern at (29)R16C79.

0m4e4cog1121k084g41k544403o0ggs409208121g1400409020g10g4o4a4110hg6082240h4hc28g4g2400h2281410g03200980g411g409k04ggg201184840321868k8k410m10g109g6o61108o2g621410g
Andrew Stuart writes:
Just tried this myself and didn't see any change in the board with the first step. Not sure why we see differently.
Add to this Thread

... by: tebo

Thursday 25-May-2023
You may have a copy/paste error in your unpack code: parseInt(narr[j * 9 + i], 32) => parseInt(narr[y * 9 + z], 32). Also, I'm not sure which board the new link (bd-vu480...) refers to.

This is very elegant!

- It captures both the Given puzzle and the current board state (i.e., by tracking the Clue in the last bit).
- It saves a lot of effort when transferring a puzzle between my solver/player and your solver/player.
- It enables more efficient storage of puzzles in the database.

This should be a community standard. Kudos.
Andrew Stuart writes:
Appreciate the comments Tebo :)
And Doh! Well spotted. I don't know why I used i and j in my code originally when x and y make more sense. Thanks
Add to this Thread

... by: Pieter, Newtown, Oz

Saturday 22-Apr-2023
Hi Andrew
Ingenious! 😃

However, where you have given the random example above, may I suggest you show both the old and the new definitions, for comparison? E.g. Using the X-Wing Example 1 as an example:

81 char string:
https://www.sudokuwiki.org/sudoku.htm?bd=100000569492056108056109240009640801064010000218035604040500016905061402621000005

162 char string, with candidates:
https://www.sudokuwiki.org/sudoku.htm?bd=03c848csc4cs1121g10hg005481020024881c8112002c0g1040h485848g0210h4481140350200gs403c4k81448050281k0091120k00gc80h4811s4cck80320g1c810c820020hc805210503cos0cok8s811

Ciao, Pieter 🙂
REPLY TO THIS POST
Article created on 18-January-2023. Views: 9475
This page was last modified on 19-January-2023.
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