Solving Towers of Hanoi in C# using recursion

Question

I'm facing the Towers of Hanoi problem, I read the concept and the recursive way of solving it from wikipedia, but I can not see what I'm missing in the implementation of the steps mentioned in wikipedia.

I have seen many examples here but I don't want my program to print the steps, I want the program solves the problem moving the "discs" between 3 collections, in my code I'm using 3 Stacks to simulate the pegs.

Here is my current code:

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

class Program
{
    static void Main(string[] args)
    {
        var hs = new HanoiSolver(discs: 3);

        hs.Solve();

        Console.ReadKey();
    }
}

class HanoiSolver
{
    private int TotalDiscs { get; set; } = 0;
    private Stack<int> FirstPeg { get; set; } = new Stack<int>();
    private Stack<int> SecondPeg { get; set; } = new Stack<int>();
    private Stack<int> ThirdPeg { get; set; } = new Stack<int>();

    public HanoiSolver(int discs = 3)
    {
        TotalDiscs = discs;

        //Create list of items (discs)
        var discList = Enumerable.Range(1, TotalDiscs).Reverse();

        //Add items (discs) to first peg
        foreach (var d in discList)
        {
            FirstPeg.Push(d);
        }
    }

    public void Solve()
    {
        if (ThirdPeg.Count != TotalDiscs)
        {
            PrintPegs();

            //Move first item from firstpeg to secondpeg
            if (FirstPeg.Any())
            {
                var fp_f = FirstPeg.Pop();
                SecondPeg.Push(fp_f);
            }

            PrintPegs();

            //Move second item from firstpeg to thirdpeg
            if (FirstPeg.Any())
            {
                var fp_s = FirstPeg.Pop();
                ThirdPeg.Push(fp_s);
            }

            PrintPegs();

            //Move first item from secondpeg to thirdpeg
            if (SecondPeg.Any())
            {
                var sp_f = SecondPeg.Pop();
                ThirdPeg.Push(sp_f);
            }

            PrintPegs();

            Solve();
        }
    }

    private void PrintPegs()
    {
        var fp = FirstPeg.Select(x => x.ToString()).ToList();

        if (fp.Count < TotalDiscs)
        {
            fp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - fp.Count)));
        }

        var sp = SecondPeg.Select(x => x.ToString()).ToList();

        if (sp.Count < TotalDiscs)
        {
            sp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - sp.Count)));
        }

        var tp = ThirdPeg.Select(x => x.ToString()).ToList();

        if (tp.Count < TotalDiscs)
        {
            tp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - tp.Count)));
        }

        Console.WriteLine($"{"[First Peg]",10}" + $"{"[Second Peg]",10}" + $"{"[Third Peg]",10}");

        for (var i = 0; i < TotalDiscs; i++)
        {
            Console.WriteLine($"{fp[i],10}" +
                              $"{sp[i],10}" +
                              $"{tp[i],10}");
        }
    }
}

Answer 1

In order to make a recursive method you need one or more base cases where the recursion will end and then one or more recursive calls that break the problem down closer to one of the base cases. For Towers of Hanoi the idea is that moving n discs from Peg A to Peg C is just moving n-1 from Peg A to Peg B, then moving the nth from A to C and finally moving the n-1 discs from C to B. That will eventually get you down to moving no discs which is your base case. That can be done in a recursive method very simply like this.

private static void Move(
    int discs, 
    Stack<int> fromPeg, 
    Stack<int> toPeg, 
    Stack<int> otherPeg)
{
    if (discs == 0)
    {
        return;
    }

    Move(discs - 1, fromPeg, otherPeg, toPeg);

    toPeg.Push(fromPeg.Pop());

    Move(discs -1, otherPeg, toPeg, fromPeg);
}

Answer 2

When you are implementing TOH, this means you are new to DS and data types. So one must use the data type which is not present in DS like stack and queue. So the below approach is using array.

using System; using static System.Console; namespace TOH {

class Program
{
    // Problem statement
    //Create an array tower(a) containing all element in ascending order

    public static int[] towerSource = new int[] { 1, 3, 5,6,7,9,11,12,13,14,15,16,17};

    //solution statement
    //we have two more towers with same capacity, tower(b) as auxiliary and tower(c) as destination
    public static int[] towerAuxiliary;
    public static int[] towerDestination;

    public static void CreateTowers()
    {
        towerAuxiliary = new int[towerSource.Length];
        towerDestination = new int[towerSource.Length];
    }

    public static void Print(int[] tower)
    {
        for (int i = 0; i < tower.Length; i++)
            Write(tower[i].ToString());
        WriteLine("--------next run-------------");
    }       
    //start operation
    public static void TOH(int numberOfDisks, int[] source,int[] auxiliary,int[] destination)
    {
        //check if there is only one disk in source
        if(numberOfDisks == 1)
        {
            //move to destination and come out
            towerDestination[numberOfDisks-1] = towerSource[numberOfDisks-1];
            Print(towerDestination);
            return;
        }

        //move n-1 disks from source to auxiliary
        TOH(numberOfDisks - 1, towerSource, towerAuxiliary, towerDestination);
        towerDestination[numberOfDisks-1] = towerSource[numberOfDisks-1];

        //move nth disc from source to dest
        //this is being handeled by if condition

        //move n-1 disks from auxiliary to dest
        TOH(numberOfDisks - 1, towerAuxiliary, towerSource, towerDestination);

        return;
    }


    static void Main(string[] args)
    {
        CreateTowers();
        TOH(towerSource.Length, towerSource, towerAuxiliary, towerDestination);
    }
}

}