Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Backtracking — Knight’s Tour Problem

Objec­tive : A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is one knight’s move from the begin­ning square (so that it could tour the board again imme­di­ately, fol­low­ing the same path), the tour is closed, oth­er­wise it is open. (Source : http://en.wikipedia.org/wiki/Knight%27s_tour)

Exam­ple:

Path-follwed-by-Knight-to-cover-all-the-cells

Path-foll0wed-by-Knight-to-cover-all-the-cells

Approach:

  • Cre­ate a solu­tion matrix of the same struc­ture as chessboard.
  • Start from 0,0 and index = 0. (index will rep­re­sent the no of cells has been cov­ered by the knight)
  • Check cur­rent cell is not already used if not then mark that cell (start with 0 and keep incre­ment­ing it, it will show us the path for the knight).
  • Check if index = N*N-1, means Knight has cov­ered all the cells. return true and print the solu­tion matrix.
    • Now try to solve rest of the prob­lem recur­sively by mak­ing index +1. Check all 8 direc­tions. (Knight can move to 8 cells from its cur­rent posi­tion.) Check the bound­ary con­di­tions as well
    • 8-moves-of-a-Knight

      8-moves-of-a-Knight

    • If none of the 8 recur­sive calls return true, BACKTRACK and undo the changes ( put 0 to cor­re­spond­ing cell in solu­tion matrix) and return false.
  • See the code for bet­ter understanding.

 

Code:

Output:
   00   59   38   33   30   17   08   63
   37   34   31   60   09   62   29   16
   58   01   36   39   32   27   18   07
   35   48   41   26   61   10   15   28
   42   57   02   49   40   23   06   19
   47   50   45   54   25   20   11   14
   56   43   52   03   22   13   24   05
   51   46   55   44   53   04   21   12

You may also like...

  • Jo Smith

    The solu­tion pre­sented works quickly (mil­lisec­onds). How­ever, note that choice of order­ing of the pos­si­ble moves affects how quickly the result comes back.

    For exam­ple, this alter­na­tive order­ing of moves doesn’t seem to ever return a result:

    // go left and up
    if (canMove(row — 1, col­umn — 2, N)
    && findPath(row — 1, col­umn — 2, index + 1, N)) {
    return true;
    }
    // go left and down
    if (canMove(row + 1, col­umn — 2, N)
    && findPath(row + 1, col­umn — 2, index + 1, N)) {
    return true;
    }
    // go right and up
    if (canMove(row — 1, col­umn + 2, N)
    && findPath(row — 1, col­umn + 2, index + 1, N)) {
    return true;
    }
    // go down and right
    if (canMove(row + 2, col­umn + 1, N)
    && findPath(row + 2, col­umn + 1, index + 1, N)) {
    return true;
    }
    // go up and left
    if (canMove(row — 2, col­umn — 1, N)
    && findPath(row — 2, col­umn — 1, index + 1, N)) {
    return true;
    }
    // go down and left
    if (canMove(row + 2, col­umn — 1, N)
    && findPath(row + 2, col­umn — 1, index + 1, N)) {
    return true;
    }
    // go right and down
    if (canMove(row + 1, col­umn + 2, N)
    && findPath(row + 1, col­umn + 2, index + 1, N)) {
    return true;
    }
    // go up and right
    if (canMove(row — 2, col­umn + 1, N)
    && findPath(row — 2, col­umn + 1, index + 1, N)) {
    return true;
    }

    • Rox­ana Sarbu

      What is the expla­na­tion for this , because , the­o­ret­i­cally , it should “enter ” in one of the cases above;
      It depends on the start point also?
      Thanks!

  • Hore Hores

    I noticed that if you changed the ini­tial start­ing point in this code, the result gets a lit­tle weird. The 00 spot is some­where ran­dom, and not con­nected with 01. Any thoughts?