-4
$\begingroup$

From what I can see on Wikipedia and the Internet at large, all sudoku solving algorithms (including human ones) employ some kind of EXPTIME backtracking search for some sudokus.

  1. Are there any SAT solving algorithms that determine satisfiability in worst-case EXPTIME, which only require a worst-case POLYTIME subset of operations for sudokus on $n^2\times n^2$ grids of $n\times n$ blocks, with $n=3$ and a single solution (a subset of UNAMBIGUOUS SAT).

  2. Would such an algorithm be a stepping stone to raise the lower bound for e.g., graph vertex coloring from k>2 to k>3. Or would it just be considered an oddity.

I am mostly interested in the extent of the POLYTIME subset of operations of such an algorithm and any actual proof that an algorithm indeed solves all instances of 3x3 sudokus, not just experimental evidence.

The papers I have come across so far, are somewhat lacking in the sample set (e.g., the assumption that the number of clues correlates to the hardness is simply unfounded). No analysis is given that correlates the hardness of a sudoku to identifiable structural properties (like the XOR loops that make some problems hard for CDCL).

CSP algorithms seem to be best suited for such questions, but do not provide much insight into the structure of a specific problem instance.

To illustrate the context of my question, here are two papers which explicitly identify POLYTIME subsets of the applied algorithm:

Helmut Simonis, Sudoku as a Constraint Problem, CP Workshop on Modeling and Reformulating Constraint Satisfaction Problems, 2005, pages 13-28. In this paper sudokus are categorized with regard to how many solutions were obtained "search free".

I. Lynce, J. Ouaknine, Sudoku as a SAT problem, in 9th International Symposium on Artificial Intelligence and Mathematics AIMATH'06, January 2006. However, the sample sudokus (only 17 clue sudokus) are very weak, which explains the result, that only polynomial operations were necessary.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ As your question concerns a finite set of instances, it does not make much sense. For example, there is the trivial non-backtracking algorithm that simply checks all possible 9x9 Latin squares. $\endgroup$
    – Gamow
    Jun 18, 2020 at 18:21
  • 3
    $\begingroup$ what does "polynomial" mean when you're talking about 3x3? even a complete brute-force is technically speaking $O(1)$. $\endgroup$
    – AmeerJ
    Jun 18, 2020 at 18:25
  • $\begingroup$ I augmented the question accordingly. I am asking about the specific behavior of an algorithm on a subset of problems. However, the algorithm must be able to handle other problem sizes. $\endgroup$
    – wolfmanx
    Jun 18, 2020 at 19:26
  • $\begingroup$ @AmeerJ an algorithm has a worst-case time complexity in relation to the input size. That is the "polynomial" I am talking about. Limiting the input set to a specific size for a specific case has no bearing on the worst-case running time. $\endgroup$
    – wolfmanx
    Jun 18, 2020 at 19:31
  • 1
    $\begingroup$ @wolfmanx You don't "limit" the input size. Consider an algorithm that answers "undecided" whenever the input is larger than a 3×3 Sudoku, and otherwise solves it using a lookup table. This accepts all inputs, runs in constant time, uses no backtracking, and satisfies all the requirements. $\endgroup$
    – Emil Jeřábek
    Jun 20, 2020 at 7:37

1 Answer 1

Reset to default
-3
$\begingroup$

Solving a Sudoku puzzle is equivalent to deciding whether there is a valid graph vertex coloring using $k$ colors, where $k = 9$ in your $3 \times 3$ Sudoku instance. The graph coloring problem is known to be NP-complete for values of $k > 2$, so a non-trivial, non-backtracking algorithm for $3 \times 3$ Sudoku would be very surprising.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ An algorithm that tests whether the graph has ≤ 81 vertices, if so tries all possible 9-colorings, and if not gives up would fit the original question's requirements, and take constant time (assuming the number of vertices is directly accessible, otherwise at most linear to count vertices), but with a very big constant, something like $9^{81}$. $\endgroup$
    – David Eppstein
    Jun 18, 2020 at 20:04
  • $\begingroup$ Sure, but I would not call that "non-trivial." $\endgroup$
    – Kyle Jones
    Jun 18, 2020 at 20:07
  • $\begingroup$ My algorithm is generic, i.e.. non-trivial, and does require "decision making" eventually (albeit not over variables). From my experience with hard sudoku instances I did also expect that those pesky "sudokus, where you have to guess" would not be solved. However, they were. So thanks for the profound answer. $\endgroup$
    – wolfmanx
    Jun 18, 2020 at 20:32
  • $\begingroup$ There are also non-trivial non-backtracking algorithms for graph coloring in time $2^n$ (see Koivisto FOCS 2006) and again this is a constant time bound when restricted to $3\times 3$ sudoku. $\endgroup$
    – David Eppstein
    Jun 19, 2020 at 4:35
  • 1
    $\begingroup$ Ask @KyleJones, he's the one who's been classifying algorithms as trivial or nontrivial. $\endgroup$
    – David Eppstein
    Jun 20, 2020 at 0:55

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