<p>Solving a Sudoku puzzle is equivalent to deciding whether there is a valid <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow noreferrer">graph vertex coloring</a> using <span class="math-container">$k$</span> colors, where <span class="math-container">$k = 9$</span> in your <span class="math-container">$3 \times 3$</span> Sudoku instance.  The graph coloring problem is known to be NP-complete for values of <span class="math-container">$k &gt; 2$</span>, so a non-trivial, non-backtracking algorithm for <span class="math-container">$3 \times 3$</span> Sudoku would be very surprising.</p>

CC BY-SA 4.0
2020-06-18T20:04:17.617Z
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}$.
David Eppstein
CC BY-SA 4.0
2020-06-18T20:07:51.320Z
Sure, but I would not call that "non-trivial."
Kyle Jones
CC BY-SA 4.0
2020-06-18T20:32:44.230Z
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.
wolfmanx
CC BY-SA 4.0
2020-06-19T04:35:10.777Z
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.
David Eppstein
CC BY-SA 4.0
2020-06-19T05:29:49.633Z
@DavidEppstein Interesting.  Thanks for the reference.
Kyle Jones
CC BY-SA 4.0
2020-06-19T19:28:27.200Z
@DavidEppstein That's what I was looking for, thanks. Just to make sure, simple distributive expansion of a CNF formula is considered a trivial non-backtracking algorithm?
wolfmanx
CC BY-SA 4.0
2020-06-20T00:55:36.987Z
Ask @KyleJones, he's the one who's been classifying algorithms as trivial or nontrivial.
David Eppstein
CC BY-SA 4.0
2020-06-20T03:49:14.670Z
Yes, a simple distributive expansion of a CNF formula would be (to me) a trivial non-backtracking algorithm for SAT.
Kyle Jones
CC BY-SA 4.0
2020-06-18T19:18:29.090Z
2020-06-18T19:18:29.090Z
Kyle Jones
<p>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.</p>
<ol>
<li><p>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 <span class="math-container">$n^2\times n^2$</span> grids of <span class="math-container">$n\times n$</span> blocks, with <span class="math-container">$n=3$</span> and a single solution (a subset of UNAMBIGUOUS SAT).</p>
</li>
<li><p>Would such an algorithm be a stepping stone to raise the lower bound for e.g., graph vertex coloring from k&gt;2 to k&gt;3. Or would it just be considered an oddity.</p>
</li>
</ol>
<p>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.</p>
<p>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).</p>
<p>CSP algorithms seem to be best suited for such questions, but do not provide much insight into the structure of a specific problem instance.</p>
<p>To illustrate the context of my question, here are two papers which explicitly identify POLYTIME subsets of the applied algorithm:</p>
<p>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 &quot;search free&quot;.</p>
<p>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.</p>

CC BY-SA 4.0
2020-06-18T18:21:22.297Z
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.
Gamow
CC BY-SA 4.0
2020-06-18T18:25:16.730Z
what does "polynomial" mean when you're talking about 3x3? even a complete brute-force is technically speaking $O(1)$.
AmeerJ
CC BY-SA 4.0
2020-06-18T19:26:10.447Z
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.
wolfmanx
CC BY-SA 4.0
2020-06-18T19:31:52.497Z
@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.
wolfmanx
CC BY-SA 4.0
2020-06-20T07:37:07.013Z
@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.
Emil Jeřábek
<cc.complexity-theory><sat><polynomial-time>
Is there an algorithm for 3x3 sudokus without backtracking?
wolfmanx
# Is there an algorithm for 3x3 sudokus without backtracking?

(Asked by: username_0 on 2020-06-18)

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.

**Tags:** cc.complexity-theory, sat, polynomial-time
> **Comments:**
> **username_1**: 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.  
> **username_2**: what does "polynomial" mean when you're talking about 3x3? even a complete brute-force is technically speaking $O(1)$.  
> **username_0**: 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.  
> **username_0**: @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.  
> **username_3**: @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.  

---

## 1 answers

### Answer by username_4 on 2020-06-18. Score: -3 | Accepted answer

Solving a Sudoku puzzle is equivalent to deciding whether there is a valid [graph vertex coloring](http://en.wikipedia.org/wiki/Graph_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.

> **Comments:**
> **username_5**: 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}$.  
> **username_4**: Sure, but I would not call that "non-trivial."  
> **username_0**: 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.  
> **username_5**: 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.  
> **username_4**: @DavidEppstein Interesting.  Thanks for the reference.  
> **username_0**: @DavidEppstein That's what I was looking for, thanks. Just to make sure, simple distributive expansion of a CNF formula is considered a trivial non-backtracking algorithm?  
> **username_5**: Ask @KyleJones, he's the one who's been classifying algorithms as trivial or nontrivial.  
> **username_4**: Yes, a simple distributive expansion of a CNF formula would be (to me) a trivial non-backtracking algorithm for SAT.  

---

