This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Paardensprong probleem - Olga Coutrin

By: a guest on Dec 16th, 2010  |  syntax: C#  |  size: 4.85 KB  |  views: 206  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace PaardenSprongProbleem
  7. {
  8.     class Paardensprong
  9.     {
  10.         // Velden
  11.         private int[,] schaakbord;
  12.         private int count;
  13.  
  14.         // Dit is een 2-dimensionale array met de X en Y afstanden dat een paard mag springen
  15.         // Normaal zou dit een constante moeten zijn maar C# geeft dan een compile-error omdat je geen array als constante mag declareren :S
  16.         private int[,] sprongen = { { -1, 2 }, { 1, 2 }, { -2, 1 }, { -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, 1 }, { 2, -1 } };
  17.  
  18.  
  19.         public Paardensprong(int size, int pos1, int pos2)
  20.         {
  21.             // Initializeer
  22.             schaakbord = new int[size, size];
  23.  
  24.             // Zet alles op 0
  25.             for (int i = 0; i < size; i++)
  26.             {
  27.                 for (int j = 0; j < size; j++)
  28.                     schaakbord[i, j] = 0;
  29.             }
  30.  
  31.             // Dit is de "start-conditie", het begint op de ingegeven positie en die 1 is de huidige stap (de eerste stap dus)
  32.             Try(pos1, pos2, 1);
  33.         }
  34.  
  35.  
  36.         // Deze methode controleert of een paard op die plaats mag staan.
  37.         // Dit mag enkel als het paard binnen de grenzen staat en niet al eens is langs geweest
  38.         private bool checkPosition(int x, int y)
  39.         {
  40.             // Dit is de beginvoorwaarde, eindvoorwaarde en controle of het paard er al eens is langs geweest
  41.             // De begin- en eindvoorwaarde MOETEN voor de controle komen of het paard er al is langs geweest.
  42.             // In C# wordt er immers "gestopt" als het een foute conditie tegenkomt.
  43.             // Hiermee voorkom je dat de compiler eerst gaat controleren op schaakbord[x, y] en zo voorkom je dus een ArrayIndexOutOfBound weet-ik-veel exception
  44.             return (x >= 0) && (y >= 0) && (x < schaakbord.GetLength(0)) && (y < schaakbord.GetLength(1)) && (schaakbord[x, y] == 0);
  45.         }
  46.  
  47.  
  48.         // Deze methode controleert of het paard al langs alle vakjes is geweest, dwz dat overal een waarde staat BEHALVE 0
  49.         private bool checkAllFields()
  50.         {
  51.             bool isOk = true;
  52.  
  53.             for (int i = 0; i < schaakbord.GetLength(0); i++)
  54.             {
  55.                 for (int j = 0; j < schaakbord.GetLength(1); j++)
  56.                     isOk &= (schaakbord[i, j] != 0);
  57.             }
  58.             return isOk;
  59.         }
  60.  
  61.  
  62.         // Dit is dezelfde methode als hierboven maar recursief, gewoon als dikke show off dat ik recursie ken...
  63.         // Het principe is eenvoudig, elke keer dat deze methode uitgevoerd wordt, gaat het de controle uitvoeren voor die plaats
  64.         // en de methode opnieuw oproepen voor het vakje rechts ervan en eronder en zo gaat dat verder totdat je aan de grenzen komt
  65.         private bool checkAllFieldsRecursive(int x, int y)
  66.         {
  67.             if ((x == schaakbord.GetLength(0)) || (y == schaakbord.GetLength(1)))
  68.                 return true;
  69.             return (schaakbord[x, y] != 0) && checkAllFieldsRecursive(x, y + 1) && checkAllFieldsRecursive(x + 1, y);
  70.         }
  71.            
  72.  
  73.  
  74.         // Dit is zoals Olga het noemt "het hart van je programma", dit is de recursieve methode die alles doet
  75.         public void Try(int x, int y, int step)
  76.         {
  77.             // Controle of het paard hier mag staan
  78.             if (checkPosition(x, y))
  79.             {
  80.                 // De stap uitvoeren
  81.                 schaakbord[x, y] = step;
  82.  
  83.                 // Controleren of het paard langs alle velden is geweest
  84.                 if (checkAllFieldsRecursive(0, 0))
  85.                         printSteps();
  86.                 // Zoniet, laat het paard verder springen
  87.                 else
  88.                 {
  89.                     // Deze lus gaat alle mogelijke sprongen af en probeert de methode Try opnieuw voor deze sprongen
  90.                     for (int i = 0; i < sprongen.GetLength(0); i++)
  91.                         Try(x + sprongen[i, 0], y + sprongen[i, 1], step + 1);
  92.                 }
  93.  
  94.                 // Dit is dat backtracking-gedoe... hier wordt de huidige positie terug op 0 gezet
  95.                 // Dit gebeurt als je een succesvolle oplossing gevonden hebt of vast zit
  96.                 schaakbord[x, y] = 0;
  97.             }
  98.         }
  99.  
  100.         // 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
  101.         private void printSteps()
  102.         {
  103.             count++;
  104.             Console.WriteLine("Oplossing " + count + ":");
  105.             for (int i = 0;i < schaakbord.GetLength(0);i++)
  106.             {
  107.                 for (int j = 0;j < schaakbord.GetLength(1);j++)
  108.                     Console.Write(String.Format("{0, 3}", schaakbord[i, j]));
  109.                 Console.WriteLine();
  110.             }
  111.             Console.WriteLine();
  112.         }
  113.     }
  114. }
clone this paste RAW Paste Data