Survo bulmacasının oluşturulması ve çözülmesı̇ ı̇çı̇n tamsayılı programlama formülasyonu

Year 2025, Issue: 71, 41 - 44, 30.08.2025

Banu Sungur , Fatma Selen Madenoğlu

https://doi.org/10.18070/erciyesiibd.1666419

Abstract

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.

Keywords

Survo , Bulmaca , Matematiksel programlama , Tamsayılı programlama

An integer programming formulation for generating and solving Survo puzzle

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

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. tcs.2023.114138 0
• Chlond, M. J. (2015). Puzzle—IP in the i. 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., Kneißl, 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, 179(17), 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, S. K., Roach, P. A., & Perkins, S. (2011). Sudoku puzzle complexity. In Proceedings of 6th Research Student Workshop (pp. 19-24).
• Keçeci, 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. J. 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, F. (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, R. S., Dhein, G., Muller, F. M., & de Araujo, O. C. B. (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, R. (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. 2226- 2230). IEEE.