Survo Puzzle

In Survo puzzles are number puzzles in a matrix ( typically in the form of 3 × 4.3 × 5.4 × 4, or 4 × 5). Published this puzzle since September 2006 on a regular basis in the second largest Finnish newspaper Ilta - Sanomat and the Journal of the University of Helsinki ( Scientific Journal of the University of Helsinki, Yliopisto - lehti ), which readers across Finland.

Description

The Survo puzzle, or Survo puzzle is a mystery, which is researched by Seppo Mustonen and was presented by him for the first time in April 2006. The name of the puzzle comes from Mustonen 's Survo system which is an integrated environment for statistical analysis, and related applications.

In a Survo puzzles it is the task of the numbers 1,2, ..., mn as in an m × n - matrix entered that each of these numbers is used only once and that the row and column sums of the numbers corresponding to which are given below and on the right side of the matrix correspond. Often some of the numbers will be entered at the start already in the matrix in order to guarantee a unique solution and / or facilitate the solution.

The Survo puzzle has certain parallels to Sudoku and Kakuro puzzles. However, the numbers to solve the puzzle not to 1,2, ..., 9 are limited and the matrix size is typically very small. Solving puzzles Survo also similar to that of magic squares.

The difficulty of solving a Survo puzzles varies greatly. Simple puzzles, which are intended primarily for school children, serve as exercises for addition and subtraction, while the more demanding and require logical thinking. The heaviest Survo puzzles can only be solved with the help of computers.

Certain properties of the Survo system, such as the Editiorial computing and operational COMB making, such as the limited cutting of natural numbers into summands that support solving Survo puzzles.

An example of

Here you see a simple Survo puzzles with 3 rows and 4 columns:

Of the 3 × 4 = 12 numbers in the matrix (for which the numbers to be used from 1 to 12 ) are the numerical values ​​3, 6, and 8 has already vorplatziert. The task now is to place the remaining numbers from 1-12 in the right place, so that the totals are correct.

The puzzle has a unique solution, which can be found step by step as follows: The missing numbers are: 1,2,4,5,7,9,10,11,12. In general, it is best to start in a row or column in which the fewest numbers are missing. In this case, these are the columns A, B and C.

Column A is not suitable as a starting column since the sum 19 of the missing numbers in different ways according to the rules can be calculated (for example, 19 = 7 7 12 = 12 = 10 = 9 10 9). In column B, the sum of the missing numbers equal to 10, which can only be calculated by a remaining facilities 10 = 1 9 as the other alternatives 8 = 10 = 2 3 4 7 = 6 no longer possible due to the already located in the matrix numbers. The number 9 can not be placed in series 2, otherwise the row total would exceed 18. Therefore, the only remaining way to get started with the solution:

Now there is for column A, only the alternative 27-8 = 19 = 7 12 = 12 7 The number 7 can not be placed in row 1, since the sum of the missing numbers in this row 30 - 7 - 6 = 17 and 17 makes no allow sharing more. Therefore, we have:

And therefore automatically for the last row 30 - 7 - 9 - 3 = 11:

12 - - In the first row, the sum of the missing numbers 30, 6 = 12, the only still permitted distribution is 12 = 2 10, where only the number 2 can be placed in column C, as 10 in this position too high would be for the column total.

The solution can now be easily completed by:

This example puzzle was thus uniquely solvable by simple arithmetic and reflection.

Properties of Survo puzzles

The rules of Survo puzzles are simpler than those of Sudoku. The number matrix is always square or rectangular and usually 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 this case, 2 × 3 ( difficulty level 0):

Are Survo puzzles suitable addition and Subtraktionsübungen.

The open 3 × 4 Survo puzzle ( Difficulty 150):

At the beginning, none of the numbers are already given, is more difficult to solve. It also has only one solution.

The problem may be simplified if some of the numbers have been entered, for example:

What almost too easy makes the task ( Difficulty level 0 ).

Estimating the degree of difficulty

Measuring the level of difficulty based on the number of mutations that were required by the first solution program Mustonen ( in April 2006). This program works with a partially randomized algorithm.

The program will start so that the missing numbers can be randomly added to the matrix. Thereafter, the program tries to heranzureichen with the calculated line and column sums as close as possible to the actual by systematically exchanging numbers in the matrix. These experiments lead to either a correct solution, or (as in most cases) to no solution if the difference between the calculated and actual sums can not be systematically minimized. In the latter case, a mutation is carried out by two or more numbers are exchanged at random. The systematic procedure plus mutation is repeated until a real solution is found. In most cases, the average number of mutations are considered as an approximate measure of the difficulty of a Survo riddle. This measurement (MD ) is calculated from the average number of mutations when the puzzle is 1000 times achieved on the basis of a randomized matrix. The distribution of the number of required mutations approximates a geometric distribution.

The numerical MD values ​​can be transferred into a 5 - star scale:

MD

The MD value as a measure of the degree of difficulty is somewhat inaccurate and can be misleading even if the solution through clever thinking and creative rate is found. The measure works good, however, if the person who solves the mystery, let him prove that the solution is unique.

Open Survo puzzles

A Survo puzzle is called open if at the beginning only are given the row and column totals. Two open m × ​​n puzzles are essentially different, if one can not be converted into the other by a mutual exchange of rows and columns or by a transposition if m = n In these puzzles, the row and column sums are unique. The number of different essential and unique solution m × ​​n Survo puzzles is represented by S (m, n).

Reijo Sund has devoted first determining the number of open Survo puzzles. He calculated S (3,3) = 38, by all 9! = 362880 possible 3 × 3 matrices examined with the standardized Combinatorics and data processing modules of Survo system. Then took Mustonen S (3,4) = 583 by emanated from all possible splits of the marginal totals and the first solution program apply an end. Petteri Kaski certain S (4,4) = 5327, he converted by the task solution in a problem of exact registration.

In summer 2007, Mustonen has created a new solution program which has confirmed the previous results. The following S (m, n ) values ​​were determined by this new program:

Even the calculation of S (5,5) appears according to current knowledge than his difficult task.

The exchange method

The exchange method for solving puzzles Survo was the combination of the idea of ​​original solution program with the observation that the products of the marginal totals show the approximate position of the correct numbers in the final solution, was born. The solution process starts by filling the original matrix with the numbers 1,2, ..., mn according to the size of these products and by calculating the row and column sum corresponding to this initial arrangement. Depending on how these sums differ from the actual totals, the solution through an exchange of two numbers is. If the exchange method is used, similar to the release of the Survo riddle of the chess problems. Through this method, the uniqueness of the solution can not be easily verified.

An example: a very challenging 4 × 4 puzzle ( MD = 2050):

Is solved by 5 times Swap. The initial configuration is:

And the solution we found by swapping (7.9 ) (10,12) (10,11) (15,16) (1,2). In Survo system a Sucro / SP_SWAP provides for the settlement, which is required for the exchange method.

Short games

The release of a heavy Survo riddle may take several hours to complete. You to solve than short games offers a further challenge. The most sophisticated type of short games is available on the Internet as a Java applet.

In this short play 5 × 5 puzzles are by selecting ( or rates) solved the figures by mouse - clicks. The incorrect placement of a number triggers a melodic sequence of notes. Their length, and the sound direction indicate the quality of the error. The score increases with the correct decisions and will be reduced, due to incorrect positioning and by the time which is needed for the solution.