SOLVING A NUMBER PLACEMENT GAME USING RECURSIVE BACKTRACKING ALGORITHM ON THE GRAPH MODEL

Year 2014, Volume: 1 , 286 - 291, 01.09.2014

Sema Bodur Sevcan Emek

Abstract

: In this study, a
number placement game has been developed. This application is designed on a
graph model. Recursive backtracking algorithm was used in the solution of this
game. Numbers on a board of nxn will
be placed in a certain order under specified rules in finite time. With
backtracking algorithm based on depth first recursive search method, finite
number of possible solutions has been revealed. In this application that was
inspired by 8-Queen problem, Knight’s Tour, coloring a map, Knapsack problem
and other search problems, advantages and disadvantages of this method have
been discussed. The larger the board size, the much more the number of
placement complexity. In further studies, the solution of this problem can be
possible with the use of heuristic or informative search techniques. 

Keywords

Backtracking, graph, depth-first search algorithm

References

• Gordon, V. S., & Slocum, T. J. (2004). The Knight’s Tour- Evolutionary vs. Depth-First Search, IEEE Tounsi, M., CS 311 Design and Algorithm Analysis Course: info.psu.edu.sa/psu/cis/mtounsi/~CS311/Chap-BKT-BB.pp Dündar, P. &Balcı, A.M. &Kılıç, E. (2011). Mathematical Modelling of Placement of Emergency Phone Centres in a Campus Network.DEÜ Mühendislik Fakültesi Mühendislik Bilimleri Dergisi, Sayı 13,Cilt 1 Retrieved April 29, 2014 fromtheWikipedia :http://en.wikipedia.org/wiki/Depth-first_search Problem Solving with Algorithms and Data Structures : http://interactivepython.org/runestone/static/pythonds/Graphs/graphdfs.html Retrieved April 29, 2014 fromhttp://www.academic.marist.edu/~jzbv/algorithms/Backtracking.htm