Survo puzzle
{{Short description|Logic puzzle}}
A Survo puzzle is a kind of logic puzzle presented (in April 2006) and studied by Seppo Mustonen.
Aitola, Kerttu (2006): "Survo on täällä" ("Survo is here"). Yliopisto 54(12): 44–45.
The name of the puzzle is associated with Mustonen's Survo system, which is a general environment for statistical computing and related areas.
Mustonen, Seppo (2007): [http://www.csc.fi/english/csc/publications/cscnews/back_issues/cscnews1_2007 "Survo Crossings"] {{Webarchive|url=https://web.archive.org/web/20081128161044/http://www.csc.fi/english/csc/publications/cscnews/back_issues/cscnews1_2007 |date=2008-11-28 }}. CSCnews 1/2007: 30–32.
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
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.
Vehkalahti, Kimmo (2007): [http://www.helsinki.fi/~kvehkala/Kimmo_Vehkalahti_Windsor.pdf "Some comments on magic squares and Survo puzzles"]. The 16th International Workshop on Matrices and Statistics, University of Windsor, Canada, June 1–3, 2007.
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.
Mustonen, Seppo (2007): [http://mtl.uta.fi/tilastopaivat2007/abstracts/Mustonen.pdf "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. {{ISBN|978-951-44-6957-2}}.
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).
[http://www.tkt-yhteisvalinta.fi/valintakoe2009/tkt09_Tehtava3.pdf "Tietojenkäsittelytieteen yhteisvalinta 22.5.2009, Tehtävä 3: Survo-ristikko"] {{Webarchive|url=https://web.archive.org/web/20110720193847/http://www.tkt-yhteisvalinta.fi/valintakoe2009/tkt09_Tehtava3.pdf |date=2011-07-20 }}. ("National entrance examination in computer science, May 22nd 2009, Exercise 3: Survo Puzzle").
Example
Here is a simple Survo puzzle with 3 rows and 4 columns:
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 6 | style="background:silver" | 30 | |||
style="color: #aaaaaa;" | 2 | 8 | style="background:silver" | 18 | |||
style="color: #aaaaaa;" | 3 | 3 | style="background:silver" | 30 | |||
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 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
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 6 | style="background:silver" | 30 | |||
style="color: #aaaaaa;" | 2 | 8 | 1 | style="background:silver" | 18 | ||
style="color: #aaaaaa;" | 3 | 9 | 3 | style="background:silver" | 30 | ||
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 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
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 12 | 6 | style="background:silver" | 30 | ||
style="color: #aaaaaa;" | 2 | 8 | 1 | style="background:silver" | 18 | ||
style="color: #aaaaaa;" | 3 | 7 | 9 | 3 | style="background:silver" | 30 | |
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 25 |
implying that the last number in the last row will be 30 - 7 - 9 -3 = 11:
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 12 | 6 | style="background:silver" | 30 | ||
style="color: #aaaaaa;" | 2 | 8 | 1 | style="background:silver" | 18 | ||
style="color: #aaaaaa;" | 3 | 7 | 9 | 3 | 11 | style="background:silver" | 30 |
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 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.
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 12 | 6 | 2 | 10 | style="background:silver" | 30 |
style="color: #aaaaaa;" | 2 | 8 | 1 | style="background:silver" | 18 | ||
style="color: #aaaaaa;" | 3 | 7 | 9 | 3 | 11 | style="background:silver" | 30 |
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 25 |
The solution is then easily completed as
class="wikitable" style="text-align:center;" | |||||
style="color: #aaaaaa;"
| | A | B | C | D | |
style="color: #aaaaaa;" | 1 | 12 | 6 | 2 | 10 | style="background:silver" | 30 |
style="color: #aaaaaa;" | 2 | 8 | 1 | 5 | 4 | style="background:silver" | 18 |
style="color: #aaaaaa;" | 3 | 7 | 9 | 3 | 11 | style="background:silver" | 30 |
style="color: #aaaaaa;" | | style="background:silver" | 27 | style="background:silver" | 16 | style="background:silver" | 10 | style="background:silver" | 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.
Mustonen, Seppo (2006): [http://solmu.math.helsinki.fi/2006/3/ "Survo-ristikot"] ("Survo puzzles"). Solmu 3/2006: 22–23.
The solving strategies are varying depending on the difficulty
of the puzzle.
In their simplest form, as in the following 2 × 3 case (degree of difficulty 0)
class="wikitable" style="text-align:center;" | |||
3 | style="background:silver" | 9 | ||
6 | style="background:silver" | 12 | ||
style="background:silver" | 9 | style="background:silver" | 7 | style="background:silver" | 5 |
Survo puzzles are suitable exercises in addition and subtraction.
The open 3 × 4 Survo puzzle (degree of difficulty 150)
class="wikitable" style="text-align:center;"
| | style="background:silver" | 24 | |||
style="background:silver" | 15 | ||||
style="background:silver" | 39 | ||||
style="background:silver" | 21 | style="background:silver" | 10 | style="background:silver" | 18 | style="background:silver" | 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
class="wikitable" style="text-align:center;"
| 7 | 5 | style="background:silver" | 24 | ||
1 | 8 | style="background:silver" | 15 | ||
11 | style="background:silver" | 39 | |||
style="background:silver" | 21 | style="background:silver" | 10 | style="background:silver" | 18 | style="background:silver" | 29 |
which makes the task almost trivial (degree of difficulty 0).
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.
Mustonen, Seppo (2006-06-02): [http://www.survo.fi/papers/puzzles.pdf ”On certain cross sum puzzles”]. Retrieved on 2009-08-30.
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:
Mustonen, Seppo (2006-09-26): [http://www.survo.fi/ristikot/vaikeusarvio.html ”Survo-ristikon vaikeuden arviointi”] (”Evaluating the degree of difficulty of a Survo Puzzle”). Retrieved on 2009-08-30.
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).
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:
Mustonen, Seppo (2007-10-30): [http://www.survo.fi/papers/enum_survo_puzzles.pdf ”Enumeration of uniquely solvable open Survo puzzles”]. Retrieved on 2009-08-30.
class="wikitable" style="text-align:right;"
! {{diagonal split header|m|n}} | 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.
Mustonen, Seppo (2007-07-09): [http://www.survo.fi/puzzles/swapm.html ”On the swapping method”]. Retrieved on 2009-08-30.
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)
class="wikitable" style="text-align:center;"
| | style="background:silver" | 51 | |||
style="background:silver" | 36 | ||||
style="background:silver" | 32 | ||||
style="background:silver" | 17 | ||||
style="background:silver" | 51 | style="background:silver" | 42 | style="background:silver" | 26 | style="background:silver" | 17 |
is solved by 5 swaps. The initial setup is
class="wikitable" style="text-align:right; border=0;"
| | Sum | OK | error | ||||
16 | 15 | 10 | 8 | 49 | style="background:silver" | 51 | -2 | |
14 | 12 | 9 | 4 | 39 | style="background:silver" | 36 | 3 | |
13 | 11 | 6 | 3 | 33 | style="background:silver" | 32 | 1 | |
7 | 5 | 2 | 1 | 15 | style="background:silver" | 17 | -2 | |
Sum | 50 | 43 | 27 | 16 | |||
OK | style="background:silver" | 51 | style="background:silver" | 42 | style="background:silver" | 26 | style="background:silver" | 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.
The most demanding form of a quick game is available in the net
as a Java applet.
[http://www.survo.fi/java/quick5x5.html ”Survo Puzzle (5x5 quick game) as a Java applet”]. Retrieved on 2009-08-30.
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".
[https://web.archive.org/web/20160325163257/https://itunes.apple.com/us/app/hot-box/id292624476?mt=8 "Hot Box, an iOS 4x4 implementation"]. Published in October 2008.
See also
References
External links
- [http://www.survo.fi/puzzles/ Survo Puzzles]: Problems and solutions