Questions tagged [sudoku]
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a $9\times9$ grid with digits so that each column, each row, and each of the nine $3\times3$ subgrids that compose the grid (also called "boxes", "blocks", "regions" or "subsquares") contain all the digits from $1$ to $9$. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution.
101 questions
11
votes
1
answer
298
views
Can a bivariate polynomial evaluated modulo 9 produce a valid Sudoku grid?
Can a bivariate polynomial with integer coefficients $f\colon \mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ generate a valid $9\times 9$ Sudoku grid, when evaluated modulo 9?
A consequence is that for ...
- 1,454
0
votes
0
answers
81
views
Classifying difficulty of Sudoku (and similar) puzzles
As per the answer to this question, the rules of Sudoku are NP-hard. However, in practice, real Sudoku puzzles are expected to be more solveable than that. General NP problems are allowed to require ...
- 738
1
vote
0
answers
178
views
Estimating the percentage of well-posed Sudoku puzzles that are unsolvable
Having written a computer program that solves Sudoku puzzles, I am intrigued by unsolvable puzzles.
By "well-posed" I mean that every row, column, and 3x3 sub-block of the puzzle contains a ...
- 19
3
votes
0
answers
58
views
What's the smallest sudoku that can be solved trivially, for some meaning of trivial? [closed]
This question was motivated by my musing about how to store the solution to a standard 9x9 sudoku in a reasonably compact form. While it's possible to solve a solvable sudoku quickly with a computer ...
- 213
44
votes
4
answers
6k
views
Is sudoku only one puzzle?
Consider a graph G where each node represents a possible Sudoku solution. We define edges between nodes based on the application of specific "equivalent transformations" that map one ...
- 573
6
votes
1
answer
231
views
What was the gap in Ariane Papke's proof that the minimum number of sudoku clues is 17?
I was reading McGuire's paper on why the minimum number of clues in a Sudoku puzzle is 17 when I came across a curious comment:
In 2008, a 17-year-old girl submitted a proof of the nonexistence of a ...
- 424
1
vote
1
answer
122
views
Can you efficiently determine the number of possible solutions for an arbitrary starting sudoku configuration?
I thought it would be fun to implement a solver which updates in real time to show how many possibilities remain as you fill in squares in any order. I'm able to find a number of resources explaining ...
- 11
4
votes
1
answer
310
views
Is there an underlying graph-theory representation of Sudoku solutions?
I have been puzzling for some time about how a completed 9x9 Sudoku solution can be represented mathematically, and how that mathematical representation can be used to enumerate the different ...
- 151
1
vote
1
answer
243
views
Finding all valid 5x5 sudoku/bingo boards where diagonals must also be unique?
I'm working on a personal project to create a bingo card for a video game. The bingo card contains items the player can use during normal play, and my goal is to be able to generate a bingo board ...
- 13
4
votes
3
answers
620
views
What type of math should I use for this puzzle?
I could use help modeling this puzzle. I'm not looking for a solution but I need help in phrasing the problem mathematically. I need a change in paradigm. My friend asked me for help with this puzzle ...
- 49
2
votes
2
answers
312
views
How many different $2 \times 2$ Sudokus are there?
PROBLEM
How many different $2 \times 2$ Sudokus are there?
APPROACH
This seems pretty easy to brute force. There are $576$ Latin squares of size $4$ (which are the sudokus without restriction on boxes)...
- 277
9
votes
0
answers
3k
views
Minimum number of clues for an unsolvable Sudoku
I am going to make a distinction between "unsolvable" and "invalid" Sudoku. A Sudoku is unsolvable if there is no way to fill in all the spaces without violating a row/column/block ...
- 223
1
vote
0
answers
115
views
Determinant of ModK Reduction of Matrix.
Let $M:=(m_{ij})$ be a square ($ n \times n $) matrix with entries in $\{ 1,2,3,.., n\}$ ,and non-zero determinant $D$ . Let $M_k$ be its reduction Mod($k$) ; $k=2,3,.., n-1$ , i.e., $M_k:=(m_{ij} ...
- 823
0
votes
1
answer
183
views
What is the maximum number of given numbers that still produces a minimal Sudoku? [closed]
The minimum number of given numbers that produce a valid Sudoku with a unique solution has been proven to be $17$, so it got me thinking, what is the maximum number of given numbers that still ...
- 19
1
vote
0
answers
159
views
Proving the validity-preserving nature of certain sudoku transformations using hypergraphs
I've been making a sudoku solver to get comfortable with graphs and the following "proof" popped into my head so I wanted to see if I could actually write it. Is this argument valid? Sorry ...
- 111
4
votes
2
answers
348
views
How Many Uniquely Enumerated $4\times4$ Sudoku Grids Exist?
I'm looking to find how many uniquely enumerated $4\times4$ Sudoku grids exist. I am aware that there are other questions with solutions to this question, however I am asking again as there seem to be ...
- 65
0
votes
0
answers
106
views
How was this Sudoku puzzle derived? Help needed to complete a possible derivation.
Solution and rules are found here.
\begin{array}{ccc|ccc|ccc}
4 & 8 & 3 & 7 & 2 & 6 & 1 & 5 & 9 \\
7 & 2 & 6 & 1 & 5 & 9 & 4 & 8 & 3\\
1 ...
- 5,328
1
vote
1
answer
206
views
Question involving filling numbers in a grid
Here's the problem and the diagram that goes with it
Fill in each empty space of the grid in the image below with a number from 1 to 8 so that every row & column contains each of these digits only ...
- 31
1
vote
1
answer
128
views
Constraint of Sudoku problem
$$\sum_{j=3q-2}^{3q}\sum_{i=3p-2}^{3p}x_{ijk}=1, \forall k = 1 :n; p,q = 1:3$$
The above constraint wants to describe what condition in the Sudoku problem?
I think the constraint here is that the ...
1
vote
0
answers
168
views
How many different "tight" sudoku puzzles are there?
How many different sudoku puzzles are there? posted a similar question and Chris Eagle's answer https://math.stackexchange.com/a/275425/26632 points to http://www.afjarvis.staff.shef.ac.uk/sudoku/...
- 5,639
0
votes
1
answer
116
views
What is the technique can be applied into this logjam in Sudoku? [closed]
The difficulty of this Sudoku is Expert. I have tried to apply swordfish, X-chain but seems like it is not valid. But I am pretty sure is my problem because I am still new to the advanced techniques. ...
- 326
0
votes
1
answer
843
views
Construct a compound proposition that asserts that every cell of a 9 × 9 Sudoku puzzle contains at least one number
Here is a problem from Kenneth Rosen's Discrete Mathematics and its Applications, Section 1.3
Construct a compound proposition that asserts that every cell of a 9 ×
9 Sudoku puzzle contains at ...
- 222
2
votes
0
answers
125
views
Is there a more abstract definition of a Sudoku Board
I was trying to figure out why a Sudoku board needs 17 answers at least to be defined and I was wondering if there are already ways in which you could convert a Sudoku board into a group or graph and ...
- 1,498
2
votes
1
answer
73
views
Sudoku prime triples
By a sudoku prime triple I mean a tripe $(p,q,r)$ of three-digit (base ten) primes which together use each of the nonzero digits $1$ to $9$ once each. I'm wondering how many such triples there are.
...
- 7,676
9
votes
1
answer
2k
views
Sudoku: Maximal minimum number of starting clues
It is well known (as shown here) that the minimum number of starting clues a Sudoku puzzle may have to generate a unique solution is 17.
My main question is
Given a completed Sudoku grid, is it ...
- 1,621