Modelling Sudoku Puzzles as Block-world Problems

Authors: Cecilia Nugraheni, Luciana Abednego

Abstract:

Sudoku is a kind of logic puzzles. Each puzzle consists of a board, which is a 9×9 cells, divided into nine 3×3 subblocks and a set of numbers from 1 to 9. The aim of this puzzle is to fill in every cell of the board with a number from 1 to 9 such that in every row, every column, and every subblock contains each number exactly one. Sudoku puzzles belong to combinatorial problem (NP complete). Sudoku puzzles can be solved by using a variety of techniques/algorithms such as genetic algorithms, heuristics, integer programming, and so on. In this paper, we propose a new approach for solving Sudoku which is by modelling them as block-world problems. In block-world problems, there are a number of boxes on the table with a particular order or arrangement. The objective of this problem is to change this arrangement into the targeted arrangement with the help of two types of robots. In this paper, we present three models for Sudoku. We modellized Sudoku as parameterized multi-agent systems. A parameterized multi-agent system is a multi-agent system which consists of several uniform/similar agents and the number of the agents in the system is stated as the parameter of this system. We use Temporal Logic of Actions (TLA) for formalizing our models.

Keywords: Sudoku puzzle, block world problem, parameterized multi agent systems modelling, Temporal Logic of Actions.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086803

References:

[1] A. Bartlett, et.al. An Integer Programming Model for the Sudoku Problem, The Journal of Online Mathematics and Its Applications: Volume 8, Issue May, 2008.
[2] A. Gupta, How to solve Su Doku: tips, 2006, available at http://theory. tifr.res.in/∼sgupta/sudoku/algo.html.
[3] T. Koch, Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, ZIB Report 05-51.
[4] R. Lewis, Metaheuristics can solve Sudoku puzzles, Journal of Heuristics, Vol. 13, 2007, pp. 387-401.
[5] I. Lynce & J. Ouaknine. Sudoku as a SAT problem, Proc. of the 9th Symposium on Artificial Intelligence and Mathematics, 2006.
[6] T. Mantere. Solving, rating and generating Sudoku puzzles with GA., Proc. of IEEE Congress on of Evolutionary Computation, 2007. CEC 2007, Singapore.
[7] X.Q. Deng & Y.D. Li A novel hybrid genetic algorithm for solving Sudoku puzzle., Optimization Letters, February 2013, Volume 7, Issue 2, pp 241-257, Springer.
[8] P. Malakonakis, et.al. An FPGA-based Sudoku Solver based on Simulated Annealing methods., Proc. of International Conference on Field- Programmable Technology, 2009. FPT 2009.
[9] V. Mladenov, et.al., Solving Sudoku Puzzles by using Hopfield Neural Networks, Proc. of ICACM’11 Proceedings of the 2011 international conference on Applied & computational mathematics, pp.174-179 World Scientific and Engineering Academy and Society (WSEAS) Stevens Point, Wisconsin, USA, 2011.
[10] J. Monk, et.al. Solving Sudoku using Particle Swarm Optimization on CUDA, Proc. of The 2012 International Conference on Parallel and Distributed Processing Techniques and Applications, 2012,.
[11] A. Moraglio & J. Togelius, Geometric Particle Swarm Optimization for the Sudoku Puzzle, Proc. of Conference in Genetic and Evolutionary Computation, GECCO 2007, Proceedings, London, England, UK, July 7-11, 2007. ACM 2007.
[12] C.E. Nugraheni. Formal Verification of Parameterized Multi-agent Systems Using Predicate Diagrams*. Proc. of COMPUTATION TOOLS 2011: The Second International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking, Rome, 2011.
[13] T. Taibi. Formal specification and validation of multi-agent behaviour using TLA+ and TLC model checker. Int. J. Artificial Intelligence and Soft Computing, Vol. 1, No. 1, pp. 99-113, 2008.
[14] T.-W. Yue & Z.-C. Lee, Sudoku Solver by Q´tron Neural Networks, Proc. of International Conference in Intelligent Computing 2006, ICIC2006, LNCS 4113, pp.943-952, 2006, Springer-Verlag, Berlin Heidelberg 2006.