Implemented Knight's Tour:Backtracking method

archie94 · archie94 · commit 9b458d82aed9 · 2016-07-03T09:34:45.000+05:30
diff --git a/algorithm/backtracking/knight's_tour/basic/code.js b/algorithm/backtracking/knight's_tour/basic/code.js
@@ -0,0 +1,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');
+}
diff --git a/algorithm/backtracking/knight's_tour/basic/data.js b/algorithm/backtracking/knight's_tour/basic/data.js
@@ -0,0 +1,29 @@
+/*
+For N>3 the time taken by this algorithm is sufficiently high
+Also it is not possible to visualise for N>6 due to stack overflow 
+caused by large number of recursive calls
+*/
+var N = 3;
+var board = new Array (N);
+for (var i = board.length - 1; i >= 0; i--) {
+	board[i] = new Array (N);
+}
+
+for (var i = board.length - 1; i >= 0; i--) {
+	for (var j = board[i].length - 1; j >= 0; j--) {
+		board[i][j] = -1;
+	}
+}
+
+/*
+Define the next move of the knight
+*/
+var X = [ 2, 1, -1, -2, -2, -1,  1,  2 ];
+var Y = [ 1, 2,  2,  1, -1, -2, -2, -1 ];
+
+var pos = new Array (2);
+pos[0] = pos[1] = -1;
+
+var boardTracer = new Array2DTracer ('Board')._setData (board);
+var posTracer = new Array1DTracer ('Knight Position')._setData (pos);
+var logTracer = new LogTracer ('Console');
diff --git a/algorithm/backtracking/knight's_tour/desc.json b/algorithm/backtracking/knight's_tour/desc.json
@@ -0,0 +1,13 @@
+{
+  "Knight&rsquo;s tour problem": "A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.",
+  "Complexity": {
+    "time": "Worst O(8<sup>N<sup>2</sup></sup>)",
+    "space": "Worst O(N<sup>2</sup>)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Knight%27s_tour'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Solving the Knight&rsquo;s tour problem using Backtracking & Recursion"
+  }
+}
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -1,6 +1,7 @@
 {
    "backtracking": {
       "list": {
+         "knight's_tour": "Knight&rsquo;s tour problem",
          "n_queens": "N Queens Problem"
       },
       "name": "Backtracking"

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,7 @@`
`1`	`1`	`{`
`2`	`2`	`"backtracking": {`
`3`	`3`	`"list": {`
	`4`	`+ "knight's_tour": "Knight’s tour problem",`
`4`	`5`	`"n_queens": "N Queens Problem"`
`5`	`6`	`},`
`6`	`7`	`"name": "Backtracking"`