Checking solved puzzles that have been printed

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

Postby Animator » Fri Jun 10, 2005 11:19 am

Another one: 6² + 7² + 8² = 2² + 3² + 9²
Animator
 
Posts: 469
Joined: 08 April 2005

Postby scrose » Fri Jun 10, 2005 1:04 pm

Animator wrote:But what's the bottom line of the question? How to verify a grid easily, as a human...

Seconding that sentiment, I still feel the need to wade into the discussion.

If you're going to use exponentiation to verify a row/column/block, take a common base and use the cell values as the exponents.

Examples:

2^1 + 2^2 + 2^3 + ... + 2^9 = 1022. Using 2 as a base, the sum of every row/column/block should be 1022.
ALL YOUR BASE ARE BELONG TO US!
7^1 + 7^2 + 7^3 + ... + 7^9 = 47079207. Using 7 as a base, the sum of every row/column/block should be 47079207.

Going to back to what Animator said, this method is clearly not for the average human brain.

Application of this method, using 2 as a base, to Animator's example of an invalid grid follows.

Code: Select all
 1 2 3 | 3 8 4 | 7 8 9   1190
 4 5 6 | 8 6 9 | 1 3 3    962   1022   1148   1010
 7 8 9 | 1 1 5 | 4 4 6   1028
-------+-------+-------
 2 3 1 | 5 6 4 | 8 9 7   1022
 5 6 4 | 8 9 7 | 2 3 1   1022   1022   1022   1022
 8 9 7 | 2 3 1 | 5 6 4   1022
-------+-------+-------
 3 1 2 | 6 4 5 | 9 7 8   1022
 6 4 5 | 9 7 8 | 3 1 2   1022   1022   1022   1022
 9 7 8 | 3 1 2 | 6 4 5   1022

 1 1 1   1 1     1 1 1
 0 0 0   1 0 9   0 0 0
 2 2 2   4 5 9   2 1 2
 2 2 2   2 2 8   2 0 2

Update: Upon further reflection, you must choose a base larger than one. In fact, I suspect you may need to choose a prime as a base.
Last edited by scrose on Tue Jun 14, 2005 2:32 pm, edited 1 time in total.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Francisco » Tue Jun 14, 2005 5:06 pm

Animator wrote:Both of you are incorrect...

Calculate 4² + 5² + 6², then calculate 2² + 3² + 8². The result is the same, meaning that the sequence 4 5 6 can be replaced with 2 3 8. (I'm pretty sure there are other combinations aswell, but I only care about one, since that prooves my point)

An example (incorrect) grid:

1 2 3 | 2 3 8 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
-----------------------
5 6 4 | 8 9 7 | 2 3 1
2 3 1 | 3 8 2 | 8 9 7
8 9 7 | 2 3 1 | 5 6 4
-----------------------
6 4 5 | 9 7 8 | 3 1 2
3 1 2 | 8 2 3 | 9 7 8
9 7 8 | 3 1 2 | 6 4 5


WRONG!!

Because in this case the sum of the 1st row doesn't add up to 45 (it gives 43)

Just to clarify something. When I said the square thing worked up, I was using it ALONG with the sum part (It's both rules at the same time, not on their own)

I hope this clears things up.
Francisco
 
Posts: 14
Joined: 09 June 2005

Postby Animator » Tue Jun 14, 2005 10:04 pm

That wasn't very clear...

Perhaps I will look for another grid tommorow...

But, do you really believe a human will go to the process of calculating all those things just to verify if the grid is correct?

Then it would be easier just to look at each individual number and see if it occures on/in every row, column and box
Animator
 
Posts: 469
Joined: 08 April 2005

Postby lobby__boy » Wed Jun 15, 2005 1:32 pm

as regards the squares, nice work on that one Animator. as regards the picking of each number, unless you do sudokus on a spreadsheet, it's almost just a better idea to count 1-9 in every row, column and square for time's sake.
lobby__boy
 
Posts: 29
Joined: 08 June 2005

Postby Francisco » Wed Jun 15, 2005 2:16 pm

Animator wrote:That wasn't very clear...

But, do you really believe a human will go to the process of calculating all those things just to verify if the grid is correct?

Then it would be easier just to look at each individual number and see if it occures on/in every row, column and box


I don't believe that anyone will calculate that if their doing the puzzles in paper... but since I'm doing them in Excel the result is "automatic" I don't have any additional work to do. In excel you can besides checking the result, put a conditional format that will be active as soon as you reach the right results (in row, column or box).

But just to clarify something else, I usually don't need the excel to see if I got the numbers right.. it's way too easy just to look at a row, column or box and check the numbers. The excel stuff is just a reinsurance, nothing more (and since it works for me, I'm fine with it).
Francisco
 
Posts: 14
Joined: 09 June 2005

Postby Animator » Wed Jun 15, 2005 8:21 pm

I was too lazy to do the calculations myself so I wrote a program, which proofes that the sum, and the sum of the square are not sufficient.

The following numbers are minimums. The program I wrote did only used each number once in it's result. (As in, the numbers after the equation symbol always have X different numbers.) Which might not be 100% correct.

Change two digits:

Square is the same on 2 occasions (or 4 depending on how you count). Example: 1 8 = 4 7 ; 2 9 = 6 7
Square and sum are the same: never

Change three digits:

Square is the same on 16 occasions. One such example: 2 4 9 = 4 6 7
Square and sum are the same on 4 occasions. Example: 1 5 6 = 2 3 7

Change four digits:
Square: 41 times. Example: 2 4 5 7 = 1 2 5 8
Square and sum: 15 times. Example: 3 4 5 8 = 2 5 6 7

Change five digits:

Square: 41 times. Example: 1 2 4 6 9 = 2 3 5 6 8
Square and sum: 15 times. Example: 1 4 6 7 9 = 2 3 5 8 9

Change six digits:

Square: 16 times. Example: 3 4 5 6 7 9 = 1 3 5 6 8 9
Square and sum: 8 times. Example: 2 3 4 7 8 9 = 1 4 5 6 8 9

Change seven digits:

Square: 2 times. Example: 1 2 3 4 5 8 9 = 1 3 4 5 6 7 8
Square and sum: never


And here is a grid to prove it (1 5 6 = 2 3 7):
2 3 7 | 2 3 4 | 7 8 9
2 3 4 | 7 8 9 | 1 5 6
7 8 9 | 1 5 6 | 2 3 4
-----------------------
3 7 2 | 3 4 2 | 8 9 7
3 4 2 | 8 9 7 | 5 6 1
8 9 7 | 5 6 1 | 3 4 2
-----------------------
7 2 3 | 4 2 3 | 9 7 8
4 2 3 | 9 7 8 | 6 1 5
9 7 8 | 6 1 5 | 4 2 3


If you really want to do it in Excel, then there is an easier way to flag the incorrect ones.

Use conditional formatting, in each cell you add the condition, and as condition, you count the number of times (there is a function like that) the cell's value occures in the row, column and box. If it is more then one you add the formatting, else you don't.
Animator
 
Posts: 469
Joined: 08 April 2005

Postby scrose » Wed Jun 15, 2005 9:13 pm

Well done! I had worked out the equivalencies (1 8 = 4 7, and so on), but I gave up trying to construct a grid that would foil Francisco's methods.

On the other hand, I am relieved to see that my method catches your grid as being invalid. Here are the results using 2 as a base.

Code: Select all
 2 3 7 | 2 3 4 | 7 8 9   1064
 2 3 4 | 7 8 9 | 1 5 6   1022   1064   1022   1022
 7 8 9 | 1 5 6 | 2 3 4   1022
-------+-------+-------
 3 7 2 | 3 4 2 | 8 9 7   1064
 3 4 2 | 8 9 7 | 5 6 1   1022   1064   1022   1022
 8 9 7 | 5 6 1 | 3 4 2   1022
-------+-------+-------
 7 2 3 | 4 2 3 | 9 7 8   1064
 4 2 3 | 9 7 8 | 6 1 5   1022   1064   1022   1022
 9 7 8 | 6 1 5 | 4 2 3   1022
 
 1 1 1   1 1 1   1 1 1
 0 0 0   0 0 0   0 0 0
 6 6 6   2 2 2   2 2 2
 4 4 4   2 2 2   2 2 2
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Animator » Thu Jun 16, 2005 11:06 am

I'm pretty sure your method will always works (or atleast when the input is limited to 1-9)...

What I'm wondering about at the moment is if it is possible to fool 1³ + 2³ + 3³ ...

My guess is yes but finding such a combination will be trickier... as in, it would require the number in the replacement to be used twice... (Little (incorrect) example to explain what I mean: if the sum would be 43 (which is impssoible), then the replacement has to be 2, 2, 3.)

The program I wroteyesterday does not generate the duplicates, but I'll probably update it when I have enough time...
Animator
 
Posts: 469
Joined: 08 April 2005

Postby Francisco » Thu Jun 16, 2005 2:21 pm

Animator wrote:I was too lazy to do the calculations myself so I wrote a program, which proofes that the sum, and the sum of the square are not sufficient.

And here is a grid to prove it (1 5 6 = 2 3 7):
2 3 7 | 2 3 4 | 7 8 9
2 3 4 | 7 8 9 | 1 5 6
7 8 9 | 1 5 6 | 2 3 4
-----------------------
3 7 2 | 3 4 2 | 8 9 7
3 4 2 | 8 9 7 | 5 6 1
8 9 7 | 5 6 1 | 3 4 2
-----------------------
7 2 3 | 4 2 3 | 9 7 8
4 2 3 | 9 7 8 | 6 1 5
9 7 8 | 6 1 5 | 4 2 3


If you really want to do it in Excel, then there is an easier way to flag the incorrect ones.

Use conditional formatting, in each cell you add the condition, and as condition, you count the number of times (there is a function like that) the cell's value occures in the row, column and box. If it is more then one you add the formatting, else you don't.


Well that grid you posted proves 2 things:

1st - my method is apparently weak to uniqueness;
2nd - I would have to be BLIND no to see so many 2s or 3s in the same boxes side-by-side:D

So, for me I won't change my method of checking grids up, Because the 1st rule I use is not the Excel it's my mind... and it usually works well enough for me in terms of noting that I wouldn't put up 2 2s or 3s side-by-side in the same box... Like I said the Excel may not be foolproof... but my personal attention is...
Francisco
 
Posts: 14
Joined: 09 June 2005

Postby Francisco » Thu Jun 16, 2005 2:24 pm

If you want a better method... use the one I suggested in the first page (I think)

1*100000000
2*10000000
3*1000000
4*100000
5*10000
6*1000
7*100
8*10
9*1

Sum them and we have 123456789.

I was then pretty sure this is infallible... but I will let Animator prove me wrong:D
Francisco
 
Posts: 14
Joined: 09 June 2005

Postby scrose » Thu Jun 16, 2005 2:44 pm

Animator wrote:I'm pretty sure your method will always works (or atleast when the input is limited to 1-9)


I think my method will also work when the input is something other than 1 through 9. For example, in a 2x5 grid each row/column/block should total 2046 when using 2 as a base, and in a 4x4 grid each row/column/block should total 131070 when using 2 as a base, and in a 2x2 grid each row/column/block should total 30 when using 2 as a base.

The gist of my method is by identifying which numbers have been used. This is easiest to explain when using 2 as a base. For a 3x3 grid using the numbers 1 through 9, we have 2^1 + 2^2 + 2^2 + ... + 2^9 = 1022. Convert 1022 to binary and we get 1111111110. From left to right, each digit indicates the numbers 9 through 0. Each 1 indicates that a number is present in the row/column/block.

Suppose we have an invalid row/column/block that contains two 4's and is missing one 7. We have 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^4 + 2^8 + 2^9 = 910. Convert 910 to binary and we get 1110001110. Because not all of the nine leftmost digits are 1's, we can say that not all of the numbers are present in the row/column/block and thus the grid is invalid. Unfortunately, my method does not identify which numbers are duplicated and which are missing.

This is a similar to the approach of one of Francisco's methods.

Animator wrote:What I'm wondering about at the moment is if it is possible to fool 1³ + 2³ + 3³ ...


My guess is no.

So, to start with, we are looking for a³ + b³ = e³ + f³ where 1 <= a < b <= 9 and 1 <= e < f <= 9 and a <> e, a <> f, b <> e, b <> f. I couldn't find any {a,b,e,f} to satisfy these constraints.

With similar constraints, I couldn't find any {a,b,c,e,f,g} to satisfy a³ + b³ + c³ = e³ + f³ + g³ and I couldn't find any {a,b,c,d,e,f,g,h} to satisfy a³ + b³ + c³ + d³ = e³ + f³ + g³ + h³.

It is because I couldn't find any equivalencies that I believe it is not possible to fool 1³ + 2³ + 3³ + ... + 9³.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby scrose » Thu Jun 16, 2005 2:47 pm

Francisco wrote:So, for me I won't change my method of checking grids up, Because the 1st rule I use is not the Excel it's my mind...


I'm impressed! For me, in my head, it is easier to scan a row/column/block for duplicates than try to make sure the sum is 45. You must be quite fast at doing sums in your head.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Animator » Thu Jun 16, 2005 2:55 pm

scrose wrote:
Animator wrote:I'm pretty sure your method will always works (or atleast when the input is limited to 1-9)


I think my method will also work when the input is something other than 1 through 9. For example, in a 2x5 grid ...


Ok, I didn't express my self very well... What I wanted to say is something like, if the numbers are limited to the ones that should be used on the grid.

So for example, replacing a number with 0 or 1.2 (one and a half) is impossible. (because it's not part of the range of numbers that should be used on in the grid)


scrose wrote:The gist of my method is by identifying which numbers have been used. This is easiest to explain when using 2 as a base. ...


I know plenty of binary numbers and I immediatly reliased this when reading the original post, but I'm sure not everyone knows the base 2 system, so it might be better to explain it using base 10. Then you also get the output 1111111110.


scrose wrote:
Animator wrote:What I'm wondering about at the moment is if it is possible to fool 1³ + 2³ + 3³ ...


My guess is no.

So, to start with, we are looking for a³ + b³ = e³ + f³ where 1 <= a < b <= 9 and 1 <= e < f <= 9 and a <> e, a <> f, b <> e, b <> f. I couldn't find any {a,b,e,f} to satisfy these constraints.


Actually no, it should be a <= b and e <= f. (And I guess it would take more then two numbers)

Ofcourse that's irrelevant when you look for only two numbers but it might be relevant when there are three... This would mean that you end up having three times (or more) the same number on a row.
Animator
 
Posts: 469
Joined: 08 April 2005

Postby Francisco » Thu Jun 16, 2005 3:12 pm

scrose wrote:
Francisco wrote:So, for me I won't change my method of checking grids up, Because the 1st rule I use is not the Excel it's my mind...


I'm impressed! For me, in my head, it is easier to scan a row/column/block for duplicates than try to make sure the sum is 45. You must be quite fast at doing sums in your head.


Oh... don't flatter me so much... although I'm quick and I know that 1+...+9=45 can be made using the Gauss rule (It should be my rule since I made it up before learning it in school:D ) =(1+9)*(9/2)=10*4.5=45 , The "my mind" rule is just PURE ATTENTION... I can check a row, column or box pretty fast and check which numbers are missing, especially after playing Sudoku a few times... when I look at a box... it's so easy to notice which numbers are missing... I guess I'm playing to much:)
Francisco
 
Posts: 14
Joined: 09 June 2005

PreviousNext

Return to General

cron