Software Programming

Kunuk Nykjaer

Backtracking – Knight’s Tour with C#

leave a comment »


Here’s an example of backtracking algorithm implemented in C#.
This solves the Knight’s Tour

program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

/// <summary>
/// Author: Kunuk Nykjaer
/// Backtracking Algorithm in C#
/// Knight's Tour on NxN board
/// </summary>
public class Program
{
    static readonly Action<object> Write = Console.Write;
    static readonly Func<ConsoleKeyInfo> Read = Console.ReadKey;

    // Composition root
    static void Main(string[] args)
    {        
        // Use timer for checking algo time
        var sw = new Stopwatch();
        sw.Start();

        // Init board and set size
        var board = new Board(5, Write);

        // Init config
        var config = new Config
        {
            MaxSolutions = 1,
            ShowBoardProgress = false,
            ShowStatus = true,
            DetectCodeError = false
        };

        // Init data
        var P = new Data(config);

        // Init backtrack algo
        var bt = new Backtrack(board, Write, P);

        // Find solutions
        bt.Run();

        // Algo done, stop time
        sw.Stop();

        // Show results
        bt.Show();

        Write(string.Format("\nSec: {0}\nPress a key to exit\n",
            sw.ElapsedMilliseconds / 1000d));

        Read();
    }
}

class Backtrack
{
    readonly Board _board;
    readonly Action<object> _write;
    private readonly Data _p;    

    public Backtrack(Board board, Action<object> write, Data P)
    {
        _board = board;
        _write = write;        
        _p = P;
    }

    void UndoLastMove(Data P)
    {
        P.RemoveLast();

        // Debug
        if (!P.ExitBacktrack && P.Config.ShowBoardProgress)
        {
            _board.Print(P.Path);
        }
    }

    void UpdatePath(Data P, Vector c)
    {
        if (c == null)
        {
            throw new ArgumentNullException("c");
        }

        Cell last = P.Path.Last();
        Cell visit = last.AddVector(c);

        P.Add(visit);

        // Debug
        if (!P.ExitBacktrack && P.Config.ShowBoardProgress)
        {
            _board.Print(P.Path);
        }
    }

    /*     
    wikipedia:
    http://en.wikipedia.org/wiki/Backtracking
     
    procedure bt(P,c)
        if reject(P,c) then return        
        if accept(P,c) then output(P,c)                                  
        s ← first(P,c)
        while s ≠ Λ do
            bt(P,s)
            s ← next(P,s)
        end while
      
        // backtrack starts here 
     end procedure
    */

    // O(?)
    void Bt(Data P, Vector c)
    {
        if (Reject(P, c)) { return; }

        // Add path data
        UpdatePath(P, c);

        // Debug
        DebugEpoch(P, c);

        if (Accept(P)) { SaveResult(P); }

        var s = First(P);

        while (s != null)
        {
            Bt(P, s);
            s = Next(P, s);
        }

        // Leaf, dead end, backtrack, roll back path data
        UndoLastMove(P);
    }

    // O(1)
    bool Accept(Data P)
    {
        // Accept condition
        if (P.Path.Count >= _board.Size * _board.Size)
        {
            return true;
        }
        return false;
    }

    // O(1)
    bool Reject(Data P, Vector c)
    {
        // Custom early exit
        if (P.ExitBacktrack)
        {
            return true;
        }

        if (c == null)
        {
            return true;
        }

        Cell last = P.Path.Last(); // last visit
        Cell candidate = last.AddVector(c); // consider candidate
        if (P.Visited.Contains(candidate))
        {
            return true;
        }

        return !_board.IsInsideBoard(candidate);
    }

    void DebugEpoch(Data P, Vector c)
    {
        if (P.ExitBacktrack)
        {
            return;
        }

        // Debug
        if (P.Config.ShowStatus && P.PathTried.Count % 200000 == 0)
        {
            _write(string.Format("PathTried: {0:n0}, Solutions: {1}\n",
                P.PathTried.Count, P.Solutions.Count));
        }
    }

    public void Run()
    {
        Cell init = new Cell(0, 0); // init pos
        _p.Add(init);

        Vector first = First(_p);
        Bt(_p, first);
    }

    public void Show()
    {
        _write("\n-----------------\n");
        foreach (var s in _p.Solutions)
        {
            _board.Print(s);
            _write("-----------------\n");
        }
        _write(string.Format("\nPaths tried: {0:n0}\n", _p.PathTried.Count));
        _write(string.Format("\nSolutions found: {0}\n", _p.Solutions.Count));
    }

    // O(n) where n is path length
    void SaveResult(Data P)
    {
        P.Solutions.Add(P.Path.ToList());
        if (P.Solutions.Count >= P.Config.MaxSolutions)
        {
            P.ExitBacktrack = true;
        }
    }

    // First valid child from path
    // O(1)
    Vector First(Data P)
    {
        Cell last = P.Path.Last();
        IList<Vector> moves = _board.GetValidMoves(last);

        return moves.FirstOrDefault(v => !P.Visited.Contains(last.AddVector(v)));
    }

    // Next sibling from current leaf
    // O(1)
    Vector Next(Data P, Vector c)
    {
        return _board.Next(c);
    }
}

class XY
{
    public int X { get; set; }
    public int Y { get; set; }

    public XY(int x, int y)
    {
        X = x;
        Y = y;
    }

    public override int GetHashCode()
    {
        return ToString().GetHashCode();
    }
    public override string ToString()
    {
        return string.Format("[{0},{1}]", X, Y);
    }
    public override bool Equals(object obj)
    {
        var other = obj as XY;
        if (other == null) { return false; }

        return GetHashCode() == other.GetHashCode();
    }
}

// Position on board
class Cell : XY
{
    public Cell(int x, int y) : base(x, y) { }
}

// Move definition
class Vector : XY
{
    private static int _count;
    public int Id { get; private set; }
    public Vector(int x, int y)
        : base(x, y)
    {
        Id = _count++;
    }
}

class Board
{
    // Define move of Knight
    private static readonly Vector[] Moves = new[] { 
        new Vector(2, 1), 
        new Vector(1, 2),
        new Vector(-1, 2), 
        new Vector(-2, 1),
        new Vector(-2, -1), 
        new Vector(-1, -2),
        new Vector(1, -2),
        new Vector(2, -1)
    };

    private void CleanBoard()
    {
        // clearn
        foreach (var i in _board)
        {
            for (var j = 0; j < i.Length; j++)
            {
                i[j] = "--";
            }
        }
    }

    // Updating display data
    private void UpdateBoard(IList<Cell> path)
    {
        CleanBoard();
        for (var i = 0; i < path.Count; i++)
        {
            Cell p = path[i];
            _board[p.Y][p.X] = i.ToString("00");
        }
    }

    // Next movement
    public Vector Next(Vector m)
    {
        if (m.Id >= Moves.Length - 1)
        {
            return null;
        }
        return Moves[m.Id + 1];
    }

    public int Size { get; private set; }
    private readonly string[][] _board;
    private readonly Action<object> _write;
    public Board(int size, Action<object> write)
    {
        Size = size;
        _write = write;

        // Board is only used for printing display
        _board = new string[Size][];

        for (var i = 0; i < _board.Length; i++)
        {
            _board[i] = new string[Size];
        }
    }

    // O(1) because Moves.Count is always 8
    // Get valid moves within board
    public List<Vector> GetValidMoves(Cell c)
    {
        return Moves.Where(a => IsInsideBoard(c.AddVector(a))).ToList();
    }

    // O(1)
    public bool IsInsideBoard(Cell c)
    {
        return c.X >= 0 && c.X < Size && c.Y >= 0 && c.Y < Size;
    }

    public void Print(List<Cell> p)
    {
        UpdateBoard(p);

        _write("\n");
        foreach (var y in _board)
        {
            foreach (var x in y)
            {
                _write(x + " ");
            }
            _write("\n\n");
        }
    }
}

class Data
{
    public bool ExitBacktrack { get; set; }
    public Config Config;

    public readonly List<Cell> Path = new List<Cell>();
    public readonly HashSet<Cell> Visited = new HashSet<Cell>();
    public readonly List<List<Cell>> Solutions = new List<List<Cell>>();
    public readonly HashSet<string> PathTried = new HashSet<string>();

    public Data(Config config)
    {
        Config = config;
    }

    // O(1)
    public void RemoveLast()
    {
        Cell cell = Path.Last(); // O(1)
        if (Config.DetectCodeError && !Visited.Contains(cell))
        {
            throw new ApplicationException("Can't remove not added cell");
        }
        Visited.Remove(cell); // O(1)
        Path.RemoveAt(Path.Count - 1); // O(1) remove last
    }

    // O(1) or O(n)
    public void Add(Cell cell)
    {
        if (Config.DetectCodeError && Visited.Contains(cell))
        {
            throw new ApplicationException("Can't add duplicate visited cell");
        }
        Visited.Add(cell);
        Path.Add(cell);

        // O(n)
        // Catch error in code, but expensive to use in running time
        if (Config.DetectCodeError)
        {
            var path = Path.GetString();
            if (PathTried.Contains(path))
            {
                throw new Exception("Error, path already tried");
            }
            PathTried.Add(path);
        }
        //O(1)
        else
        {
            PathTried.Add((PathTried.Count + 1).ToString());
        }

    }
}

class Config
{
    public int MaxSolutions { get; set; }
    public bool ShowBoardProgress { get; set; }
    public bool ShowStatus { get; set; }
    public bool DetectCodeError { get; set; } // cost running time if true
}

static class Extensions
{
    public static string GetString<T>(this IEnumerable<T> arr)
    {
        return arr.Aggregate("", (a, b) => a + "->" + b);
    }
    public static Cell AddVector(this Cell c, Vector v)
    {
        return new Cell(c.X + v.X, c.Y + v.Y);
    }
}

Examples:

Knight’s Tour on a 5 x 5 board

00 13 18 07 24

05 08 01 12 17

14 19 06 23 02

09 04 21 16 11

20 15 10 03 22
-----------------

Paths tried: 8,840
Sec: 0.202

below 1 sec. for first result.

Knight’s Tour on a 6 x 6 board

00 33 16 31 22 35

15 24 01 34 17 30

06 11 32 23 02 21

25 14 07 20 29 18

10 05 12 27 08 03

13 26 09 04 19 28
-----------------

Paths tried: 248,169
Sec: 6.024

About 6 seconds for first result.

Knight’s Tour on a 7 x 7 board

00 31 38 27 40 23 48

37 28 01 24 21 26 41

30 19 32 39 02 47 22

07 36 29 20 25 42 03

18 15 08 33 44 11 46

35 06 13 16 09 04 43

14 17 34 05 12 45 10
-----------------

Paths tried: 7,151,179
Sec: 155.465

About 2.5 minutes for first result.

Knight’s Tour on a 8 x 8 board

00 37 58 35 42 47 56 51

59 34 01 48 57 50 43 46

38 31 36 41 02 45 52 55

33 60 39 26 49 54 03 44

30 09 32 61 40 25 22 53

17 62 27 10 23 20 13 04

08 29 18 15 06 11 24 21

63 16 07 28 19 14 05 12
-----------------

Paths tried: 8,250,733
Sec: 186.499

About 3 minutes for first result.

Advertisements

Written by kunuk Nykjaer

December 23, 2012 at 10:47 am

Posted in Algorithm, Csharp

Tagged with , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: