Weird Question

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

Weird Question

Postby liturgygeek » Wed Jul 26, 2006 10:01 pm

I have a weird question....Like any good nerd, I check my work after finishing a puzzle, just to make sure I did it correctly. I check across, down and in each square.

Within each 3x3 square, it appears to be impossible to reach nine from one in such a way that each number is next (either to the top, bottom, left, right, or diagonal) to the one preceding AND following it. (This is really hard to describe non-visually)

So, an example of what I think should be possible, in at least ONE 3x3 square, would look like this:
123 or 456 or 245
654 137 136
789 289 987

You get the idea?

I know it seems weird, but this really bugs me. Is there any reason why this should NEVER happen?

~liturgygeek
liturgygeek
 
Posts: 2
Joined: 26 July 2006

Postby tso » Wed Jul 26, 2006 11:53 pm

Each and every sudoku can be converted into one in which at least one of the 3x3 boxes has the numbers in any order you like. Just swap all of one digit for all of another, etc. For example:

This randomly selected puzzle ...
Code: Select all
+-------+-------+-------+
| 4 . . | 2 . 9 | 6 . . |
| . . . | . 1 . | . . 8 |
| . . . | . 6 . | 7 2 . |
+-------+-------+-------+
| 7 . 4 | 6 . . | . 1 . |
| . 1 . | . . . | . 5 . |
| . 9 . | . . 1 | 4 . 3 |
+-------+-------+-------+
| . 2 5 | . 9 . | . . . |
| 3 . . | . 8 . | . . . |
| . . 1 | 7 . 3 | . . 5 |
+-------+-------+-------+
... can be changed into this one ...
Code: Select all
+-------+-------+-------+
| 4 . . | 8 . 6 | 1 . . |
| . . . | . 9 . | . . 7 |
| . . . | . 1 . | 5 8 . |
+-------+-------+-------+
| 5 . 4 | 1 . . | . 9 . |
| . 9 . | . . . | . 3 . |
| . 6 . | . . 9 | 4 . 2 |
+-------+-------+-------+
| . 8 3 | . 6 . | . . . |
| 2 . . | . 7 . | . . . |
| . . 9 | 5 . 2 | . . 3 |
+-------+-------+-------+
The center box will meet your criteria.
tso
 
Posts: 798
Joined: 22 June 2005

Postby JPF » Thu Jul 27, 2006 12:09 am

tso wrote:...The center box will meet your criteria.

Of course.
But I think the point is that it’s impossible to have 2 boxes having this property on a same band or a same stack.
So the maximum for a grid would be 3 boxes.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Thu Jul 27, 2006 4:40 am

Here is a band with all 3 boxes satisfying this property:
Code: Select all
123|456|789
894|137|265
765|298|134

I think the challenge is to get all 9 boxes satisfying this... Will have to work on that...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby tso » Thu Jul 27, 2006 6:03 am

JPF wrote:But I think the point is that it’s impossible to have 2 boxes having this property on a same band or a same stack.
So the maximum for a grid would be 3 boxes.

JPF



That's not what was asked -- nor is it true. I've added [ c o d e ] to a portion of the original post:


liturgygeek wrote:So, an example of what I think should be possible, in at least ONE 3x3 square, would look like this:
Code: Select all
123          or          456                    or     245
654                      137                           136
789                      289                           987




udosuk wrote:Here is a band with all 3 boxes satisfying this property:
Code: Select all
123|456|789
894|137|265
765|298|134


The top three boxes of this puzzle match udosuk's band:

Code: Select all
+-------+-------+-------+
| 1 . . | . . 6 | . . . |
| . . 4 | . 3 . | 2 . 5 |
| . 6 . | 2 . 8 | . 3 . |
+-------+-------+-------+
| . . . | . 1 . | . 4 8 |
| . . 6 | 3 . 2 | 9 . . |
| 5 3 . | . 7 . | . . . |
+-------+-------+-------+
| . 4 . | 8 . 1 | . 9 . |
| 2 . 1 | . 6 . | 4 . . |
| . . . | 7 . . | . . 1 |
+-------+-------+-------+



In this one, 5 of the boxes match the criteria:

Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| . 9 . | . 3 7 | . . . |
| . . . | 2 8 9 | 1 3 . |
+-------+-------+-------+
| . 1 8 | . 6 . | . 9 . |
| . 7 . | . . 2 | . 6 . |
| . 5 6 | . 1 . | 8 7 . |
+-------+-------+-------+
| . . 1 | 5 7 8 | . 2 . |
| . . 2 | 6 . 1 | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
Last edited by tso on Thu Jul 27, 2006 2:16 am, edited 1 time in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby JPF » Thu Jul 27, 2006 6:11 am

udosuk wrote:Here is a band with all 3 boxes satisfying this property:

Well done !
I was wrong for a band/stack.
Let's try the challenge for the grid

tso wrote:In this one, 5 of the boxes match the criteria:

Excellent !
I was also wrong for the maximum number of boxes...

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby liturgygeek » Thu Jul 27, 2006 8:08 pm

You all are AWESOME!!!! This was way more than I expected or could have hoped for. Thank you so much!

I will probably never be able to create my own grid where every box fulfills this (I tried it once but gave up; I know, I'm such a slacker), but you've given me hope that one day I'll solve a puzzle and find at least one box that fulfills this. Thank you, too, for inventing and taking on your own challenges based on my question. I am, in a strange and perhaps even inappropriate way, very flattered by that.

Thank you, thank you, thank you!!!!

~liturgygeek
liturgygeek
 
Posts: 2
Joined: 26 July 2006

Postby JPF » Thu Jul 27, 2006 9:32 pm

liturgygeek wrote:You all are AWESOME!!!! This was way more than I expected or could have hoped for. Thank you so much!
~liturgygeek

I’m glad you appreciate the challenge provoked by your “weird” question.

These special boxes which I call t-boxes are interesting to study.
A t-box is a box in which the digits k and k+1 (k=1,2,…, 8) are in adjacent cells.

After tso’ post, I tried to find a grid with more than 5 t-boxes.
No success yet.

Here is an other puzzle with 5 t-boxes in the solution grid:

Code: Select all

 . 2 3 | . 5 . | . . .
 . . 4 | 1 3 7 | . . .
 . . 5 | . 8 . | . . .
-------+-------+-------
 . . 8 | . . . | . . 3
 3 . . | . . . | 5 6 .
 . . 6 | . . . | 7 1 .
-------+-------+-------
 . . . | . . 4 | . 8 .
 . . . | . 7 8 | . . 6
 . . . | 5 . 2 | 1 3 4



with a solution :
Code: Select all

T1 T2  .
T3 T4  .
 .  . T5


where Ti is a t-box.

tso’grid was
Code: Select all
 
T1 T2 T3
T4 T5 .
.  .  .


There are not a lot of t-boxes.
I counted only 784 t-boxes* for a total number of possible boxes equal to 9!=362880.

It should explain why it’s so hard to make a grid with only these special boxes.
I’ll keep trying.

JPF

*138 starting (r1c1) with 1, 48-2, 84–3, 84-4, 76-5, 84-6, 84-7, 48-8, 138-9.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Fri Jul 28, 2006 9:10 am

Let's raise the bar a little bit...

Code: Select all
129|678|345
348|159|267
567|234|198
---+---+---
..2|765|431
..1|843|952
...|921|876
---+---+---
...|...|...
...|...|...
...|...|...

In this grid the 5 "chains" in the t-boxes are linked together... But I can't continue with a 3 in the 6th box... Can you do better?

But perhaps I shouldn't be that ambitious... I couldn't even get a chain of [123456789]*9 to fill the whole 9x9 grid freely (hamiltonian path) yet...

Also, JPF, could you count how many t-boxes are circuits too, i.e. 1 & 9 are also adjacent?

Code: Select all
Examples:
123  187  913
894  926  842
765  345  765
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Smythe Dakota » Fri Jul 28, 2006 9:41 am

How about "wrap-around" t-boxes, i.e. not only are consecutive digits adjacent, but 9 and 1 are adjacent as well?

What is the maximum number of wrap-around t-boxes that can occur in a completed grid?

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Postby JPF » Fri Jul 28, 2006 1:46 pm

Smythe Dakota wrote:How about "wrap-around" t-boxes, i.e. not only are consecutive digits adjacent, but 9 and 1 are adjacent as well?

Udosuk wrote:Also, JPF, could you count how many t-boxes are circuits too, i.e. 1 & 9 are also adjacent?


There are 288 (=9x32) wrap-around t-boxes (wat-boxes).
The list is given below.

Smythe Dakota wrote:What is the maximum number of wrap-around t-boxes that can occur in a completed grid?


I’m (slowly) working on an algorithm for any types of boxes.
Not ready yet.

List of the 32 wat-boxes starting with 1 :
(The others are obtained by applying cyclic permutations (2,3,4,5,6,7,8,9,1), etc... on the digits)
Code: Select all
123794865
123894765
123945876
123946875
123954876
123964785
123964875
123974856
123974865
123984765
124935876
124953876
128397456
134295876
134925876
143925876
178296345
187296345
187926345
193824765
197268345
197286345
198237456
198247356
198247365
198257346
198257436
198267345
198275346
198276345
198327456
198427356

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Smythe Dakota » Sun Jul 30, 2006 3:15 am

How about this one:

Find a completed Sudoku grid such that there exists a path (each cell leads to another cell which is adjacent either horizontally, vertically, or diagonally) which covers all 81 cells, each cell only once, and such that the digit in each cell is consecutive (one more or one less) to the one in the previous cell in the path?

If you like, you can also consider 9 and 1 to be consecutive, but in return the path should be a circular path (first cell is adjacent to the last cell).

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Postby JPF » Sun Jul 30, 2006 8:34 am

No t-sudoku exists

I have completed an exshautive search on the t-boxes :
there is no t-sudoku (a grid with 9 t-boxes).

The maximum of t-boxes in a sudoku grid is 6.
Here is one with 6 wat-boxes (as defined above) :

Code: Select all
 2 3 4 | 5 6 7 | 8 9 1
 9 1 5 | 3 4 8 | 6 7 2
 8 7 6 | 2 1 9 | 5 4 3
-------+-------+-------
 3 2 1 | 6 5 4 | 9 8 7
 4 9 8 | 7 3 2 | 1 6 5
 5 6 7 | 8 9 1 | 2 3 4
-------+-------+-------
 1 8 3 | 9 7 5 | 4 2 6
 6 4 9 | 1 2 3 | 7 5 8
 7 5 2 | 4 8 6 | 3 1 9



There are 8 strange t-boxes which cannot be in the same band or the same stack of an other t-box :
In other words, T is a strange t-box if :
Code: Select all
T T'.
. . .
. . .

is impossible for any t-box T'

and
Code: Select all
T . .
T'. .
. . .

is impossible for any t-box T'

Here is one strange t-box :
Code: Select all
123
654
789

Unfortunately, that's the box I used to test the possibility of having TT' for my first post...

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Sun Jul 30, 2006 9:02 am

Great job!:)

Is it easy to construct a 6-t-box/wat-box grid? Are they built by a very limited set of t-boxes or any non-strange t-box could be used as a building block? Could identical t-boxes be put into the same grid (for a 6-t-boxer)?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Sun Jul 30, 2006 8:04 pm

udosuk wrote:Great job!:)
Is it easy to construct a 6-t-box/wat-box grid? Are they built by a very limited set of t-boxes or any non-strange t-box could be used as a building block? Could identical t-boxes be put into the same grid (for a 6-t-boxer)?

Thanks,
Let's take the wat-boxes.
There are only 288 (and no strange) wat-boxes ; but each box is band-compatible or stack-compatible with only 20 or 22 boxes.

For example T :
Code: Select all
123
894
765
is band-compatible with 20 boxes and stack-compatible with 22 boxes.
These boxes are different, except two in that case :
Code: Select all
456   689
317   571
289   432
which are compatible with T in both directions.

The limited number of compatible boxes makes the exhaustive search very quick.
It's a matter of 1 or 2 seconds.

For this type of shape :
Code: Select all
T T T
T T T
. . .

there are 270 possible arrangements (9x30).
It means 30 really different arrangements, before cyclic permutations of the digits.

Only 68 (among 288) wat-boxes are used in all these solutions.
Don't ask me why 68 is not divisible by 9...

Finally, I picked one of these solutions :
Code: Select all
 2 3 4 | 5 6 7 | 8 9 1
 9 1 5 | 3 4 8 | 6 7 2
 8 7 6 | 2 1 9 | 5 4 3
-------+-------+-------
 3 2 1 | 6 5 4 | 9 8 7
 4 9 8 | 7 3 2 | 1 6 5
 5 6 7 | 8 9 1 | 2 3 4
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .


which gives a puzzle with 120 solutions.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Next

Return to General