Skip to content

sgalal/knights-tour-visualization

Repository files navigation

Knight's Tour Visualization

Build status Maintainability

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/.

Knight's Tour on a 14*14 board

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.

Fig. 1. Required moves for a structured knight's tour.

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.

Fig. 2. Structured knight’s tours for (in row-major order) 6 x 6, 6 x 8, 8 x 8, 8 x 10, 10 x 10, and 10 x 12 boards.

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:

Divide example

Then connect the parts together. Since all the parts are structured, we can combine them by substitute the directions on the corners:

Fig. 3. How to combine four structured knight’s tours into one.

Data Structure

Since every point is connected with other two points, and there are only 8 possible directions (from 0 to 7):

8 directions

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.