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

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

Ú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;
    }
  }
}