Paardensprong probleem - Olga Coutrin

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

namespace PaardenSprongProbleem
{
    class Paardensprong
    {
        // Velden
        private int[,] schaakbord;
        private int count;

        // Dit is een 2-dimensionale array met de X en Y afstanden dat een paard mag springen
        // Normaal zou dit een constante moeten zijn maar C# geeft dan een compile-error omdat je geen array als constante mag declareren :S
        private int[,] sprongen = { { -1, 2 }, { 1, 2 }, { -2, 1 }, { -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, 1 }, { 2, -1 } };


        public Paardensprong(int size, int pos1, int pos2)
        {
            // Initializeer
            schaakbord = new int[size, size];

            // Zet alles op 0
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                    schaakbord[i, j] = 0;
            }

            // Dit is de "start-conditie", het begint op de ingegeven positie en die 1 is de huidige stap (de eerste stap dus)
            Try(pos1, pos2, 1);
        }


        // Deze methode controleert of een paard op die plaats mag staan.
        // Dit mag enkel als het paard binnen de grenzen staat en niet al eens is langs geweest
        private bool checkPosition(int x, int y)
        {
            // Dit is de beginvoorwaarde, eindvoorwaarde en controle of het paard er al eens is langs geweest
            // De begin- en eindvoorwaarde MOETEN voor de controle komen of het paard er al is langs geweest.
            // In C# wordt er immers "gestopt" als het een foute conditie tegenkomt.
            // Hiermee voorkom je dat de compiler eerst gaat controleren op schaakbord[x, y] en zo voorkom je dus een ArrayIndexOutOfBound weet-ik-veel exception
            return (x >= 0) && (y >= 0) && (x < schaakbord.GetLength(0)) && (y < schaakbord.GetLength(1)) && (schaakbord[x, y] == 0);
        }


        // Deze methode controleert of het paard al langs alle vakjes is geweest, dwz dat overal een waarde staat BEHALVE 0
        private bool checkAllFields()
        {
            bool isOk = true;

            for (int i = 0; i < schaakbord.GetLength(0); i++)
            {
                for (int j = 0; j < schaakbord.GetLength(1); j++)
                    isOk &= (schaakbord[i, j] != 0);
            }
            return isOk;
        }


        // Dit is dezelfde methode als hierboven maar recursief, gewoon als dikke show off dat ik recursie ken...
        // Het principe is eenvoudig, elke keer dat deze methode uitgevoerd wordt, gaat het de controle uitvoeren voor die plaats
        // en de methode opnieuw oproepen voor het vakje rechts ervan en eronder en zo gaat dat verder totdat je aan de grenzen komt
        private bool checkAllFieldsRecursive(int x, int y)
        {
            if ((x == schaakbord.GetLength(0)) || (y == schaakbord.GetLength(1)))
                return true;
            return (schaakbord[x, y] != 0) && checkAllFieldsRecursive(x, y + 1) && checkAllFieldsRecursive(x + 1, y);
        }


        // Dit is zoals Olga het noemt "het hart van je programma", dit is de recursieve methode die alles doet
        public void Try(int x, int y, int step)
        {
            // Controle of het paard hier mag staan
            if (checkPosition(x, y))
            {
                // De stap uitvoeren
                schaakbord[x, y] = step;

                // Controleren of het paard langs alle velden is geweest
                if (checkAllFieldsRecursive(0, 0))
                        printSteps();
                // Zoniet, laat het paard verder springen
                else
                {
                    // Deze lus gaat alle mogelijke sprongen af en probeert de methode Try opnieuw voor deze sprongen
                    for (int i = 0; i < sprongen.GetLength(0); i++)
                        Try(x + sprongen[i, 0], y + sprongen[i, 1], step + 1);
                }

                // Dit is dat backtracking-gedoe... hier wordt de huidige positie terug op 0 gezet
                // Dit gebeurt als je een succesvolle oplossing gevonden hebt of vast zit
                schaakbord[x, y] = 0;
            }
        }

        // Dit print de oplossing af... je kan ook een controle op count invoeren zodat er maar 1 oplossing gegeven word maar het is leuker om alle oplossingen te zien
        private void printSteps()
        {
            count++;
            Console.WriteLine("Oplossing " + count + ":");
            for (int i = 0;i < schaakbord.GetLength(0);i++)
            {
                for (int j = 0;j < schaakbord.GetLength(1);j++)
                    Console.Write(String.Format("{0, 3}", schaakbord[i, j]));
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
}