knights-tour-visualization
knights-tour-visualization copied to clipboard
An online Knight's tour visualizer using divide and conquer algorithm
Knight's Tour Visualization
An online Knight's tour visualizer using divide and conquer algorithm
This project uses Emscripten to compile C code into JavaScript.
For an online version, see https://sgalal.github.io/knights-tour-visualization/.
Project Structure
- Source files:
src
- For test:
test
- For web pages:
index.html
,index.js
,index.css
Build
- Prerequisite: Emscripten
-
Build:
emcc -std=c11 -Weverything -Werror -Wno-unused-function -Wno-language-extension-token -O2 -s ASSERTIONS=1 -s EXPORTED_FUNCTIONS='["_getNextPointSerialize"]' -s EXTRA_EXPORTED_RUNTIME_METHODS='["ccall","cwrap"]' -o tour.js src/tour.c
-
Test:
clang -std=c11 -Weverything -Werror -Wno-language-extension-token -DDEBUG -o tour src/tour.c test/tour_tb.c && ./tour
Implementation
Algorithm
The code is an implementation of Parberry, Ian. "An efficient algorithm for the Knight's tour problem." Discrete Applied Mathematics 73.3(1997):251-260.
A knight’s tour is called closed if the last square visited is also reachable from the first square by a knight’s move.
A knight’s tour is said to be structured if it includes the knight’s moves shown in Fig. 1.
An n * n chessboard has a closed knight's tour iff n ≥ 6 is even.
For board size of 6 * 6, 6 * 8, 8 * 8, 8 * 10, 10 * 10, and 10 * 12, we have already found structured, closed knight’s tours, which are shown in Fig. 2.
This means the problem is already solved when n ∈ {6, 8, 10}.
For larger n, divide the chess board into parts to meet the sizes above. For instance, a board with n = 42 can be divided as follows:
Then connect the parts together. Since all the parts are structured, we can combine them by substitute the directions on the corners:
Data Structure
Since every point is connected with other two points, and there are only 8 possible directions (from 0 to 7):
The 6 pre-defined tours are stored in 2-dimensional arrays.
There are 8 types of corners (as were shown in Fig. 3.), which are denoted by 0-7, is recorded in point attribute. Besides, the point attribute of ordinary points is 8.