sudoku is a 6-dimensional problem

Everything about Sudoku that doesn't fit in one of the other sections

sudoku is a 6-dimensional problem

Postby dukuso » Mon Nov 07, 2005 8:28 am

am I the only one who views sudoku as a 6-dimensional problem
or has this been mentioned elsewhere ?


I wonder why I didn't already read about it or found it
earlier by myself.

It's so clear,obvious,beautiful,general,easy to implement,...


e.g. sudoku:
given a {1,2,3}^6 binary hypercube-grid with exactly
c ones (clues).
Place 81-c further ones such that each of the 2-dimensional planes
of varying (x1,x2),(x3,x4),(x5,x6),(x2,x4) contains
exactly 1 one.


this can be illustrated by a constraint-diagram,
the xi are the coordinates, edges are constraints=
planes spanned by two coordinates :



Code: Select all
   x1---x2
        |
        |
x5      |   x3
 \      |  /
  \     | /
   x6   x4

sudoku,{1,2,3}^6={1,2,3,4,5,6,7,8,9}^3


(x1,x2):rows
(x3,x4):columns
(x5,x6):symbols
(x2,x4):blocks
each in base 3, with x2,x4,x6 being the less significant digits
in their two-digit base3-numbers


Now see the diagrams of these variants:
(of course, when the graphs are isomorphic then the
problems are equivalent and vice versa)


Code: Select all
   x2---x1
    \     \
     \     \
x5    \     x3
 \     \   /
  \     \ /
   x6   x4

4sudoku,{1,2,3}^6


http://www.setbb.com/phpbb/viewtopic.php?t=57&mforum=sudoku



Code: Select all
   x1---x2
         
         
x3          x6
 \         /
  \       /
   x4   x5

latin squares,QCP,QWH {1,2,3}^6




Code: Select all
   x1---x2
       /|
      / |
x3---/  |   x6
|\      |  /
| \     | /
x4 \----x5

3doku,{1,2,3}^6


http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&highlight=3doku+coloin&start=393&sid=e1a32d25184f22650f08704f608b2889


Code: Select all

          x5---x6
          | \ / |
          | / \ |
     x1---x2---x4---x3

magic sudoku,{1,2,3}^6

http://forum.enjoysudoku.com/viewtopic.php?t=2082&sid=e2f5ec28e9ee56b4b9dbded15f47db87



Code: Select all

          x1---x2      x5
          | \ / |       |
          | / \ |       |
          x3---x4      x6



4-dim sudoku,sudoku6{1,2,3}^6

http://magictour.free.fr/sudoku6





Code: Select all
   x4   x1
  /     | \
 /      |  \
x5      |   x2
        |  /
        | /
        x3

minicube,{1,2,3}^5








Code: Select all
   x1   x2
  /     | 
 /      |   
x3      |   x6
        |  /
        | /
        x5

3*9 sudoku-band,{1,2,3}^5







Code: Select all
   x1---x2
        | \
        |  \
x3      |   x6
 \      |  /
  \     | /
   x4   x5

3*3*9-tower,{1,2,3}^6





Code: Select all


   x1---x2       x7
       /|        |
      / |        |
x3---/  |   x6   x8
|\      |  /
| \     | /
x4 \----x5


9*9*9 - Dion-cube, {1,2,3}^8


http://forum.enjoysudoku.com/viewtopic.php?t=532&sid=8c16e3605e25c8a8629020087e87f683


this shows also that the 3*3 blocks are not just a puzzle-specific
creation but can be naturally interpreted as an additional dimension
which makes it more mathematical and maybe even applicable
to molecules or such.




-Guenter


----------edit 2010/06/05-------------

Code: Select all
   x1---x2
       /|
       /|
x5    / |    x3
 \   /  |  /
  \ /   | /
   x6---x4

3er-sudoku


(x1,x2):rows
(x3,x4):columns
(x5,x6):symbols
(x2,x4):blocks
write symbols in base 3, or 3 symbols only but in 3 colors,
different symbols and colors in minirows and minicolumns

81 nonattacking sudokurunners (moves inside 9*1*1 or 3*3*1 boxes) on a 9*9*9 board
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: sudoku is a 6-dimensional problem

Postby dukuso » Sun Jul 04, 2010 2:24 pm

a sudoku is a map s:{1,2,3}^4 --> I9={1,2,3,4,5,6,7,8,9} such that

s(a,-,c,-)=I9 , blocks
s(a,b,-,-)=I9 , rows
s(-,-,c,d)=I9 , columns

this is somehow asymmetric. Add at least:
s(-,b,-,d)=I9 , distance=3-squares

4-sudoku http://www.setbb.com/phpbb/viewtopic.ph ... rum=sudoku
http://www.setbb.com/phpbb/viewtopic.ph ... rum=sudoku
4sudoku



and better also:
s(i,-,-,l)=I9 , minicolumns in a band
s(-,j,k,-)=I9 , minirows in a tower

su-doku-s-maths-t44-390.html
math-27

104 solutiongrids
how many for 16*16 ? it can be done ...

1-rookeries for n=3,4,5,...: 1,6,216, ... *n!*n!*2
-------------------------------------------------

s:I3^3-->I9
s(i,-,-)=I9
s(-,j,-)=I9
s(-,-,k)=I9

3*3*3 cube with all 3*3*1 subcubes containing 1,2,3,4,5,6,7,8,9
does it exist ?

--------------------------------------------

s:I3^5-->I9
s(a,b,c,-,-)=I9=s(a,-,-,d,-)=s(...
10=C(5,2) conditions

-------------------------

s:I3^6-->I9

...

there should be a math-name for these
combinatorial design ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: sudoku is a 6-dimensional problem

Postby dobrichev » Tue Jul 06, 2010 10:36 pm

dukuso wrote:am I the only one who views sudoku as a 6-dimensional problem
or has this been mentioned elsewhere ?


I wonder why I didn't already read about it or found it
earlier by myself.

It's so clear,obvious,beautiful,general,easy to implement,...


e.g. sudoku:
given a {1,2,3}^6 binary hypercube-grid with exactly
c ones (clues).
Place 81-c further ones such that each of the 2-dimensional planes
of varying (x1,x2),(x3,x4),(x5,x6),(x2,x4) contains
exactly 1 one.


this can be illustrated by a constraint-diagram,
the xi are the coordinates, edges are constraints=
planes spanned by two coordinates :



Code: Select all
   x1---x2
        |
        |
x5      |   x3
 \      |  /
  \     | /
   x6   x4

sudoku,{1,2,3}^6={1,2,3,4,5,6,7,8,9}^3


(x1,x2):rows
(x3,x4):columns
(x5,x6):symbols
(x2,x4):blocks
each in base 3, with x2,x4,x6 being the less significant digits
in their two-digit base3-numbers


... (of course, when the graphs are isomorphic then the problems are equivalent and vice versa) ...

Here is a projection of hypercube. It is slightly modified (to isomorph) so that x1=R=B (row MS and box MS), x2=r (row LS), x3=C=b (column MS and box LS), x4=c (column LS), x5=S (symbol MS), and x6=s (symbol LS).
Image
Example values representing MinLex form of the Most Canonical grid are placed.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: sudoku is a 6-dimensional problem

Postby dukuso » Wed Jul 07, 2010 5:19 am

nice presentation in 2d . Some solvers use thi matrix to display the options for a cell
during the solving process.

better in 3d (IMO)
make frames s and S as the 3rd dimension, use a tool to grasp it and rotate it with the mouse
when you rotate it, exchange the roles of Ss and Rr is it still a sudoku ?


> a sudokugrid is a map s:{1,2,3}^4 --> I9={1,2,3,4,5,6,7,8,9} such that
> s(a,-,c,-)=I9 , blocks
> s(a,b,-,-)=I9 , rows
> s(-,-,c,d)=I9 , columns

alternatively:

a sudokugrid is a map s:{1,2,3}^6-->{0,1} such that
sum s(-,-,C,c,S,s) = sum s(R,r,-,-,S,s) = sum s(R,r,C,c,-,-) = sum s(R,-,C,-,S,s) = 1

(the 4*81 columns (=constraints) in the exact-cover-matrix)

represent a sudoku as a (virtual) 9*9*9 box with some marbles (clues) in it.
Then solve it by adding the other marbles, 81 in total , such that
each row,column,pile, 3*3*1-box have exactly one marble

for full cubic symmetry we would also require
sum s(R,r,C,-,S,-) = s(R,-,C,c,S,-) = 1
(each 3*1*3-box and each 1*3*3-box has exactly one marble)

how to call these, how many are there, do they make good puzzles ?
you can always "rotate" it to get another view - when solving in the
computer that would be easy to perform


in reality, for the sudoku museum , maybe use a cubic grid from wire
and inflatable small balloons as marbles to be placed and inflated with a stick
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: sudoku is a 6-dimensional problem

Postby AR4793 » Sun Oct 10, 2010 10:01 pm

Been thinking about this and I don't believe that Sudoku is a 6-dimensional problem. In fact I think that the problem has 9^3 or 729 dimensions. Thus the possible Sudoku puzzles and solutions would be on the surface of a 729 dimension polytope.

:D I do think that you raise an interesting point however. Thinking from an object-oriented programing point of view there is a primitive cell object which is holding a value. Let's let the cell know its position in the line, column and box per the normal format. Now I can easily flatten the 81 cells to 2-D and produce 6 different boards. (The cell object is just a quick cut at this. Not sure if I'd really do it that way...)

(1) row column - cells contain digit per "normal board"
(2) row number = columns contain position of that digit in that row of (1) eg r1c1 is position of the "1" in row 1 of (1)
(3) row box
(4) column number
(5) column box
(6) box number

:? Now the part that I am confused about is how do all these different boards impact the rules? I haven't waded all the way through Berthier's book, but it seems clear that looking at a problem on a different board can have quite an impact. Berthier points out, that these are really equivalent views of the network. Hidden singles in (1) become naked singles in (2).

From a truly object oriented point of view, I think that you could define let all six of the views be children of some abstract_board. You could then define methods on the abstract class across all of the six flat views .

Now if this were a good object oriented program you'd spend two days trying to figure out where any work is getting done. All the objects just seem to be swimming in a sea of messages. :roll:

Regards,
Herb
AR4793
 
Posts: 13
Joined: 26 September 2010

Re: sudoku is a 6-dimensional problem

Postby dobrichev » Mon May 22, 2017 9:31 pm

A paper from 2010 Markov bases for sudoku grids explains sudoku as a 6-dimensional problem in the same manner.
4x4 sudoku is analysed (p=2).
Constrains for valid solution grids consist of 4p^4 linear conditions.
Starting form one valid solution grid, any other can be reached after finite "moves" trough either universal for all grids unavoidable sets (the Validity Preserving Transformations), or trough a specific to the particular grid pattern (unavoidable set).
The concept of the unavoidable sets is possibly immature. There are "feasible" moves but it is unclear whether they are equivalent of the minimal UA sets - probably not, because they are reversible, or the authors don't realize that for p=3 (9x9 sudoku) not all minimal UA are reversible.
Classification of all UA for 4x4 sudoku is done.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: sudoku is a 6-dimensional problem

Postby StrmCkr » Mon May 29, 2017 4:27 am

It's more then 6

Rbc naked hidden
Mini row, col hidden naked

Empty rectangle intersection (hidden, naked)

Each of these breaks down into every solving technique known to date.. It's also how I run my solvwr

12 dimensions which define the 729 constraints of fitting 9 digits into Rbc.

The difference between naked and hidden is all in storage data

One stores pencmarks the other stores applicable position by sector.

Translating and using both diffrent set types is a pain in the butt
I have yet to see any solver use both set types logic at the same time.
Every solving technique used todate uses data from one type of dimension.

A point of intrest
fact a "set" in one has an inverse purpotioal ( 9-"set " size) in the opposite.

Given that relationship it can be argued not to use both types however when computing combtraonics a set size of 4 is searched in full faster then 5.
A folding time increase per set size increase,
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Re: sudoku is a 6-dimensional problem

Postby Maq777 » Tue Mar 23, 2021 3:25 pm

Just as 4x4 sudoku can be perfectly represented in a hypercube with 16 vertices for its templates, 9x9 sudoku can be represented in its hypercube equivalent of 46656 vertices for its templates, on wikipedia you have it as Y6 / 6.

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/Hipercuboy66.png

http://forum.enjoysudoku.com/shidoku-study-with-graphs-t38842.html
Last edited by Maq777 on Sun Apr 04, 2021 12:08 am, edited 1 time in total.
Maq777
 
Posts: 56
Joined: 30 April 2016

Re: sudoku is a 6-dimensional problem

Postby Maq777 » Sat Apr 03, 2021 11:48 pm

I think the dimensionality of the sudokus would be like this

Code: Select all
Sudoku   Templates       n       P       R(dimension)    Vertices
-------------------------------------------------------------------------
1x1      1               1       1       1               1
4x4      16              2       2       4               16
9x9      46656           3       6       6               46656
16x16    110075314176    4       24      8               110075314176
25x25    6,19174E+20     5       120     10              6,19174E+20
36x36    1,94084E+34     6       720     12              1,94084E+34
-------------------------------------------------------------------------


Maq777 wrote:.- For n = 2 we are in the case of sudoku 4x4, 16 vertices are needed for its 16 Templates, the way to build it is:
2 * 2 * 2 * 2 = 2 ^ 4 = 16 that is why the 4x4 sudoku puzzle is located at R4 and at P = 2
With this we can embed the 4x4 sudoku in the first tesseract (the usual Y (2-4)), for that we already know that it has 24 faces of which are used
only 12 to place the possible models or invariant grids of that sudoku puzzle

.- For n = 3 we are in the case of sudoku 9x9 (the typical one of the newspapers) 46656 vertices are needed for its 46656 Templates, the way to build it is:
6 * 6 * 6 * 6 * 6 * 6 = 6 ^ 6 = 46656 that is why the 9x9 sudoku puzzle is located at R6 and at P = 6
With this we can embed the sudoku 9x9 in the generalized hypercube Y (6-6), for that we do not know how many 9-faces it has,
but we know that there must be at least 18,383,222,420,692,992 which are used to place the possible models or invariant grids of the 9x9 sudoku

.- For n = 4 we are in the case of sudoku 16x16, 110075314176 vertices are needed for its 110075314176 Templates, the way to build it is:
24 * 24 * 24 * 24 * 24 * 24 * 24 * 24 = 24 ^ 8 = 110075314176 that is why the 16x16 sudoku is located at R8 and at P = 24
With this we can embed the 16x16 sudoku in the generalized hypercube Y (24-8), for that we do not know how many 16-faces it has,
nor do we know the order of magnitude of the possible 16x16 sudoku models

We can continue like this successively Embedding the larger and larger sudokus into bigger and bigger Politopes .
Maq777
 
Posts: 56
Joined: 30 April 2016


Return to General