Modelling Sudoku Puzzles as Block-world Problems

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.

• Cecilia Nugraheni
• Luciana Abednego

• Sudoku puzzle
• block world problem
• parameterized multi agent systems modelling
• Temporal Logic of Actions.

<p>[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/&sim;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 &amp; 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 &amp; 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&rsquo;11 Proceedings of the 2011 international
conference on Applied &amp; 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 &amp; 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 &amp; Z.-C. Lee, Sudoku Solver by Q&acute;tron Neural Networks, Proc.
of International Conference in Intelligent Computing 2006, ICIC2006,
LNCS 4113, pp.943-952, 2006, Springer-Verlag, Berlin Heidelberg
2006.</p>