Headnote
JEL: C60, C61, C69
ABSTRACT
Puzzles are often generated for entertainment but also mathematical or logical problems. Every puzzle has its logic and mathematics. Puzzles become more understandable when we can grasp and model the underlying logic. For this reason, puzzles constitute a research area of interest to scientists. One of the logic puzzles is the Survo puzzle. We have formulated an integer linear programming model to generate and solve this puzzle. Illustrative examples have been given to show the validity of the formulation. The model's effectiveness has been tested by solving Survo puzzles available on the internet. The solutions have been obtained in short CPU times. Then, the effectiveness of the model has been analyzed using experimental computations. The computational results have been obtained from a number of Survo puzzle instances. The proposed mathematical model has generated puzzles up to 50x50 size in short CPU times, a maximum of 254 seconds. Puzzles up to size 15x15 have been solved.
Keywords: Survo, Puzzle, Mathematical formulation, Integer programming
ÖZ
Bulmacalar genellikle eǧlence için üretilir ancak aynı zamanda matematiksel veya mantıksal problemlerdir. Her bulmacanın kendine özgü bir mantıǧı ve matematiǧi vardır. Altta yatan mantıǧı kavrayıp modelleyebildiǧimizde bulmacalar daha anlaşılır hale gelir. Bu nedenle bulmacalar bilim insanlarının ilgisini çeken bir araştırma alanı oluşturmaktadır. Mantık bulmacalarından biri de Survo bulmacasıdır. Bu bulmacayı oluşturmak ve çözmek için bir tamsayılı doǧrusal programlama modeli formüle edilmiştir. Formülasyonun geçerliliǧini göstermek için açıklayıcı örnekler verilmiştir. Modelin etkinliǧi internette bulunan Survo bulmacaları çözülerek test edilmiştir. Çözümler kısa işlemci sürelerinde elde edilmiştir. Daha sonra, modellerin etkinliǧi deneysel hesaplamalar kullanılarak analiz edilmiştir. Hesaplama sonuçları bir dizi Survo bulmaca örneǧi üzerinden elde edilmiştir. Önerilen matematiksel model, 50x50 boyutuna kadar bulmacaları kısa CPU sürelerinde, maksimum 254 saniyede üretmiştir. 15x15 boyutuna kadar olan bulmacalar çözülmüştür.
Anahtar Kelimeler: Survo, Bulmaca, Matematiksel programlama, Tamsayılı programlama
(ProQuest: ... denotes formulae omitted.)
INTRODUCTION
Survo is a kind of logic-based puzzle presented by Mustonen in 2006. In this puzzle, the goal is to fill mxn grid of cells with integers (1,2,...,mxn) so that no integer is repeated in the grid. These integers are placed in each cell so as to satisfy row and column sums. Some integers are given readily in the table to guarantee uniqueness and/or to facilitate the solution. Survo puzzle's challenging level might vary based on factors like the size of the grid and the number of empty cells (Mustonen, 2007). The number of missing values is represented as k. There are k! ways of ordering k numbers (Jones et al., 2011). Thus, the overall complexity of this puzzle is (£/). This is a non-polynomial function. This complexity shows that this puzzle is NP. In computational complexity theory, NP is a complexity class that describes certain types of decision problems.
Figure 1 shows the 3 x 4 example of the Survo puzzle and its solution. Numbers outside the grid indicate the total of cells in the corresponding row or column. The sum of the cells in the first, second , and third rows must be 30, 18, and 30, respectively. 27, 16, 10, and 25 are the sums of the integers to be written in the relevant columns from the first to the fourth column, respectively. For this example integers 3, 6 and 8 are given readily. There are nine blank cells (4=9) in the grid. Then we are asked to fill these nine empty cells with 1, 2, 4, 5, 7, 9, 10, 11, 12. These integers are written in blank cells, providing row and column totals.
In this paper, we have formulated an integer linear programming (ILP) model to generate and solve Survo puzzles.The remainder of the paper is organized as follows. In Section 2, a literature review 1s presented. Section 3 is devoted to the mathematical formulation of Survo puzzle. The computational experiments are presented in Section 4. Finally, concluding remarks are given in Section 5.
1. Literature Review
Puzzles have been studied both conceptually and mathematically in the literature. Mathematical models have been proposed for different puzzles. Hurliman (2015) has written a book that is a comprehensive guide to mathematical modeling for puzzles and games. The author has proposed mathematical models that can be adapted to a wide range of puzzle types and game scenarios, emphasizing the role of mathematical optimization in recreational problem solving. Sudoku has the most attention in the scientific community. Various mathematical models have been formulated to generate and solve them. Bartlett et al. (2008) have presented a binary integer linear programming (BILP) model to solve Sudoku puzzles. Their model formulates the placement of digits in each cell using binary variables and expresses the puzzle's rules through linear constraints. Coelho and Laporte (2014) have described two mathematical programming models and four enumerative algorithms for Sudoku. They have conducted a comparative analysis of these algorithms regarding solution performance, providing valuable insights into the effectiveness of different solving techniques. Yu et al. (2016) have proposed a BILP model to solve Odd/Even Sudoku puzzles. Their model incorporates standard Sudoku rules and constraints requiring certain cells to contain only odd or even digits. Reddy et al. (2016) have presented a BILP model to solve Sudoku puzzles, demonstrating the applicability of binary programming approaches to this widely studied problem. Ates and Cavdur (2025) have proposed a new mathematical programming formulation for generating Sudoku puzzles. They have discussed how to ensure the uniqueness of a solution for a puzzle instance generated by a hybrid approach that integrates the mathematical program with a heuristic algorithm. Beyond Sudoku, other logic-based puzzles have also begun to receive attention in the puzzle literature. Hinz et al. (2009) have proposed a mathematical model and computer tool to solve the Tower of Hanoi and Tower of London puzzles. Often used in cognitive science research, these puzzles have been modeled analytically and their solution spaces have been systematically explored. Meuffels and Hertog (2010) have solved a logical puzzle, the Battleship, by ILP model. Their approach has involved representing ship sizes, orientations, and valid placements through a set of linear constraints, ensuring compliance with the game's rules. Trindade et al. (2011) have presented a mixed integer linear programming (MILP) model for solving the Shisen-Sho puzzle, a tile-matching game of Chinese origin. The model captures the puzzle's matching and connection rules through mathematical formulations. Chlond (2015) has presented an ILP model for solving Wijuko and ABC logic puzzles. Puzzles' rules have been encoded as linear inequalities, allowing the derivation of optimal solutions using exact methods. Kegeci (2021) has proposed a MILP formulation for solving and generating Smashed Sums puzzles. Sungur (2022) has developed an ILP model to solve the Futoshiki puzzles. The model enforces the uniqueness of numbers in each row and column and the satisfaction of inequality conditions between adjacent cells. Burkardt and Garvie (2023) have developed an ILP model to solve the Eternity Puzzle, a notoriously complex tiling puzzle. Their work highlights the potential of ILP approaches in handling puzzles with large solution spaces and intricate placement constraints.
The Survo puzzle has not been studied much in the literature. Mustonen (2006) has suggested algorithms for solving Survo puzzles. Vehkalahti and Sund (2015) have formulated a Survo puzzle as a combinatorial matrix problem and developed a computational approach with binary matrices to solve Survo puzzles. They noted that this method, while not computationally efficient, is an interesting way to solve Survo puzzles.
To our knowledge, the ILP model has never been considered in the Survo puzzle literature so far. In the paper, we have presented an ILP model for generating and solving Survo puzzles for the first time.
2. Mathematical Formulation for Survo Puzzle
This section presents a mathematical formulation for the Survo puzzle. First, we give the notation which will be used throughout the section:
irows (Vi G I)
Jcolumns (j 6 J)
sinteger numbers (s E S)
mnumber of rows
nnumber of columns
Iset of rows
Jset of columns
Sset of integers
Rthe sum of row i (Vi E I)
cthe sum of column...
Adummy variable
...1, if integer number s is assigned to cell(ij); 0, otherwise
ytthe sum of row 1 (Vi E \)
zthe sum of column j (Vj E J)
The sets of ... denote the rows and columns, respectively. The set S={l,-f/wxw}denotes the integers assigned to the cells. The puzzle consists of mxn integers, each of which can be assigned to only one cell.
The integer linear programming model to generate Survo puzzles can be formulated as follows:
... (1)
subject to:
... (2)
... (3)
... (4)
... (5)
... (6)
... (7)
... (8)
The objective function (1) minimizes the dummy variable A. The constraints are as follows: (2) places only one integer s in each cell (ij). (3) ensures that each integer 5 must be placed only in one cell. (4) determines the total sum of row i (y). (5) determines the total sum of column 7 (2). (6),(7) and (8) define restrictions on the variables.
The model defined by (1)-(8) has [(mxn)?+m+n/] variables and [@xmxn)+m+n] linear constraints.
The model formulated to generate Survo puzzles can also solve these puzzles with a little modification. The right-hand sides of constraints (4) and (5) are replaced by parameters R, and C, respectively and these two constraints are rewritten into the model as follows:
... (9)
... (10)
Constraint (9) ensures that the total value of the integer numbers assigned to the row i is equal to the given row sum R, Constraint (10) ensures that the total value of the integer numbers assigned to the column 7 is equal to the given column sum C, This model has [(тхп)? ] variables and [(2xmxn)+m+n] linear constraints.
The proposed model has been illustrated on the examples to first generate and then to solve the Survo puzzles. We can examine how the parameters and decision variables take values according to these illustrative puzzles.
The model has been first applied to generate a 5x5 Survo puzzle with m=5,n=5. There are 25 integers (s=1,2,...,25) to be placed in the table. The optimal solution is given in the Table 1.
A 5x5 Survo puzzle has been generated with its solution as seen in Figure 2. For instance, the sum of the integers placed in the first row is 48, that's why y1 =48. Similarly z1 =90 for column 1. The number 7 is placed into the cell (2,2), that's why x227 =1 . Similarly x3322 =1 means 22 is placed in cell (3,3).
The integer programming model has been also applied to solve the illustrative example in Figure 1. In this example: m=3, n=4, R,=30, R,=18, R,=30,C,=27, C,=16, C,=10, C,=25.
In the illustrative puzzle, integers '1' to "72" (s=1.2....,12) should be placed in cells considering row and column sums. Three integers (3,6,8) are given in advance. The integer 6 has been written in the 2" column of the 1" row, that's why x, =1. Similarly x,,,=1 and x,,,=1. These three variable values have been written as constraints to the model. Other cells are blank. When the model is solved, the remaining integers (1,2,4,5,7,9,10,11,12) are placed in the puzzle as shown in the solution below:
For instance, ... thats why the integer 12 is written in the 1st column of the 1st row cell.
3. Computational Experiments
The integer programming model has been coded in AIMMS. All computations are done on computer with Intel(R) Cоге( ТM) 15-1035G1 CPU @ 1.00GHz 1.19 GHz and 8,00 GB Ram. The experimental study is done for solving the given puzzles are available on the web site https://www.survo.fi/puzzles/. A total of 377 puzzles of similar sizes were shared between 2006 and 2016 on the web site. Among these puzzles, 24 puzzles shared in the last two years have been chosen. These puzzles have been solved by the proposed model. Puzzles and solutions are given in Table 2. The first six columns present information about puzzles and the last column expresses the puzzle's solutions. The problem numbers and difficulty levels of the puzzles specified on the website are in the first and third columns, respectively. Optimal solutions have been obtained for all puzzles. As seen in Table 2, the CPU times are short in duration.
The puzzles found on the internet are small-sized puzzles. Survo puzzles becomes more difficult for larger 7 and j combinations. For that reason, we have generated the larger size puzzles by using proposed mathematical model. These generated puzzles are given in Table 3. The first column presents the problem size from 5x5 to 50x50. The second column shows the number of constraints, the third column shows the number of the variables. As seen in the last column (CPU times), all puzzles have been generated in a short time. The proposed mathematical model has generated puzzles up to 50x50 size. Larger-sized puzzles have not been generated. Solution process has been terminated by the solver.
We have solved newly generated larger size puzzles by proposed ILP model. Solutions are given in Table 4. In 15x15 puzzle, the optimum solution has been found when 12 integers (5% of the total integers) were given readily. Except for tthe 15x15 puzzle, no integers have been given readily in the other dimensional puzzles. The optimum solutions have not been found for other dimensional puzzles not included in Table 4.
Concluding Remarks
Mathematical models exist in a wide variety of puzzle applications, however, it has not been considered in the Survo puzzle literature so far. Survo puzzle is considered in this paper. This paper contributes to the literature by introducing, for the first time, an ILP model for Survo puzzle. We have formulated an ILP model for generating and solving Survo puzzles.
A computational study has been conducted to depict the capability of the mathematical model. The complexity of the corresponding formulation is analyzed computationally. The puzzles on the related website are solved using the proposed ILP model. In addition to these puzzles, new puzzles up to 50x50 have been generated with the proposed model. Of these newly generated puzzles, puzzles up to the size of 15x15 have been solved.
Sidebar
References
REFERENCES
Bartlett, A., Chartier, T. P., Langville, A. N., & Rankin, T. D. (2008). An integer programming model for the Sudoku problem. Journal of Online Mathematics and its Applications, 8(1), 1798
Burkardt, J., & Garvie, M. R. (2023). An integer linear programming approach to solving the Eternity Puzzle. Theoretical Computer Science, 975, 114138. https://doi.org/10.1016/j. tes.2023.114138 0
Chlond, M. J. (2015). Puzzle -IP in the 1. INFORMS Transactions on Education, 16(1), 39-41. https:// doi.org/10.1287/ited.2015.0142
Coelho, L. C., & Laporte, G. (2014). A comparison of several enumerative algorithms for Sudoku. Journal of the Operational Research Society, 65(10), 1602-1610. : https://doi. org/10.1057/jors.2013.114
Hinz, A. M., Kostov, A., KneiBl, F., Sürer, F., & Danek, A. (2009). A mathematical model and a computer tool for the Tower of Hanoi and Tower of London puzzles. Information Sciences, 17917), 2934-2947. https://doi.org/10.1016/j.ins.2009.04.010
Hurliman, T. (2015). Puzzles and games: a mathematical modeling approach. Lulu. com.
Jones, 5. K., Roach, P A, & Perkins, 5. (2011). Sudoku puzzle complexity. In Proceedings of 6th Research Student Workshop (pp. 19-24).
Kececi, B. (2021). A mixed integer programming formulation for Smashed Sums puzzle: Generating and solving problem instances. Entertainment Computing, 36, 100386. https://doi.org/10.1016/j.entcom.2020.100386
Meuffels, W. I. M., & den Hertog, D. (2010). Puzzle-Solving the Battleship puzzle as an integer programming problem. Informs Transactions on Education, 10(3), 156-162. https://doi.org/10.1287/ited.1100.0047
Mustonen, S. (2006, June). On certain cross sum puzzles. http://www.survo.fi/papers/ puzzles.pdf
Mustonen, S. (2007). Enumeration of uniquely solvable open Survo puzzles. Available from: http://www.survo.fi/papers/enum_survo_puzzles.pdf
Reddy, C. B., Reddy, K. K., € Upendra, D. (2016). An Integer Programming Model for the Sudoku Problem. International Journal of Mathematics Trends and Technology, 40(2), 164-169.
Sungur, B. (2022). An Integer Programming Formulation for the Futoshiki Puzzle. International Review of Economics and Management, 10(2), 38-49. http://dx.doi. org/10.18825/iremjournal. 1149837
Ates, T., & Cavdur, E. (2025). Sudoku Puzzle Generation Using Mathematical Programming and Heuristics: Puzzle Construction and Game Development. Expert Systems with Applications, 282, 127710. https://doi.org/10.1016/j.eswa.2025.127710
Trindade, E. S., Dhein, G., Muller, E. M., & de Araujo, О. C. В. (2011, August). Mixed Integer Linear Programming Models to Solve the Shisen-Sho Puzzle. In 2011 Workshop-School on Theoretical Computer Science (pp. 108-112). IEEE.
Vehkalahti, K., & Sund, K. (2015). Solving Survo puzzles using matrix combinatorial products. Journal of Statistical Computation and Simulation, 85(13), 2666-2681. http://dx.doi.org/10.1080/00949655.2014.899363
Yu, H., Tang, Y, € Zong, C. (2016, August). Solving odd even sudoku puzzles by binary integer linear programming. In 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD) (pp. 22262230). IEEE.
Footnote
