Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
String Representation of a Sudoku
This note provides background information for the following functions:
Converts a sudoku to a string | |
Converts a string to a sudoku |
In the paclet, a sudoku is a Sudoku expression with two arguments. The first argument contains the information from which we can construct the groups and the numbers of the sudoku, the second argument contains only options for the display of the sudoku. So when we want to represent a sudoku by a string, this string must contain all information of the first argument.
In[1]:=
Needs["FredSimons`SudokuHints`"];AppendTo[$ContextPath,"FredSimons`SudokuHints`Private`"];
In[3]:=
sud=
"3MNXsj$J&STcAWTgnzOv2ltC5VkxxNH#fJULJdkyryNq||||v1X6ibxszaEMven0GdI524QPixLTK",
True
 | SudokuFromString |
 | ShowCandidates |
Out[3]=
In[4]:=
sud〚1〛
Out[4]=
The first step in making a string representation is that we store these data in integers of lists of integers.
The first list is the flattened list of the values of size, rowcolpositions and blockpositions, separated by the integer 0. In the example the list becomes {9,9,0,1,0,1}. We find back the three values by splitting the list at the inserted integer 0.
The values of outlinedgroups and coloredgroups are lists of lists of 9 integers. When we flatten these lists, we find back the original lists by partitioning with length 9.
Observe that from these three lists we can compute the groups of the sudoku, and therefore the cells of the sudoku.
A number value is either a list of one integer, which is a clue, or a list starting with 0, followed by the candidates in that cell. Clues and candidates will be treated differently.
For storing the clues, to each cell we assign 0 if there is no clue there and otherwise the clue itself.
In[5]:=
numbers=sud〚1〛["numbers"];cellvalues=First/@numbers
Out[6]=
10,22,30,49,50,60,70,80,90,100,110,129,138,142,150,160,170,180,190,200,210,220,230,245,250,260,270,280,293,300,310,320,330,340,350,360,370,380,390,400,414,420,437,441,450,460,470,480,490,500,510,520,530,540,550,569,570,587,590,601,613,620,630,640,650,660,670,680,690,700,710,721,730,747,752,760,775,780,790,800,810
These values can be considered as the digits of an integer:
In[7]:=
cluesinteger=FromDigits@Values[cellvalues]
Out[7]=
20900000009820000000005000030000000000040710000000000090701300000000001072050000
From this integer, we can reconstruct the clues. Convert the integer to a string, add the leading zeros and assign each digit to its string position:
In[8]:=
str=StringPadLeft[ToString[cluesinteger],81,"0"]AssociationThread[Range[81],ToExpression/@Characters[str]]
Out[8]=
020900000009820000000005000030000000000040710000000000090701300000000001072050000
Out[9]=
10,22,30,49,50,60,70,80,90,100,110,129,138,142,150,160,170,180,190,200,210,220,230,245,250,260,270,280,293,300,310,320,330,340,350,360,370,380,390,400,414,420,437,441,450,460,470,480,490,500,510,520,530,540,550,569,570,587,590,601,613,620,630,640,650,660,670,680,690,700,710,721,730,747,752,760,775,780,790,800,810
Actually, instead of Range[81], we have to use the list of cells found above.
Now that we know where the clues are placed, we also know in which cells we have candidates. We only have to store the list of candidates lists:
In[10]:=
Values@Select[numbers,#〚1〛0&]
Out[10]=
{{0,1,5,6,7,8},{0,1,3,4,5,6,7,8},{0,1,3,6,7},{0,3,4,6,7},{0,1,4,5,6,8},{0,3,4,5,6,7,8},{0,3,5,6,7,8},{0,1,3,4,5,6,7},{0,1,5,6},{0,3,4,6,7},{0,1,4,5,6},{0,3,5,6,7},{0,3,4,5,6,7},{0,1,3,4,6,7,8},{0,1,4,6,8},{0,1,6,7,8},{0,1,3,4,6},{0,1,3,6,7},{0,1,2,6,8,9},{0,2,3,4,6,7,8,9},{0,2,3,4,6,7,8,9},{0,1,2,4,5,6,7,8,9},{0,1,4,5,6,7,8},{0,1,2,5,6},{0,1,6,7,8,9},{0,2,6,7,8,9},{0,2,4,5,6,8,9},{0,2,4,5,6,8,9},{0,2,4,5,6,8,9},{0,2,5,6,8,9},{0,5,6,8},{0,5,6,8},{0,2,3,5,6},{0,2,3,6,8,9},{0,2,3,5,6,8,9},{0,1,2,4,5,6,7,8,9},{0,1,4,5,6,8},{0,1,4,5,6,7,8},{0,1,2,3,5,6},{0,1,3,6,7,8,9},{0,2,6,7,8,9},{0,2,4,5,6,8,9},{0,2,3,4,5,6,8,9},{0,2,3,4,5,6,8,9},{0,4,5,6,8},{0,5,6,8},{0,6,8},{0,2,4,5,6,8},{0,2,4,5,6,8},{0,3,4,5,6,8},{0,5,6,8},{0,3,4,5,6,8},{0,2,3,4,6},{0,3,6,8,9},{0,2,3,4,6,8,9},{0,2,4,5,6,8,9},{0,2,5,6,7,8,9},{0,1,3,6,8},{0,3,4,6},{0,3,4,6,8,9},{0,4,6,8,9},{0,4,6,8,9},{0,6,8,9}}
Each element in this list can be seen as a list of digits of an integer, and we can transform the list into a list of integers:
In[11]:=
clist=FromDigits/@%
Out[11]=
{15678,1345678,1367,3467,14568,345678,35678,134567,156,3467,1456,3567,34567,134678,1468,1678,1346,1367,12689,2346789,2346789,12456789,145678,1256,16789,26789,245689,245689,245689,25689,568,568,2356,23689,235689,12456789,14568,145678,12356,136789,26789,245689,2345689,2345689,4568,568,68,24568,24568,34568,568,34568,2346,3689,234689,245689,256789,1368,346,34689,4689,4689,689}
Finding back the candidates lists from this list is straightforward.
The second step in making a string representation of a sudoku, is that we need short strings both for integers and for list of integers.
Integers become considerably shorter when we use a digit system with base much larger than 10. We are going to use base 68, with the following digits:
In[12]:=
chars
Out[12]=
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!@#$%&
This is how we convert an integer to a short string and conversely, thereby showing the implementation of the functions integerto68 and integerfrom68:
In[13]:=
IntegerDigits[cluesinteger,68]to68/@%cluesstring=StringJoin[%]
Out[13]=
{3,22,23,33,54,45,65,19,67,28,29,38,10,32,29,42,49,61,24,57,2,47,55,12,5,31,46,59,59,23,17,64,41,19,30,21,19,39,46,60,53,60,23,52}
Out[14]=
{3,M,N,X,s,j,$,J,&,S,T,c,A,W,T,g,n,z,O,v,2,l,t,C,5,V,k,x,x,N,H,#,f,J,U,L,J,d,k,y,r,y,N,q}
Out[15]=
3MNXsj$J&STcAWTgnzOv2ltC5VkxxNH#fJULJdkyryNq
In[16]:=
Characters[cluesstring]from68/@%FromDigits[%,68]
Out[16]=
{3,M,N,X,s,j,$,J,&,S,T,c,A,W,T,g,n,z,O,v,2,l,t,C,5,V,k,x,x,N,H,#,f,J,U,L,J,d,k,y,r,y,N,q}
Out[17]=
{3,22,23,33,54,45,65,19,67,28,29,38,10,32,29,42,49,61,24,57,2,47,55,12,5,31,46,59,59,23,17,64,41,19,30,21,19,39,46,60,53,60,23,52}
Out[18]=
20900000009820000000005000030000000000040710000000000090701300000000001072050000
In[19]:=
integerto68[cluesinteger]integerfrom68[%]
Out[19]=
3MNXsj$J&STcAWTgnzOv2ltC5VkxxNH#fJULJdkyryNq
Out[20]=
20900000009820000000005000030000000000040710000000000090701300000000001072050000
Now the conversion of lists of integers. We will shortly discuss the implementation of the functions listto68 and listfrom68.
Let us consider the list for the coloredgroups:
In[21]:=
list=Flatten[sud〚1〛["info"]["coloredgroups"]]
Out[21]=
{9,17,25,33,41,49,57,65,73,1,11,21,31,41,51,61,71,81}
In[22]:=
{9,17,25,33,41,49,57,65,73,1,11,21,31,41,51,61,71,81}
Out[22]=
{9,17,25,33,41,49,57,65,73,1,11,21,31,41,51,61,71,81}
We replace each cell with the list of digits and separate thesedigit lists with the integer 10, and then flatten the result:
In[23]:=
Riffle[IntegerDigits/@list,10]Flatten[%]
Out[23]=
{{9},10,{1,7},10,{2,5},10,{3,3},10,{4,1},10,{4,9},10,{5,7},10,{6,5},10,{7,3},10,{1},10,{1,1},10,{2,1},10,{3,1},10,{4,1},10,{5,1},10,{6,1},10,{7,1},10,{8,1}}
Out[24]=
{9,10,1,7,10,2,5,10,3,3,10,4,1,10,4,9,10,5,7,10,6,5,10,7,3,10,1,10,1,1,10,2,1,10,3,1,10,4,1,10,5,1,10,6,1,10,7,1,10,8,1}
This list can be considered as the base 11 representation of an integer, for which we can construct the string:
In[25]:=
listinteger=FromDigits[%,11]liststring=integerto68[listinteger]
Out[25]=
116490621855670012694849965972419670029337746686608856
Out[26]=
v1X6ibxszaEMven0GdI524QPixLTK
Conversely: the string gives an integer, of which we want to have the base 11 digits:
In[27]:=
integerfrom68[liststring]zzz=IntegerDigits[%,11]
Out[27]=
116490621855670012694849965972419670029337746686608856
Out[28]=
{9,10,1,7,10,2,5,10,3,3,10,4,1,10,4,9,10,5,7,10,6,5,10,7,3,10,1,10,1,1,10,2,1,10,3,1,10,4,1,10,5,1,10,6,1,10,7,1,10,8,1}
We construct the digits of the numbers of the list:
Finally the list itself:
The string is pretty much shorter than the list. Let us have a look at the list for the candidates:
Finally, the string for the sudoku itself. It consists of 5 substrings, separated by the character '|', in this order:
The candidates are only included when the option InCludeCandidates is set to True. Otherwise this substring is empty.
The third string has a default value of "2gF&GRM", which corresponds to the size, rowcolpositions and standardpositions of a single standard sudoku. When such a sudoku has no other blocks, the string representation consists only of the clues.