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.
20
questions
0
votes
0
answers
25
views
How to formulate "The general Sudoku problem is in P" formally and rigorously? How to calculate then the input size?
We consider a partially filled starting grid, where $n^2$ is the side size of the grid, $m$ is the number of non-empty initial squares, $f$ is the function that places randomly initially the integers ...
- 9
0
votes
1
answer
106
views
Proof: Solving a 9x9 sudoku is just as hard as determining whether there is a solution
I have so show that, for the normal 9x9 sudoku, determining whether there is a solution is just as hard as computing a solution if it exists. I should do that by assuming i have a polynomial-time ...
- 5
2
votes
0
answers
351
views
Least constraining value heuristic in Sudoku [closed]
I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
- 21
0
votes
1
answer
228
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 ...
- 309
0
votes
1
answer
205
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 ...
- 309
1
vote
1
answer
491
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 ...
- 309
2
votes
1
answer
514
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 ...
- 309
22
votes
2
answers
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 ...
user101371
2
votes
2
answers
623
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 ...
- 103
0
votes
1
answer
113
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
2
answers
900
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?...
- 593
2
votes
0
answers
208
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 ...
- 149
14
votes
3
answers
1k
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 ...
- 1,701
6
votes
1
answer
407
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 ...
- 1,013
7
votes
2
answers
494
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,701
1
vote
0
answers
163
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 ...
- 1,701
-2
votes
2
answers
381
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?...
- 7
17
votes
3
answers
2k
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 =...
- 1,072
12
votes
3
answers
9k
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 ...
- 1,072
13
votes
2
answers
5k
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 ...
- 263