Transcript Can a knight visit all squares of a chessboard exactly once?

Can visit all squares
of a chessboard exactly
once ?
by Krishna Mahesh Deevela Murali
Overview
Problem Statement of Real World Problem
Basic Concepts
Formulating Graph Problem
Solution to Graph Problem and Real world Problem
Interesting Facts
Can visit all squares of a
chessboard exactly once ?
Our real world Problem is a very simple Question, it is to
find if a Knight can legally visit every square on a
Chessboard only once and Return to Starting position?
If Knight’s tour Exist ??
If Yes!! when does it happen??
If Not!!! Why??
Topic sounds Interesting rite… so lets not waste time and
jump into topic just like the Knight …
Solution to Graph Problem
Hamilton Circuit
A Hamiltonian cycle (or Hamiltonian circuit) is
a cycle in an undirected graph which visits each
vertex exactly once and also returns to the
starting vertex. E.g 0,1,2,3,0
•A
path visits each vertex of a graph once
and only once. E.g 0,1,2,3
Formulating Graph Problem
In a chessboard the vertices would represent the squares of the board
and the edges would represent a knight’s legal moves between squares
results in a graph as shown below, Known as Knight’s graph.
Highlights :
Every Vertex represents
square on chessboard.
Every edge is one legal move
of a Knight.
Special Properties of Knight’s Graph
MxN chessboard has MN vertices. i.e Number of
Squares equal to Vertices.
Graph is Undirected.
Edges of equal length, i.e one legal Knight Move.
Knight’s Move is Symmetric. A to B is equal to B to A.
Every move of knight Alternates between black
and white. i.e move from white square will always
result in an ending position on a black square and
vice-versa
Solution to Graph Problem
The Knight’s Tour is a well-known classic problem. The objective
is to move a knight, starting from any square on a chessboard, to
every other square once. Note that the knight makes only L-shaped
moves (two spaces in one direction and one space in a
perpendicular direction).
If we observe the Knight's Tour problem turns out to be an
instance of the more general Hamiltonian path problem in graph
theory.
The problem of getting a closed Knight's Tour is similarly an
instance of the Hamiltonian cycle problem.
Solution to Graph Problem
We have 2 types of solutions, Hamiltonian Path when
Knight starts at a vertex and doesn't end at the same vertex,
Open Knight tour.
Hamiltonian Cycle where starting vertex and final vertex is
the same, thus resulting a Cycle, Closed tour.
The Solution to both Closed and Open tour are same just
that start and final vertices are going to same and different
correspondingly.
Algorithm:
We can use simple algorithm to find if Knights tour Exists on the
given board or not.
M x N be size of board i.e mn number of squares.
Total number of moves would be A=m*n-1.
Visited be a two dimentional array [M][N] initialized to false, when
Knight visits this square it is set to
true.
I be integer between 0 & A representing the number of moves,
intialially it is 0, and if knight completes the Path it is A.
After Completeting the path if the one of next possible move
results to initial position, it is a Closed tour, else it is Open Tour.
Algorithm move(x,y,i)
1.
if( (x < 0) OR (x ≥ M) OR (y < 0) OR (y ≥ N) )return false
2.
if( visited[x, y] = true ) return false
3.
if( m = M ) print “A solution has been found”
•
•
•
print “ x, y ” //This starts printing the solution
set visited[x, y] = true
return true
else //This is a valid move, but a tour has not been completed.
•
•
•
•
•
•
•
•
set result = false OR Move( x+2, y+1, m+1)
set result = false OR Move( x+2, y-1, m+1)
set result = false OR Move( x-2, y+1, m+1)
set result = false OR Move( x-2, y-1, m+1)
set result = false OR Move( x+1, y+2, m+1)
set result = false OR Move( x+1, y-2, m+1)
set result = false OR Move( x-1, y+2, m+1)
set result = false OR Move( x-1, y-2, m+1)
Algorithm move(x,y,i) contd..
4. if( result = true ) //One of the 8 moves above led to a completed tour.
•
•
print “ x, y ”
return true
5. Else //None of the moves from this position led to a successful tour.
//Now we must backtrack and try a different path
•
•
set visited[x, y] = false //Unvisit this location
return false
Hence our Real World Problem is Solved..
Using Knights Graph and Basic Graph
Theory.
The Closed Knight’s Tour
The Open Knight’s Tour where start and final vertex are different
Are you finding it hard to believe this would even work... Then take a live look.
http://commons.wikimedia.org/wiki/File:Knight%27s_tour_anim_2.gif#medi
aviewer/File:Knight%27s_tour_anim_2.gif
http://upload.wikimedia.org/wikipedia/commons/1/1e/Turk-knightstour_anim.svg
How many closed knight’s tours are there on an 8 × 8
board?
1 ?? 100 ??
10000??
No No No… it is biggerrrrrr
26,534,728,821,064
If we have to find all the closed paths every
human has to find 3500 diff paths
Population of world 7 billion but no of paths are
26 trillion
How many open knight’s tours are there on an 8 × 8
board?
19,591,828,170,979,904
19 Quadrillion
When does this Closed Knight’s Tour occur
In 1991, Allen Schwenk completely determined which
rectangular chessboards have a closed knight’s tour.
An m × n chessboard with m <= n has a closed knight’s tour
unless one or more of the following three conditions hold:
(a) m and n are both odd;
(b) m = 1, 2 or 4 ;
(c) m = 3 and n = 4, 6 or 8.
(explaination is not given due to
complexity and time for condition c)
Condition (a): m and n are both
odd.
Recall that a legal move for a knight whose
initial position is a white square will always
result in an ending position on a black square
and vice-versa.
Hence, every tour representing the legal moves
of a knight alternates between black and white
squares.
Condition (a): m and n are both odd.
Suppose m and n are both odd.
There will exist an odd number of squares on the
board.
The number of black squares will not equal the
number of white squares.
No closed tour can exist.
Condition (b): m = 1, 2 or 4.
Suppose m = 1
K
Suppose m = 2
K
Condition (b): m = 1, 2 or 4.
For 4 × n boards we require a more complex coloring of
the board than the traditional black and white
coloring.
Condition (b): m = 1, 2 or 4.
Note that a knight must move from a brown square
to a black square. Likewise, a knight must move from
a white square to a green square. Two closed cycles
are now forced to exist and no closed tour exists for
the 4×n board.
Solomon Golomb
Double and single loop in
4x5 board
Double loop in 4x8 board
Closed tours of few Boards
18x18 board
5x6
8x3
10x3
6x6
30x30
7x6
7x8
5x8
8x6
12x3
60x60 board
Semi Magic Squares
First semi-magic knight’s tour
In each quadrant,
the sum of the
numbers equals
520 and each of
the
rows and columns
adds to 130
The sum of the numbers in each 2x2
section is 130
Even after so many number patterns it is called
semi magic because the diagonals did not also add
to 260.
Total of 140 semi magic knight’s tours are
found. But not even a single fully magic
knight’s tour in 8x8 is possible
Knight’s tours and cryptography
A cryptotour is a puzzle in which the 64 words or syllables of a verse are
printed on the squares of a chessboard and are to be read in the sequence of
a knight’s tour.
Knight’s tours and 3-D patterns
Four polygons formed by 16 knight moves and their tessellation of the plane
Knight’s tour
tessellations can
even be used to
create beautiful 3-D
patterns such as
astersphaira
hexastersphaira
References..
Jelliss, George. ”Introducing Knight’s Tours.”
http://homepages.stayfree.co.uk/gpj/ktn.htm
“Knight’s Tours”- Ben Hill, Kevin Tostado
“Closed Knight Tour on Rectangular Boards”sciencedirect.com
A. J. Schwenk, Which Rectangular Chessboards have a
Knight.s Tour? Mathematics Magazine
Any Questions
Thankyou..