# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ?
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
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
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