1
$\begingroup$

I am interested in knowing what algorithmic paradigm are the usual recursive sudoku solvers. Can I consider it a local search? or are they Dynamic programming, greedy, divide and conquer, backtracking?

$\endgroup$
  • $\begingroup$ Well, for each of these paradigms, have you looked up what they mean? Have you tried looking at, e.g., the wikipedia article for "dynamic programming" and tried to see whether the description fits your understanding of a recursive sudoku solver? I'm afraid that just telling you the answer won't help you understand the underlying concepts, so try solving this exercise on your own first. Perhaps you can formulate a more specific question if you are still unsure after looking up what these algorithmic paradigms mean. $\endgroup$ – Tom van der Zanden Nov 14 '17 at 10:35
  • $\begingroup$ @TomvanderZanden I have but I feel it combines one from every paradigm. For example, the recurrence relation of breaking the sudoku into smaller simpler to sudokus feels like DP or divide and conquer. The recursive "backtracking" when we encounter a problem feels like backtracking. It also feels like a local search because you're going from one possible solution to the nearest next possible solution and backtracking along the line. It just feels there are many paradigms mixed together and I'm not sure which one is it $\endgroup$ – AspiringMat Nov 14 '17 at 11:28
  • $\begingroup$ Just a note: you could implement an efficient (though exponential-time because the problem is NP-complete) sudoku solver with a dozen of lines of code if you use a constraint programming library ( "CP paradigm"). See this minizinc example. $\endgroup$ – Vor Nov 14 '17 at 11:42
  • 1
    $\begingroup$ Check Wikipedia: en.wikipedia.org/wiki/Sudoku_solving_algorithms. The standard recursive solution is straightforward backtracking. It has nothing at all to do with local search, dynamic programming, greedy, or divide and conquer. $\endgroup$ – Yuval Filmus Nov 14 '17 at 14:35
5
$\begingroup$

Let us go over your paradigms one by one:

  • Local search: In this paradigm, we start with some solution and try to improve it by local changes. Local search can be applied to Sudoku in at least two ways:

    1. Start with a non-legal solution (either not satisfying the Sudoku constraints or not conforming to the filled cells), and try to make local changes (say, one cell at a time) that make it more legal.
    2. Same as before, only we also allow partially filled boards. In this case we might as well start with the board as given, and at each step pick a cell and fill in some legal value. When we get stuck, we can choose a cell and erase it, and so on. This is a stochastic form of local search which in some sense goes against the essence of classical local search, which is completely deterministic and strives to reach an arbitrary locally optimal solution.
  • Dynamic programming: In this paradigm, we reduce our instance to smaller instances in such a way that the "repertory" of smaller instances is small, and each could be reached in many different ways.

    One way you could try to implement this paradigm to Sudoku is as follows. Pick an empty cell and fill it in all possible legal ways. For each such filling, check whether it leads to a solution. Each filling is a smaller problem since it has fewer empty cells. However, the number of possible smaller instances is huge, and each is reached in a unique way, so while this is the same as your recursive solution, it's not really in the spirit of dynamic programming.

  • Greedy: In this paradigm, you repeatedly make choices that you cannot later change. In the case of Sudoku, this corresponds to identifying unfilled cells which have only one legal filling. This is the approach used by most humans to solve Sudoku, though some puzzles require rather elaborate case analysis to find such safe fillings.

  • Divide and conquer: In this paradigm you divide your instance into independent instances which you solve separately, and then use their solutions to solve the original instance. One way this could be applied to Sudoku is by finding all possible solutions of 3×3 squares, and then try to combine them together. This is not only a terrible algorithm, but also the recursion is very shallow, whereas in divide and conquer we are aiming at deeper levels of recursion.

  • Backtracking: The standard recursive approach for Sudoku (pick a cell, enumerate all values, and recurse) is a great example of backtracking, which is the paradigm that best describes this algorithm.

$\endgroup$
  • $\begingroup$ Thank you, that's exactly what I needed to take away my confusion! $\endgroup$ – AspiringMat Nov 14 '17 at 15:00
0
$\begingroup$

You can ask the following 4 x 81 questions:

Where in column c does the number x go
Where in row r does the number x go
Where in 3x3 block b does the number x go
Which number goes into cell l

Obviously you leave out those questions that are already forced by the filled out cells. Now if any of the remaining questions has 0 possible answers, then the Sudoku cannot be solved. If any of the questions has exactly one answer, then fill a cell according to that answer. If each question has two or more answers, then you use backtracking with all possible answers of one of the questions that had the smallest number of answers.

$\endgroup$

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.