8
$\begingroup$

In particular I would like to know:

  1. is it possible to say if a sudoku is solvable only having the initial scheme? If yes, what are the condition for which it is solvable?
  2. Given the initial scheme of a solvable sudoku the final solution is always unique?
  3. There exist some simple free codes to solve a sudoku?
  4. Is there any deep mathematical theory behind or connected with a sudoku (some theorem of group theory or number theory) or it is only a simple and pretty game?
  5. What are the smartest means and strategies for solve a sudoku?

I am also interested in the pure mathematics behind my questions, so if you know some article or book in which the sudoku theory is explained, please let me know.

$\endgroup$
10
  • $\begingroup$ My impressions: 1) Yes, brute force checking runs reasonably fast. Ok, I don't think there is a QUICK way :-) 2) No. But all the (serious) publishers of sudokus design their puzzles in such a way that the answer is unique. Opinions differ, whether solvers can assume that. I belong to the school that teaches that you are not allowed to assume uniqueness (there are ways of taking advantage of this piece of information). 3) I think there are, but cannot give you a link to one. I have never used any, so couldn't recommend one anyway. $\endgroup$
    – Jyrki Lahtonen
    Commented Jun 27, 2013 at 11:13
  • $\begingroup$ I know this is probably not what you're looking for, but check out this article describing the connection between the solution of sudokus and CAT scans, via the Radon Transform. In my opinion, that is really quite incredible! $\endgroup$
    – torbonde
    Commented Jun 27, 2013 at 11:14
  • 1
    $\begingroup$ The simplest answer to the two above is to try to solve them and see what happens. Most computer algorithms employ brute force in one form or another, and the simplest one is just a recursive brute force, not too hard to code in an afternoon. For a more fancy approach, you could try to google "dancing links sudoku". According to wikipedia, any 9x9 sudoku is solved with a reasonable dancing links implementation within the blink of an eye on a regular home computer. So much so that the processors are too fast to really compare the time neccessary for different implementations. $\endgroup$
    – Arthur
    Commented Jun 27, 2013 at 11:16
  • 2
    $\begingroup$ Please check out this Mathematics of Soduko Wiki page. $\endgroup$
    – Nobody
    Commented Jun 27, 2013 at 11:19
  • 1
    $\begingroup$ The Sudoku Solver by Andrew Stuart provides a clever simulator and analyzer to judge the hardness of a given Sudoku. While many sudokus are solvable, the interesting question is "by what means and strategies?". $\endgroup$
    – Axel Kemper
    Commented Jun 27, 2013 at 13:42

2 Answers 2

Reset to default
8
$\begingroup$

Certainly almost everything you could want to know about the mathematics of sudoku will be at the wiki page entitled "mathematics of sudoku".

The first most famous obvious connection of mathematics to sudoku puzzles is that they are special Latin squares, which have been studied for centuries.

If by "solvable" you mean "can be completed into a valid sudoku solution," then it's obvious there are puzzles which have more than one solution (you could start with just a blank $9\times 9$ grid.) If by solvable you mean "you can complete the sudoku puzzle filling in each square one by one using logic and not guessing," then the question is a little bit more tricky, because one might imagine two logical progressions through the puzzle that lead to distinct valid solutions. (EDIT: However, it looks like you can still reason that any two logical progressions (meaning that each step completely determines the number added) leading to solutions have to agree. )

As commented before, though, the puzzle books usually stick to unique solutions (so that they can provide the correct solution).

There are certainly many free blocks of sudoku solving code for you. In fact Project Euler has a problem dedicated to designing exactly that code. Solutions for this problem are available all over the web.

$\endgroup$
3
  • $\begingroup$ Yes, by solvable I mean "can be completed filling in each square one by one using logic and not guessing" $\endgroup$
    – Red
    Commented Jun 27, 2013 at 13:37
  • $\begingroup$ Almost by definition, two 'logical progressions' through the puzzle cannot lead to distinct valid solutions. Logical deductions of a Sudoku are (primarily) restrictions indicating which cell-number pairs are impossible (e.g. 'this cell cannot have a 6 in it'); if there are e.g. two 'valid' solutions to a puzzle, where say one solution has a 4 in cell a5 and the other solution has a 6 in that cell, then whichever step eliminates the possibility of 6 in cell a5 in the process of leading to the solution with a 4 there is not a 'logical deduction', because 6 can't be logically eliminated. $\endgroup$
    – Steven Stadnicki
    Commented Jul 9, 2013 at 18:49
  • $\begingroup$ Dear @StevenStadnicki : I agree (looking back) that the only sensible meaning of "logical progression" has to entail that the result of each deduction is deterministic, so it couldn't lead to two valid solutions. $\endgroup$
    – rschwieb
    Commented Jul 9, 2013 at 19:22
1
$\begingroup$

Grobner bases might be what you are looking for, the only issue is that, as far as I know, they might not be very computer friendly (polynomials in 81 variables might be too big).

Check propositions 2 and 3 in this paper, or google for sudoku and grobner bases.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .