Artificial Bee Colony Algorithm for Solving the Knight's Tour Problem


Banharnsakun A.

1st International Conference on Intelligent Computing and Optimization (ICO), Pattaya, Thailand, 4 - 05 October 2018, vol.866, pp.129-138 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 866
  • Doi Number: 10.1007/978-3-030-00979-3_13
  • City: Pattaya
  • Country: Thailand
  • Page Numbers: pp.129-138

Abstract

The knight's tour problem is one of the most interesting classic chessboard puzzles, in which the objective is to construct a sequence of admissible moves made by a chess knight from square to square in such a way that it lands upon every square of a chessboard exactly once. In this work, we consider the knight's tour problem as an optimization problem and propose the artificial bee colony (ABC) algorithm, one of the most popular biologically inspired methods, as an alternative approach to its solution. In other words, we aim to present an algorithm for finding the longest possible sequence of moves of a chess knight based on solutions generated by the ABC method. Experimental results obtained by our method demonstrate that the proposed approach works well for constructing a sequence of admissible moves of a chess knight and outperforms other existing algorithms.