Solving Sudoku's mathematically (?)

Kamphuys

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?

Ruud · Site Admin

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.

treffer · Posted: Tue Mar 14, 2006 9:08 am Post subject:

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

treffer · Posted: Tue Mar 14, 2006 9:14 am Post subject:

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).

Kamphuys · Posted: Tue Mar 14, 2006 12:24 pm Post subject:

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

evert · Posted: Wed Apr 05, 2006 6:31 pm Post subject:

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

Myth Jellies · Posted: Sun Apr 09, 2006 8:41 am Post subject:

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

Pho3NiX · Posted: Thu Sep 28, 2006 4:43 am Post subject:

[deleted] will split post in two

Pho3NiX · Posted: Thu Sep 28, 2006 4:44 am Post subject:

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.

Pho3NiX · Posted: Thu Sep 28, 2006 4:46 am Post subject:

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

tarun · Posted: Sat Mar 10, 2007 7:30 pm Post subject: Hey

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

m_b_metcalf · Posted: Sun Mar 11, 2007 9:09 pm Post subject: Re: Hey

Quintessentialbum · Posted: Sun Jun 03, 2007 3:05 pm Post subject: working mathematic model

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

gamez · Posted: Thu Jun 07, 2007 2:57 pm Post subject:

a lot of maths =(

Arkh · Posted: Mon Jan 26, 2009 6:27 pm Post subject:

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...