Survo puzzle
In Survo puzzles is number puzzle in a matrix (typically in the form of 3 × 4, 3 × 5, 4 × 4 or 4 × 5). These puzzles have been published regularly since September 2006 in the second largest Finnish newspaper Ilta-Sanomat and in the Journal of the University of Helsinki (Scientific Journal of the University of Helsinki, Yliopisto-lehti), which has readers all over Finland.
description
The Survo Puzzle , or Survo-Riddle, is a puzzle that is being researched by Seppo Mustonen and was first introduced by him in April 2006. The name of the puzzle is derived from Mustonen's Survo-System , which is an integrated environment for statistical analysis and related applications.
In a Survo puzzle, the task is to enter the numbers 1, 2, ..., mn in an m × n matrix in such a way that each of these numbers is used only once and that the row and column sums correspond to the numbers, which are given below and on the right side of the matrix. Often some of the numbers are already entered in the matrix at the beginning in order to guarantee a clear solution and / or to facilitate the solution.
The Survo puzzle has certain parallels to Sudoku and Kakuro puzzles. However, the numbers for solving the puzzle are not limited to 1, 2, ..., 9 and the matrix size is typically very small. Solving Survo puzzles is also similar to solving magic squares .
The difficulty of solving a Survo puzzle varies greatly. Simple puzzles, which are primarily intended for school children, serve as exercises for addition and subtraction, while the more demanding puzzles also require logical thinking. The most difficult Survo puzzles can only be solved with the help of computers.
Certain features of the Survo system , such as editorial computing and COMB operation making, such as B. the limited decomposition of natural numbers into summands , support the solving of Survo puzzles.
An example
Here is a simple 3-row, 4-column Survo puzzle:
A. | B. | C. | D. | ||
1 | 6th | 30th | |||
2 | 8th | 18th | |||
3 | 3 | 30th | |||
27 | 16 | 10 | 25th |
Of the 3 × 4 = 12 numbers in the matrix (for which the numbers 1–12 are to be used) the numerical values 3, 6 and 8 are already placed in front. The task now is to place the remaining numbers from 1–12 in the right place so that the sums are correct.
The puzzle has a clear solution, which can be found step by step as follows: The missing numbers are: 1, 2, 4, 5, 7, 9, 10, 11, 12. As a rule, it is best to put in a line or Start the column with the fewest numbers missing. In this case these are columns A, B and C.
Column A is not suitable as a starting column, since the sum 19 of the missing numbers can be calculated in different ways according to the rules (for example 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). In column B the sum of the missing numbers is equal to 10, whereby this can only be calculated using the remaining option 10 = 1 + 9, since the other alternatives 10 = 2 + 8 = 3 + 7 = 4 + 6 are no longer possible, based on the numbers already in the matrix. The number 9 cannot be placed in row 2, otherwise the row total would exceed 18. Therefore, the only remaining option to start resolving is:
A. | B. | C. | D. | ||
1 | 6th | 30th | |||
2 | 8th | 1 | 18th | ||
3 | 9 | 3 | 30th | ||
27 | 16 | 10 | 25th |
Now there is only the alternative 27 - 8 = 19 = 7 + 12 = 12 + 7 for column A. The number 7 cannot be placed in row 1 because the sum of the missing numbers in this row is 30 - 7 - 6 = 17 is and 17 no longer allows a permitted division. Hence:
A. | B. | C. | D. | ||
1 | 12 | 6th | 30th | ||
2 | 8th | 1 | 18th | ||
3 | 7th | 9 | 3 | 30th | |
27 | 16 | 10 | 25th |
and therefore also automatically for the last row 30 - 7 - 9 - 3 = 11:
A. | B. | C. | D. | ||
1 | 12 | 6th | 30th | ||
2 | 8th | 1 | 18th | ||
3 | 7th | 9 | 3 | 11 | 30th |
27 | 16 | 10 | 25th |
In the first row the sum of the missing numbers is 30 - 12 - 6 = 12. The only allowed division is 12 = 2 + 10, whereby only the number 2 can be placed in column C, as 10 is too high in this position for the column sum would be.
A. | B. | C. | D. | ||
1 | 12 | 6th | 2 | 10 | 30th |
2 | 8th | 1 | 18th | ||
3 | 7th | 9 | 3 | 11 | 30th |
27 | 16 | 10 | 25th |
The solution can now be completed simply by:
A. | B. | C. | D. | ||
1 | 12 | 6th | 2 | 10 | 30th |
2 | 8th | 1 | 5 | 4th | 18th |
3 | 7th | 9 | 3 | 11 | 30th |
27 | 16 | 10 | 25th |
This example puzzle could be solved clearly by simple arithmetic and thinking.
Properties of Survo Puzzles
The rules of Survo puzzles are simpler than those of Sudoku . The number matrix is always rectangular or square and mostly smaller than in Sudoku or Kakuro .
The solution strategies are different and depend on the difficulty of the puzzle. In its simplest form, as in the following 2 × 3 case (difficulty level 0):
3 | 9 | ||
6th | 12 | ||
9 | 7th | 5 |
Survo puzzles are suitable addition and subtraction exercises.
The open 3 × 4 Survo-Puzzle (difficulty level 150):
24 | ||||
15th | ||||
39 | ||||
21st | 10 | 18th | 29 |
If none of the numbers are already given at the beginning, it is more difficult to solve. It also has only one solution.
The problem can be simplified if some of the numbers are already filled in, for example:
7th | 5 | 24 | ||
1 | 8th | 15th | ||
11 | 39 | |||
21st | 10 | 18th | 29 |
which makes the task almost too easy (level of difficulty 0).
Estimating the difficulty level
The measurement of the level of difficulty is based on the number of mutations required by Mustonen's first solution program (in April 2006). This program works with a partially randomized algorithm.
The program starts with the missing numbers being entered randomly into the matrix. Then the program tries to get the calculated row and column sums as close as possible to the actual ones by systematically exchanging numbers in the matrix. These attempts either lead to a correct solution or (as in most cases) to no solution if the difference between the calculated and actual sums cannot be systematically minimized. In the latter case, a mutation is made by randomly swapping two or more numbers. The systematic procedure plus mutation is repeated until a true solution has been found. In most cases, the average number of mutations can be used as an approximate measure of the difficulty level of a Survo-Puzzle. This measure (MD) is calculated from the average number of mutations if the puzzle is solved 1000 times, based on a randomized matrix. The distribution of the number of mutations required approximates a geometric distribution.
The numerical MD values can be transferred to a 5-star scale:
MD
0-30 | * |
31-150 | ** |
151-600 | *** |
601-1500 | **** |
1500– | ***** |
However, the MD value as a measure of the degree of difficulty is somewhat imprecise and can even be misleading if the solution is found through clever thought and creative guesswork. However, the measure works well if the person solving the puzzle is also to prove that the solution is unique.
Open Survo Puzzles
A Survo-Puzzle is called open if only the row and column sums are given at the beginning. Two open m × n puzzles are essentially different if one cannot be converted into the other by exchanging rows and columns or by transposing when m = n . In these puzzles, the row and column totals are unique. The number of essentially different and clearly solvable m × n survo puzzles is represented by S ( m , n ).
Reijo Sund was the first to dedicate himself to determining the number of open Survo puzzles. He calculated S (3, 3) = 38 by taking all 9! = 362880 possible 3 × 3 matrices with the standardized combinatorial and data processing modules of the Survo system . Mustonen then found S (3, 4) = 583 by starting from all possible distributions of the marginal sums and using the first solution program. Petteri Kaski determined S (4, 4) = 5327 by converting the problem into a problem of exact coverage .
In the summer of 2007, Mustonen created a new solution program that confirmed the previous results. The following S ( m , n ) values were determined by this new program:
m / n | 2 | 3 | 4th | 5 | 6th | 7th | 8th | 9 | 10 |
2 | 1 | 18th | 62 | 278 | 1146 | 5706 | 28707 | 154587 | 843476 |
3 | 18th | 38 | 583 | 5337 | 55815 | 617658 | |||
4th | 62 | 583 | 5327 | 257773 | |||||
5 | 278 | 5337 | 257773 | ||||||
6th | 1146 | 55815 | |||||||
7th | 5706 | 617658 | |||||||
8th | 28707 | ||||||||
9 | 154587 | ||||||||
10 | 843476 |
Even the calculation of S (5, 5) appears to be a difficult task according to today's knowledge.
The exchange method
The swap method for solving Survo puzzles was born from the combination of the idea of the original solution program with the observation that the products of the marginal sums roughly indicate the position of the correct numbers in the final solution. The solution process starts by filling in the original matrix with the numbers 1, 2, ..., mn according to the size of these products and by calculating the row and column sums according to this initial arrangement. Depending on how these sums differ from the actual sums, the solution is to swap two numbers. When the exchange method is used, solving the Survo puzzle is similar to solving chess problems. This method makes it difficult to verify the uniqueness of the solution.
An example: A very challenging 4 × 4 puzzle (MD = 2050):
51 | ||||
36 | ||||
32 | ||||
17th | ||||
51 | 42 | 26th | 17th |
is solved by exchanging 5 times. The initial arrangement is:
total | OK | error | |||||
16 | 15th | 10 | 8th | 49 | 51 | −2 | |
14th | 12 | 9 | 4th | 39 | 36 | 3 | |
13 | 11 | 6th | 3 | 33 | 32 | 1 | |
7th | 5 | 2 | 1 | 15th | 17th | −2 | |
total | 50 | 43 | 27 | 16 | |||
OK | 51 | 42 | 26th | 17th | |||
error | −1 | 1 | 1 | −1 |
and the solution is found by swapping (7, 9) (10, 12) (10, 11) (15, 16) (1, 2). In the Survo system , a sucro / SP_SWAP takes care of the billing, which is required for the exchange method.
Short games
Solving a difficult Survo puzzle can take several hours. Solving them as short games presents another challenge. The most demanding type of short game is available on the Internet as a Java applet.
In these short games, 5 × 5 puzzles are solved by selecting (or guessing) the numbers with mouse clicks. The wrong placement of a number triggers a melodic sequence of tones. Their length and tone direction indicate the quality of the error. The score increases with correct decisions and is reduced due to incorrect positioning and the time required for the solution.
Web links
- Survo puzzles
- Enumeration of Survo puzzles (PDF file; 494 kB)
- Swapping method
- Quick game