Snipes
From Sudoku Theory
Revision as of 16:41, 25 April 2023 by Ryokousha (talk | contribs) (→Local Constraints: image Syzygy Stardust)
This page is for collecting "nerd snipes" - various tasks to answer questions about minimums, maximums, and counts for all things sudoku.
Classic Sudoku
- The fewest given digits in a classic sudoku is 17; this was proven by McGuire et al. There exist 16 given sudoku with as few as 2 solutions. There are exactly 49158 essentially different 17 given puzzles; the last was found in 2019 (link), and an exhaustive search (link) has confirmed that this is a complete list. List of all essentially different 17 given puzzles.
- For 6x6 (standard, with 3x2 regions), the minimum is 8 givens (link).
- Every solution grid has at least one minimal puzzle with fewer than 22 givens, as shown by Mathemagics and blue. There are exactly four grids which do not have a minimal puzzle with fewer than 21 givens (link).
- The most givens for a minimal classic sudoku is 40 Template:Citation needed. Two examples are known. This is believed to be the maximum, but it is not proven to be.
- The most empty houses in a classic sudoku is 9 (3 boxes, 3 rows, 3 columns). This is the maximum, shown by exhaustive search Template:Citation needed.
- For a 6x6 grid, the most empty houses is 6 (link), found by randomra.
- The largest rectangle of empty cells in a classic sudoku is 32 cells (4x8). This is believed to be the maximum, but it is not proven to be. If the rectangle is allowed to rotate, then an area of 36 is possible, covering 54 cells and enclosing 27 (link).
- The largest number of consecutive blanks in a classic sudoku string is 34 (link). This is the theoretical maximum.
Variants
Unless otherwise noted, the minimums for variants are given either for the fewest givens needed for a unique solution (for a global variant), the fewest of a constraint needed for a unique solution with no given digits, or the fewest cells covered by a constraint needed for a unique solution with no given digits.
Global Variants
Irregular Sudoku
- The fewest givens with irregular regions is 8 (link). This is the theoretical minimum, as at least this many digits are needed to disambiguate the digit permutation. It is unknown who first discovered this pattern of regions - similar solution grids with a cyclic pattern in the rows and/or columns are useful for many minimal sudoku tasks.
Anti-Knight
- The fewest givens in an anti-knight sudoku is 8; there are 4 essentially different puzzles, found initially by ryokousha, rangsk, and Philip Newman (PN below). An exhaustive search using a gauntlet showed that these are the only four (link). This is the theoretical minimum, as at least this many digits are needed to disambiguate the digit permutation.
- If givens are restricted to the borders of the grid, the fewest possible is 10, found by PN (link). For 9 givens, the lowest solution count is 18, found by PN and ryokousha; this has been verified by rangsk.
- If givens are forbidden from touching, even diagonally, then the fewest possible is 9, found by ryokousha (link). This is the theoretical minimum, as all 8c anti-knight puzzles are known.
- Most anti-knight snipes are known for being terribly unhumanable. The closest anyone has come to a 9-given puzzle that resolves with only singles is TopAutism, with 67 cells filled (link).
Anti-King
- The fewest givens in an anti-king sudoku is 11, found by PN in collaboration with ryokousha (link). It is believed this is minimal, but this has not been proven.
Anti-King + Anti-Knight
- With both anti-king and anti-knight constraints, there is exactly one "essentially different” solution grid (which can be rotated, reflected, or have the digits permuted, to obtain the full list of possible solutions). The fewest possible givens remains 8 in order to disambiguate the digit permutation.
Diagonal (Sudoku X)
- The fewest givens known in a diagonal sudoku is 12; over 500,000 such puzzles are known (link). It is not known whether 11 is possible, though a number of 11c puzzles with 2 solutions are known (including four with 8 distinct digits, found by ryokousha).
Diagonal + Anti-King
- The fewest givens in a sudoku with both diagonal and anti-king constraints is 9, found by PN (link); there are 3 examples known currently. This is believed to be minimal, but this may be proven or disproven by exhaustive search (see above anti-knight section).
Non-Consecutive
- The fewest givens in a non-consecutive sudoku is 4; it is unknown who first determined this, but an exhaustive list has been produced Template:Citation needed.
- The fewest unique given digits needed for a non-consecutive sudoku is 1, discovered by Freddie Hand (link).
"Miracle" (Non-Consecutive + Anti-Knight + Anti-King)
- The fewest givens with anti-knight, anti-king, and non-consecutive constraints ("Miracle Sudoku") is 2, found by Mitchell Lee (link). This ruleset takes its name from the video linked. It has exactly 72 possible solution grids, which are equivalent to one another up to rotation, reflection, and cycling of digits.
Kropki (Anti-Ratio + Non-Consecutive)
- The fewest givens for a dotless kropki — that is, non-consecutive and anti-ratio (2:1) — is believed to be 4, like non-consecutive on its own. There are 8448 dotless solution grids Template:Citation needed.
Kropki (Anti-Ratio + Non-Consecutive) + Irregular
- The fewest givens for an irregular dotless kropki is 0, found by PN (link). Several of these are known, and this category has come to be referred to as a Scooby (after the title of the linked puzzle). We are reasonably confident that you can’t have -1 givens.
Anti-Ratio + Anti-XV + Irregular
- The fewest givens for an irregular anti-ratio anti-XV grid is 0, found by PN (link).
Local Constraints
Killer
- The fewest cages in a killer sudoku with no givens is 6 (link), and the fewest cells covered is 18 (link), both found by PN. The former is believed to be minimal, but this has not been proven (and 7 was believed to be minimal before the 6 was found, so...).
- The minimum of 18 cells has been proven by Scott Bathurst and PN (link) by filtering known 17 given classics. The existence of a 17-cell killer would imply the existence of a 17-given classic with the killer cells as givens (this is strictly more information than the killer cages give). Only 1 of the 49158 17-given classics passed the first two filters used - requiring the puzzle to be morphable into a form such that every given is adjacent to at least one other given with the property that switching these two givens results in 0 solutions (if swapping the givens results in 1 or more solutions, then replacing them with a killer cage can never disambiguate between these possibilities) - and this cannot be made unique with only killer cages by inspection. It has since been shown that all 49158 17-given classics are known, completing the proof that there is no 17-cell givenless killer.
- The fewest 2-cell cages is 9 (link) found by PN, again covering the theoretical minimum of 18 cells.
- The fewest 2- or 3-cell cages is 7 (link) found by PN, again covering the theoretical minimum of 18 cells.
- The fewest 2-cell cages with all different totals is 10 (link), found by PN.
- For 6x6, the fewest is 4 cages and 10 cells, found by PN (link). It is believed this is minimal, but this has not been proven. Puzzles with as few as 2 solutions are known for 4 cages and 8-9 cells.
- The fewest digits required in killer cage totals is 5 (5 single-digit totals), found by TopAutism (link). This is the theoretical minimum — although 4 clued cages would be sufficient to disambiguate the digits 1-9, at least one would need a double-digit total.
- The fewest number of distinct cage totals needed is 1; this can be done for the following values. All other totals permit digit permutations that guarantee more than one solution.
- If 1 cell cages are allowed, 8 is possible - link (found by clover)
- 10 - link (found by clover)
- 11 - link (found by clover)
- 12 - link (found by clover)
- 13 - link (found by clover)
- 14 - link (found by clover)
- 15 - link (found by clover)
- 16 - link (found by clover)
- 17 - link (found by clover)
- 18 - link (found by clover)
- 19 - link (found by clover)
- 20 - link (found by clover)
- 21 - link (found by clover)
- 22 - link (found by clover)
- 23 - link (found by clover)
- 24 - link (found by clover)
- 25 - link (found by Joseph Nehme)
- 26 - link (found by clover)
- 27 - link (found by ahaupt)
- 28 - link (found by clover)
- 29 - link (found by clover)
- 30 - link (found by clover)
- 31 - link (found by clover)
- 32 - link (found by Joseph Nehme)
- 33 - link (found by clover)
- 34 - link (found by clover)
- 35 - link (found by clover)
- 37 - link (found by Sam Cappleman-Lynes)
- For 6x6, the following totals are possible (all found by PN). All other totals permit digit permutations that guarantee more than one solution.
Killer + Anti-Knight
- The fewest cages is 4, found by ryokousha (link). This is the theoretical minimum, as 3 cages cannot disambiguate 9 digits. The fewest cells covered is 12, found by jovi_al (link), which is also the theoretical minimum.
- For 6x6, the fewest is 3 cages and 7 cells, found by PN (link). This is the theoretical minimum for both, as any lower is insufficient to disambiguate the digits.
Killer + Anti-King
- For 6x6, the fewest is 3 cages and 7 cells, found by PN (link). This is the theoretical minimum for both, as any lower is insufficient to disambiguate the digits.
Killer + Diagonal
- For 6x6, the fewest is 3 cages and 7 cells, found by PN (link). This is the theoretical minimum for both, as any lower is insufficient to disambiguate the digits.
Killer + Anti-King + Diagonal
- The fewest cages is 5, found by PN (link).
Thermo
- The fewest thermos is 3, originally found by PN; the fewest cells covered is 20, found by blue (link - note that this is called "17c" in the post, referring to the number of greater-than constraints rather than cells covered; as a result, the thermos in this puzzle are purely orthogonal). It is believed that the former is minimal, as a 2-thermo puzzle would require a corresponding 18c classic, but while these are relatively rare they have not been exhaustively cataloged, nor has a search been made to check for whether any can be morphed to a 2-thermo puzzle. It is unknown whether this is minimal — puzzles with as few as 3 solutions are known for 3 thermos and 19 cells (link).
- If limited to 2-cell thermos, the fewest is 18 if they are allowed to overlap at bulbs, found by PN and ryokousha collaboratively (link), and 19 if not, with two examples found by ryokousha (link) and PN (link) independently. It is unknown whether these are minimal.
Thermo + Anti-Knight
- The fewest thermos is 1, and the fewest cells covered is 9, found by PN (link). This is the theoretical minimum for both — at least 8 comparisons are needed to disambiguate the digits.
- If limited to 2-cell thermos, the fewest is 10, found by ryokousha (link). It is unknown whether this is minimal.
- If limited to 3-cell thermos, the fewest is 5, found by ryokousha (link). The lowest number of solutions for a puzzle with four thermos is 774 (link), also found by ryokousha.
Slow Thermo
- The longest possible slow thermo is 27 cells, found by PN (link). This is the theoretical maximum.
- The fewest slow thermos is 2 (see previous link). This is the theoretical minimum.
Arrow
- The fewest arrows is 5, and the fewest cells covered is 21, both found by PN in collaboration with (based on a puzzle by) BlueJay (link). It is unknown whether either is minimal.
- If the arrows are restricted to 2-cells, then the minimum is 9 (link), found by PN.
- If the arrows are restricted to 3-cell arrows, each contained within one house, then the minimum is 7 (link) found by PN.
Arrow + Anti-Knight
- The fewest arrows (single digit sums) is 3, found by PN (link). This is the theoretical minimum (with two arrows you can have at most seven distinct digits).
- If two-digit sums are allowed then 1 arrow is sufficient, as found by Gliperal (link).
Arrow + Non-Consecutive
- The fewest arrows is 1, and the fewest cells on that arrow is 5 (link) found by PN. The smallest number of solutions known for a 4-cell arrow is 4 (link), also found by PN.
Kropki (with negative constraint)
- The fewest dots (with negative constraint otherwise) is 1, found by jovi_al (link). This is the theoretical minimum. (Interestingly, this dot can be either white or black.)
Kropki Pairs
- The fewest dots for a kropki pairs sudoku (no negative constraint) is 14, found by PN (link). It is unknown whether this is minimal. At least two white dots are required to disambiguate the digits.
- For 6x6, the fewest dots is 7, found by PN (link). It is unknown whether this is minimal.
Quadruples
- The fewest known number of quadruple clues needed for a unique solution is 7 with 4 digits in each quadruple, found by PN (link). It is believed 7 quadruples is minimal, but this has not been proven; it is also unknown whether 7 quadruples with fewer than 4 digits in at least one quadruple is possible.
Palindrome
- The longest palindrome possible is 73 cells, found by PN (link). This is the theoretical maximum, since only one digit can appear an odd number of times (the digit at the center of the palindrome).
- The fewest number of cells covered by palindromes required to uniquely color the grid is 26 (link), found by PN. The fewest solutions for a 24-cell coverage puzzle is only 2 (link), found by ryokousha.
Palindrome + Anti-Knight
- The fewest number of cells covered by palindromes required to uniquely color an anti-knight grid is 8 (link), found by PN. This is believed to be minimal.
Palindrome + Anti-King
- The fewest number of cells covered by palindromes required to uniquely color an anti-king grid is 19 (link), found by Gliperal.
Clone
- The maximum number of times a clone domino can appear in a sudoku without overlapping is 8, proven by thirdmunky and Botaku (actually, they provied the more general case of a non-overlapping domino which can take any orientation). If the sudoku is considered toroidally, 9 dominoes are placeable Template:Citation needed.
- The maximum for non-overlapping three-cell clones is also 8, found by Botaku (link).
- The maximum for non-overlapping 3x3 clones is 5 Template:Citation needed. The 3x3 clone in this case must form an extra region (a digit appearing twice in the clone would need to appear 10 times in the grid).
Magic Square
- The maximum number of non-overlapping magic squares is 5 (see above clone section).
X-Sums
- The fewest known number of X-Sum clues needed for a unique solution is 7 (link). This is believed to be minimal, but has not been proven.
- The fewest number of distinct sums needed is 1; this can be done for the following sums:
- 15 - link (found by clover)
- 17 - link (found by PN)
- 18 - link (found by clover)
- 19 - link (found by clover)
- 20 - link (found by clover)
- 21 - link (found by Astral Sky Ranger)
- 23 - link (found by PN)
- 24 - link (found by PN)
- 25 - link (found by PN)
- 26 - link (found by PN)
- 27 - link (found by PN)
- 28 - link (found by Sam Cappleman-Lynes)
- 30 - link (found by PN)
- 31 - link (found by PN)
- 32 - link (found by PN)
- 33 - link (found by PN)
- 35 - link (found by PN)
- This list is believed to be complete; it has been proven impossible for sums <= 13 and >= 37 (by marek stefanik), and the sums 16, 22, 29, and 34 only have two values for X, resulting in a maximum of 8 clues (believed to be insufficient for this more restricted problem). The fewest solutions for a puzzle with only 36-sums is 38 (link), which is also believed to be the minimum.
Sandwich
- The smallest possible total of all the sandwich sums in a puzzle is 16 (link). This is believed to be minimal.
- The largest possible total of all the sandwich sums in a puzzle is 361 (link) found by ryokousha. It is thought to be the highest achievable limit, although there is no concrete proof.
- The fewest distinct sandwich totals possible is 2 (link), found by Gliperal. This it the theoretical minimum, as demonstrated by brute force. It is unknown if this is possible without one of the totals being 0.
Sandwich + Anti-Knight + Non-Consecutive
- The fewest sandwich clues required is 2 (link), found by Gliperal, which is the theoretical minimum, as 1 clue would allow the grid to be mirrored.
Little Killer
- The fewest known number of Little Killer clues needed for a unique solution is 5 (link), found by Bastien Vial-Jaime.
- The fewest number of distinct sums needed is 1; this can be done for the following sums:
- 13 - link (found by PN)
- 14 - link (found by PN)
- 15 - link (found by PN)
- 16 - link (found by clover)
- 17 - link (found by AFrayedKnot)
- 18 - link (found by AFrayedKnot)
- 19 - link (found by AFrayedKnot)
- 20 - link (found by AFrayedKnot)
- 21 - link (found by AFrayedKnot)
- 22 - link (found by AFrayedKnot)
- 23 - link (found by AFrayedKnot)
- 24 - link (found by PN)
- 25 - link (found by clover)
- 32 - link (found by AFrayedKnot)
- 33 - link (found by AFrayedKnot)
- 34 - link (found by AFrayedKnot)
- 35 - link (found by PN)
- 39 - link (found by AFrayedKnot)
- 48 - link (found by SSGranor)
- The fewest solutions for a puzzle with only 11-sums is 9 (link) found by ryokousha.
- The fewest solutions for a puzzle with only 12-sums is 2 (link) found by ryokousha.
- For 6x6, the following totals are possible (all found by rubenscube):
Skyscrapers
- The fewest number of distinct Skyscraper clues needed is 1; this can be done for the following values:
- 5 - link (found by PN)
- 6 - link (found by SSGranor)
- The fewest solutions for a puzzle with only 4-clues is 4 (link) found by Youri.
- The fewest solutions for a puzzle with only 3-clues is 8 (link) found by AFrayedKnot.
- The fewest solutions for a puzzle with only 2-clues is 2, all of which rely on using 8 clues on one edge. It can be proven that this is insufficient for a unique solution, however, and the prospects of any other arrangement seem very bleak.
German Whispers
- German whispers cannot result in a unique solution on its own, due to the symmetry of the digits; any solution can be transformed to a different valid solution by mapping each digit X to 10-X.
- The minimum number of cells covered by a single line resulting in only two solutions is 19 found by PN (link). This is a total of 18 connections/comparisons between cells, also the minimum known. The best known for 18 cells/17 connections has 36 solutions. It is unknown if allowing branching can improve on this.
- The longest single line possible covers 60 cells, found by Reson (link). It is unknown if this is maximal.
First and Last Impressions?
- The maximum number of clues is 31 (link), found by Sam Cappleman-Lynes.
Pro-King
- The maximum number of pro-king cells is 52 (link), found by PN.
Activated Cells
- The fewest possible activated cells in a sudoku grid is 11, first found by SSGranor (link). This is the theoretical minimum, as every row will have at least one, and rows with 5 on the edge will have two.
- The most possible activated cells in a sudoku grid is 36, first found by Youri (link). It is also possible for the activated cells to form a single orthogonally connected region, as shown by Reson (link). It is unknown whether a snake is possible.
Miscellaneous
Grid Properties
- There exist solved 9x9 latin squares which cannot be divided into sudoku regions aside from the trivial row and column partitions. The first known was found by PN and proven by AFrayedKnot (link).
- There exist solved sudoku grids which exhibit all three types of symmetry: rotational, reflectional (on both diagonals), and translational. The first recorded example comes from shye (link).
- There exist pencil-mark sudoku that have exactly two solutions which share no digits in common, first documented by jovi_al (link).
- It is possible for one digit in a sudoku grid to completely avoid touching (even diagonally) two others, as discovered by Emphyrio (link). The properties hold toroidally as well. Up to isomorphisms, it is the only pattern that works.
- For a symmetric, non-consecutive grid, the minimum amount of roping is two bands and one stack, found by shye (link). It is unknown if better is possible.
- There exist sudoku solutions that can be divided into two sets of digits, such that any orthogonally connected group in either set contains no repeated digits, as demonstrated by JMoat13(link) using a 4-digit/5-digit split. It is believe to be impossible for a 3-digit/6-digit split, even if the restriction on the 3-digit clusters is lifted.
- The minimum number of distinct sums of orthogonally adjacent digits in a filled sudoku grid is 7 (link) found by PN. The current best theoretical lower bound is 6, as proven by rubenscube Template:Citation needed.
- The minimum number of regions into which a solved grid can be partitioned, such that any one region can be deleted without adding solutions, is 3. Youri was first to describe the trivial partition where each region consists of 3 boxes, one from each band and stack. If the regions are required to be orthogonally connected, then the best known is 5 (link) found by AFrayedKnot. For specific grids, this can be improved to 2 (link), also found by Youri.
- There also exist specific grids which can be partitioned into 3 or even 4 sets of digits, such that each group individually (that is, deleting all other groups) still results in a unique solution. The first of these "Troikas" were found by Mathimagics (link); in fact, the linked grids are "Perfect Troikas" in that they are partitioned into equal (27-cell) sets and each resulting grid is minimal. The first "Quadriga" was found by coloin (link).
- There exists a numbered rooms grid with one set of the clues 1-9 on each edge of the grid, found by nathanf (link), with a unique solution.
Augmented Classics
- Although it is not possible for a sudoku puzzle to be unique with only given digits along the borderTemplate:Citation needed, many individual constraints are enough to finish the job, including:
