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: 1302
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: 1302
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.
User avatar
StrmCkr
 
Posts: 604
Joined: 05 September 2006


Return to General