Questions tagged [sudoku]

Sudoku is a puzzle that requires filling a 3x3 grid of 3x3 sub-grids in a way that each column, row and sub-grid contains every digit from 1 to 9.

-1
votes
1answer
97 views

2-SAT reduction to Easy Puzzle Solving

Introduction I've been developing interest in complexity classes and thought I was unable to prove my problem is NP hard, so I wanted to see if it was P-hard. I wanted to see if my puzzle solving is ...
0
votes
1answer
85 views

Pseudo-Proof of Constrained Sudoku is co-np

The definition of CO-NP A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. In other words, co-NP is the class of problems for which there ...
1
vote
1answer
79 views

Sudoku Puzzles in O log n time although inefficient

Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles. I then create the pseudo-code to demonstrate the algorithm. The algorithm does a search to compare the indexes of ...
1
vote
1answer
403 views

Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

Constrained Puzzle Generation: Let us say a sudoku puzzle is generated with the following procedure: Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$. Map $S$ to a $3 ...
22
votes
2answers
5k views

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku. Can you treat this program as a black box and use this to solve ...
1
vote
1answer
107 views

Is any sudoku solver an SAT solver?

I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning ...
0
votes
1answer
43 views

How can I complete my derivation of an algorithm to solve Sudoku puzzles from my formalisation of the rules?

I'm hoping to design and implement an intuitive algorithm that solves 9x9 Sudoku puzzles. I want to do this by first formalising the basic rules of the puzzle, and then deriving principles from these ...
1
vote
2answers
349 views

What algorithm paradigm is a recursive solver of Sudoku?

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?...
2
votes
0answers
177 views

How to color sudoku with this added constraint?

I couldn't figure out an algorithm for following graph coloring problem: Output color of each vertex for this graph: Given a solved 9*9 sudoku board that is a 9-colored board, applied first three ...
14
votes
3answers
985 views

How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?

So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a ...
5
votes
1answer
223 views

Minimum number of givens for General Sudoku of size $n^2 \times n^2$

Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens). What ...
7
votes
2answers
378 views

Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?

So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty ...
1
vote
0answers
138 views

Worst-case recursion depth for guessing numbers in a Sudoku puzzle when certain polynomial-time deduction rules are used

So for an arbitrary $n^2 \times n^2$ Sudoku puzzle, there are rules for inferring values and auxillary information in cells that run in polynomial time, e.g. using the filled in values to check to see ...
-2
votes
2answers
193 views

At what n, does a n^2xn^2 sudoku puzzle take too long to solve? [closed]

I'm creating a sudoku solver, and I'm wondering at what point, with a simple backtracking sudoku solving algorithm, does the result take way too long to compute? I'm thinking like more than 30 minutes?...
16
votes
1answer
831 views

Efficient encoding of sudoku puzzles

Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 =...
9
votes
2answers
467 views

Minimum number of clues to fully specify any sudoku?

We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all ...
13
votes
1answer
4k views

Random Sudoku generator

I want to generate a completely random Sudoku. Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a ...