Fruitless Sudoku Discoveries

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

Fruitless Sudoku Discoveries

Postby BlueSpark » Wed Oct 05, 2005 1:41 pm

I have only recently learned of sudoku, and it looks like I will soon be addicted if I am not already. Like everyone else I have poked around to see if I could find quicker or novel ways to solve them. Many of the things I have found out are, alas, completely useless in that regard. Here are some of them:

(1) It is obvious that if you were to assign values to the positions of each row and column--1 to 9 from top to bottom and left to right, or whatever--then the sum of the position values of any given number in a completed sudoku adds up to 45, since 1+2+3+4+5+6+7+8+9=45 and each number appears in every row and column only once. This is also true, however, when you assign position values 1 to 9 within the 3x3 boxes of the sudoku--even though a given number might appear at the same position in 2 or 3 different boxes (3 is the limit I think). For instance, number X might appear in the 9th cell of the upper-left hand box and also appear in the 9th cell of the center box, but this high total (18 for only two boxes) will be elsewhere balanced off and 45 will be the total of the position values of X. Cool!

(2) If you assign values to the positions of the entire sudoku (1 to 81), then the total of the position values of any given number is 369, which is a fine, fine number. Cool!

(3) Take a sudoku puzzle. Select any 3x3 box (or column or row) that has some numbers in it. In a blank sudoku write the numbers 1 to 9 in order (they don't have to be in order but it makes it easier as they are meant to be position values) in the 3x3 box that corresponds to the one you have chosen in the puzzle. As you figure out numbers in the puzzle, in the corresponding cells of the blank sudoku write the number of the position that that number you have figured out occupies in the chosen 3x3 box of the puzzle. (For instance, suppose you have chosen the top left box. You then figure out that r7c6 is a 9. In the top left box there is a 9 at position 4. Write 4 at r7c6.) This process creates in the blank sudoku another valid sudoku. Upon reflection it is clear that this must be so--and it is so obvious as not to be helpful. I thought at first that the two "sister sudokus" might help each other to maturity in a sort of logical feedback and transfer snowball maelstrom, but they don't as, of course, each one contains the exact same information. Of course, sometimes you don't see something in one of the sudokus that strikes you immediately in the other, and this can be helpful, but it is too rare an occurrence (for me) to bother with it. It is certainly not any faster than the standard approaches.

(4) I am very unsure about this one, but my probably very unorthodox (and probably very misguided) statistical approach revealed that there are 46,000+ ways of validly placing a given number onto the sudoku grid. Is that right? Seems like a lot.

Anyone else got any of these sort of dead-end ideas?
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby PaulIQ164 » Wed Oct 05, 2005 1:50 pm

That result about the number's positions in each 3x3 box totalling 45 is quite interesting. Like you say, it's an obvious result for the rows and colums, because each row has to have its 2 (say) in a different column that every other row. But this isn't true with the boxes, so it makes it a more remarkable result. How'd you work it out (or is it really obviously true and I'm being thick)?
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby coloin » Wed Oct 05, 2005 2:04 pm

I think the 45 is self determining -

Place the same number/clue validly in 6 of the boxes labled

B1B2B3
B4B5B6
B7B8B9

Pick these 6 - B1B2B4B6B8B9

The other 3 clues in B3B5B7 have one position each - so it always adds up to 45
.
coloin
 
Posts: 1547
Joined: 05 May 2005

Postby frazer » Wed Oct 05, 2005 2:50 pm

(1) is clear if looked at correctly -- the box position is a slight red herring. The point is simply that each number occurs in the leftmost column 3 times, the middle column 3 times and the rightmost column 3 times, and similarly for the rows. This means that if we number the box

1 2 3
4 5 6
7 8 9

we can think about this as

1+0 2+0 3+0
1+3 2+3 3+3
1+6 2+6 3+6

so the 1, 2 and 3 in the first term occur three times each, and the 0, 3 and 6 of the second arise 3 times each. This gives a total of
3*(1+2+3 + 0+3+6) = 45.

(2) is similarly easy; if we write the 81 entries as

1+0 2+0 3+0 4+0 5+0 6+0 7+0 8+0 9+0
1+9 2+9 3+9 4+9 5+9 6+9 7+9 8+9 9+9
... etc

since each number appears in every row and column once, we get a contribution of 1+2+3+4+5+6+7+8+9 = 45 from the row positions, and 0+9+18+27+36+45+54+63+72=324 from the column positions, making 369 in total.

(3) didn't seem to involve a question.

(4) I would guess that the answer here is 9x6x3x6x4x2x3x2x1=46656. The digit 1 can go into any column on the top row. Then there are 6 possibilities on row two, 3 on row three; 6 on row four, 4 on row five, 2 on row six, 3 on row seven, 2 on row eight, and 1 on the bottom row. I feel sure that valid sudoku grids can be fit around all of these, although I didn't think too hard about it.

(It wasn't clear from your message whether or not you already had realised these arguments, so I hope I'm not wasting everyone's time!)
frazer
 
Posts: 46
Joined: 06 June 2005

Postby BlueSpark » Wed Oct 05, 2005 3:19 pm

Hey Frazer,

Yes, your explanations are correct and are basically equivalent to my own thoughts in chancing upon them and figuring them out, but I don't think you are wasting any time with them either! Just a couple quibbles:

Number (3) wasn't meant as a question (none of the points were). I was just describing one of the fruitless meanderings of thought that have passed over my synapses since recently getting interested in sudoku.

Also, you claim that, with respect to (1), "the box position is a slight red herring" and that "(1) is clear if looked at correctly." You then proceed to explain the 45-sum in terms of columns and rows. But "box position" is just another way of talking about row and column--in fact it is a shorthand for the coordinates of row and column. Instead of saying "the third row in the fourth column" I simply say "7". Neither way of thinking about it seems "incorrect." And neither seems less illuminating than the other. It's just 2 ways of saying the same thing. In fact, I arrived at the "box position" idea simply as a way of bringing together the information about rows and columns. After all, I described the "adds to 45" property with respect to the rows and columns using the idea of "position" and so it seems only natural to do the same with respect to the 3x3 boxes--a nice parallelism (which is why I bothered to bring it up in the first place).

Also, remember, I describe these ideas as "fruitless" and "useless" and "dead-end," so I agree there isn't much here to begin with. I think we also can agree that the fact that this "adds to 45" property is much more obvious with regard to the rows and columns than it is with respect to the 3x3 boxes (notice how much longer your explanation of it was than the explanation of why it is true for the rows and columns). I was merely describing my pleasant (if fruitless)discovery.

Oh, and with respect to (4) your reasoning was exactly the same as mine, I believe, since I have a piece of paper here with almost the exact same words and numbers. So maybe my approach wasn't so unorthodox after all. Thanks for taking the time!

Cheers
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby frazer » Wed Oct 05, 2005 4:21 pm

Thanks for the reply -- I didn't quite see from your first post whether you were posting (1) observations that you could explain, or (2) observations that you hadn't explained yet. In case it was (2), I thought I'd give a quick explanation (possibly also for the benefit of anyone else who looked at the thread), but I guessed from your way of writing that you had been able to explain them perfectly well yourself.
frazer
 
Posts: 46
Joined: 06 June 2005

Postby Shazbot » Wed Oct 05, 2005 9:28 pm

PaulIQ164 wrote:That result about the number's positions in each 3x3 box totalling 45 is quite interesting. Like you say, it's an obvious result for the rows and colums, because each row has to have its 2 (say) in a different column that every other row. But this isn't true with the boxes, so it makes it a more remarkable result. How'd you work it out (or is it really obviously true and I'm being thick)?


It's really obviously true. If every row, and every column, and every block, has to have numbers 1 thru 9, then it follows that the sum of the numbers in every row, every column and every block has to equal the sum of the numbers 1 thru 9: 45. Just like a "magic square" with a twist. An interesting fact, but it's not helpful in solving them.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby PaulIQ164 » Wed Oct 05, 2005 9:45 pm

I don't see how the boxes result is as obvious as you say. It's clearly a different situation to the rows/columns.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Shazbot » Thu Oct 06, 2005 5:40 am

I assume by "box" you mean the 3x3 grid - the same as what's referred to as a "block".

Every row MUST contain the numbers 1 thru 9 once and only once - they add up to 45
Every column MUST contain the numbers 1 thru 9 once and only once - they add up to 45
If every "box" (block) also must contain the numbers 1 thru 9 once and only once, then they also must add up to 45. It doesn't matter where they appear in the block, just as it doesn't matter where they appear in the row or column - you know every one is going to be there, somewhere, just once.

Unless you mean something else by "box"?
Shazbot
 
Posts: 220
Joined: 24 September 2005

Re: Fruitless Sudoku Discoveries

Postby Shazbot » Thu Oct 06, 2005 5:48 am

Ah, I think I've mixed myself up.... I was thinking the sum of the numbers (or the sum of the positions) in any ONE 3x3 box would be 45, but I think I've "got the bull by the horns"

BlueSpark wrote:(1) It is obvious that if you were to assign values to the positions of each row and column--1 to 9 from top to bottom and left to right, or whatever--then the sum of the position values of any given number in a completed sudoku adds up to 45, since 1+2+3+4+5+6+7+8+9=45 and each number appears in every row and column only once. This is also true, however, when you assign position values 1 to 9 within the 3x3 boxes of the sudoku--even though a given number might appear at the same position in 2 or 3 different boxes (3 is the limit I think). For instance, number X might appear in the 9th cell of the upper-left hand box and also appear in the 9th cell of the center box, but this high total (18 for only two boxes) will be elsewhere balanced off and 45 will be the total of the position values of X. Cool!


So what's meant here, is that blocks 1, 5 and 9 could contain the same number in cell 9 (bottom right cell in each of those blocks), giving a total of 27. You'd then end up with one of two possibilities I believe - 3 blocks with that number in position 5 (total 15) and 3 with it in position 1 (total 3) - grand total 45; OR 3 blocks with that number in position 4 (total 12) and 3 with it in position 2 (total 6) - grand total again is 45.

NOW that I understand what's REALLY being said, then no, I don't think it's that obvious at all. Sorry for the confusion.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby 9X9 » Thu Oct 06, 2005 10:17 am

shazbot - If you take the bull by the horns, what you get is a toss up !!!
9X9
 
Posts: 100
Joined: 26 September 2005

Postby Shazbot » Thu Oct 06, 2005 12:38 pm

toss up? I'm not sure I know the expression. I sure got this one tossed BACK though!:)
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby Condor » Fri Oct 21, 2005 2:59 am

frazer wrote:(4) I would guess that the answer here is 9x6x3x6x4x2x3x2x1=46656. The digit 1 can go into any column on the top row. Then there are 6 possibilities on row two, 3 on row three; 6 on row four, 4 on row five, 2 on row six, 3 on row seven, 2 on row eight, and 1 on the bottom row. I feel sure that valid sudoku grids can be fit around all of these, although I didn't think too hard about it.


There is indeed 46656 ways of placing a digit on a sudoku grid. (Properly called templates) A sudoku consists of 9 non-overlapping templates. Interestingly 46656 = 6^6.

With a simple computer program it is easy enought to produce a complete list of templates, something I did early on and then was able to solve some problems quite easily.

One thing I have discovered is that if you take any template and permute the columns in the stacks and rows in the bands then all the other templates can be produced. There are 6 ways of permuting the rows/columns in a band/stack and 6 bands and stacks on a sudoku grid.

[Edit] I have just found that the same thing was post by Ocean here on Sep 20 2005, so this would be his discovery (unless found by someone earlier).
Last edited by Condor on Wed May 02, 2007 2:07 am, edited 1 time in total.
Condor
 
Posts: 62
Joined: 19 June 2005

Postby BlueSpark » Thu Nov 03, 2005 10:53 pm

That is very interesting condor. If you have anything else you have discovered along this line, I would be interested in hearing about it.

Thanks!
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby BlueSpark » Fri Nov 04, 2005 4:20 pm

Condor,

I too have found it very helpful to think of the sudoku as 9 interlocking templates (although I used the term "pattern" but will use "template" in the future as it is to my ear much better ).

It seems that the template concept would be one model by which to approach the question of the minimum number of clues required for a valid sudoku puzzle. After all, if you have an empty grid and place a 7 in a cell somewhere, all 6^6 templates remain open for the 7. If you place a 3 in some cell outside the 7's box, then you eliminate a bunch of templates for the 7 (and the 7 eliminates certain templates for the 3). As you go on adding numbers you are basically just eliminating templates. And, of course, you will reach a point at which the set of available templates for each number will equal exactly one. It would be interesting to have a program by which you could actually watch this process take place (with the templates still available shaded or something and becoming unshaded as templates are eliminated).

I am not a math guy, but I assume that the fact that there are 6 ways of permuting the "stacks" and 6 "stacks" is the reason why there are 6^6 templates. Is that right?

Cheers
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Next

Return to General