#### Bentley

##### Member

**GM Version**: GM2

**Links:**https://www.dropbox.com/s/j5q1972edqneu16/Knight's Tour Gif.gif?dl=0

__:__

**Summary**The Knight's Tour is a Chess problem where you try to move the knight to every square on the Chessboard without revisiting a square. The Warnsdorf algorithm makes this complex problem simple. In this tutorial we will code an animated version of the algorithm. Click the link above to see it run.

A finished Knight's Tour showing the path of the knight.

Algorithm

1. Mark the knight's square

*visited.*

2. Look at all the valid squares the knight can move to. A valid square is both on the board and unvisited. Give each of those potential squares a score. That score is equal to how many

*valid*moves a knight could make

*from the potential square.*

3. Move the knight to the square with the smallest score (ties between scores are ok, just pick one of the lowest).

4. Repeat 1-3.

__:__

**Tutorial**[Create Event]

GML:

```
#macro COLS 8
#macro ROWS 8
#macro CELL_SIZE (room_width div COLS)
#macro c_light make_color_rgb(241, 194, 125)
#macro c_dark make_color_rgb(141, 85, 36)
// move_x/y are synced arrays storing the 8 moves the knight can make
move_x = [1, 2, 2, 1, -1, -2, -2, -1];
move_y = [-2, -1, 1, 2, 2, 1, -1, -2];
// This 2D array is initialized to 0 and has two purposes:
// Boolean checks for unvisited squares and for numbering the Knight's path through the board (from 1 to 64).
for (var i = 0; i < COLS; i++)
{
for (var j = 0; j < ROWS; j++)
{
visited[i, j] = 0;
}
}
// Save the knight's position
knight_x = irandom(COLS - 1);
knight_y = irandom(ROWS - 1);
// Make the square the knight starts on a part of the tour by setting it to 1
visited[knight_x, knight_y] = 1;
// Count the moves made
moves_made = 1;
```

GML:

```
// Run the algorithm each step until 64 moves are made
if (moves_made < 64)
{
// Find the square with the least score
var least = infinity;
var least_x = -1;
var least_y = -1;
// Loop through the moves
for (var i = 0; i < 8; i++)
{
var check_x = knight_x + move_x[i];
var check_y = knight_y + move_y[i];
// A square is valid if it's on the board and unvisited
if (is_valid(check_x, check_y))
{
// Get the square's score and if it's the smallest...
var _score = score_from_square(check_x, check_y);
if (_score < least)
{
// Save the square's (x,y) for moving the knight
// Save the square's score for further comparisions
least_x = check_x;
least_y = check_y;
least = _score;
}
}
}
// Move!
knight_x = least_x;
knight_y = least_y;
// Make this square a part of the tour by setting it to the move number (from 2-64)
visited[knight_x, knight_y] = ++moves_made;
}
```

GML:

```
/// @func score_from_square(x, y)
/// @arg x
/// @arg y
/// @desc Return a score equal to the amount of valid moves from (x,y)
var xx = argument0;
var yy = argument1;
// Count how many squares the knight could move to if it were at (x, y)
var _score = 0;
// Loop through the moves
for (var i = 0; i < 8; i++)
{
var check_x = xx + move_x[i];
var check_y = yy + move_y[i];
// If the square we're checking is valid, increment the score
if (is_valid(check_x, check_y))
{
_score++;
}
}
return _score;
```

GML:

`return (inside(argument0, argument1) && !visited[argument0, argument1]);`

GML:

`return (point_in_rectangle(argument0, argument1, 0, 0, COLS - 1, ROWS - 1));`

GML:

```
draw_board();
draw_set_halign(fa_center);
draw_set_valign(fa_middle);
draw_set_color(c_black);
// Draw stuff on visited squares
for (var i = 0; i < COLS; i++)
{
for (var j = 0; j < ROWS; j++)
{
if (visited[i, j])
{
var x1 = i * CELL_SIZE;
var y1 = j * CELL_SIZE;
var x2 = (i + 1) * CELL_SIZE;
var y2 = (j + 1) * CELL_SIZE;
// Cross it out
draw_line_color(x2, y1, x1, y2, c_red, c_red);
draw_line_color(x1, y1, x2, y2, c_red, c_red);
// Draw the move number
draw_text(x1 + CELL_SIZE / 2, y1 + CELL_SIZE / 2, visited[i, j]);
}
}
}
// Draw the knight
draw_sprite_ext(s_knight, 0, knight_x * CELL_SIZE + CELL_SIZE / 2, knight_y * CELL_SIZE + CELL_SIZE / 2, 0.75, 0.75, 0, c_white, 0.66);
```

GML:

```
for (var i = 0; i < COLS; i++)
{
for (var j = 0; j < ROWS; j++)
{
// Alternate light and dark
var color = ((i mod 2 == 0 && j mod 2 == 0) || (i mod 2 != 0 && j mod 2 != 0) ? c_light : c_dark);
// Draw the square
draw_set_color(color);
draw_rectangle(i * CELL_SIZE, j * CELL_SIZE, (i + 1) * CELL_SIZE, (j + 1) * CELL_SIZE, false);
draw_set_color(-1);
}
}
```

Last edited: