AN INTEGER PROGRAMMING FORMULATION FOR THE FUTOSHIKI PUZZLE

Öz

AN INTEGER PROGRAMMING FORMULATION FOR THE FUTOSHIKI PUZZLE

Öz

This paper is concerned with the problem of solving the Futoshiki puzzle. The Futoshiki, also known as “Unequal,” is a puzzle with an n × n grid containing inequality signs between the cells. Some digits may have been given at the beginning of the game. The aim is to fill in the empty cells so that each row and column contains the digits ‘1’ to ‘n’ without repeats. We have formulated an integer linear programming model to solve this problem. An illustrative example is given to show the validity of the model. The computational results are obtained and analyzed on some instances.

Anahtar Kelimeler

• Puzzle
• Fuhoshiki
• Mathematical Formulation
• Integer Programming Model

Kaynakça

1. Boreland, B., Clement, G. & Kunze, H. 2015. Set selection dynamical system neural networks with partial memories with applications to Sudoku and KenKen Puzzles. Neural Networks, 68: 46–51. http://dx.doi.org/10.1016/j.neunet.2015.04.008
2. Chlond, M.J. 2015. IP in the i. Informs, 16 (1): 39–41.
3. Coelho, L.C. & Laporte, G. 2014. A comparison of several enumerative algorithms for Sudoku. Journal of the Operational Research Society, 65: 1602–1610.
4. Espasa, J., Gent, I.P., Hoffmann, R., Jefferson, C. & Lynch, A.M. 2021. Using small muses to explain how to solve pen and paper puzzles. ArXiv, abs/2104.15040.
5. Haraguchi, K. 2013. The number of inequality signs in the design of Futoshiki Puzzle. Journal of Information Processing, 21(1): 26-32.
6. Haraguchi, K. & Ono, H. 2015. How simple algorithms can solve Latinsquare completion-type puzzles approximately. Journal of Information Processing, 23(3): 276–283.
7. Hinz, A.M., Kostov, A., KneißI, 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: 2934-2947.
8. Keçeci, B. 2021. A mixed integer programming formulation for Smashed Sums puzzle: Generating and solving problem instances. Entertainment Computing, 36: 1-8. https://doi.org/10.1016/j.entcom.2020.100386

9. Lloyd, H., Crossley, M., Sinclair, M. & Amos, M. (2021) (online). J-POP: Japanese puzzles as optimization problems. IEEE Transactions on Games. M.
10. Mahmood, A.S. 2019. Design random number generator utilizing the Futoshiki puzzle. Journal of Information Hiding and Multimedia Signal Processing, 10 (1): 178-186.
11. Maji, A.K., Jana, S. & Pal, R.K. 2013. An algorithm for generating only desired permutations for solving Sudoku Puzzle. Procedia Technology, 10: 392–399.
12. Piette, C., Piette, E., Stephenson, M., Soemers, D. J. & Browne, C. 2019. Ludii and XCSP: playing and solving logic puzzles. IEEE Conference on Games (CoG), 1-4.
13. Santos-Garcia, G. & Palomino, M. 2007. Solving Sudoku Puzzles with rewriting rules. Electronic Notes in Theoretical Computer Science, 176: 79–93.
14. Wang, W.L. & Tang, M.H. 2014. Simulated annealing approach to solve Nonogram Puzzles with multiple solutions. Procedia Computer Science, 36: 541–548.
15. Waziri, M.Y., Saidu, I. & Musa, H. 2010. A mathematical approach on solving Hausa Puzzles in Northern Nigeria. Procedia Social and Behavioral Sciences, 8: 694–699.
16. Yu, H., Tang, Y. & Zong, C. 2016. Solving Odd Even Sudoku Puzzles by binary integer linear programming. 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), 2226-2230.
17. Futoshiki online puzzles, https://www.futoshiki.org/.