{"title":"Modelling Sudoku Puzzles as Block-world Problems","authors":"Cecilia Nugraheni, Luciana Abednego","volume":80,"journal":"International Journal of Computer and Information Engineering","pagesStart":1124,"pagesEnd":1131,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/16224","abstract":"
Sudoku is a kind of logic puzzles. Each puzzle consists
\r\nof a board, which is a 9×9 cells, divided into nine 3×3 subblocks
\r\nand a set of numbers from 1 to 9. The aim of this puzzle is to
\r\nfill in every cell of the board with a number from 1 to 9 such
\r\nthat in every row, every column, and every subblock contains each
\r\nnumber exactly one. Sudoku puzzles belong to combinatorial problem
\r\n(NP complete). Sudoku puzzles can be solved by using a variety of
\r\ntechniques\/algorithms such as genetic algorithms, heuristics, integer
\r\nprogramming, and so on. In this paper, we propose a new approach for
\r\nsolving Sudoku which is by modelling them as block-world problems.
\r\nIn block-world problems, there are a number of boxes on the table
\r\nwith a particular order or arrangement. The objective of this problem
\r\nis to change this arrangement into the targeted arrangement with the
\r\nhelp of two types of robots. In this paper, we present three models
\r\nfor Sudoku. We modellized Sudoku as parameterized multi-agent
\r\nsystems. A parameterized multi-agent system is a multi-agent system
\r\nwhich consists of several uniform\/similar agents and the number of
\r\nthe agents in the system is stated as the parameter of this system. We
\r\nuse Temporal Logic of Actions (TLA) for formalizing our models.<\/p>\r\n","references":"
[1] A. Bartlett, et.al. An Integer Programming Model for the Sudoku\r\nProblem, The Journal of Online Mathematics and Its Applications:\r\nVolume 8, Issue May, 2008.\r\n[2] A. Gupta, How to solve Su Doku: tips, 2006, available at http:\/\/theory.\r\ntifr.res.in\/∼sgupta\/sudoku\/algo.html.\r\n[3] T. Koch, Rapid Mathematical Programming or How to Solve Sudoku\r\nPuzzles in a few Seconds, Konrad-Zuse-Zentrum fur Informationstechnik\r\nBerlin, ZIB Report 05-51.\r\n[4] R. Lewis, Metaheuristics can solve Sudoku puzzles, Journal of Heuristics,\r\nVol. 13, 2007, pp. 387-401.\r\n[5] I. Lynce & J. Ouaknine. Sudoku as a SAT problem, Proc. of the 9th\r\nSymposium on Artificial Intelligence and Mathematics, 2006.\r\n[6] T. Mantere. Solving, rating and generating Sudoku puzzles with GA.,\r\nProc. of IEEE Congress on of Evolutionary Computation, 2007. CEC\r\n2007, Singapore.\r\n[7] X.Q. Deng & Y.D. Li A novel hybrid genetic algorithm for solving\r\nSudoku puzzle., Optimization Letters, February 2013, Volume 7, Issue\r\n2, pp 241-257, Springer.\r\n[8] P. Malakonakis, et.al. An FPGA-based Sudoku Solver based on Simulated\r\nAnnealing methods., Proc. of International Conference on Field-\r\nProgrammable Technology, 2009. FPT 2009.\r\n[9] V. Mladenov, et.al., Solving Sudoku Puzzles by using Hopfield Neural\r\nNetworks, Proc. of ICACM’11 Proceedings of the 2011 international\r\nconference on Applied & computational mathematics, pp.174-179 World\r\nScientific and Engineering Academy and Society (WSEAS) Stevens\r\nPoint, Wisconsin, USA, 2011.\r\n[10] J. Monk, et.al. Solving Sudoku using Particle Swarm Optimization on\r\nCUDA, Proc. of The 2012 International Conference on Parallel and\r\nDistributed Processing Techniques and Applications, 2012,.\r\n[11] A. Moraglio & J. Togelius, Geometric Particle Swarm Optimization for\r\nthe Sudoku Puzzle, Proc. of Conference in Genetic and Evolutionary\r\nComputation, GECCO 2007, Proceedings, London, England, UK, July\r\n7-11, 2007. ACM 2007.\r\n[12] C.E. Nugraheni. Formal Verification of Parameterized Multi-agent Systems\r\nUsing Predicate Diagrams*. Proc. of COMPUTATION TOOLS\r\n2011: The Second International Conference on Computational Logics,\r\nAlgebras, Programming, Tools, and Benchmarking, Rome, 2011.\r\n[13] T. Taibi. Formal specification and validation of multi-agent behaviour\r\nusing TLA+ and TLC model checker. Int. J. Artificial Intelligence and\r\nSoft Computing, Vol. 1, No. 1, pp. 99-113, 2008.\r\n[14] T.-W. Yue & Z.-C. Lee, Sudoku Solver by Q´tron Neural Networks, Proc.\r\nof International Conference in Intelligent Computing 2006, ICIC2006,\r\nLNCS 4113, pp.943-952, 2006, Springer-Verlag, Berlin Heidelberg\r\n2006.<\/p>\r\n","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 80, 2013"}