Survo puzzle

from Wikipedia, the free encyclopedia

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