AlgorithmVisualizer/algorithm/backtracking/knight's_tour/basic/code.js at master · pythonpeixun/AlgorithmVisualizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
function knightTour(x, y, moveNum) {
	if (moveNum === N*N) {
		return true;
	}

	for (var i = 0; i < 8; i++) {
		var nextX = x + X[i];
		var nextY = y + Y[i];

		posTracer._notify ( 0, nextX)._wait ();
		posTracer._notify ( 1, nextY)._wait ();
		posTracer._denotify (0);
		posTracer._denotify (1);
		/*
		Check if knight is still in the board
		Check that knight does not visit an already visited square
		*/
		if (nextX>=0 && nextX<N && nextY>=0 && nextY<N && board[nextX][nextY]===-1) {
			board[nextX][nextY] = moveNum;

			logTracer._print ('Move to ' + nextX + ',' + nextY);
			boardTracer._notify ( nextX, nextY, moveNum)._wait();
			boardTracer._denotify( nextX, nextY);
			boardTracer._select ( nextX, nextY);

			var nextMoveNum = moveNum + 1;
			if ( knightTour (nextX,nextY, nextMoveNum) === true) {
				return true;
			} else {
				logTracer._print ('No place to move from ' + nextX + ',' +nextY + ': Backtrack');
				board[nextX][nextY] = -1; // backtrack
				boardTracer._notify ( nextX, nextY, -1)._wait();
				boardTracer._denotify( nextX, nextY);
				boardTracer._deselect( nextX, nextY);
			}
		} else {
			logTracer._print (nextX + ',' + nextY + ' is not a valid move');
		}
	}
	return false;
}

board[0][0] = 0; // start from this position
pos[0] = 0;
pos[0] = 0;

boardTracer._notify ( 0, 0, 0)._wait();
posTracer._notify ( 0, 0)._wait ();
posTracer._notify ( 1, 0)._wait ();
boardTracer._denotify( 0, 0);
boardTracer._denotify( 0, 0);
posTracer._denotify (0);
posTracer._denotify (1);

if (knightTour ( 0, 0, 1) === false ) {
	logTracer._print ('Solution does not exist');
} else {
	logTracer._print ('Solution found');
}