
View previous topic :: View next topic 
Author 
Message 
 Kamphuys
 Joined: 13 Mar 2006  Posts: 2  :   Items 

Posted: Mon Mar 13, 2006 6:52 pm Post subject: Solving Sudoku's mathematically (?) 


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 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Mon Mar 13, 2006 8:51 pm Post subject: 


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 


 treffer
 Joined: 14 Feb 2006  Posts: 7  :   Items 

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


 treffer
 Joined: 14 Feb 2006  Posts: 7  :   Items 

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

Back to top 


 Kamphuys
 Joined: 13 Mar 2006  Posts: 2  :   Items 

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 nonlinear, 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 


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

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:
Code: 
**
672845931
918693572
345721468
++
521389746
736452819
489167253
++
263974185
897516324
154238697
**

All columns and boxes fit and all but two rows fit.
R2&R3 together do contain all numbers 19 twice.
It should not trick your method.


Back to top 


 Myth Jellies
 Joined: 20 Sep 2005  Posts: 14  :   Items 

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


Of course the 19 are just symbols. You should feel free to assign any value you want to each symbol, x, such as 2**(x1) 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 


 Pho3NiX
 Joined: 28 Sep 2006  Posts: 3  :   Items 

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


[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 


 Pho3NiX
 Joined: 28 Sep 2006  Posts: 3  :   Items 

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 Lequivalent 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 Lineequivalent 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 lequivalent 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 


 Pho3NiX
 Joined: 28 Sep 2006  Posts: 3  :   Items 

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 

Back to top 


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

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 

Back to top 


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

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


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 A wellformulated question is much more likely to elicit a reply. 

Back to top 


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

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


 gamez
 Joined: 07 Jun 2007  Posts: 4  :   Items 

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


a lot of maths =( 

Back to top 


 Arkh
 Joined: 26 Jan 2009  Posts: 1  :   Items 

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

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
