Here is a solution using an interpretation of Warnsdorff’s Algorithm:
Knight's tour - Wikipedia[
^]
Update: the code was refactored without sacrificing performance.
Objective
Flexible core with the following goals:
1. Reuse in other board-orientated puzzles like:
Eight queens puzzle - Wikipedia[
^],
Rook polynomial - Wikipedia[
^], and
No-three-in-line problem - Wikipedia[
^].
2. Plus other "bonus" tasks like:
2a. Determine all solvable tours for a given board size
2b. Determine the smallest board size with a valid solution
2c. Duelling Knights - solvable solutions with one or more knights on the board.
2d. The user can visually navigate forwards and backwards through the tour and see the how the decision making process works, not just the moves being made.
2e. Performance - not sacrifice flexibility over performance
To meet all of the above objectives, I chose to work with the
Stack(T) Class (System.Collections.Generic)[
^].
Core Code
The code is self-contained in a PCL (portable class library).
To meet the performance goal, when the
Knight class is initialized, it will reset the board and pre-calculate moves for every position.
1.
Location class:
public class Location
{
public Location(int cols, int rows, int index)
{
this.cols = cols;
this.rows = rows;
this.index = index;
}
public Location(int cols, int rows, int index, int moveNum)
: this(cols, rows, index)
{
this.moveNum = moveNum;
}
int cols, rows, iRow, col, row, index, moveNum;
public int MoveNum => moveNum;
public int Index => index;
public int Col
{
get
{
if (col == 0) calcCoords();
return col;
}
}
public int Row
{
get
{
if (row == 0) calcCoords();
return row;
}
}
private void calcCoords()
{
col = index % cols;
row = index / cols;
iRow = rows - row;
}
public override string ToString()
{
if (col == 0) calcCoords();
if (col < 26) return $"{(char)(col % 26 + 'A')}-{iRow}";
if (col < 52) return $"{new string('A', col / 26) + (char)(col % 26 + 'A')}-{iRow}";
return $"{"AZ" + (col - 52).ToString()}-{iRow}";
}
}2.
Board class & interface:
using System.Collections.Generic;
public interface IBoard
{
int Columns { get; }
List<List<int>> Locations { get; }
IEnumerable<int> Missed { get; }
int Rows { get; }
IRule Rules { set; }
bool[] Visited { get; }
Location Init(int? cellId = default(int?));
void ResetVisits();
void UndoVisit(int index);
}
public class Board : IBoard
{
public Board(int columns, int rows)
{
Columns = columns;
Rows = rows;
Size = columns * rows;
}
public int Size { get; }
public int Rows { get; } = 8;
public int Columns { get; } = 8;
public List<List<int>> Locations { get; private set; }
= new List<List<int>>();
public IEnumerable<int> Missed
=> Locations.Where((x, i) => !Visited[i]).Select((x, i) => i);
private static bool[] visited;
public bool[] Visited => visited;
public IRule Rules { private get; set; }
public Location Init(int? locationId = null)
{
totalLocations = Columns * Rows;
BuildMovesTable();
return new Location(Columns, Rows,
locationId.HasValue && locationId.Value > -1
? locationId.Value : r.Next(0, totalLocations), 0);
}
public void ResetVisits()
{
visited = new bool[totalLocations];
}
public void UndoVisit(int index)
{
Visited[index] = false;
}
private int totalLocations;
private Random r = new Random();
private void BuildMovesTable()
{
ResetVisits();
RebuildTable();
}
private void RebuildTable()
{
Locations = Enumerable.Range(0, totalLocations)
.Select(x => Rules.BuildLocation(x))
.ToList();
}
}3.
Knight class &
IRule interface:
using System.Collections.Generic;
public interface IRule
{
List<int> BuildLocation(int index);
}
public class Knight : IRule
{
public Knight(IBoard board, int? startLocation = null)
{
Board = board;
board.Rules = this;
Init(startLocation);
}
public void Init(int? startLocation)
{
Board.ResetVisits();
Moves = new Stack<Location>();
Moves.Push(Board.Init(startLocation));
CanMoveNext = true;
}
public IBoard Board { get; }
public Location Start => Moves?.Last();
public Location Current => Moves?.Peek();
public Stack<Location> Moves { get; private set; }
public bool CanMoveNext { get; private set; }
public void ExecuteMoves()
{
while (true) { if (MoveNext() == null) break; }
}
public Location MovePrevious()
{
if (Moves.Count > 0) Board.Visited[Moves.Pop().Index] = false;
CanMoveNext = true;
return Moves.Count > 0 ? Moves.Peek() : null;
}
public Location MoveNext()
{
var index = Moves.Peek().Index;
var c1 = Board.Locations[index];
int ndx = 0, score = int.MaxValue;
for (int i = 0; i < c1.Count; i++)
if (!Board.Visited[c1[i]] && c1[i] != index)
{
var tscore = 0;
var c2 = Board.Locations[c1[i]];
for (int j = 0; j < c2.Count; j++)
if (!Board.Visited[c2[j]] && c2[j] != i) tscore++;
if (tscore < score)
{
ndx = c1[i];
score = tscore;
}
}
Board.Visited[index] = true;
CanMoveNext = score != int.MaxValue;
if (CanMoveNext)
{
var newLoc = new Location(Board.Columns, Board.Rows, ndx, Moves.Count);
Moves.Push(newLoc);
return newLoc;
}
return null;
}
List<int> IRule.BuildLocation(int index)
{
var loc = new List<int>();
int pc = index % Board.Columns, pr = index / Board.Columns;
for (int k = 0; k < rules.GetLength(0); k++)
{
int nc = pc + rules[k, 0], nr = pr + rules[k, 1];
if (nc < Board.Columns && nc > -1 && nr < Board.Rows && nr > -1)
loc.Add(nr * Board.Columns + nc);
}
return loc;
}
private readonly int[,] rules = new int[,]
{
{ -1, -2 }, { 1, -2 }, { 2, -1 }, { 2, 1 },
{ 1, 2 }, { -1, 2 }, { -2, 1 }, { -2, -1 }
};
}
Challenge Proof
This project tests the Core Code against a number of different board sizes and dimensions for a). completing the challenge; b). performance.
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using KnightsTour.Core;
static class Program
{
static void Main()
{
ResetWindow();
Console.WriteLine("Weekly Challenge: Knight's Tour");
Console.WriteLine("===============================\n");
var styles = new List<IReportStyle>
{
new ChessStyle(),
new IndexedStyle(),
new LocationStyle()
};
foreach (var tour in new List<Tour>
{
new Tour("Standard Chess Board (8 x 8)", () => Activity(8, 8, null)),
new Tour("Smallest Viable Rectangle (4 x 3)", () => Activity(4, 3, 0)),
new Tour("2nd Smallest Viable Rectangle (7 x 3)", () => Activity(7, 3, 0)),
new Tour("Smallest Viable Square (5 x 5)", () => Activity(5, 5, 0)),
new Tour("Large Square Board", () => Activity(20, 20, null)),
new Tour("Very Large Square Board", () => Activity(300, 300, 89700)),
})
Report(tour.Activity(), styles[(int)ReportStyle.Chess]);
Console.WriteLine("\n-- press any key to exit --");
Console.ReadKey();
Console.CursorVisible = true;
}
private static Tuple<TimeSpan, Knight>
Activity(int cols, int rows, int? startLocation)
{
TimeSpan elapsed;
var sw = new Stopwatch();
var knight = new Knight(new Board(cols, rows), startLocation);
knight.ExecuteMoves();
knight.Init(startLocation);
sw.Start();
knight.ExecuteMoves();
elapsed = sw.Elapsed;
sw.Stop();
return new Tuple<TimeSpan, Knight>(elapsed, knight);
}
private static void Report(Tuple<TimeSpan, Knight> result,
IReportStyle styleWriter)
{
var elapsed = result.Item1;
var knight = result.Item2;
Console.WriteLine($"Board Size : {knight.Board.Columns}, {knight.Board.Rows}");
Console.WriteLine($"\nStarted at : {knight.Start}");
Console.WriteLine($"Final Loc'n : {knight.Current}");
Console.WriteLine($"Total moves : {knight.Moves.Count - 1:N0}");
Console.WriteLine($"Time taken : {elapsed.TotalMilliseconds:N6} ms");
if (knight.Moves.Count < 500)
{
Console.WriteLine("\nMoves used :");
Console.WriteLine(styleWriter.Format
(knight.Moves.OrderBy(x => x.MoveNum)));
}
if (knight.Board.Missed.Any())
{
var missedLocations
= knight.Board.Missed.Select
(x => new Location(knight.Board.Columns, knight.Board.Rows, x));
Console.WriteLine($"\nCells skipped : {missedLocations.Count()}");
if (knight.Moves.Count < 500)
Console.WriteLine(styleWriter.Format(missedLocations));
}
else
{
Console.WriteLine("\nCompleted the board!");
}
Console.WriteLine($"\n{new string('-', 80)}\n");
}
private static void ResetWindow()
{
Console.Title = "CODE PROJECT | WEEKLY CODE CHALENGE";
Console.CursorVisible = false;
Console.SetWindowSize(80, Console.WindowHeight);
Console.Clear();
}
}
class Tour : Job<Knight>
{
public Tour(string title, Func<Tuple<TimeSpan, Knight>> func)
: base(title, func) { }
}
class Job<T>
{
public Job(string title, Func<Tuple<TimeSpan, T>> func)
{
Title = title;
this.func = func;
}
private readonly Func<Tuple<TimeSpan, T>> func;
public string Title { get; }
public Tuple<TimeSpan, T> Activity()
{
Console.WriteLine(Title);
Console.WriteLine(new string('-', Title.Length));
Console.WriteLine();
return func.Invoke();
}
}
enum ReportStyle
{
Chess,
Indexed,
Location
}
interface IReportStyle
{
string Format(IEnumerable<Location> moves);
}
class ChessStyle : IReportStyle
{
public string Format(IEnumerable<Location> moves)
=> string.Join(", ", moves);
}
class IndexedStyle : IReportStyle
{
public string Format(IEnumerable<Location> moves)
{
var m = moves.ToList();
return string.Join("\n",
Enumerable.Range(0, m.Count - 1)
.Select(i => $"{i,-3}: {m[i].Index + 1}"));
}
}
class LocationStyle : IReportStyle
{
public string Format(IEnumerable<Location> moves)
{
var m = moves.ToList();
return string.Join(", ",
Enumerable.Range(0, m.Count - 1)
.Select(i => $"{{{m[i].Row}, {m[i].Col}}}")); ;
}
}And the output:
Weekly Challenge: Knight's Tour
===============================
Standard Chess Board (8 x 8)
----------------------------
Board Size : 8, 8
Started at : E-2
Final Loc'n : B-2
Total moves : 63
Time taken : 0.049700 ms
Moves used :
E-2, G-1, H-3, G-5, H-7, F-8, G-6, H-8, F-7, H-6, G-8, E-7, C-8, A-7, C-6, B-8, A-6, B-4, A-2, C-1, B-3, A-1, C-2, E-1, G-2, H-4, F-3, H-2, F-1, D-2, B-1, A-3, B-5, D-4, F-5, G-7, H-5, G-3, H-1, F-2, G-4, E-3, D-1, C-3, E-4, D-6, E-8, F-6, D-5, C-7, A-8, B-6, D-7, E-5, C-4, A-5, B-7, D-8, E-6, F-4, D-3, C-5, A-4, B-2
Completed the board!
--------------------------------------------------------------------------------
Smallest Viable Rectangle (4 x 3)
---------------------------------
Board Size : 4, 3
Started at : A-3
Final Loc'n : D-1
Total moves : 5
Time taken : 0.017400 ms
Moves used :
A-3, C-2, A-1, B-3, D-2, B-1, C-3, A-2, C-1, D-3, B-2, D-1
Completed the board!
--------------------------------------------------------------------------------
2nd Smallest Viable Rectangle (7 x 3)
-------------------------------------
Board Size : 7, 3
Started at : A-3
Final Loc'n : F-2
Total moves : 20
Time taken : 0.006800 ms
Moves used :
A-3, C-2, A-1, B-3, C-1, A-2, C-3, B-1, D-2, F-3, G-1, E-2, G-3, F-1, E-3, G-2, E-1, D-3, B-2, D-1, F-2
Completed the board!
--------------------------------------------------------------------------------
Smallest Viable Square (5 x 5)
------------------------------
Board Size : 5, 5
Started at : A-5
Final Loc'n : B-2
Total moves : 24
Time taken : 0.009800 ms
Moves used :
A-5, C-4, E-5, D-3, E-1, C-2, A-1, B-3, C-5, E-4, D-2, B-1, A-3, B-5, D-4, E-2, C-1, A-2, B-4, D-5, E-3, D-1, C-3, A-4, B-2
Completed the board!
--------------------------------------------------------------------------------
Large Square Board
------------------
Board Size : 20, 20
Started at : J-15
Final Loc'n : C-5
Total moves : 399
Time taken : 0.341300 ms
Moves used :
J-15, I-17, H-19, J-20, L-19, N-20, P-19, R-20, T-19, S-17, T-15, S-13, T-11, S-9, T-7, S-5, T-3, S-1, Q-2, O-1, M-2, K-1, I-2, G-1, E-2, C-1, A-2, B-4, A-6, B-8, A-10, B-12, A-14, B-16, A-18, B-20, D-19, F-20, G-18, H-20, J-19, L-20, N-19, P-20, R-19, T-20, S-18, T-16, S-14, T-12, S-10, T-8, S-6, T-4, S-2, Q-1, R-3, T-2, R-1, S-3, T-1, R-2, P-1, O-3, N-1, P-2, Q-4, R-6, T-5, R-4, P-3, N-2, L-1, K-3, J-1, L-2, M-4, O-5, N-3, M-1, O-2, P-4, Q-6, R-8, T-9, S-7, R-5, T-6, S-4, Q-3, P-5, N-4, L-3, J-2, H-1, G-3, F-1, H-2, I-4, K-5, J-3, I-1, K-2, L-4, M-6, O-7, Q-8, R-10, S-8, T-10, S-12, T-14, R-15, Q-17, S-16, T-18, S-20, R-18, Q-20, S-19, T-17, R-16, Q-18, O-19, M-20, N-18, O-20, Q-19, P-17, Q-15, R-17, P-18, O-16, M-17, O-18, P-16, Q-14, S-15, T-13, R-12, Q-10, S-11, R-13, Q-11, R-9, Q-7, P-9, O-11, P-13, R-14, Q-16, P-14, Q-12, P-10, R-11, Q-13, P-15, O-17, N-15, O-13, P-11, Q-9, R-7, Q-5, P-7, O-9, N-11, P-12, O-14, N-16, M-18, K-17, M-16, O-15, N-17, M-19, K-18, L-16, M-14, N-12, O-10, P-8, O-6, N-8, M-10, L-12, N-13, M-15, L-17, K-19, I-20, J-18, K-20, L-18, K-16, L-14, M-12, N-14, O-12, N-10, O-8, P-6, O-4, N-6, M-8, L-10, N-9, M-11, L-13, K-15, J-17, I-19, G-20, H-18, I-16, J-14, L-15, M-13, K-12, I-13, K-14, J-16, I-18, H-16, I-14, K-13, L-11, M-9, N-7, M-5, L-7, K-9, J-11, H-12, J-13, I-15, H-17, G-19, E-20, F-18, G-16, H-14, I-12, K-11, L-9, M-7, N-5, M-3, L-5, K-7, J-9, L-8, K-10, J-12, I-10, J-8, K-6, J-4, I-6, H-8, J-7, L-6, K-4, J-6, K-8, J-10, I-8, H-10, G-12, I-11, H-13, G-15, F-17, E-19, C-20, A-19, C-18, D-20, B-19, A-17, B-15, A-13, C-14, A-15, B-17, C-19, A-20, B-18, D-17, E-15, G-14, F-16, E-18, D-16, F-15, E-17, F-19, G-17, H-15, G-13, H-11, I-9, G-10, F-12, E-14, C-15, A-16, C-17, E-16, D-18, C-16, D-14, F-13, G-11, H-9, I-7, J-5, I-3, H-5, G-7, F-9, E-11, D-13, F-14, D-15, B-14, A-12, C-13, E-12, F-10, G-8, H-6, G-4, I-5, H-3, F-2, D-1, B-2, A-4, C-3, B-1, A-3, B-5, A-7, B-9, A-11, B-13, C-11, D-9, C-7, A-8, B-10, C-12, E-13, D-11, E-9, F-11, D-10, B-11, D-12, C-10, A-9, C-8, B-6, D-5, E-7, G-6, H-4, G-2, F-4, D-3, E-1, C-2, A-1, B-3, A-5, C-6, D-4, F-5, E-3, C-4, D-2, F-3, E-5, D-7, C-9, E-10, F-8, H-7, G-9, E-8, F-6, E-4, D-6, F-7, G-5, E-6, D-8, B-7, C-5
Completed the board!
--------------------------------------------------------------------------------
Very Large Square Board
-----------------------
Board Size : 300, 300
Started at : A-1
Final Loc'n : L-21
Total moves : 89,999
Time taken : 124.877700 ms
Completed the board!
--------------------------------------------------------------------------------
-- press any key to exit --
Bonus Task 1 - Number of Possible Tours
Given a board size, find all the possible solvable paths available.
using KnightsTour.Core;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
class Program
{
static List<Tuple<TimeSpan, Knight>> Tours = new List<Tuple<TimeSpan, Knight>>();
static void Main()
{
ResetWindow();
Console.WriteLine("Weekly Challenge: Knight's Tour");
Console.WriteLine("===============================\n");
Console.WriteLine("Bonus Challenge: Find All Solutions for a given Board Size\n");
var styles = new List<IReportStyle>
{
new ChessStyle(),
new IndexedStyle(),
new LocationStyle()
};
TripPlanner(3, 7);
ReportResults(styles[(int)ReportStyle.Chess]);
Console.WriteLine("\n-- press any key to exit --");
Console.ReadKey();
Console.CursorVisible = true;
}
private static void TripPlanner(int rows, int cols)
{
int size = rows * cols;
for (int start = 0; start < size; start++)
TryTour(rows, cols, start);
}
private static void TryTour(int rows, int cols, int startLocation)
{
TimeSpan elapsed;
var sw = new Stopwatch();
var knight = new Knight(new Board(cols, rows), startLocation);
knight.ExecuteMoves();
knight.Init(startLocation);
sw.Start();
knight.ExecuteMoves();
elapsed = sw.Elapsed;
sw.Stop();
var success = !knight.Board.Missed.Any();
if (success)
Tours.Add(new Tuple<TimeSpan, Knight>(elapsed, knight));
}
private static void ReportResults(IReportStyle styleWriter)
{
var board = Tours[0].Item2.Board;
Console.WriteLine($"Board Size : {board.Columns}, {board.Rows}");
Console.WriteLine($"Task Outcome : {(Tours.Any() ? "Completed!"
: "Failed!")}");
Console.WriteLine($"Total Tours : {Tours.Count} possible");
foreach (var tour in Tours)
{
var elapsed = tour.Item1;
var knight = tour.Item2;
Console.WriteLine($"\nStarted at : {knight.Start}");
Console.WriteLine($"Final Loc'n : {knight.Current}");
Console.WriteLine($"Time taken : {elapsed.TotalMilliseconds:N6} ms");
if (knight.Moves.Count < 500)
{
Console.WriteLine("Moves used :\n");
Console.WriteLine(styleWriter.Format
(knight.Moves.OrderBy(x => x.MoveNum)));
}
}
}
private static void ResetWindow()
{
Console.Title = "CODE PROJECT | WEEKLY CODE CHALENGE";
Console.CursorVisible = false;
Console.SetWindowSize(80, Console.WindowHeight);
Console.Clear();
}
}
And the output:
Weekly Challenge: Knight's Tour
===============================
Bonus Challenge: Find All Solutions for a given Board Size
Board Size : 7, 3
Task Outcome : Completed!
Total Tours : 5 possible
Started at : A-3
Final Loc'n : F-2
Time taken : 0.006800 ms
Moves used :
A-3, C-2, A-1, B-3, C-1, A-2, C-3, B-1, D-2, F-3, G-1, E-2, G-3, F-1, E-3, G-2, E-1, D-3, B-2, D-1, F-2
Started at : E-3
Final Loc'n : F-2
Time taken : 0.033800 ms
Moves used :
E-3, G-2, E-1, F-3, G-1, E-2, G-3, F-1, D-2, B-1, A-3, C-2, A-1, B-3, C-1, A-2, C-3, D-1, B-2, D-3, F-2
Started at : F-2
Final Loc'n : C-3
Time taken : 0.013300 ms
Moves used :
F-2, D-1, B-2, D-3, E-1, G-2, E-3, F-1, G-3, E-2, G-1, F-3, D-2, B-1, A-3, C-2, A-1, B-3, C-1, A-2, C-3
Started at : C-1
Final Loc'n : F-2
Time taken : 0.00600 ms
Moves used :
C-1, A-2, C-3, B-1, A-3, C-2, A-1, B-3, D-2, F-3, G-1, E-2, G-3, F-1, E-3, G-2, E-1, D-3, B-2, D-1, F-2
Started at : E-1
Final Loc'n : F-2
Time taken : 0.007200 ms
Moves used :
E-1, G-2, E-3, F-1, G-3, E-2, G-1, F-3, D-2, B-1, A-3, C-2, A-1, B-3, C-1, A-2, C-3, D-1, B-2, D-3, F-2
-- press any key to exit --
Bonus Task 2 - Smallest Square and Rectangular Board Sizes
This task uses the concept from Bonus 1 and looks from a standard-size chess board grid of 8 x 8 and looks for smaller Square and rectangular board sizes that are solvable. The code to perform this task is quite compact.
using KnightsTour.Core;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
class Program
{
static List<Tuple<TimeSpan, Knight>> Tours = new List<Tuple<TimeSpan, Knight>>();
static void Main()
{
ResetWindow();
Console.WriteLine("Weekly Challenge: Knight's Tour");
Console.WriteLine("===============================\n");
Console.WriteLine("Bonus Challenge: Find the smallest Solvable Board Sizes\n");
Console.WriteLine("Starting at the size of a Chess board size (8 x 8 = 64), determine (up to 10)\ndimensions of the smallest solvable solution for both square and rectangular\nboards.\n");
for (int size = 64 - 1; size >= 9; size--)
TryTour(size);
var orderedTours = Tours.OrderBy(x => x.Item2.Moves.Count);
var bestBox = orderedTours
.Where(x => x.Item2.Board.Columns.Equals(x.Item2.Board.Rows))
.GroupBy(x => $"{x.Item2.Board.Columns} x {x.Item2.Board.Rows}")
.Take(10);
var bestRects = orderedTours
.Where(x => !x.Item2.Board.Columns.Equals(x.Item2.Board.Rows))
.GroupBy(x => $"{x.Item2.Board.Columns} x {x.Item2.Board.Rows}")
.Take(10);
var detailedReporting = false;
Console.WriteLine("Smallest Boxes");
ReportSolutions(bestBox, detailedReporting);
Console.WriteLine("\nSmallest Rectangles");
ReportSolutions(bestRects, detailedReporting);
Console.WriteLine("\n-- press any key to exit --");
Console.ReadKey();
Console.CursorVisible = true;
}
private static void TryTour(int size)
{
var factors = getFactors(size).ToArray();
if (factors.Length == 1)
TryTour(new int[,] { { factors[0], factors[0] } }, size);
else
for (int factor = 0; factor < factors.Length / 2; factor++)
{
var index = factor * 2;
TryTour(new int[,] { { factors[index], factors[index + 1] } }, size);
}
}
private static void TryTour(int[,] gridSize, int size)
{
for (int start = 0; start < size; start++)
{
TryTour(gridSize[0, 0], gridSize[0, 1], start);
if (!gridSize[0, 0].Equals(gridSize[0, 1]))
TryTour(gridSize[0, 1], gridSize[0, 0], start);
}
}
private static bool TryTour(int rows, int cols, int startLocation)
{
TimeSpan elapsed;
var sw = new Stopwatch();
var knight = new Knight(new Board(cols, rows), startLocation);
knight.ExecuteMoves();
knight.Init(startLocation);
sw.Start();
knight.ExecuteMoves();
elapsed = sw.Elapsed;
sw.Stop();
var success = !knight.Board.Missed.Any();
if (success)
Tours.Add(new Tuple<TimeSpan, Knight>(elapsed, knight));
return success;
}
public static IEnumerable<int> getFactors(int x)
{
for (int i = 2; i * i <= x; i++)
if (0 == (x % i))
{
yield return i;
if (i != (x / i)) yield return x / i;
}
}
private static void ReportSolutions
(IEnumerable<IGrouping<string, Tuple<TimeSpan, Knight>>> bestBox,
bool isDetailed = false)
{
foreach (var item in bestBox)
{
var loc = $"{{{item.First().Item2.Board.Rows},{ item.First().Item2.Board.Columns}}}";
var count = item.Count();
var moves = item.First().Item2.Moves.Count - 1;
Console.WriteLine($"{loc} has {count} solutions in {moves} moves");
if (isDetailed)
foreach (var result in item)
{
var start = result.Item2.Moves.First();
var end = result.Item2.Moves.Last();
var ms = result.Item1.TotalMilliseconds;
Console.WriteLine($" - From: {start} To: {end} in {ms:N6} ms");
}
}
}
private static void ResetWindow()
{
Console.Title = "CODE PROJECT | WEEKLY CODE CHALENGE";
Console.CursorVisible = false;
Console.SetWindowSize(80, Console.WindowHeight);
Console.Clear();
}
}And the output:
Weekly Challenge: Knight's Tour
===============================
Bonus Challenge: Find the smallest Solvable Board Sizes
Starting at the size of a Chess board size (8 x 8 = 64), determine (up to 10)
dimensions of the smallest solvable solution for both square and rectangular
boards.
Smallest Boxes
{5,5} has 5 solutions in 24 moves
{7,7} has 19 solutions in 48 moves
Smallest Rectangles
{3,4} has 6 solutions in 11 moves
{4,3} has 5 solutions in 11 moves
{4,5} has 5 solutions in 19 moves
{5,4} has 10 solutions in 19 moves
{3,7} has 5 solutions in 20 moves
{7,3} has 5 solutions in 20 moves
{3,8} has 11 solutions in 23 moves
{8,3} has 10 solutions in 23 moves
{4,6} has 10 solutions in 23 moves
{6,4} has 4 solutions in 23 moves
-- press any key to exit --
Bonus Task 3 - Duelling Knights
With this task, I am using a 8 x 8 board with 4 Knights, and a 20 x 20 board with 8 Knights, each with Knights independently doing their tours attempting to complete the tasks.
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using KnightsTour.Core;
static class Program
{
static void Main()
{
ResetWindow();
Console.WriteLine("Weekly Challenge: Knight's Tour");
Console.WriteLine("===============================\n");
Console.WriteLine("Bonus Challenge: Dueling Knights\n");
var styles = new List<IReportStyle>
{
new ChessStyle(),
new IndexedStyle(),
new LocationStyle()
};
foreach (var tour in new List<Tour>
{
new Tour("Standard Chess Board (8 x 8)",
() => Test(8, 8, new List<int?>
{ null, null, null, null })),
new Tour("Large Board (20 x 20)",
() => Test(20, 20, new List<int?>
{ 0, 19, 126, 133, 266, 273, 380, 399 }))
})
ReportResults(tour.Activity(), styles[(int)ReportStyle.Chess]);
Console.WriteLine("\n-- press any key to exit --");
Console.ReadKey();
Console.CursorVisible = true;
}
private static Tuple<TimeSpan, List<Knight>>
Test(int cols, int rows, List<int?> startLocations)
{
TimeSpan elapsed;
var sw = new Stopwatch();
bool canMove;
var board = new Board(cols, rows);
var knights = new List<Knight>();
foreach (var loc in startLocations)
{
var knight = new Knight(new Board(cols, rows), loc);
knight.ExecuteMoves();
knight.Init(loc);
knights.Add(new Knight(board, loc));
}
int tl = knights.Count;
sw.Start();
do
{
canMove = false;
for (int i = 0; i < tl; i++)
{
knights[i].MoveNext();
if (knights[i].CanMoveNext) canMove = true;
}
if (!canMove)
{
elapsed = sw.Elapsed;
break;
}
} while (true);
sw.Stop();
return new Tuple<TimeSpan, List<Knight>>(elapsed, knights);
}
private static void ReportResults(Tuple<TimeSpan, List<Knight>> result,
IReportStyle styleWriter)
{
var elapsed = result.Item1;
var knights = result.Item2;
var board = knights[0].Board;
Console.WriteLine($"Board Size : {board.Columns}, {board.Rows}");
Console.WriteLine($"Time taken : {elapsed.TotalMilliseconds:N6} ms");
Console.WriteLine($"Task Outcome : {(board.Missed.Any()
? "Failed!" : "Completed!")}");
for (int i = 0; i < knights.Count; i++)
{
var knight = knights[i];
Console.WriteLine($"\nStarted at : {knight.Start}");
Console.WriteLine($"Final Loc'n : {knight.Current}");
Console.WriteLine($"Total moves : {knight.Moves.Count - 1:N0}");
if (knight.Moves.Count < 500)
{
Console.WriteLine("Moves used :\n");
Console.WriteLine(styleWriter.Format
(knight.Moves.OrderBy(x => x.MoveNum)));
}
}
Console.WriteLine($"\n{new string('-', 80)}\n");
}
private static void ResetWindow()
{
Console.Title = "CODE PROJECT | WEEKLY CODE CHALENGE";
Console.CursorVisible = false;
Console.SetWindowSize(80, Console.WindowHeight);
Console.Clear();
}
}And the output:
Weekly Challenge: Knight's Tour
===============================
Bonus Challenge: Duelling Knights
Standard Chess Board (8 x 8)
----------------------------
Board Size : 8, 8
Time taken : 0.085500 ms
Task Outcome : Completed!
Started at : F-6
Final Loc'n : D-3
Total moves : 23
Moves used :
F-6, G-8, H-6, G-4, F-2, H-3, G-1, E-2, C-3, B-1, A-3, B-5, A-7, C-8, D-6, F-5, D-4, E-6, C-5, B-3, A-1, C-2, E-1, D-3
Started at : C-1
Final Loc'n : D-3
Total moves : 23
Moves used :
C-1, A-2, B-4, A-6, B-8, D-7, F-8, H-7, G-5, E-4, D-2, C-4, E-3, G-2, H-4, F-5, D-4, E-6, C-5, B-3, A-1, C-2, E-1, D-3
Started at : D-1
Final Loc'n : F-3
Total moves : 22
Moves used :
D-1, B-2, A-4, B-6, A-8, C-7, E-8, G-7, H-5, F-4, D-5, E-7, C-8, D-6, F-5, D-4, E-6, D-8, F-7, H-8, G-6, E-5, F-3
Started at : H-2
Final Loc'n : D-3
Total moves : 23
Moves used :
H-2, F-1, G-3, H-1, F-2, H-3, G-1, E-2, C-3, B-1, A-3, B-5, A-7, C-6, A-5, B-7, D-8, F-7, H-8, G-6, E-5, F-3, E-1, D-3
--------------------------------------------------------------------------------
Large Board (20 x 20)
---------------------
Board Size : 20, 20
Time taken : 0.958200 ms
Task Outcome : Completed!
Started at : L-18
Final Loc'n : D-7
Total moves : 131
Moves used :
L-18, K-20, M-19, O-20, Q-19, S-20, T-18, R-19, P-20, Q-18, R-16, S-14, T-12, S-10, T-8, S-6, T-4, S-2, R-4, Q-6, R-8, Q-10, R-12, Q-14, O-15, Q-16, R-14, P-13, O-11, Q-12, R-10, P-9, Q-7, R-5, P-4, R-3, T-2, R-1, P-2, N-1, O-3, P-1, R-2, Q-4, P-6, O-8, N-10, M-12, L-14, K-16, J-18, I-16, J-14, K-12, L-10, N-9, O-7, N-5, M-3, O-2, Q-1, P-3, N-4, L-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, I-9, K-10, L-8, J-9, I-11, G-10, H-8, I-10, G-11, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, K-6, J-4, H-5, I-3, K-4, J-2, H-1, G-3, F-5, E-7, D-9, C-7, B-5, D-6, F-7, D-8, C-6, D-4, F-3, G-5, H-7, I-5, H-3, F-2, E-4, F-6, G-4, E-5, D-7
Started at : T-20
Final Loc'n : D-7
Total moves : 131
Moves used :
T-20, S-18, R-20, T-19, S-17, T-15, S-13, T-11, S-9, T-7, S-5, T-3, S-1, Q-2, O-1, M-2, K-1, I-2, G-1, E-2, C-1, A-2, B-4, A-6, B-8, A-10, C-9, A-8, B-10, A-12, B-14, C-16, E-15, F-17, D-18, E-20, G-19, I-20, K-19, L-17, M-15, N-13, M-11, L-13, K-15, M-14, L-16, N-15, M-13, N-11, P-10, Q-8, R-6, S-4, Q-3, P-5, O-7, N-5, M-3, O-2, Q-1, P-3, N-4, L-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, I-9, K-10, L-8, J-9, I-11, G-10, H-8, I-10, G-11, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, K-6, J-4, H-5, I-3, K-4, J-2, H-1, G-3, F-5, E-7, D-9, C-7, B-5, D-6, F-7, D-8, C-6, D-4, F-3, G-5, H-7, I-5, H-3, F-2, E-4, F-6, G-4, E-5, D-7
Started at : G-14
Final Loc'n : D-3
Total moves : 130
Moves used :
G-14, F-16, E-18, D-20, B-19, A-17, C-18, B-20, A-18, C-19, A-20, B-18, C-20, A-19, B-17, A-15, C-14, D-16, E-14, C-15, D-17, E-19, G-20, I-19, K-18, J-20, L-19, M-17, O-16, Q-17, R-15, P-14, O-12, Q-13, P-15, O-17, M-18, N-16, O-14, P-12, R-11, Q-9, O-10, N-12, P-11, O-13, N-15, M-13, N-11, P-10, Q-8, R-6, S-4, Q-3, P-5, O-7, N-5, M-7, O-6, Q-5, O-4, N-2, L-1, K-3, J-1, L-2, M-4, N-6, M-8, L-6, K-8, J-6, L-5, K-7, I-8, H-10, G-12, F-14, G-16, E-17, D-15, C-13, D-11, E-13, F-15, G-13, F-11, H-12, F-13, D-12, C-10, A-11, B-13, D-14, C-12, D-10, B-9, A-7, C-8, E-9, G-8, I-7, K-6, J-4, I-6, H-4, J-5, H-6, I-4, H-2, F-1, D-2, B-1, A-3, C-2, E-1, G-2, E-3, D-1, C-3, D-5, B-6, C-4, B-2, A-4, C-5, E-6, F-8, G-6, F-4, D-3
Started at : N-14
Final Loc'n : D-7
Total moves : 131
Moves used :
N-14, M-16, N-18, M-20, O-19, Q-20, S-19, T-17, S-15, R-17, T-16, S-14, T-12, S-10, T-8, S-6, T-4, S-2, R-4, Q-6, R-8, Q-10, R-12, Q-14, O-15, Q-16, R-14, P-13, O-11, Q-12, R-10, P-9, Q-7, R-5, P-4, R-3, T-2, R-1, P-2, N-1, O-3, P-1, R-2, Q-4, P-6, O-8, N-10, M-12, L-14, K-16, J-18, I-16, J-14, K-12, L-10, N-9, M-7, O-6, Q-5, O-4, N-2, P-3, N-4, L-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, I-9, K-10, L-8, J-9, I-11, G-10, H-8, I-10, G-11, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, I-6, H-4, J-5, I-3, K-4, J-2, H-1, G-3, F-5, E-7, D-9, C-7, B-5, D-6, F-7, D-8, C-6, D-4, F-3, G-5, H-7, I-5, H-3, F-2, E-4, F-6, G-4, E-5, D-7
Started at : G-7
Final Loc'n : D-7
Total moves : 131
Moves used :
G-7, F-9, E-11, D-13, B-12, A-14, B-16, A-18, C-19, A-20, B-18, C-20, A-19, B-17, A-15, C-14, D-16, E-14, C-15, D-17, E-19, G-20, I-19, K-18, J-20, L-19, M-17, O-16, Q-17, R-15, P-14, O-12, Q-13, P-15, O-17, M-18, N-16, O-14, P-12, R-11, Q-9, O-10, N-12, P-11, O-13, M-14, L-16, J-17, H-18, F-19, H-20, I-18, J-16, H-17, I-15, K-14, L-12, J-13, K-11, M-10, O-9, P-7, O-5, N-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, I-9, K-10, L-8, J-9, I-11, G-10, H-8, I-10, G-11, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, I-6, H-4, J-5, I-3, K-4, J-2, H-1, G-3, F-5, E-7, D-9, C-7, B-5, D-6, F-7, D-8, C-6, D-4, F-3, G-5, H-7, I-5, H-3, F-2, E-4, F-6, G-4, E-5, D-7
Started at : N-7
Final Loc'n : D-3
Total moves : 130
Moves used :
N-7, M-9, L-11, K-13, L-15, K-17, J-19, L-20, N-19, P-18, N-17, P-16, O-18, N-20, P-19, R-18, P-17, Q-15, S-16, T-14, R-13, Q-11, S-12, T-10, R-9, P-8, R-7, T-6, S-8, R-10, P-9, Q-7, R-5, P-4, R-3, T-2, R-1, P-2, N-1, O-3, P-1, R-2, Q-4, P-6, O-8, N-10, M-12, L-14, K-16, J-18, I-16, J-14, K-12, L-10, N-9, O-7, N-5, M-3, O-2, Q-1, P-3, N-4, L-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, G-13, F-11, H-12, F-13, D-12, C-10, A-11, B-13, D-14, C-12, D-10, B-9, A-7, C-8, E-9, G-8, I-7, K-6, J-4, H-5, I-3, K-4, J-2, H-1, G-3, F-1, D-2, B-1, A-3, C-2, E-1, G-2, E-3, D-1, C-3, D-5, B-6, C-4, B-2, A-4, C-5, E-6, F-8, G-6, F-4, D-3
Started at : A-1
Final Loc'n : D-7
Total moves : 131
Moves used :
A-1, B-3, A-5, B-7, A-9, B-11, A-13, B-15, C-17, A-16, B-18, C-20, A-19, B-17, A-15, C-14, D-16, E-14, C-15, D-17, E-19, G-20, I-19, K-18, J-20, L-19, M-17, O-16, Q-17, R-15, P-14, O-12, Q-13, P-15, O-17, M-18, N-16, O-14, P-12, R-11, Q-9, O-10, N-12, P-11, O-13, M-14, L-16, J-17, H-18, F-19, H-20, I-18, J-16, H-17, I-15, K-14, L-12, J-13, K-11, M-10, O-9, P-7, O-5, N-3, M-5, L-7, N-8, L-9, J-10, I-12, H-14, J-15, H-16, G-18, F-20, D-19, F-18, G-16, E-17, D-15, C-13, D-11, E-13, F-15, G-13, F-11, H-12, F-13, D-12, C-10, A-11, B-13, D-14, C-12, D-10, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, I-6, H-4, J-5, H-6, I-4, H-2, F-1, D-2, B-1, A-3, C-2, E-1, G-2, E-3, D-1, C-3, D-5, B-6, C-4, B-2, A-4, C-5, E-6, F-8, G-6, F-4, D-3, E-5, D-7
Started at : T-1
Final Loc'n : D-7
Total moves : 130
Moves used :
T-1, S-3, T-5, S-7, T-9, S-11, T-13, S-15, R-17, T-16, S-14, T-12, S-10, T-8, S-6, T-4, S-2, R-4, Q-6, R-8, Q-10, R-12, Q-14, O-15, Q-16, R-14, P-13, O-11, Q-12, R-10, P-9, Q-7, R-5, P-4, R-3, T-2, R-1, P-2, N-1, O-3, P-1, R-2, Q-4, P-6, O-8, N-10, M-12, L-14, K-16, J-18, I-16, J-14, K-12, L-10, N-9, O-7, N-5, M-3, O-2, Q-1, P-3, N-4, L-3, M-1, K-2, I-1, J-3, L-4, M-6, K-5, J-7, K-9, J-11, I-13, H-15, I-17, H-19, G-17, E-16, G-15, I-14, J-12, H-13, F-12, H-11, I-9, K-10, L-8, J-9, I-11, G-10, H-8, I-10, G-11, E-12, C-11, E-10, G-9, E-8, F-10, H-9, J-8, K-6, J-4, H-5, I-3, K-4, J-2, H-1, G-3, F-5, E-7, D-9, C-7, B-5, D-6, F-7, D-8, C-6, D-4, F-3, G-5, H-7, I-5, H-3, F-2, E-4, F-6, G-4, E-5, D-7
--------------------------------------------------------------------------------
-- press any key to exit --
NOTE: The first tour is an 8 x 8 chess board with 4 knights randomly placed. It is possible that not all 4-Knight-Tours will complete based on where they start. However, it is possible this puzzle to be solved. Experiment and have fun with it.
Bonus Task 4 - Retro Visual Solver with Navigation
This task is quite a simple one as the title indicates - move forwards and backwards and watch the board get solved. This does quite a bit more than just that. Rather than trying to describe it in words, a picture tells it much better...
Screenshot[
^]
There are a few hundred lines of code in this project, so rather than post it all here, I have provided a downloadable link below so you can try it out and see visually exactly how the algorithm works, not just the moves that the Knight makes on its tour of the board. ;)
Here an extract of the core navigation code that allows the user to move forwards & backwards. Navigation is only a single line per direction and a check if we are at the end of the tour or not.
private static void TourGuide(int cols, int rows)
{
InitWorkArea(cols, rows);
knight = new Knight(new Board(cols, rows));
UpdateLocation(knight.Moves.Peek());
bool Active = true;
while (Active)
{
switch (Console.ReadKey(true).Key)
{
case ConsoleKey.P:
isPreview = !isPreview;
break;
case ConsoleKey.PageUp:
case ConsoleKey.LeftArrow:
case ConsoleKey.UpArrow:
if (knight.Moves.Count > 1)
{
ClearLocation(knight.Moves.Peek());
UpdateLocation(knight.MovePrevious());
}
break;
case ConsoleKey.Spacebar:
case ConsoleKey.RightArrow:
case ConsoleKey.PageDown:
case ConsoleKey.DownArrow:
if (knight.CanMoveNext)
UpdateLocation(knight.MoveNext());
break;
case ConsoleKey.Escape:
Active = false;
break;
}
}
}Output:
Weekly Challenge: Knight's Tour
===============================
Bonus Challenge: Visually let a user move through the moves of a tour
Hot Keys:
Forward: Down arrow / PgDn / Right arrow / SpaceBar
Backward: Up arrow / PgUp / Left arrow
Preview: P - toggles preview decisions before move
Exit: ESC to quit
-- press any key to begin --
And a
Screenshot[
^] of the visual output.
Download
Here is a link to the downloadable solution:
C# Version[
^]
The Download includes the Core PCL + all the sample apps for each of the Tours above. Bonus: I have included the original prototype for this challenge. ;)
A detailed article coming soon (time permitting)...
Enjoy!
Submit an article or tip