Example of a Killer Sudoku problemSolution to the example aboveThe same example problem, as it would be printed in black and white
Killer sudoku (also killer su doku, sumdoku, sum doku, sumoku, addoku, or samunamupure) is a puzzle that combines elements of sudoku and kakuro. Despite the name, the simpler killer sudokus can be easier to solve than regular sudokus, depending on the solver's skill at mental arithmetic; the hardest ones, however, can take hours to solve.
A typical problem is shown on the right, using colors to define the groups of cells. More often, puzzles are printed in black and white, with thin dotted lines used to outline the "cages" (see below for terminology).
History
Killer sudoku puzzles were already an established variant of sudoku in Japan by the mid-1990s, where they were known as "samunamupure." The name stemmed from a Nipponised form of the English words "sum number place." Killer sudokus were introduced to most of the English-speaking world by The Times in 2005.
Traditionally, as with regular sudoku puzzles, the grid layout is symmetrical around a diagonal, horizontal or vertical axis, or a quarter or half turn about the centre. This is a matter of aesthetics, though, rather than obligatory: many Japanese puzzle-makers will make small deviations from perfect symmetry for the sake of improving the puzzle. Other puzzle-makers may produce entirely asymmetrical puzzles.
Terminology
Cell
A single square that contains one number in the grid
Row
A horizontal line of 9 cells
Column
A vertical line of 9 cells
Nonet
A 3×3 grid of cells, as outlined by the bolder lines in the diagram above; also called a box
Cage
The grouping of cells denoted by a dotted line or by individual colours.
House
Any nonrepeating set of 9 cells: can be used as a general term for "row, column, or nonet" (or, in Killer X variants, "long diagonal")
Rules
The objective is to fill the grid with numbers from 1 to 9 in a way that the following conditions are met:
Each row, column, and nonet contains each number exactly once.
The sum of all numbers in a cage must match the small number printed in its corner.
No number appears more than once in a cage. (This is the standard rule for killer sudokus, and implies that no cage can include more than 9 cells.)
In 'Killer X', an additional rule is that each of the long diagonals contains each number once.
Duplicate cell ambiguity
By convention in Japan, killer sudoku cages do not include duplicate numbers. However, when The Times first introduced the killer sudoku on 31 August 2005, the newspaper did not make this rule explicit. Even though the vast majority of killer sudoku puzzles followed the rule anyway, English-speaking solvers were confused about appropriate solving strategies given the ambiguity. On September 16, 2005, The Times added a new ruling that “Within each dotted-line shape, a digit CAN be repeated if the normal row, column and 3x3 box rules are not broken”. But on September 19 the rule changed to “Within each dotted-line shape, a digit CANNOT be repeated if the normal row, column and 3x3 box rules are not broken” - causing even more confusion. This revised rule stuck and the world standard[citation needed] is no duplicates within cages.
Solving strategies
Fewest possible combinations
Generally the problem is best tackled starting from the extreme sums—cages with the largest or the smallest sums. This is because these have the fewest possible combinations. For example, 5 cells within the same cage totalling 34 can only be 4, 6, 7, 8, and 9. Yet, 5 cells within the same cage totaling 25 has twelve possible combinations.
In the early stages of the game, the most common way to begin filling in numbers is to look at such low-sum or high-sum cages that form a 'straight line'. As the solver can infer from these that certain numbers are in a certain row or column, they can begin 'cross-hatching' across from them.
The Rule of 45
A further technique can be derived from the knowledge that the numbers in all houses (rows, columns and nonets) add up to 45. By adding up the cages and single numbers in a particular house, the user can deduce the result of a single cell. If the cell calculated is within the house itself, it is referred to as an 'innie'; conversely if the cell is outside it, it is called an 'outie'. Even if this is not possible, advanced players may find it useful to derive the sum of two or three cells, then use other elimination techniques (see below for an example of this). This '45' technique can also be extended to calculate the innies or outies of N adjacent houses, as the difference between the cage-sums and N*45.
Clock Arithmetic
A short-cut to calculating or checking the value of a single 'innie' or 'outie' on a large number of cages is to add up the cages using 'clock' arithmetic (formally, Modular Arithmetic modulo 10), in which all digits other than the last in any number are ignored.
When two numbers are added together, the last digit of the total is not affected by anything other than the last digits of the two original numbers. Adding together a number ending in 7 and a number ending in 8 always results in a number ending in 5, for example. So, for example, 17 + 18 = 35 becomes, in clock arithmetic, 7 + 8 = 5. The biggest number an 'innie' or 'outie' can hold is 9, so adding or subtracting that value will change the last digit of the total in a way that no other value would - allowing the 'innie' or 'outie' to be directly calculated. Clock arithmetic has the advantage that you are only ever dealing with single-digit sums, rather than sums like, say, 58+27 - and even if the concept is initially unfamiliar, it rapidly becomes trivial.
Example: A set of cages form a complete nonet with an 'outie'. The cages have values 8, 10, 14, 7, 14.
Using normal arithmetic, those add up to 53. A single nonet totals 45, so the 'outie' must contain an 8.
Checking that, using clock arithmetic on those values in turn: 8+0=8; 8+4=2; 2+7=9; 9+4=3. So the clock total is 3, meaning that the actual total also ends in 3 (which we've seen that it does). Any odd number of houses (in this case, 1 nonet) always have an arithmetic total ending in 5 - so, the only 'outie' we could add to change that 5 to a 3 is, again, 8.
Clock arithmetic has the additional bonus that, when the final digits of two cage totals add up to 10 (13 and 27, for example), the pair will make no difference to the overall clock total, and can simply be skipped.
Clock arithmetic should at most be used with caution for houses with more than one 'innie' or 'outie', when more than one set of values may result in the same final number, but may still be useful as a quick arithmetic check.
Consistent numbers within combinations
Even though some cages can have multiple combinations of numbers available, there can often be one or more numbers that are consistent within all available solutions. For example: a 4 cell cage totaling 13 has the possible combinations of (1, 2, 3, 7), (1, 2, 4, 6), or (1, 3, 4, 5). Even though, initially, there is no way to tell which combination of numbers is correct, every solution available has a 1 in it. The player then knows for certain that one of the numbers within that cage is 1 (no matter which is the final solution). This can be useful if, for example, they have already deduced another cell within a nonet the cage resides in as having the number 1 as its solution. They then know that the 1 can only reside in cells that are outside of this nonet. If there is only one cell available, it is a 1.
Initial analysis of the sample problem
The sample problem
Fewest possible combinations
The two cells in the top left must be 1+2. The 3 cells to the right totaling 15 cannot therefore have either a 1 or a 2, so they must be either 3+4+8, 3+5+7, or 4+5+6.
The two vertical cages in the top left of the top right nonet cannot be 2+2 as that would mean duplicates, so they must be 1+3. The 1 cannot be in the top line as that conflicts with our first 2 cells therefore the top cell of this pair is 3 and the lower cell 1. This also means the 3 cell cage 15 to the left cannot contain a 3 and so is 4+5+6.
Similarly the neighbouring 16 must be 9+7.
The four cells in the top right cage (totaling 15) can only include one of 1, 3, 7, or 9 (if at all) because of the presence of 1, 3, 7, and 9 in the top right hand nonet. If any one of 1, 3, 7, or 9 is present then this must be the lone square in the nonet below. Therefore, these 4 cells are one of 1+2+4+8 or 2+3+4+6.
The 2 cells in the middle of the left edge must be either 1+5 or 2+4; and so on.
45 rule example
Looking at the nonet on the left hand side in the middle, we can see that there are three cages which do not cross over into another nonet; these add up to 33, meaning that the sum of the remaining two cells must be 12. This does not seem particularly useful, but consider that the cell in the bottom right of the nonet is part of a 3-cage of 6; it can therefore only contain 1, 2 or 3. If it contained 1 or 2, the other cell would have to contain 11 or 10 respectively; this is impossible. It must, therefore, contain 3, and the other cell 9.
Complements
With 6-cell, 7-cell or 8-cell cages, correlating the combinations with their 3-cell, 2-cell, or 1-cell complements usually simplifies things. The table for 6 cell cages is the complement of the 3 cell table adding up to 45 minus the listed value; similarly, the 7 cell table complements the 2 cell table. An 8-cell cage is of course missing only one digit (45 minus the sum of the cage).
For example, the complement of a 7-cell cage totalling 41 is a 2-cell cage totalling 4 (because 9–7=2 and 45–41=4). As a 2-cell cage totalling 4 can contain only 1 and 3, we deduce that a 7-cell cage totalling 41 contains neither 1 nor 3.
Cage total tables
The following tables list the possible combinations for various sums.
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.
Addition is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or sum of those values combined. The example in the adjacent image shows two columns of three apples and two apples each, totaling at five apples. This observation is equivalent to the mathematical expression "3 + 2 = 5".
Subtraction is one of the four arithmetic operations along with addition, multiplication and division. Subtraction is an operation that represents removal of objects from a collection. For example, in the adjacent picture, there are 5 − 2 peaches—meaning 5 peaches with 2 taken away, resulting in a total of 3 peaches. Therefore, the difference of 5 and 2 is 3; that is, 5 − 2 = 3. While primarily associated with natural numbers in arithmetic, subtraction can also represent removing or decreasing physical and abstract quantities using different kinds of objects including negative numbers, fractions, irrational numbers, vectors, decimals, functions, and matrices.
17 (seventeen) is the natural number following 16 and preceding 18. It is a prime number.
Verbal arithmetic, also known as alphametics, cryptarithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. The name can be extended to puzzles that use non-alphabetic symbols instead of letters.
Mental calculation consists of arithmetical calculations using only the human brain, with no help from any supplies or devices such as a calculator. People may use mental calculation when computing tools are not available, when it is faster than other means of calculation, or even in a competitive context. Mental calculation often involves the use of specific techniques devised for specific types of problems. People with unusually high ability to perform mental calculations are called mental calculators or lightning calculators.
Casting out nines is any of three arithmetical procedures:
Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966, Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu, seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings.
Sudoku is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.
Elementary arithmetic is a branch of mathematics involving addition, subtraction, multiplication, and division. Due to its low level of abstraction, broad range of application, and position as the foundation of all mathematics, elementary arithmetic is generally the first branch of mathematics taught in schools.
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in exactly one subset in . One says that each element in is covered by exactly one subset in . An exact cover is a kind of cover. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.
Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.
This is a glossary of Sudoku terms and jargon. Sudoku with a 9×9 grid is assumed, unless otherwise noted.
Inshi no heya is a type of logic puzzle published by Nikoli. It is a specific form of the KenKen puzzle genre where every operation is implied to be multiplication.
In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.
A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine, and each number can only occur once in each row, column, and box. A Sudoku starts with some cells containing numbers (clues), and the goal is to solve the remaining cells. Proper Sudokus have one solution. Players and investigators use a wide range of computer algorithms to solve Sudokus, study their properties, and make new puzzles, including Sudokus with interesting symmetries and other properties.
KenKen and KenDoku are trademarked names for a style of arithmetic and logic puzzle invented in 2004 by Japanese math teacher Tetsuya Miyamoto, who intended the puzzles to be an instruction-free method of training the brain. The name derives from the Japanese word for cleverness. The names Calcudoku and Mathdoku are sometimes used by those who do not have the rights to use the KenKen or KenDoku trademarks.
Str8ts is a logic-based number-placement puzzle, invented by Jeff Widderich in 2008. It is distinct from, but shares some properties and rules with, Sudoku. The name is derived from the poker straight. The puzzle is published in a number of newspapers internationally, in two book collections, and in downloadable apps. It was featured on the Canadian television show Dragons' Den on November 24, 2010.
Takuzu, also known as Binairo, is a logic puzzle involving placement of two symbols, often 1s and 0s, on a rectangular grid. The objective is to fill the grid with 1s and 0s, where there is an equal number of 1s and 0s in each row and column and no more than two of either number adjacent to each other. Additionally, there can be no identical rows or columns. Similar to Sudoku, each puzzle begins with several squares in the grid already filled.
Sudoku codes are non-linear forward error correcting codes following rules of sudoku puzzles designed for an erasure channel. Based on this model, the transmitter sends a sequence of all symbols of a solved sudoku. The receiver either receives a symbol correctly or an erasure symbol to indicate that the symbol was not received. The decoder gets a matrix with missing entries and uses the constraints of sudoku puzzles to reconstruct a limited amount of erased symbols.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
