Knight Tour Problem And Its Graph Analysis

Knight’s Tour Problem and its GraphAnalysisDeepak KumarKent State University

In this Presentation: Knight’s Tour and its Problem discussionBuilding Knight’s GraphAnalysis on Knight GraphSpecial Properties of the Knight Graph

Knight Tour Problem The knight is placed on any block of an empty board and is moveaccording to the rules of chess, must visit each square exactly once. If the knight ends on a square that is one knight's move from thebeginning square, the tour is closed otherwise it is open tour. It is alsocalled as Hamiltonian path. A cycle that uses each graph vertex of a graph exactly once is called aHamiltonian cycle Knight's tour can be defined on any grid pattern.

There are few questions we can ask:1. Is it possible for a knight to start on some square and, by a seriesof valid knight moves, visit each square on an 8 8 chessboard orany other grid once?2. Is the graph will be connected? Can I start my knight at a vertexand get to any vertex by only making valid knight’s moves?3. What is the degree of each vertex?4. How many colors does it take to color this graph such that no twovertices of the same color are connected by an edge?

Open and Closed Tour

Building Knight Graph Each square on the chessboard can be represented as a node in thegraph. Each legal move by the knight can be represented as an edge in thegraph. Legal move is shift one square along one axis and two square alongthe other axis

For a n*m knight's tour graph the total number of vertices issimply n*m. For a n*n knight's tour graph the total number of vertices issimply n2 and the total number of edges is 4(n-2)(n-1). Knight's tour path exists on an n*n board if n 5

Bipartite Graph A bipartite is a graph whose vertices can be divided into twodisjoint sets U and V (that is, U and V are each independent sets)such that every edge connects a vertex in U to one in V. The two sets U and V may be thought of as a coloring of the graphwith two colors: if one colors all nodes in U blue, and all nodes in Vgreen, each edge has endpoints of differing colors. All acyclic graph is bipartite, and a cyclic graph is bipartite if all itscycles are of even length. A graph is bipartite if and only if it does not contain an odd cycle. if it is 2-colorable.

.Special Properties of Knight Graph Knight Graph are bipartite graph. In Knight graph, no two graph vertices within the same set areadjacent. A knight move always alternates between white and black squares. Knight graph are equivalent to two-colorable graph. Its chromaticnumber is 2.

Knight graph is a special case of k-partite graph with k 2. Knight graph are perfect Graph. A perfect graph is a graph G such that for every induced subgraphof G, the clique number equals the chromatic number, i.e.,w(G) c(G).For Knight graph, w(G) c(G) 2.

A Knight graph is perfect as neither the graph G nor itsgraph complement has a chord less cycle of odd order. The perfect graph theorem states that the graphcomplement of a perfect graph is itself perfect. A Knightgraph is therefore perfect as its complement is alsoperfect. Degree of each vertex in Knight graph is 2. It is also calledas regular bipartite graph as degree is same for everyvertex. In general, every bipartite graph is perfect. Every tree is a bipartite graph.

Solution Approach Brute forceNeural networksDepth first search with backtracking:- Knight moves to a square thathas the lowest number of next moves available. The idea is that atthe end of the tour it will visit squares that have more move choicesavailable.Ant colony optimization:- ACO has a good capability of finding bettertour path, which not only uses the feedback principle to quickenevolution process of colonies but also is an essential parallelalgorithm.The Knight’s tour problem can be solved in linear time.

Questions?

Knight Tour Problem The knight is placed on any block of an empty board and is move according to the rules of chess, must visit each square exactly once. If the knight ends on a square that is one knight's move from the beginning square, the tour is closed otherwis