A Block World Problem Based Sudoku Solver

Authors: Luciana Abednego, Cecilia Nugraheni

Abstract:

There are many approaches proposed for solving Sudoku puzzles. One of them is by modelling the puzzles as block world problems. There have been three model for Sudoku solvers based on this approach. Each model expresses Sudoku solver as a parameterized multi agent systems. In this work, we propose a new model which is an improvement over the existing models. This paper presents the development of a Sudoku solver that implements all the proposed models. Some experiments have been conducted to determine the performance of each model.

Keywords: Sudoku puzzle, Sudoku solver, block world problem, parameterized multi agent systems.

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

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] 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.
[3] Wayne Gould. Su Doku Junior. Penerbit Erlangga. 2005.
[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] 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.
[8] 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.
[9] 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,.
[10] 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.
[11] C.E. Nugraheni & L. Abednego. Modelling Sudokus as Block World Problems. International Journal of Computer, Information, Systems and Control Engineering, volume 7, no. 8, pp. 48-54, World Academy of Science, Engineering and Technology, 2013.
[12] Thomas Ag. S. Sudoku - Edisi Lengkap dengan 270 Aneka Teka-teki Sudoku. Penerbit Andi. 2012.
[13] 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.