Knight’s tour algorithm

Knight’s tour algorithm

• 1.
  Knight’s TourExplanation andAlgorithms
• 2.
  GROUP MEMBERSHassan Tariq(2008-EE-180)ZairHussainWani (2008-EE-178)
• 3.
  Introduction
• 4.
  What is ‘Knight’sTour’?Chess problem involving a knightStart on a random squareVisit each square exactly ONCE according to rulesTour called closed, if ending square is same as the starting
• 5.
  ConstraintsA closed knight’stour is always possible on an m x n chessboard, unless: m and n are both odd, but not 1 m is either 1, 2 or 4 m = 3, and n is either 4, 6 or 8
• 6.
  m and nare both odd, but not 1
• 7.
  Knight moves eitherfrom black square to white, or vice versaIn closed tour knight visits even squaresIf m and n are odd i.e. 3x3, total squares are odd so tour doesn`t exist
• 8.
  m = 1,2, or 4; m and n are not both 1
• 9.
  for m =1 or 2, knight will not be able to reach every squarefor m = 4, the alternate pattern of white and black square is not followed so tour not closed
• 10.
  m = 3;n = 4, 6, or 8
• 11.
  Have to beverified for each caseFor n > 8, existence of closed tours can be proved by induction
• 12.
  AlgorithmsNeural Network SolutionsWarnsdorff’sAlgorithm
• 13.
  Neural Network SolutionsEverymove represented by neuronEach neuron initialized to be active or inactive ( 1 or 0 )Each neuron having state function initialized to 0
• 14.
  Neural Network Solutions(contd.)Ut+1 (Ni,j) = Ut(Ni,j) +2 –  Vt(N)NG(Ni,j) 1 Ut+1(Ni,j) > 3Vt+1(Ni,j) = 0 Ut+1(Ni,j) < 0Vt(Ni,j) otherwise
• 15.
  Neural Network Solutions(contd.)The network ALWAYS convergeSolution: Closed knight’s tour
• 16.
  Series oftwo or more open toursWarnsdorff's AlgorithmHeuristic MethodEach move made to the square from which no. of subsequent moves is least
• 17.
  Warnsdorff's Algorithm (contd.)SetP to be a random initial position on the boardMark the board at P with the move number "1" For each move number from 2 to the number of squares on the board:Let S be the set of positions accessible from the input position
• 18.
  Set P tobe the position in S with minimum accessibility
• 19.
  Mark the boardat P with the current move numberReturn the marked board – each square will be marked with the move number on which it is visited.
• 20.
  ComparisonNeural networksWarnsdorff's AlgorithmComplex algorithm (a lot of variables to be monitored)Longer run-timeNOT always gives a complete tourSimple algorithmLinear run-timeAlways gives a CLOSED tour
• 21.
  ConclusionWARNSDORFF’S ALGORITHM ISBETTER