GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Merge pull request #201 from archie94/knight-tour · hhy5277/AlgorithmVisualizer@17b0a94

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • backtracking/knight's_tour
      • basic
        • code.js
        • data.js
      • desc.json
    • category.json
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/backtracking/knight's_tour/basic/code.js‎

Copy file name to clipboard
+59Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
function knightTour(x, y, moveNum) {
2+
if (moveNum === N*N) {
3+
return true;
4+
}
5+
6+
for (var i = 0; i < 8; i++) {
7+
var nextX = x + X[i];
8+
var nextY = y + Y[i];
9+
10+
posTracer._notify ( 0, nextX)._wait ();
11+
posTracer._notify ( 1, nextY)._wait ();
12+
posTracer._denotify (0);
13+
posTracer._denotify (1);
14+
/*
15+
Check if knight is still in the board
16+
Check that knight does not visit an already visited square
17+
*/
18+
if (nextX>=0 && nextX<N && nextY>=0 && nextY<N && board[nextX][nextY]===-1) {
19+
board[nextX][nextY] = moveNum;
20+
21+
logTracer._print ('Move to ' + nextX + ',' + nextY);
22+
boardTracer._notify ( nextX, nextY, moveNum)._wait();
23+
boardTracer._denotify( nextX, nextY);
24+
boardTracer._select ( nextX, nextY);
25+
26+
var nextMoveNum = moveNum + 1;
27+
if ( knightTour (nextX,nextY, nextMoveNum) === true) {
28+
return true;
29+
} else {
30+
logTracer._print ('No place to move from ' + nextX + ',' +nextY + ': Backtrack');
31+
board[nextX][nextY] = -1; // backtrack
32+
boardTracer._notify ( nextX, nextY, -1)._wait();
33+
boardTracer._denotify( nextX, nextY);
34+
boardTracer._deselect( nextX, nextY);
35+
}
36+
} else {
37+
logTracer._print (nextX + ',' + nextY + ' is not a valid move');
38+
}
39+
}
40+
return false;
41+
}
42+
43+
board[0][0] = 0; // start from this position
44+
pos[0] = 0;
45+
pos[0] = 0;
46+
47+
boardTracer._notify ( 0, 0, 0)._wait();
48+
posTracer._notify ( 0, 0)._wait ();
49+
posTracer._notify ( 1, 0)._wait ();
50+
boardTracer._denotify( 0, 0);
51+
boardTracer._denotify( 0, 0);
52+
posTracer._denotify (0);
53+
posTracer._denotify (1);
54+
55+
if (knightTour ( 0, 0, 1) === false ) {
56+
logTracer._print ('Solution does not exist');
57+
} else {
58+
logTracer._print ('Solution found');
59+
}
Collapse file

‎algorithm/backtracking/knight's_tour/basic/data.js‎

Copy file name to clipboard
+29Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*
2+
For N>3 the time taken by this algorithm is sufficiently high
3+
Also it is not possible to visualise for N>6 due to stack overflow
4+
caused by large number of recursive calls
5+
*/
6+
var N = 3;
7+
var board = new Array (N);
8+
for (var i = board.length - 1; i >= 0; i--) {
9+
board[i] = new Array (N);
10+
}
11+
12+
for (var i = board.length - 1; i >= 0; i--) {
13+
for (var j = board[i].length - 1; j >= 0; j--) {
14+
board[i][j] = -1;
15+
}
16+
}
17+
18+
/*
19+
Define the next move of the knight
20+
*/
21+
var X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
22+
var Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
23+
24+
var pos = new Array (2);
25+
pos[0] = pos[1] = -1;
26+
27+
var boardTracer = new Array2DTracer ('Board')._setData (board);
28+
var posTracer = new Array1DTracer ('Knight Position')._setData (pos);
29+
var logTracer = new LogTracer ('Console');
Collapse file

‎algorithm/backtracking/knight's_tour/desc.json‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Knight’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.",
3+
"Complexity": {
4+
"time": "Worst O(8<sup>N<sup>2</sup></sup>)",
5+
"space": "Worst O(N<sup>2</sup>)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Knight%27s_tour'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Solving the Knight’s tour problem using Backtracking & Recursion"
12+
}
13+
}
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
{
22
"backtracking": {
33
"list": {
4+
"knight's_tour": "Knight’s tour problem",
45
"n_queens": "N Queens Problem"
56
},
67
"name": "Backtracking"

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.