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.
Ú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;
}
}
}
Zobrazené 2 správy z 2.