Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement