Constrained Grid Solutions

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

Constrained Grid Solutions

Postby coloin » Sun Feb 03, 2008 7:48 pm

A sudoku solution grid is a 9*9 latin square with an additional box constraint. {3 [row/column/box]equivalent constraints}

The total number of sudoku grids was estimated and calculated a few years ago - ~6.7*10^21

For completeness and clarity, I might add that it has been estimated that there are ~10^15 different minimal puzzles per individual grid solution. [No danger of running out of puzzles]

The total number of 9*9 latin squares has been calculated ~ 5.5*10^27. {2 out of the 3 constraints}
Code: Select all
+---+---+---+
|123|456|789|
|234|567|891|
|345|678|912|
+---+---+---+
|456|789|123|
|567|891|234|
|678|912|345|
+---+---+---+
|789|123|456|
|891|234|567|
|912|345|678|
+---+---+---+ An example of a valid latin square [ignore the boxes]


There are I think many many grids which dont quite satisfy the initial row and/or column constraints.

I suspect the minimum number of cells which dont comply is 2
Code: Select all
+---+---+---+
|175|386|4*2|
|293|417|*58|
|846|295|713|
+---+---+---+
|458|923|176|
|319|674|825|
|627|851|349|
+---+---+---+
|781|532|694|
|534|169|287|
|962|748|531|
+---+---+---+  2 cells non-complient - or 25/27 constraints  complied with.

+---+---+---+
|5**|136|284|
|*18|245|976|
|*24|978|315|
+---+---+---+
|167|382|549|
|293|451|768|
|485|697|132|
+---+---+---+
|841|523|697|
|359|764|821|
|672|819|453|
+---+---+---+  4 cells in one box non-complient

+---+---+---+
|78*|123|456|
|*9*|456|123|
|*41|*87|*9*|
+---+---+---+
|157|238|*69|
|2*8|619|347|
|369|7*4|582|
+---+---+---+
|41*|365|7**|
|52*|94*|61*|
|63*|*71|9*8|
+---+---+---+  19 cells non-complient.


These are some of the constrained grids which made the counting of the grids complicated.

I suppose these are the "grid solutions" when you "guess" a couple of wrong proposition clues - and everybody has made one of these grids when they have made a mistake with their pen and paper puzzle solving !.

In the above grid with 2 non complient cells, it is easily transformed into a valid grid by swapping 2 clues
Code: Select all
+---+---+---+                   +---+---+---+                         
|175|386|4*2|                   |175|386|492|                         
|293|417|*58|                   |293|417|658|                         
|846|295|713|                   |846|295|713|                         
+---+---+---+                   +---+---+---+                         
|458|923|176|                   |458|923|176|                         
|319|674|825|                   |319|674|825|                         
|627|851|349|                   |627|851|349|                         
+---+---+---+                   +---+---+---+                         
|781|532|694|                   |781|532|964|     r7c7 & r7c8 swapped
|534|169|287|                   |534|169|287|                         
|962|748|531|                   |962|748|531|                         
+---+---+---+                   +---+---+---+     valid grid

So there would appear to be a great number of these invalid grids.
C
coloin
 
Posts: 1637
Joined: 05 May 2005

Return to General