Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Solving Sudoku's mathematically (?)

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
Kamphuys

Joined: 13 Mar 2006
Posts: 2
:

Items
PostPosted: Mon Mar 13, 2006 6:52 pm    Post subject: Solving Sudoku's mathematically (?) Reply with quote

I was wondering if one could solve sudoku's mathematically. I was looking for a mathematical 'law' which is the same as that every number can only be used once in a row, colomn and squares. I was thinking about this for a while and came up with the following equations:

1) The sum of all rows, colomns and squares has to be : 45
2) The product of all rows,colums and squares has to be : 9!

If the sum of a row equals 45 and the product equals 9!, then every number 1..9 is used only once. I have no real proof for this, so please convince yourself. My temporary 'proof' is:

Sum of two numbers is 10, product is 24, then we know the numbers are 6 and 4.
a+b = 10, a x b = 24 -> a + 24/a = 10 -> a^2 + 24 = 10a -> a=4 and b=6

There are 27 equations of type 1 and 27 equations of type 2. A sudoku consists of 81 numbers, so we need 27 givens and we should be able to solve the sudoku puzzle mathematically.

1. Is this correct?
2. Can we actually solve these equations?
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Mar 13, 2006 8:51 pm    Post subject: Reply with quote

The equations are not linear.

a can be 4 or 6 in your example. With more variables, the number of permutations will also increase.

I cannot prove it, but I think Sudokus cannot be solved this way. The only thing the equations will reveal is which digits can be placed in each unit. But we already know that.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
treffer

Joined: 14 Feb 2006
Posts: 7
:

Items
PostPosted: Tue Mar 14, 2006 9:08 am    Post subject: Reply with quote

regard every row, col and box as a bitset. This results in the following equation:

Code:

2^a + 2^b + 2^c + 2^d + 2^e + 2^f + 2^g + 2^h + 2^i = 1023


where a..i \in {0,...,8} are the numbers in a box, col or row minus 1. 27 equations.

Don't know how to solve it, perhaps try Mathematica/Maple?

Your equations are wrong:

1, 2, 4, 4, 4, 5, 7, 9, 9

Product is 9!, sum is 45

Javacode to try it out (runs in less than 1s on nearly all systems):

Code:

int count = 0;
for (int a = 1; a < 10; a++) {
   for (int b = a; b < 10; b++) {
      for (int c = b; c < 10; c++) {
         for (int d = c; d < 10; d++) {
            for (int e = d; e < 10; e++) {
               for (int f = e; f < 10; f++) {
                  for (int g = f; g < 10; g++) {
                     for (int h = g; h < 10; h++) {
                        for (int i = h; i < 10; i++) {
                           if (a+b+c+d+e+f+g+h+i == 45) {
                              if (a*b*c*d*e*f*g*h*i == 9*8*7*6*5*4*3*2) {
                                 count++;
                                 if (
                                       (a != 1)||
                                       (b != 2)||
                                       (c != 3)||
                                       (d != 4)||
                                       (e != 5)||
                                       (f != 6)||
                                       (g != 7)||
                                       (h != 8)||
                                       (i != 9)
                                    ) {
                                    System.out.println("Invalid solution: " + a + ", " + b + ", " + c + ", " + d + ", " + e + ", " + f + ", " + g + ", " + h + ", " + i);
                                 }
                              }
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }
}
System.out.println("Setups found: " + count);
System.out.println("q.e.d.");


Output:

Code:

Invalid solution: 1, 2, 4, 4, 4, 5, 7, 9, 9
Setups found: 2
q.e.d.
Back to top
View user's profile Send private message
treffer

Joined: 14 Feb 2006
Posts: 7
:

Items
PostPosted: Tue Mar 14, 2006 9:14 am    Post subject: Reply with quote

I should have explained the following:
I've ordered the numbers ascending, as the order does not matter. That's why I've initialized the loops with b=a, c=b, d=c.... and the output is 1<=2<=4<=4<=4<=5<=7<=9<=9

The code could even be optimized (if you check for the possibility to reach 45 and 9), this way it could be possible to do the prove by hand in less than 5 A4 pages (just a guess).
Back to top
View user's profile Send private message
Kamphuys

Joined: 13 Mar 2006
Posts: 2
:

Items
PostPosted: Tue Mar 14, 2006 12:24 pm    Post subject: Reply with quote

Hmmmm, I could have done that check myself.....

Too bad my equations didn't work. But as Ruud stated, they are non-linear, so I think it would be difficult (if not imposiible) to solve them anyway.

Maybe I'll think some more about it
Back to top
View user's profile Send private message
evert

Joined: 30 Aug 2005
Posts: 68
:
Location: Amsterdam

Items
PostPosted: Wed Apr 05, 2006 6:31 pm    Post subject: Reply with quote

Assuming that you still have something in mind.
The following grid could be a convenient test case:
Code:

*-----------*
|672|845|931|
|918|693|572|
|345|721|468|
|---+---+---|
|521|389|746|
|736|452|819|
|489|167|253|
|---+---+---|
|263|974|185|
|897|516|324|
|154|238|697|
*-----------*

All columns and boxes fit and all but two rows fit.
R2&R3 together do contain all numbers 1-9 twice.

It should not trick your method.
Smile
Back to top
View user's profile Send private message Send e-mail
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Sun Apr 09, 2006 8:41 am    Post subject: Reply with quote

Of course the 1-9 are just symbols. You should feel free to assign any value you want to each symbol, x, such as 2**(x-1) if it helps. I think this may possibly lead you down the path to templating.

Not sure if it ties in to the original topic, but Vidar has written a POM solver which basically uses binary equations derived from unsolved cells to make deductions
_________________
Myth Jellies
Back to top
View user's profile Send private message
Pho3NiX

Joined: 28 Sep 2006
Posts: 3
:

Items
PostPosted: Thu Sep 28, 2006 4:43 am    Post subject: Reply with quote

[deleted] will split post in two

Last edited by Pho3NiX on Thu Sep 28, 2006 4:45 am; edited 1 time in total
Back to top
View user's profile Send private message
Pho3NiX

Joined: 28 Sep 2006
Posts: 3
:

Items
PostPosted: Thu Sep 28, 2006 4:44 am    Post subject: Reply with quote

Hi Kamphuys and all,

I've been exploring this possiblity, however have not yet make something that fully solve any puzzle.

One of the bad news you should know about is that there isnt really 27 diferent equation. you can combine two or more equation to make a third one so you end up with something like 21 equation.


One good news is that you do not _need_ to have uniqueness contraint wich would require you the 9! or other means. The matrix of addition to 45 generate a solution set wich include the real soduku solution if any.

In matrix term, this means that a valid soduku solution will be L-equivalent to your equation system.

A ~ B

A =
1 0 0
0 1 0
0 0 1


B =
1 0 0
0 1 2
0 0 1

B is Line-equivalent of A as 2 time last line of A + second line of A = second line of B


The very good news for you is that once fully reduced, there is only one solution for l-equivalent matrix of given size.


In layman terms this means that if you start from your equation system
1 1 1 1 1 1 1 1 1 1 1 ... 45


and you end up in something on the form of

1 0 0 0 0 0 0 0 0 0 0 0 ... 8
0 1 0 0 0 0 0 0 0 0 0 0 ... 7
0 0 1 0 0 0 0 0 0 0 0 0 ... 9
0 0 0 1 0 0 0 0 0 0 0 0 ... 2
0 0 0 0 1 0 0 0 0 0 0 0 ... 1


It will be valid for any solution including soduku ones.

wich means:
If you put a partially solved soduku in your matrix,
and you know that this soduku have one unique valid solution
and you are able to fully simplify your matrix

Then the given solution will and must be the soduku solution.

Back to top
View user's profile Send private message
Pho3NiX

Joined: 28 Sep 2006
Posts: 3
:

Items
PostPosted: Thu Sep 28, 2006 4:46 am    Post subject: Reply with quote

the 21 eq i've found:
green is positive, red is negative, white is null

grid:

1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 | 135
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | 45
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 45
0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 | 45
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 | 45
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 | 45
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 | 45
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 | 45
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 | 45
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 | 45
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 | 45



edit:
well, no white for you guy .... i guess i pushed to limit the buffer of open / close tag
Back to top
View user's profile Send private message
tarun

Joined: 10 Mar 2007
Posts: 1
:
Location: NY

Items
PostPosted: Sat Mar 10, 2007 7:30 pm    Post subject: Hey Reply with quote

Alrite,,I was thinking about this too,, and i have sumthing to add. By the way i am 15 years old high school student from NY. anywyas,,coming to the point,,

if you add each row, column and squares you should get 45. (9 * 3 = 27 equations)
if you multiply each row, column and squares you should get 362880 (9 * 3 = 27 equations)
if you subtract each row, coumn and squares you should get -43 (9 * 3 = 27 equations)

so thats a total of 81 equations, which is wat we need at most sinice the sudoku puzzles have 81 squares

i really dont know if this is going to work or not,,so i was wondering if any one over here could help me?

thank you very much
Back to top
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Sun Mar 11, 2007 9:09 pm    Post subject: Re: Hey Reply with quote

tarun wrote:

if you add each row, column and squares you should get 45. (9 * 3 = 27 equations)
if you multiply each row, column and squares you should get 362880 (9 * 3 = 27 equations)
if you subtract each row, coumn and squares you should get -43 (9 * 3 = 27 equations)

so thats a total of 81 equations, which is wat we need at most sinice the sudoku puzzles have 81 squares


You might like to think about this for a smaller system of equations, for instance
Code:

i + j + k = 6
i * j * k = 6
-i -j -k = -6

(if I have understood your question). You will see that they are not independent of one another, and so do not provide sufficient constraints to obtain a unique solution.

Regards,

Mike Metcalf

P.S. I write "If I understand your question" as it appears that NY high schools are failing to provide proper tuition in English Exclamation A well-formulated question is much more likely to elicit a reply.
Back to top
View user's profile Send private message
Quintessentialbum

Joined: 03 Jun 2007
Posts: 1
:
Location: New York

Items
PostPosted: Sun Jun 03, 2007 3:05 pm    Post subject: working mathematic model Reply with quote

I might be late to the party, but I just started playing around with sudoku and have a working mathematic model for solving any sudoku thrown my way.

The basic strategy is to understand sudoku as a three-dimensional binary matrix (row, col, num). On a 3x3, it generates 729 cells, 81 of which are ones and those signify the correct answer.

Here are the basic systems of equations:

num_constraint: for every row and collumn, add up all the numbers
e.g. r1c1n1+r1c1n2+r1c1n3... = 1

row_constraint: for every row and number, add up all the collumns
e.g. r1c1n1+r1c2n1+r1c3n1... = 1

col_constraint: for every collumn and number, add up all the rows
e.g. r1c1n1 +r2c1n1 + r3c1n1... = 1

box_constraint: add up every cell with the same number within a box
e.g. r1c1n1+r1c2n1+r1c3n1+r2c1n1... = 1

these four basic equations generate many more, but the end result is a solvable sudoku and if you set it up well, it's easily expandable for any size sudoku. I wrote the code in GAMS, but i'd love to see an equivelant code in other languages. Out of curiosity, what is the most common language for sudoku solvers? I too am a highschool kid and as i said before, i'm new at this, and i've got a lot to learn from you guys
Back to top
View user's profile Send private message
gamez

Joined: 07 Jun 2007
Posts: 4
:

Items
PostPosted: Thu Jun 07, 2007 2:57 pm    Post subject: Reply with quote

a lot of maths =(
Back to top
View user's profile Send private message
Arkh

Joined: 26 Jan 2009
Posts: 1
:

Items
PostPosted: Mon Jan 26, 2009 6:27 pm    Post subject: Reply with quote

Hello everybody,

First, sorry for my poor english...
As said Quintessentialbum, this way of building a mathematical model for sudokus works pretty well... I have searched on this forum for the following key words : "Linear Programming" and "Simplex" and i'm surprised there's no entries because this method (The Simplex method developed by G. Dantzig) enables us to find any Sudokus (for the moment I haven't found any problems with it and i think there's no) in less than a second, even
.................................................................................
aka 'the empty sudoku' is filled with a solution (which, of course, is not the only, but it works).

This method is using mathematical concept to solve it (polygonal and convex area, matrices etc...) and the models described by Quintessentialbum. And we developed a program using a C Library called GLPK on this model...
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron