Diskusia – 8 dam (konzolová aplikácie) v .NET

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

Mediel

Tvůrce

Mediel:1.11.2012 22:21

Já ti nevim, ten algoritmus je nejaky divny... A z tohohle kodu se mi to lustit nechce. Ale kazdopadne ti to funguje dobre...

Odpovedať

1.11.2012 22:21

Nechci vám ukazovat, jak dobrý jsem já ... Chci vám ukázat, jak dobrý můžete být vy ... Když uvěříte ... V sami sebe...

Petr Laštovička

Tvůrce

Petr Laštovička:23.4.2013 0:28

Úloha 8 dam je typický příklad na využití rekurze. Lze to zobecnit a rozmísťovat N dam na šachovnici NxN.

using System;
namespace ConsoleApplication
{
  class _8DAM
  {
    static int N, N1;
    static int[] Column;
    static bool[] DiagU, DiagV;
    static long Total, Unique;

    //parametrem je rozmer sachovnice
    static void Main(string[] args)
    {
      if (args.Length == 1) int.TryParse(args[0], out N);
      if (N == 0) N = 8;
      N = Math.Max(4, Math.Min(20, N));
      N1 = N - 1;
      Column = new int[N];
      DiagU = new bool[2 * N];
      DiagV = new bool[2 * N];
      for (int i = 0; i < N; i++) Column[i] = -1;
      Backtrack(0);
      Console.WriteLine("Pocet dam: " + N);
      Console.WriteLine("Pocet vsech reseni: " + Total);
      Console.WriteLine("Pocet unikatnich reseni: " + Unique);
    }

    static void Backtrack(int row)
    {
      if (row < N)
      {
        for (int i = 0; i < N; i++)
          if (Column[i] < 0 && !DiagU[i + row] && !DiagV[i - row + N1])
          {
            Column[i] = row; //pridej damu na sachovnici
            DiagU[i + row] = true;
            DiagV[i - row + N1] = true;
            Backtrack(row + 1); //rekurze
            Column[i] = -1; //odeber damu ze sachovnice
            DiagU[i + row] = false;
            DiagV[i - row + N1] = false;
          }
      }
      else
      {
        Total++;
        if (TestUnique()) //vypis pouze unikatni reseni
        {
          Console.Write("{0}. reseni: ", ++Unique);
          for (int j = 0; j < N; j++)
            Console.Write("{0}{1} ", (char)('A' + j), Column[j] + 1);
          Console.WriteLine();
        }
      }
    }

    static bool TestUnique()
    {
      //porovnej toto reseni se vsemi symetrickymi (otoceni, zrcadleni)
      for (int sym = 0; sym < 7; sym++)
        //porovnavej sloupce zleva doprava, dokud se obe reseni shoduji
        for (int i = 0; i < N; i++)
        {
          int a = Column[i];
          int b = 0;
          switch (sym)
          {
            case 0: b = N1 - Column[N1 - i]; break;
            case 1: b = N1 - Array.IndexOf<int>(Column, i); break;
            case 2: b = Array.IndexOf<int>(Column, N1 - i); break;
            case 3: b = N1 - a; break;
            case 4: b = Column[N1 - i]; break;
            case 5: b = Array.IndexOf<int>(Column, i); break;
            case 6: b = N1 - Array.IndexOf<int>(Column, N1 - i); break;
          }
          if (a > b) return false;
          if (a < b) break;
        }
      return true;
    }
  }
}

Odpovedať

23.4.2013 0:28

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – 8 dam (konzolová aplikácie) v .NET