In a Survo puzzle, the task is to fill an m × n table with integers 1, 2, ..., m·n so that each of these numbers appears only once and their row and column sums are equal to integers given on the bottom and the right side of the table. Often some of the integers are given readily in the table to guarantee uniqueness of the solution and/or for making the task easier.[2]
To some extent, Survo puzzles resemble Sudoku and Kakuro puzzles. However, numbers used in the solution are not restricted to 1, 2, ..., 9 and the size of puzzle grid is typically very small. Solving Survo puzzles is also related to making of magic squares.[3]
The degree of difficulty in solving Survo puzzles is strongly varying. Easy puzzles, meant for school children, are pure exercises in addition and subtraction, while more demanding ones require also good logic reasoning. The hardest Survo puzzles cannot be solved without computers.[4]
Certain properties of the Survo system like editorial computing and the COMB operation, making e.g. restricted integer partitions, support solving of Survo puzzles.
Survo puzzles have been published regularly in Finland by Ilta-Sanomat and the scientific magazine of the University of Helsinki from September 2006. Solving of Survo puzzles was one of the three main topics in the national entrance examination of the Finnish universities in computer science (2009).[5]
Example
Here is a simple Survo puzzle with 3 rows and 4 columns:
A
B
C
D
1
6
30
2
8
18
3
3
30
27
16
10
25
Numbers 3, 6, and 8 are readily given. The task is to put remaining numbers of 1-12 (3×4=12) to their places so that the sums are correct.
The puzzle has a unique solution found stepwise as follows: The missing numbers are 1,2,4,5,7,9,10,11,12. Usually it is best to start from a row or a column with fewest missing numbers. In this case columns A, B, and C are such.
Column A is not favorable since the sum 19 of missing numbers can be presented according to the rules in several ways (e.g. 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). In the column B the sum of missing numbers is 10 having only one partition 10 = 1 + 9 since the other alternatives 10 = 2 + 8 = 3 + 7 = 4 + 6 are not accepted due to numbers already present in the table. Number 9 cannot be put in the row 2 since then the sum of this row would exceed the value 18. Therefore, the only choice is to start the solution by
A
B
C
D
1
6
30
2
8
1
18
3
9
3
30
27
16
10
25
Now the column A has only one alternative 27 - 8 = 19 = 7 + 12 = 12 + 7. Number 7 cannot be in the row 1 because the sum of missing numbers in that row would be 30 - 7 - 6 = 17 and this allows no permitted partition. Thus we have
A
B
C
D
1
12
6
30
2
8
1
18
3
7
9
3
30
27
16
10
25
implying that the last number in the last row will be 30 - 7 - 9 -3 = 11:
A
B
C
D
1
12
6
30
2
8
1
18
3
7
9
3
11
30
27
16
10
25
In the first row the sum of the missing numbers is 30 - 12 - 6 = 12. Its only possible partition is 12 = 2 + 10 and so that number 2 will be in the column C; 10 in this position is too much for the column sum.
A
B
C
D
1
12
6
2
10
30
2
8
1
18
3
7
9
3
11
30
27
16
10
25
The solution is then easily completed as
A
B
C
D
1
12
6
2
10
30
2
8
1
5
4
18
3
7
9
3
11
30
27
16
10
25
Thus basic arithmetics and simple reasoning is enough for solving easy Survo puzzles like this one.
Properties of Survo puzzles
The rules of Survo puzzles are simpler than those of Sudoku. The grid is always rectangular or square and typically much smaller than in Sudoku and Kakuro. [6]
The solving strategies are varying depending on the difficulty of the puzzle. [6] In their simplest form, as in the following 2 × 3 case (degree of difficulty 0)
3
9
6
12
9
7
5
Survo puzzles are suitable exercises in addition and subtraction. [6]
The open 3 × 4 Survo puzzle (degree of difficulty 150)
24
15
39
21
10
18
29
where none of the numbers are readily given, is much harder. Also it has only one solution.
The problem can be simplified by giving some of the numbers readily, for example, as
7
5
24
1
8
15
11
39
21
10
18
29
which makes the task almost trivial (degree of difficulty 0). [6]
Assessing degree of difficulty
Measuring the degree of difficulty is based on the number of 'mutations' needed by the first solver program made by Mustonen in April 2006. This program works by using a partially randomized algorithm. [7]
The program starts by inserting the missing numbers randomly in the table and tries then to get the computed sums of rows and columns as close to the true ones as possible by exchanging elements in the table systematically. This trial leads either to a correct solution or (as in most cases) to dead end where the discrepancy between computed and true sums cannot be diminished systematically. In the latter case a 'mutation' is made by exchanging two or more numbers randomly. Thereafter the systematic procedure plus mutation is repeated until a true solution is found. In most cases, the mean number of mutations works as a crude measure for the level of difficulty of solving a Survo puzzle. This measure (MD) is computed as the mean number of mutations when the puzzle is solved 1000 times by starting from a randomized table. The distribution of the number of mutations comes close to a geometric distribution.
These numeric values are often converted to a 5-star scale as follows: [8]
MD
0 - 30
*
31 - 150
**
151 - 600
***
601 - 1500
****
1500 -
*****
The degree of difficulty given as an MD value is rather inaccurate and it may be even misleading when the solution is found by clever deductions or by creative guesswork. This measure works better when it is required that the solver also proves that the solution is unique.
Open Survo puzzles
A Survo puzzle is called open, if merely marginal sums are given. Two open m × n puzzles are considered essentially different if one of them cannot converted to another by interchanging rows and columns or by transposing when m = n. In these puzzles the row and column sums are distinct. The number of essentially different and uniquely solvable m × n Survo puzzles is denoted by S(m,n). [7]
Reijo Sund was the first to pay attention to enumeration of open Survo puzzles. He calculated S(3,3)=38 by studying all 9! = 362880 possible 3 × 3 tables by the standard combinatorial and data handling program modules of Survo. Thereafter Mustonen found S(3,4)=583 by starting from all possible partitions of marginal sums and by using the first solver program. Petteri Kaski computed S(4,4)=5327 by converting the task into an exact cover problem.
Mustonen made in Summer 2007 a new solver program which confirms the previous results. The following S(m,n) values have been determined by this new program: [9]
n
m
2
3
4
5
6
7
8
9
10
2
1
18
62
278
1146
5706
28707
154587
843476
3
18
38
583
5337
55815
617658
4
62
583
5327
257773
5
278
5337
257773
6
1146
55815
7
5706
617658
8
28707
9
154587
10
843476
Already computation of S(5,5) seems to be a very hard task on the basis of present knowledge.
Swapping method
The swapping method for solution of Survo puzzles has been created by combining the idea of the original solver program to the observation that the products of the marginal sums crudely indicate the positions of the correct numbers in the final solution. [10] The procedure is started by filling the original table by numbers 1,2,...,m·n according to sizes of these products and by computing row and column sums according to this initial setup. Depending on how these sums deviate from the true sums, it is tried to improve the solution by swapping two numbers at a time. When using the swapping method the nature of solving Survo puzzles becomes somewhat similar to that of Chess problems. By this method it is hardly possible to verify the uniqueness of the solution.
For example, a rather demanding 4 × 4 puzzle (MD=2050)
51
36
32
17
51
42
26
17
is solved by 5 swaps. The initial setup is
Sum
OK
error
16
15
10
8
49
51
-2
14
12
9
4
39
36
3
13
11
6
3
33
32
1
7
5
2
1
15
17
-2
Sum
50
43
27
16
OK
51
42
26
17
error
-1
1
1
-1
and the solution is found by swaps (7,9) (10,12) (10,11) (15,16) (1,2). In the Survo system, a sucro /SP_SWAP takes care of bookkeeping needed in the swapping method.
Quick games
Solving of a hard Survo puzzle can take several hours. Solving Survo puzzles as quick games offers another kind of challenges. [4] The most demanding form of a quick game is available in the net as a Java applet. [11] In this quick game, open 5 × 5 puzzles are solved by selecting (or guessing) the numbers by mouse clicks. A wrong choice evokes a melodic musical interval. Its range and direction indicate the quality and the amount of the error. The target is to attain as high score as possible. The score grows by correct choices and it is decreased by wrong ones and by the time used for finding the final solution.
A 4x4 version of is available for iOS devices as "Hot Box". [12]
Napier's bones is a manually-operated calculating device created by John Napier of Merchiston, Scotland for the calculation of products and quotients of numbers. The method was based on lattice multiplication, and also called rabdology, a word invented by Napier. Napier published his version in 1617. It was printed in Edinburgh and dedicated to his patron Alexander Seton.
Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that satisfies the given conditions. Mathematical puzzles require mathematics to solve them. Logic puzzles are a common type of mathematical puzzle.
77 (seventy-seven) is the natural number following 76 and preceding 78. Seventy-seven is the smallest positive integer requiring five syllables in English.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.
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.
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 contain 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.
Hitori is a type of logic puzzle published by Nikoli.
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.
Killer sudoku 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.
This is a glossary of Sudoku terms and jargon. It is organized thematically, with links to references and example usage provided as ([1]). Sudoku with a 9×9 grid is assumed, unless otherwise noted.
In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. 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.
Hidato, also known as "Hidoku", is a logic puzzle game invented by Dr. Gyora M. Benedek, an Israeli mathematician. The goal of Hidato is to fill the grid with consecutive numbers that connect horizontally, vertically, or diagonally. The name Hidato is a registered trademark of Doo-Bee Toys and Games LTD, a company co-founded by Benedek himself. Some publishers use different names for this puzzle such as Number Snake, Snakepit, Jadium or Numbrix.
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.
In the mathematics of Sudoku, the Sudoku graph is an undirected graph whose vertices represent the cells of a (blank) Sudoku puzzle and whose edges represent pairs of cells that belong to the same row, column, or block of the puzzle. The problem of solving a Sudoku puzzle can be represented as precoloring extension on this graph. It is an integral Cayley graph.
In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem.
References
↑ Aitola, Kerttu (2006): "Survo on täällä" ("Survo is here"). Yliopisto54(12): 44–45.
1 2 Mustonen, Seppo (2007): "On Survo cross sum puzzles". In J. Niemelä, S. Puntanen, and E. P. Liski (eds.) Abstracts of the Annual Conference of Finnish Statisticians 2007, "Multivariate Methods", pp. 23–26. Dept. of Mathematics, Statistics and Philosophy, University of Tampere. ISBN978-951-44-6957-2.
↑ Mustonen, Seppo (2006-09-26): ”Survo-ristikon vaikeuden arviointi” (”Evaluating the degree of difficulty of a Survo Puzzle”). Retrieved on 2009-08-30.
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.
