4
$\begingroup$

Is always possible to solve a sudoku (that has a unique solution) using only naked pair/triple/quad methods? If not, what about using naked set and hidden set methods combined togheter? I need to know it because I would like to use those methods in a c++ software and I don't wanna use "guessing" because it costs too much in terms of calculations. Is there a solving method that allows me to solve sudokus without guessing?

$\endgroup$
6
  • $\begingroup$ Can you assume that the sudoku has a single solution? $\endgroup$ – bobble Aug 27 '20 at 18:28
  • 1
    $\begingroup$ what's the reason for the downvotes? $\endgroup$ – Ben Barden Aug 27 '20 at 18:49
  • 1
    $\begingroup$ IDK but my method is to eliminate impossibility and follow through certainty, with recursion and backtracking. So when placing a number, if the resulting elimination leaves another cell with a single possibility, I digress to follow that through immediately. I do this when placing the given starting numbers, and for simple puzzles that's all that is needed, the puzzle is solved without going to the next stage: choose cells with the least options and try them all, using the same algorithm. This worked for Project Euler #96 and Puzzling.SE problems like #97391 and others, and is quick. $\endgroup$ – Weather Vane Aug 27 '20 at 19:09
  • $\begingroup$ Yes, the sudoku has a single and unique solution $\endgroup$ – IlJoker11 Aug 27 '20 at 19:17
  • 3
    $\begingroup$ Pretty sure no. Check out Andrew Stuart's interactive solver which annotates steps (based on "human techniques"). Attached wiki gives example puzzles where many of the more complicated techniques are apparently needed. sudokuwiki.org/sudoku.htm $\endgroup$ – tehtmi Aug 28 '20 at 1:09
2
$\begingroup$

As tehtmi mentioned in a comment above, you can confirm using Andrew Stewart's solver that these techniques do not suffice for most difficult Sudoku.

But more generally, if your main goal is to write a fast solver (rather than one which models human solving), then don't be afraid of guessing. The fastest solvers for standard Sudoku are usually based on efficient backtracking algorithms with constraint propagation only for hidden singles and locked candidates (i.e., just things that can be implemented really efficiently). Computationally it's a bad trade-off to add more expensive forms of forward inference in an effort to reduce backtracking.

On the question of whether there are solving methods that are guaranteed to work without guessing, the answer is 'yes' if you don't insist that the algorithm be efficient. For example, you can write the rules of Sudoku and the givens of a puzzle as a propositional formula in CNF and then run a prime implicates algorithm like Tison's. Such an algorithm only advances valid consequences, so there's nothing you could call a guess, and it eventually finds all consequences, so it's guaranteed to find your solution. But you'd better get a coffee while it runs. Make that a lot of coffees.

If you want an efficient algorithm that doesn't guess, then you've got to be precise about what you count as a guess since there is range of reasonable definitions arising from different perspectives and tastes.

$\endgroup$
2
  • $\begingroup$ As a guess I mean to make compiler try some possible numbers until it stops because of an incompatibility between rows, cols or houses. If it guessed all numbers sudoku is completed, otherwise it goes back and restarts from that bad choice. My teacher suggested me to use "naked pairs" until the calculator can't go on anymore, then to continue solving the problem with "guessing method". That costs much less in terms of computing after excluding a lot of numbers. $\endgroup$ – IlJoker11 Aug 28 '20 at 21:24
  • 2
    $\begingroup$ Teachers don't tell you that, but the goal is not to solve sudokus, but to learn how to do backtracking efficiently. If you first apply standard elimination rules and then try to guess the case with the lowest number of possibilities (fewest numbers in a place or fewest places for a number) you will be fine in terms of performance. $\endgroup$ – Florian F Aug 29 '20 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.