Click here to Skip to main content
14,162,244 members
Rate this:
 
Please Sign up or sign in to vote.
See more:
Today's challenge is provided by Jeroen Landheer.

Write a program that lets a knight hop over a chessboard so it touches all squares, but that knight may never use the same spot twice. Starting position should be given by the user (or provided as a random location if you don't feel like accepting user input), and the program must compute and output the solution in a list of coordinates.

Example:

Start at: A1
Solution: A1 – B3 – C5 etc


Last week
Special mention to ProgramFOX for his polyglot solution. Awesome. For the winner it was neck and neck between Jörgen Andersson and Graeme but I'm going to give it to Jörgen in the hope of inspiring Graeme to even higher feats of insanity.
Posted
Updated 16-Mar-17 20:01pm
Comments
Graeme_Grant 10-Mar-17 7:35am
   
So performance & reliability when a word not found was not important? In-memory SQLite was just as fast as my optimized Dictionary solution... Much faster & more reliable than Jörgen's... Hmmm... The table is stacked against me. :/

I must admit that Jörgen gave it a good shot... well done mate.
Chris Maunder 12-Mar-17 23:30pm
   
If this becomes something where I have to sit down and fully test each solution, time them, verify their correctness, check for plagiarism and provide a point-by point independently verified set of judging criteria then I'm afraid I'll have to leave it to you guys to come up with the challenges and announce a "winner".

It's for fun. The judging is deliberately random and sometimes wildly biased.

How about we just leave this as a challenge and I forgo any attempt at declaring a winner. I want this to be fun, not something where it could potentially upset participants.
Graeme_Grant 13-Mar-17 11:53am
   
Noted and I will be more mindful in future.
PIEBALDconsult 10-Mar-17 23:40pm
   
... and the world's your oyster.
Graeme_Grant 11-Mar-17 2:01am
   
Graeme_Grant 11-Mar-17 9:27am
   
Chris, there appears to some confusion for some by what is meant by "touches all squares". Would you mind giving some clarification for these people, please.
Graeme_Grant 13-Mar-17 11:39am
   
"the hope of inspiring Graeme to even higher feats of insanity." - Updated and Done! ;)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

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 // a Knight's move
{
    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)),
        })
            // choose a reporting style format...
            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);

        //Prime to ensure correct timings...
        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;

        // try each location for a valid solution
        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);
        
        //Prime to ensure correct timings...
        knight.ExecuteMoves();
        knight.Init(startLocation);

        //Actual Task
        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");


        // down to 4 x 4 = 20 which is invalid & test each location as a start point

        for (int size = 64 - 1; size >= 9; size--)
            TryTour(size);

        // smallest grid to largest
        var orderedTours = Tours.OrderBy(x => x.Item2.Moves.Count);

        // group square boards by dimensions
        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);

        // group rectangular boards by dimensions
        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);

        // false = sized grid summary only, 
        // true  = every solution by grid size
        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)
    {
        // break the size into boxes
        var factors = getFactors(size).ToArray();

        if (factors.Length == 1)
            // square
            TryTour(new int[,] { { factors[0], factors[0] } }, size);
        else
            //rectangle
            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)
    {
        // try each location for a valid solution
        for (int start = 0; start < size; start++)
        {
            // try the normal grid
            TryTour(gridSize[0, 0], gridSize[0, 1], start);

            //try the inverted grid if failed
            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);

        //Prime to ensure correct timings...
        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 }))
        })
            // choose a reporting style format...
            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);

            //Prime to ensure correct timings...
            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; // show/hide
                break;

            case ConsoleKey.PageUp:
            case ConsoleKey.LeftArrow:
            case ConsoleKey.UpArrow:    // back

                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:  // forward

                if (knight.CanMoveNext)
                    UpdateLocation(knight.MoveNext());
                break;

            case ConsoleKey.Escape: // exit

                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!
   
v16
Comments
Maciej Los 13-Mar-17 17:41pm
   
Well, what to say to version 13? WOW!
5ed!
Graeme_Grant 13-Mar-17 19:35pm
   
Thanks! Chris did ask for "even higher feats of insanity"... :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 3

That was fun! My code and answer were growing really big, here's an article instead:
Knight's tour on a square chess board: coding challenge[^]
As a bonus, it can also draw a picture or animated GIF of the knight path :)
   
v2
Comments
Maciej Los 12-Mar-17 15:44pm
   
Great!
Thomas Daniels 12-Mar-17 16:28pm
   
Thank you!
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

Here's my solution based on shortest path algorithm:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KnightChess
{
    class KnightMove
    {
        public bool ChessToIndex(string sMove, ref int Row, ref int Col)
        {
            if ((sMove[0] >= 'A' && sMove[0] <= 'H') &&
                (sMove[1] >= '1' && sMove[1] <= '8'))
            {
                Col = System.Convert.ToInt32(sMove[0]) - 0x41;
                Row = System.Convert.ToInt32(sMove[1].ToString()) - 1;
        
                return true;
            }

            return false;
        }

        public bool IndexToChess(ref string sMove, int Row, int Col)
        {
            sMove += Convert.ToChar(Col + 0x41);
            sMove += Convert.ToString(Row + 1);

            return true;
        }
        public KnightMove(int Row, int Col)
        {
            this.Row = Row; this.Col = Col;
        }
        public KnightMove(string sMove)
        {
            int Row = -1, Col = -1;
            if (this.ChessToIndex(sMove, ref Row, ref Col) != false)
                this.Row = Row; this.Col = Col;
        }

        public int Row
        {
            get { return m_Row; }
            set { m_Row = value; }
        }
        public int Col
        {
            get { return m_Col; }
            set { m_Col = value; }
        }

        private int m_Row = -1;
        private int m_Col = -1;
    }

    class Corner
    {
        public Corner(KnightMove mv1, KnightMove mv2)
        {
            this.Move1 = mv1; this.m_Move2 = mv2;
        }

        public KnightMove Move1
        {
            get { return m_Move1; }
            set { m_Move1 = value; }
        }
        public KnightMove Move2
        {
            get { return m_Move2; }
            set { m_Move2 = value; }
        }

        private KnightMove m_Move1;
        private KnightMove m_Move2;
    }

    class KnightMoves : ICloneable
    {
        public KnightMoves() { }
        public KnightMoves(List<KnightMove> Path, int Length)
        {
            this.Path = Path; this.Length = Length;
        }

        public List<KnightMove> Path
        {
            get { return m_Path; }
            set { m_Path = value; }
        }

        public int Length
        {
            get { return m_Length; }
            set { m_Length = value; }
        }

        private int m_Length = -1;
        private List<KnightMove> m_Path = null;

        public object Clone()
        {
            KnightMoves Target_Moves = new KnightMoves();
            Target_Moves.m_Length = Length;
            Target_Moves.Path = new List<KnightMove>();
            foreach (KnightMove km in this.Path)
                Target_Moves.Path.Add(km);
            return Target_Moves;
        }
    }

    class KnightPaths : IEnumerable<KnightMoves>
    {
        private List<KnightMoves> m_PathList = null;
        public KnightPaths()
        {
            if (m_PathList == null)
                m_PathList = new List<KnightMoves>();
        }

        public KnightPaths(KnightPaths Knight_Path)
        {
            m_PathList = new List<KnightMoves>();
            foreach (KnightMoves km in Knight_Path)
                m_PathList.Add(km);
        }

        public void Add(KnightMoves Move)
        {
            m_PathList.Add(Move);
        }
        public KnightMoves this[int iIndex]
        {
            get { return m_PathList[iIndex]; }
            set { m_PathList[iIndex] = value; }
        }
        public int Count() { return m_PathList.Count(); }
        public void Clear() { m_PathList.Clear(); }

        public IEnumerator GetEnumerator()
        {
            return m_PathList.GetEnumerator();
        }
        IEnumerator<KnightMoves> IEnumerable<KnightMoves>.GetEnumerator()
        {
            return (IEnumerator<KnightMoves>)this.GetEnumerator();
        }
    }
    class Program
    {
        static bool IsValidMove(int value1, int value2, int PathID)
        {
            if ((value1 > value2) && (PathID == 0 || PathID == 1) ||
                (value1 < value2) && (PathID == 2 || PathID == 3)) return true;

            return false;
        }
        static bool IsValidPath(int Row1, int Col1, int Row2, int Col2, int PathID)
        {
            if (((((Row1 == 0 && Col1 == 5) &&
                   (Row2 == 1 && Col2 == 7)) ||
                  ((Row1 == 0 && Col1 == 6) &&
                   (Row2 == 2 && Col2 == 7))) && (PathID == 0)) ||
 
                ((((Row1 == 5 && Col1 == 7) &&
                   (Row2 == 7 && Col2 == 6)) ||
                  ((Row1 == 6 && Col1 == 7) &&
                   (Row2 == 7 && Col2 == 5))) && (PathID == 1)) ||

                ((((Row1 == 7 && Col1 == 2) &&
                   (Row2 == 6 && Col2 == 0)) ||
                  ((Row1 == 7 && Col1 == 1) &&
                   (Row2 == 5 && Col2 == 0))) && (PathID == 2)) ||

                ((((Row1 == 2 && Col1 == 0) &&
                   (Row2 == 0 && Col2 == 1)) ||
                   ((Row1 == 1 && Col1 == 0) &&
                   (Row2 == 0 && Col2 == 2))) && (PathID == 3))) return true;

            return false;
        }
        static void Main(string[] args)
        {
            string _StartMove = "";
            Console.Write("Start At: ");
            _StartMove = Console.ReadLine();

            Console.WriteLine();

            KnightPaths Knight_Paths = new KnightPaths();
            KnightMoves Knight_Moves = new KnightMoves();

            Knight_Moves.Path = new List<KnightMove>();

            Knight_Moves.Length = 1;
            Knight_Moves.Path.Add(new KnightChess.KnightMove(_StartMove));

            Knight_Paths.Add(Knight_Moves);

            KnightPaths Knight_Paths2 = new KnightPaths();

            List<Corner> Corners = new List<Corner>();
            Corners.Add(new Corner(new KnightMove(0, 5), new KnightMove(1, 7)));
            Corners.Add(new Corner(new KnightMove(0, 6), new KnightMove(2, 7)));

            Corners.Add(new Corner(new KnightMove(5, 7), new KnightMove(7, 6)));
            Corners.Add(new Corner(new KnightMove(6, 7), new KnightMove(7, 5)));

            Corners.Add(new Corner(new KnightMove(7, 2), new KnightMove(6, 0)));
            Corners.Add(new Corner(new KnightMove(7, 1), new KnightMove(5, 0)));

            Corners.Add(new Corner(new KnightMove(2, 0), new KnightMove(0, 1)));
            Corners.Add(new Corner(new KnightMove(1, 0), new KnightMove(0, 2)));

            var watch = new System.Diagnostics.Stopwatch();
            watch.Start();

            for (int PathID = 0; PathID < 4; PathID++)
            {
                for (int Route = 0; Route < Knight_Paths.Count(); Route++)
                {
                    KnightMoves CurrPath = Knight_Paths[Route];

                    if (Knight_Paths[Route].Path.Count() > 1)
                    {
                        if (IsValidPath(CurrPath.Path[Knight_Paths[Route].Path.Count() - 2].Row,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 2].Col,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col, PathID))
                        {
                            Knight_Paths2.Add(new KnightMoves(CurrPath.Path, CurrPath.Path.Count()));
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1) < 8) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2) < 8))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2)
                                Exists = true;

                        int value1 = 0, value2 = 0;
                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1) >= 0) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2) < 8))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2)
                                Exists = true;

                        int value1 = 0, value2 = 0;
                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1,
                                 CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1) < 8) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2) >= 0))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2)
                                Exists = true;

                        int value1 = 0, value2 = 0;
                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1,
                                 CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1) >= 0) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2) >= 0))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2)
                                Exists = true;

                        int value1 = 0, value2 = 0;

                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2) >= 0) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1) < 8))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1)
                                Exists = true;

                        int value1 = 0, value2 = 0;

                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2) >= 0) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1) >= 0))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1)
                                Exists = true;

                        int value1 = 0, value2 = 0;

                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 2,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2) < 8) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1) >= 0))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1)
                                Exists = true;

                        int value1 = 0, value2 = 0;

                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col - 1));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2) < 8) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1) < 8))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1)
                                Exists = true;

                        int value1 = 0, value2 = 0;

                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 2,
                                 CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 1));

                            Knight_Paths.Add(NewPath);
                        }
                    }
                }

                if (Knight_Paths2.Count() > 0)
                {
                    Knight_Paths = new KnightPaths(Knight_Paths2);
                    Knight_Paths2.Clear();
                }
            }

        var elapsed = watch.Elapsed;
        watch.Stop();

        int nCount = 0;
        for (int Index = 0; Index < Knight_Paths.Count(); Index++)
            {
                int Count = 0;
                KnightMoves CurrPath = Knight_Paths[Index];
                for (int Move = 0; Move < CurrPath.Path.Count() - 1; Move++)
                {
                    for (int nIndex = 0; nIndex < Corners.Count(); nIndex++)
                        Count = (Corners[nIndex].Move1.Row == CurrPath.Path[Move].Row &&
                            Corners[nIndex].Move1.Col == CurrPath.Path[Move].Col &&
                            Corners[nIndex].Move2.Row == CurrPath.Path[Move + 1].Row &&
                            Corners[nIndex].Move2.Col == CurrPath.Path[Move + 1].Col) ? Count + 1 : Count;
                }

                if (Count == 4)
                {
                    Console.Write("{0}. ", nCount);

                    for (int Move = 0; Move < CurrPath.Path.Count(); Move++)
                    {
                        string sMove = "";
                        CurrPath.Path[Move].IndexToChess(ref sMove, 
                            CurrPath.Path[Move].Row, CurrPath.Path[Move].Col);

                        Console.Write("({0};{1})", sMove[0], sMove[1]);
                    }

                    Console.WriteLine(" Moves = {0}", CurrPath.Path.Count());

                    nCount++;
                }
            }

            Console.WriteLine("Total = {0}", nCount);
            Console.WriteLine("Execution Time: {0:N6} msecs", elapsed.TotalMilliseconds);

            Console.ReadKey();
        }
    }
}


Output: (the following code provides the variety of different paths across a chess board touching all board's squares)
Start At: A1

0. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 14
1. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 14
2. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
3. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
4. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
5. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
6. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
7. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
8. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
9. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
10. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
11. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
12. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
13. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
14. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
15. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
16. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
17. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
18. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
19. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
20. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
21. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
22. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
23. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
24. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
25. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
26. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
27. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
28. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
29. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
30. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
31. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
32. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
33. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
34. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
35. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
36. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
37. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15
38. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
39. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
40. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
41. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
42. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
43. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
44. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
45. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
46. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
47. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
48. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
49. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 16
50. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
51. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
52. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
53. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
54. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
55. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
56. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
57. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
58. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
59. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
60. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
61. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
62. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
63. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
64. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
65. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
66. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
67. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
68. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
69. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
70. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
71. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
72. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
73. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
74. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
75. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
76. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
77. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
78. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
79. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 18
80. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
81. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
82. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
83. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
84. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
85. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
86. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
87. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
88. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
89. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
90. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
91. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
92. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
93. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
94. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
95. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 19
96. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
97. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
98. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
99. (A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
100. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
101. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
102. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
103. (A;1)(B;3)(C;5)(D;3)(E;5)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
104. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
105. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
106. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
107. (A;1)(B;3)(C;5)(D;7)(E;5)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 21
108. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 15
109. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 15
110. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 15
111. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 15
112. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
113. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
114. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
115. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
116. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
117. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
118. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
119. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
120. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
121. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
122. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
123. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
124. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
125. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
126. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 17
127. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 17
128. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
129. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
130. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
131. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
132. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
133. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
134. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
135. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
136. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
137. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
138. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
139. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
140. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
141. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
142. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(B;4)(A;2)(C;1) Moves = 19
143. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(B;5)(C;3)(A;2)(C;1) Moves = 19
144. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 16
145. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 16
146. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 16
147. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 16
148. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
149. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
150. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
151. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
152. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
153. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
154. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
155. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
156. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
157. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
158. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
159. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
160. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
161. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
162. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
163. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
164. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
165. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
166. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
167. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
168. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
169. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
170. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
171. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
172. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
173. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
174. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
175. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
176. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
177. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
178. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
179. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
180. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
181. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
182. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
183. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
184. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
185. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
186. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
187. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
188. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
189. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
190. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
191. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
192. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
193. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
194. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
195. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
196. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
197. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
198. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
199. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
200. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
201. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
202. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
203. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
204. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
205. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
206. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 17
207. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 17
208. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
209. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
210. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
211. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
212. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
213. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
214. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
215. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
216. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
217. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
218. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
219. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
220. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
221. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(E;7)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
222. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
223. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(D;7)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
224. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
225. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
226. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
227. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
228. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
229. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
230. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 18
231. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 18
232. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
233. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
234. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
235. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
236. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
237. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
238. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
239. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
240. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
241. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
242. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
243. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
244. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
245. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
246. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
247. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
248. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
249. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
250. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
251. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
252. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
253. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
254. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
255. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
256. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
257. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
258. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
259. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(G;5)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
260. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
261. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
262. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 19
263. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 19
264. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
265. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
266. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
267. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
268. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
269. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
270. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
271. (A;1)(C;2)(E;3)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
272. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
273. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
274. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
275. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(H;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
276. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
277. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;4)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
278. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(E;5)(C;4)(A;3)(B;1) Moves = 20
279. (A;1)(B;3)(D;2)(F;1)(H;2)(F;3)(D;4)(F;5)(H;6)(G;8)(F;6)(E;8)(D;6)(C;8)(A;7)(C;6)(A;5)(C;4)(A;3)(B;1) Moves = 20
280. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
281. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
282. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
283. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
284. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
285. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
286. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
287. (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
288. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
289. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
290. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
291. (A;1)(C;2)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
292. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
293. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
294. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
295. (A;1)(C;2)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
296. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
297. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
298. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
299. (A;1)(B;3)(D;4)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
300. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
301. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
302. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
303. (A;1)(B;3)(D;4)(E;2)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
304. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
305. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
306. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
307. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(H;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
308. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
309. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;4)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
310. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(E;4)(C;3)(A;2)(C;1) Moves = 21
311. (A;1)(B;3)(D;2)(F;3)(G;1)(H;3)(F;4)(D;5)(F;6)(H;7)(F;8)(E;6)(D;8)(C;6)(B;8)(A;6)(C;5)(A;4)(C;3)(A;2)(C;1) Moves = 21
Total = 312
Execution Time: 99,043500 msecs
   
v2
Comments
Thomas Daniels 11-Mar-17 7:55am
   
"Moves = 14" is impossible for an 8x8 board if you want to visit all squares. Am I missing something?
Arthur V. Ratz 11-Mar-17 8:04am
   
ProgramFox, all these two paths:

0. (A;1)(C;2)(E;3)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 14
1. (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 14

*ARE* *VALID*. The first and second paths really touch all squares:

(F;1), (H;2) - 1st corner
(H;6), (G;8) - 2nd corner
(C;8), (A;7) - 3rd corner
(A;3), (B;1) - 4th corner

That's all. If you've got any more comments or questions, just post your message.
Thomas Daniels 11-Mar-17 8:19am
   
I don't understand it. Touching all squares on a 3x3 board means that you have 63 moves, right? Just 'moving over a square with the knight' does not count as 'touching', if that's what you did here.
Arthur V. Ratz 11-Mar-17 8:43am
   
if it's not, what does it mean "to touch a square" unless otherwise ??
Thomas Daniels 11-Mar-17 8:54am
   
Touching a square means that the square is used as the begin-point and end-point of a new knight hop. See the GIFs on this Wikipedia page to see what I mean: https://en.wikipedia.org/wiki/Knight's_tour
Graeme_Grant 11-Mar-17 9:21am
   
It is simple, chess rules apply...
Arthur V. Ratz 11-Mar-17 8:10am
   
And also, I believe that my solution is rather efficient since it allows to select the most appropriate path from the variety of all possible paths found by the code I've suggested.
Arthur V. Ratz 11-Mar-17 8:14am
   
The variety of paths produced by the following code also includes the complete path given in question e.g.:

Example:

Start at: A1
Solution: A1 – B3 – C5 etc

Answer: Here's that:
(A;1)(B;3)(C;5)(D;3)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 17
PIEBALDconsult 11-Mar-17 8:42am
   
A knight doesn't "touch" the squares it jumps over.
And if it _did_, I'm sure you must have many multiple-touches in there.
Arthur V. Ratz 11-Mar-17 8:45am
   
I've already got multiple touches, for example: (F;1),(H;2) and (G;1), (H;3).

For example: (A;1)(B;3)(D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3)(B;1) Moves = 14 - touches (F;1), (H;2),

whereas (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2)(C;1) Moves = 15 - touches (G;1),(H;3).

Arthur V. Ratz 11-Mar-17 8:47am
   
I mean there's already multiple paths that include upper right corner of the chess board, hovering the knight over the either (F;1), (H;2) or (G;1), (H;3).
PIEBALDconsult 11-Mar-17 8:50am
   
Knights don't "hover". Only the places where the knight comes to rest after a move matter.
Arthur V. Ratz 11-Mar-17 8:45am
   
Multiple opinions ? That's good.
Graeme_Grant 11-Mar-17 8:53am
   
8 x 8 grid has a fixed number of moves - 8 x 8 - 1 = 63 (not including the starting square). Now the path taken is a different story... ;)
Arthur V. Ratz 11-Mar-17 9:01am
   
No that's wrong. Normally chess table 8x8 has about 26,534,728,821,064 directed closed tours. I refer to https://en.wikipedia.org/wiki/Knight's_tour
Thomas Daniels 11-Mar-17 9:04am
   
Yes, that's the count of different closed tours. But one closed tour consists of 1 starting square and 63 moves.
Arthur V. Ratz 11-Mar-17 9:06am
   
I'm sorry, but Graeme_Grant has stated that 8 x 8 grid has a fixed number of moves - 8 x 8 - 1 = 63...
Thomas Daniels 11-Mar-17 9:08am
   
And he's right. But that's the fixed number of moves for a single knight tour.
Arthur V. Ratz 11-Mar-17 9:10am
   
According to the problem statement, there's no matter how many moves the knight makes, but it's supposed to touch all corners. In the other words, the number of moves cannot be a correctness criteria for this particular case.
Graeme_Grant 11-Mar-17 9:13am
   
There is no mention of corners, only knight hop over a chessboard so it touches all squares, but that knight may never use the same spot twice, not adjacent to.
PIEBALDconsult 11-Mar-17 9:21am
   
Where does it say "touch all corners"?
Graeme_Grant 11-Mar-17 9:10am
   
...which is the requirement of the challenge. ;)
Arthur V. Ratz 11-Mar-17 9:12am
   
The number of moves cannot be the challenge requirement. There was not a word about that.
Graeme_Grant 11-Mar-17 9:14am
   
No, but implied by touching all squares, not corners...
Arthur V. Ratz 11-Mar-17 8:54am
   
Oh, Probably you're not understanding it. If the knight is supposed to touch a square at the point where it comes to rest, you'll never build a path in which the knight's touching all squares this way.
Graeme_Grant 11-Mar-17 8:56am
   
"knight hop over a chessboard so it touches all squares" - more information on this can be found here: Knight's tour - Wikipedia[^]
PIEBALDconsult 11-Mar-17 9:17am
   
Correct, and newbies should also note that the knight jumps _straight_ from one space to the next; _not_ in an L-shape.
Graeme_Grant 11-Mar-17 9:19am
   
just with a lean, not perpendicular.. ;)
Arthur V. Ratz 11-Mar-17 9:20am
   
yes, that's right.
Arthur V. Ratz 11-Mar-17 9:19am
   
Nobody is in doubt that. In my solution the knight jumps straight, for instance: (F;1) -> (H;2) and so on.
Arthur V. Ratz 11-Mar-17 9:05am
   
I'm sorry, but I also refer to Wikipedia's article too, but by reading this article I didn't find that it was mentioned directly. I refer to the animated chess board illustrating knight's moves. It still normally touches all corners by touches both sides of a corner. Look more carefully at this.
Graeme_Grant 11-Mar-17 9:09am
   
Draw a grid 8 x 8, put an X in every cell that your solution finds. If any cells are empty, then it did not pass the test.
PIEBALDconsult 11-Mar-17 9:12am
   
"Touch" means "land on", not "land beside" or "hover over".
Arthur V. Ratz 11-Mar-17 9:12am
   
yes, definitely, to "hover over".
Graeme_Grant 11-Mar-17 9:15am
   
We are just trying to help you... Do it your way and we will learn the outcome in a few days...
Arthur V. Ratz 11-Mar-17 9:17am
   
I'm sorry, but this is only solution to this problem I have found. I've got no more ways to solve this problem but this.
Graeme_Grant 11-Mar-17 9:24am
   
Just in case you have not played chess before: A Quick Summary of the Rules of Chess[^] - Note how the Knight moves as opposed to a Bishop or Queen...
Arthur V. Ratz 11-Mar-17 9:26am
   
It normally is able to make 8 moves. And so what ?
Graeme_Grant 11-Mar-17 9:28am
   
I've asked Chris to give clarification as to what "touches" exactly means. Hopefully he will update the challenge notes shortly.
Arthur V. Ratz 11-Mar-17 9:30am
   
O'key. No problem. I'll take into account the latest problem's update.
Arthur V. Ratz 11-Mar-17 9:28am
   
As far as I can understand, according to your theory the knight cannot touch all squares by stopping for a rest at each of the four squares in the chess board. That's impossible.
Graeme_Grant 11-Mar-17 9:29am
   
Map out on a grid the steps/moves in my solution and you will see that it is not.
Arthur V. Ratz 11-Mar-17 9:33am
   
I'm sorry but you've made a mistake D-4, E-2, G-1, H-2, G-5, H-6, F-8, G-6, H-7, F-7, H-5, G-8, E-7, C-8, A-7, B-5, A-3, B-1, C-3, A-2, C-1, B-3, A-1, C-2, E-1, G-2, H-3, F-3, H-1, F-1, D-2, E-4, G-3, H-0, F-2, D-1, B-2, A-4, B-6, A-8, C-7, E-8, G-7, H-4, F-4, E-6, D-8, B-7, D-6, F-5, E-3, D-5, F-6, G-4, E-5, C-4, A-5, C-6, B-8, D-7, C-5, D-3, B-4, A-6

The knight cannot move from G-1 to H-2. Just check with a chess board. :D
Graeme_Grant 11-Mar-17 9:36am
   
Yeah, sorry about that, spotted an hour ago. There is an error in my string override mapping for outputting the solution. The solution is correct though. I have an update pending for when I complete what I am working on but I'll do it now. Give me a couple of minutes and I'll have it updated...

[edit:] updated with correction to output...
Member 14361425 9-May-19 11:36am
   
https://gamesroute.com/how-to-play-chess/
Graeme_Grant 11-Mar-17 9:14am
   
:D
Graeme_Grant 11-Mar-17 9:31am
   
Hey, will we be seeing a solution from you this week?
Arthur V. Ratz 11-Mar-17 9:34am
   
What solution are you expecting to see ? For this problem, I've already posted a solution (see Solution 2).
Arthur V. Ratz 11-Mar-17 9:35am
   
As I've already explained that there's no appropriates solution in which the knight stops in all four corners of the chess board.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 5

Well, ummm, my solution is not complete. The problem isn't really interesting to me, but I have a brute-force exhaustive backtracking implementation that, in theory, can find all tours. Given a 6x6 board, it found what it says are all the tours from square (0,0) in about an hour. But, given a chess board (8x8), it has been running for two days and has not reported any results yet.

All I'm really prepared to say at this time is that I use a Graph (Network) of Nodes, not a two-dimensional representation of the board. No recursion either.

I'm not interested in finding a tour or any tour, I'm looking for a closed tour and I'm too lazy to transcribe one from the Net; I want to find one myself.

A Closed Knight's Tour from any square is a Closed Knight's Tour from every square.

Anyway, my plan for a solution to the Challenge is:
Given (well, not given, as stated above) a Closed Knight's Tour of a Chess Board...
Hard code that tour and simply use it every time.
Whatever square is specified as the starting place, start there on the hard-coded tour, and tour.
Done
(I'll try to keep you updated on that.)

Having said that, and having a Graph traversing implementation, I am now considering generalizing my code to address more general questions of traversing Graphs. In fact, there is a puzzle from the mid-80s that I completely failed to solve, which comes to mind occasionally (like a white whale), and I think I might be able to apply this technique to it.


Update: After running for a full week -- using 100% of one virtual CPU -- my code found no tours at all. Time to kill it and find the problem...
   
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web01 | 2.8.190518.1 | Last Updated 21 Mar 2017
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100