Solved

sudoku - is there a Maths to solving a puzzle?

Posted on 2014-11-23
6
303 Views
Last Modified: 2014-11-24
I am intrigued to solving Sudoku puzzles, and of course there is the hard way of analyzing each cell, then the grid, etc.   But I am sure there must be a math to solving such a puzzle.  Does anyone know about it.  Thank u.
0
Comment
Question by:jegajothy
6 Comments
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 200 total points
ID: 40461127
Even tbough Soduku uses numbers, it is a logical puzzle rather than a mathematical one.  You could work Soduku with nine letters, nine punctuation marks, or nine shapes.
You can automate the sort of analysis you use to solve a Soduku manually in a fairly simple computer program.
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 200 total points
ID: 40461187
Here is one of the classic essays on solving Soduku puzzles.
     http://norvig.com/sudoku.html
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 100 total points
ID: 40461218
Mathematics of Sudoku http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
The general problem is NP-complete, but Dancing Links is fast for 9x9
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 8

Accepted Solution

by:
ShannonEE earned 200 total points
ID: 40461226
Hi there jegajothy,

There is going to be many different mathematical ways to get a sudoku solution.

The one you may first try to set up would be to formalise the human solution technique of listing for each cell all the current possible values that aren't ruled out by horizontal, vertical or sub 3x3 grids.  Then go through and actually assign each cell that has only one possibility and repeat iteratively.  The rules for determining what is possible needs to include more than just horizontal, vertical and 3x3 cell remainders. For example if any 2 cells have the same two choices, then these values must be removed as a choice for other cells in the corresponding horizontal, vertical and 3x3 grid.  The same applies for 3 cells that have the same 3 choices, etc.

However I imagine that that "procedure" is not what you are thinking about.

Another method would involve setting up a system of equations and solving them.
To explain first check out linear programming http://en.wikipedia.org/wiki/Linear_programming. This is a guaranteed method of obtaining an optimum solution of a set of (linear) equations with an objective function.  Next there is integer programming http://en.wikipedia.org/wiki/Integer_programmingwhich typically hase the same form but with the restriction of only allowing integer solution to some (or all) of its variables.  In general there is no guaranteed of an optimal solution to integer programming problems, but the techniques of getting the solution of the system of equations does produce what is termed local optimums if not a global optimum.  In the suduko problem there really is nothing to minimise or maximise, we just want a feasible (ie every equation has values of the associated variables that make it true). The solution to linear programming and integer programming problems involves first getting a feasible solution and then by transforming that solution get an optimum solution.

Using integer programming it is possible to specify any suduko problem.  The easiest formulation will be a big problem - 243 equations with 324 variables - less 9 variables for each of the given numbers already in the shown problem. Then you can derive a solution to it using the integer programming techniques.

Such a formulation would be -
for each of the 81 individual grid positions establish 9 variables.  All there variables are restricted to integer values with a minimum value of 0 and a maximum value of 1.  (That is they all are what is termed 0/1 binary variables).  Number the grid positions (1, 1) up to (9, 9) where (i, j) denotes the grid for row i, column j where both i and j range from 1 - 9.  I will call the variable created Xijk. The first 9 variables X11k are all concerned with grid position (1, 1), X111 is 1 if and only if grid(1, 1) has 1 as its value when solved. If no then its value will be 0.  likewise X112 is 1 if grid (1, 1) has a 2 as its value when solved, 0 otherwise.

In general  Xijk is 1 if grid position (i, j) has "k" as the solution value, 0 otherwise.

The to specify the equations, notice that each grid position can only have one number in it, so there will be 81 equations of the form
Xij1 + Xij2 + Xij3 + ... + Xij9 = 1
Or compactly  Sum (over the 1-9 k values) Xijk = 1.

Those 81 equations ensure that the solution has exactly 1 value in each cell.

Now for each row (and also each column and each 3x3 sub grid) we must have exactly one "1", exactly one "2", ... exactly one "9".
X111 + X121 + X131 + ... X191 = 1
or Sum(j=1..9)  X1j1 = 1

and in general for each of the 9 digits for each of the 9 rows we have 81 equations
Sum (j=1 ..9) Xijk = 1

and in general for each of the 9 digits for each of the 9 columns we have 81 equations
Sum (i=1 ..9) Xijk = 1

and in general for each of the 9 digits for each of the 3x3 sub grids 81 we have 81 equations
Sum (i,j range over the 9 values in 3x3 grid) Xijk = 1

====

The initial clues can either be put in as additional equations like
Eg X264 = 1  being In row 2 column 6 there is a 4.  This will be conceptually the easiest way to go, but to improve efficiency it would be possible to remove the columns from the above formulation corresponding to disallowed values. In the example we would remove X261, X262, X263 (leave for the time being X264) and remove X265, X266, ...X269.  Next for all equations that mention X264, the value of X264 is given as 1 so the X264 variable can be removed as long as we also subtract 1 from the right hand side of each equation that it is in.

====

This method will set up the equations that specify the suduko problem and will lead to its solution.

=====
0
 
LVL 8

Assisted Solution

by:ShannonEE
ShannonEE earned 200 total points
ID: 40461490
Hi again jegajothy,

You can use schemes like I specified above to describe the sudoku problem and then determine the solution by solving the associated problem with integer programming.  Such a scheme can exactly specify the problem so that solving the suduko is equivalent to solving the associated integer programming problem.

With further careful study I'm sure that it may be possible to reduce the size of the associated system of equations, but hey with the mathematics it is not the quick solving but the ability to solve that is interesting.

In fact if you wanted to turn the whole problem on its head, given an integer programming system that has the form given above, a solution to the integer programming set of equations could be done using a compact 9x9 sudoku grid!!

If compute power is of no concern;  if you can set up the matrix corresponding to the system of equations;  if you have access to integer programming codes then go ahead.

From the integer programming processing you should be able to determine one of -

1/ There is no feasiable solution
2/ There is a feasiable solution (and what that solution was).

However if there was more than one feasiable solution then most integer programming codes would not tell you that another solution existed and was possible.

These results and the speed of doing so is dependent on the integer programming code, though the size of the problem is specified up front and hence this is not a problem that will grow without bounds.
 
If you know beforehand that there is (at least one) feasiable solution then the code should be able to make use of that fact in its method to determine the first feasiable solution (by minimising the infeasibilities).
0
 

Author Closing Comment

by:jegajothy
ID: 40462221
Well done everyone for your suggestions, it is overwhelming.  Thank u.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Probability 2 52
Maya SDK Getting total rotation from Rotation Anim Curves 1 33
Quadratic Equation 5 66
Calculating Standard Deviation inside Excel. 5 83
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
This Micro Tutorial will teach you how to censor certain areas of your screen. The example in this video will show a little boy's face being blurred. This will be demonstrated using Adobe Premiere Pro CS6.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now