Snipes

From Sudoku Theory
Revision as of 05:38, 21 September 2022 by Mith (talk | contribs) (→‎Classic Sudoku)

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, 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.
  • 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.

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 PN. An exhaustive search using a guantlet 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.

Anti-King

  • The fewest givens in an anti-king sudoku is 11, found by Philip Newman 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 Template:Citation needed. 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

"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)

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.

Local Constraints

Killer

  • The fewest cages in a killer sudoku with no givens is 7, and the fewest cells covered is 18, both found by PN (link). The former is believed to be minimal, but this has not been proven.
  • 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.
  • 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.

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.
  • 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.

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.

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).

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 to create 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).

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).
Retrieved from "http://sudokutheory.com/wiki/index.php?title=Snipes&oldid=17"