An Ant Algorithm for the Sudoku Problem

• Autorzy: Schiff K.

Identyfikatory

DOI

10.14313/JAMRIS_2-2015/14

• Języki publikacji: EN

Abstrakty

EN

In this paper an ant algorithm for the Sudoku problem is presented. This is the first ant algorithm enabling discovery of an optimal solution to the Sudoku puzzle for 100% of investigated cases. The Sudoku is a one of many combinatorial optimisation problems, as well as an NPcomplete problem, hence an ant algorithm which constructs an optimal solution as a meta-heuristic method is important for this problem.

Słowa kluczowe

EN

swarm optimization; Sudoku puzzle

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2015
• Tom: Vol. 9, No. 2
• Strony: 24--27
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology, ul. Warszawska 24, 31-155 Kraków, Poland

Bibliografia

• [1] Boryczko U., Juszczuk P., “Solving The Sudoku With Differential evolution”, Zeszyty Naukowe Politechniki Białostockiej. Informatyka, no. 9, 2012, 5–16.
• [2] Gold M., Using Genetic Algorithms to come up with Sudoku Puzzles, 2005.
• [3] Kaur A., Goyal S.,Survey on the Applications of Bee Colony Optimization Techniques. International Journal on Computer Science and Engineering (IJCSE), 3, 8, 2011, 3037-3046.
• [4] Lawler E. and Rinnooy K.A. (1985) The Traveling Salesman Problem: A guided Tour of Combinatorial Optimization.
• [5] Lewis R. (2009) Metaheuristics can solve Sudoku puzzles. Journal of Heuristics,13, 387-401.
• [6] Lynce I. and Ouaknine J. (2006) Sudoku as a SAT Problem, Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics.
• [7] Mantere T. and Koljonen J. (2007) Solving, Rating and Generating Sudoku Puzzles with GA IEEE Congress on Evolutionary Computation, 1382-1389.
• [8] McGerty S. (2009) Solving Sudoku Puzzles with Particle Swarm Optimization – Final Report, Macquarie University.
• [9] Moraglio A. et al. (2007) Geometrical Particle Swarm Optimization – Research Article, Journal of Artificial Evolution and Applications, 2008.
• [10] Moraglio A. and Togelius J. (2009) Geometrical differential evolution, GECCO 2009, Genetic and Evolutionary Computation Conference, 1705-1712.
• [11] Mullaney D., Using Ant Systems to solve Sudoku Problems, University College Dublin, 2009.
• [12] Pacurib, J. A. et al. (2009) Solving Sudoku Puzzles using Improved Artificial Bee Colony Algorithm. In: Proc. 4th Int. Conf. Innovative Computing, Information and Control, 885-888.
• [13] Pillay N. (2012) Finding Solutions to Sudoku Puzzles Using Human Intuitive Heuristics, Research Article — SACJ, 49, 25-34.
• [14] Weber T. (2005) A SAT-based Sudoku solver, 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2005, 11-15.
• [15] Yato T. (2003) Complexity and Completeness of Finding Another Solution and Application to Puzzles, IEICE – Transactions on Fundamentals of Electronic Communications and Computer Science, 5, 1052-1060.