Solving Knight's Tour with Backtracking (javascript)

Question

I am trying to write an algorithm in javascript to solve the Knight's Tour problem using Backtracking, but it doesn't work. Basically, the function is supposed to output an array called visited, which contains the locations of each moves. However, no location is appended to the array, which remains as [[0,0]]. Here is my code. Any clue?

var unit = 75;

function m1(position) { position[0] += unit; position[1] += 2*unit; return [position[0],position[1]]}
function m2(position) { position[0] -= unit; position[1] += 2*unit; return [position[0],position[1]]}
function m3(position) { position[0] += 2*unit; position[1] += unit; return [position[0],position[1]]}
function m4(position) { position[0] -= 2*unit; position[1] += unit; return [position[0],position[1]]}
function m5(position) { position[0] += unit; position[1] -= 2*unit; return [position[0],position[1]]}
function m6(position) { position[0] -= unit; position[1] -= 2*unit; return [position[0],position[1]]}
function m7(position) { position[0] += 2*unit; position[1] -= unit; return [position[0],position[1]]}
function m8(position) { position[0] -= 2*unit; position[1] -= unit; return [position[0],position[1]]}

var moves = [m1, m2, m3, m4, m5, m6, m7, m8];   
var currentPosition = [0, 0];
var visited = [currentPosition];

function knightour(currentPosition)
{

    var j; 

    if (promising(currentPosition))
    {

        if (visited.length == 64)
        {
            return visited;
        } 
        else 
        {
            for (j=0; j<moves.length; j++)
            {
                context.drawImage(knight, currentPosition[0], currentPosition[1]);
                alert("NEXT");
                visited.push(moves[j](currentPosition));
                knightour(currentPosition);
            }
        }
    } 
}  

function promising(currentPosition)
{
    if (currentPosition[0] < 600 && currentPosition[0] >= 0 &&
        currentPosition[1] < 600 && currentPosition[1] >= 0 &&
        isVisited(currentPosition, visited))
        {
        return true;
    } else {
        return false;
    }

} 

function isVisited(position, visited)               // visited is an array of size n of array of size 2 ([x,y])
{                                                       // currentPosition is an array of size 2 ([x,y])
    for (var i=0; i<visited.length; i++)
    {
        if (position[0] == visited[i][0] && position[1] == visited[i][1])
        {
            return true;
        }
    }
    return false;

}

Thank you.

Hi Aeon, Welcome to Stack Overflow? May I ask if this is homework? — , Jun 26 '11 at 21:54
Hi, thank you. Yes. this is an extra credit homework assignment. — ratsimihah, Jun 26 '11 at 22:03
Your functions isVisited and promising aren't returning false if they fail. — Ravan Scafi, Jun 26 '11 at 22:08
Now your isVisited only checks first position. Return false must be out of your `for()`. Pay attention. — Ravan Scafi, Jun 26 '11 at 22:13
That's true, thank you. I edited my post. I think the problem is in the knightour function. Because what it does is just executing each movies in order, from m1 to m8. You can see it at http://knightstourhr.appspot.com - I am pretty new to backtracking, and so the concept isn't quite clear yet. — ratsimihah, Jun 26 '11 at 22:14
Indeed, I got a different result by using push instead. Now, instead of executing the 8 moves in order, it executes the first move 3 times, and then runs into a infinite loop executing the 3rd move. (sample at http://knightstourhr.appspot.com/) It looks more like backtracking, but there's definitely something wrong. — ratsimihah, Jun 26 '11 at 22:29

score 3 · Accepted Answer · answered Jun 29 '11 at 02:47

You've got to step back: you haven't even got the backtracking algorithm sorted out and you're already conflating the board you display with the board the algorithm requires. Best bet is to start over, solve the algorithm, and then worry about the display of it all. With that thought, you should solve the algorithm with pseudocode first, and then translate that pseudocode to JavaScript. (Hint: in your code, you never seem to change the current position.)

I see the overall process like this:

findAllKnightsTours:
  for every board position
    set path = empty
    set board = all false
    findKnightsTour(currentPosition, path, board)

Having the path as a stack is great. Searching through it every time to see if a square has been visited is a pain, so I'd use a separate "board". The board should be a matrix of boolean values (false==not visited, true=visited) although for simplicity I would use a simple array.

findKnightsTour(position, path, board):
  push position onto path
  set board[position] to true

  if path.length == 64
    print out path
  else
    for each of the eight moves
      next = calculate new position based on move
      if validPosition(next, board)
        findKnightsTour(next, path, board)

  set board[position] to false
  pop position off path

The validPosition routine checks to see if the position is within the board limits and is not currently visited (that is, true).

If you look at this routine, you'll see that it adds the current position to the path and to the board, does stuff, and then removes it from the path and board. This is the backtracking part of the algorithm: save some state, try something, and then restore the old state.

I leave the JavaScript conversion as an easy exercise for the Reader.

Solving Knight's Tour with Backtracking (javascript)

1 Answers1