Problema Damelor

Cerință: Se dau N dame și o tablă de șah de dimensiune NxN. Să se găsească toate modalitățile de a aranja toate damele astfel încât oricare două dame să nu se atace. Două dame se atacă dacă se află pe aceeași linie, coloană sau diagonală. Se cere să se afișeze prima soluție în ordine lexicografică și numărul total de soluții.

Indicații de rezolvare

Aranjarea damelor pe tabla de șah este o problema clasica de backtracking. Metoda de rezolvare cu backtracking presupune generarea tuturor soluțiilor si testarea lor daca sunt valide sau nu. O dama poate fi plasata pe tabla de șah daca pentru fiecare dama aranjata deja, aceasta nu se afla pe aceeași coloana, linie sau diagonala cu niciuna dintre ele. Pentru a optimiza algoritmul, pentru fiecare dama de pe tabla de șah, se va marca, folosind vectori auxiliari linia, coloana si diagonala pe care este plasata aceasta. Astfel se poate verifica in complexitate O(1) daca o dama poate fi pusa sau nu pe tabla de șah la o anumita poziție.

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace RegineCS
{
    class Program
    {
        static bool ConditiiContinuare(int[]x,int k)
        {
            bool atac = false;
            int i = 1;
            while (!atac && i < k)
                if (x[i] == x[k] || k - i == Math.Abs(x[k] - x[i]))
                    atac = true;
                else
                    i++;
            return !atac;
        }
 
        static void ScrieSolutia(int[]x,int n,int nsol)
        {
            Console.WriteLine("Solutia " + nsol + " este: ");
          
            for (int i = 1; i <= n; i++)
            {
                Console.WriteLine("Asezati regina nr. " + i + " pe linia " + x[i] + " si pe coloana " + i);
            }
            Console.ReadLine();
        }
 
        static void Main(string[] args)
        {
            int n, k,nsol;
            bool buna;
            int [] x = new int[50];
            Console.WriteLine("Problema reginelor");
            Console.Write("Dati numarul n ");
            n = Convert.ToInt32(Console.ReadLine());
            k = 1;
            x[k] = 0;
            nsol = 0;
            while (k > 0)
            {
                buna = false;
                while (!buna && x[k] <n)
                {
                    x[k]++;
                    if (ConditiiContinuare(x,k))
                        buna = true;
                }
                if (buna)
                    if (k == n)
                    {
                        nsol++;
                        ScrieSolutia(x, n,nsol);
                    }
                    else
                    {
                        k++;
                        x[k] = 0;
                    }
                else
                    k--;
            }
        }
    }
}

Cod Sursa VB

Imports System.Math
Module Module1
    Dim x(51) As String
    Dim n, k, nsol As Integer
    Dim buna As Boolean
 
    Function ConditiiContinuare(ByVal k As Integer)
        Dim atac As Boolean
        atac = False
        Dim i As Integer
        i = 1
        While (Not atac And i < k)
            If (x(i) = x(k) Or k - i = Math.Abs(x(k) - x(i))) Then
                atac = True
            Else
                i = i + 1
            End If
        End While
        Return Not atac
    End Function
 
    Sub ScrieSolutie()
        nsol = nsol + 1
        Console.WriteLine("Solutia " & nsol & " este: ")
        For i = 1 To n
            Console.WriteLine(" Asezati regina nr. " & i & " pe linia " & x(i) & " si coloana " & i)
        Next i
        Console.ReadLine()
    End Sub
 
    Sub Main()
        Console.WriteLine("Problema Reginelor")
        Console.Write("Dati numarul n: ")
        n = Convert.ToInt32(Console.ReadLine())
        k = 1
        x(k) = 0
        nsol = 0
        While (k > 0)
            buna = False
            While (Not buna And x(k) < n)
                x(k) = x(k) + 1
                If (ConditiiContinuare(k)) Then
                    buna = True
                End If
            End While
            If (buna) Then
                If (k = n) Then
                    ScrieSolutie()
                Else
                    k = k + 1
                    x(k) = 0
                End If
            Else
                k = k - 1
            End If
        End While
    End Sub
 
End Module

Cod Sursa C++

// OptRegineCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include 
#include 
 
using namespace std;
 
int x[51];
int k, n, nsol;
bool buna;
 
bool ConditiiContinuare(int k)
{
     // aici testam ca regina k sa nu se atace 
     // pe linie sau pe diagonala cu vreuna 
     // din reginele dinaintea sa
     bool atac=false; 
     int i=1;
     while (!atac && i<k)
           if (x[i]==x[k] || k-i==abs(x[k]-x[i])) 
	//doar prima conditie pentru ture si doar a doua conditie pentru nebuni
              atac=true;
           else i++;
     return !atac;
}
 
void ScrieSolutia()
{
     nsol++;
     cout<<"Solutie "<<nsol<<" este:\n";
     for (int i=1; i<=n; i++)
	 {
         cout<<"  Asezati regina nr. "<<i<<" pe linia "
             <<x[i]<<" si coloana "<<i<<"\n";
		 //cout<<x[i]; //pentru generarea permutarilor
	 }
	 //system("pause");
     getchar();
}
 
int main()
{
    cout<<"Problema reginelor\n";
    cout<<"Dati numarul n: ";
    cin>>n;
    k=1; // plecam cu prima regina
    x[k]=0; // asezam regina aceasta sub tabla
    nsol=0; // numarul de solutii
    while (k>0) // cat timp inca mai avem regine pe tabla
      {
          buna=false; // deocamdata regina nu sta bine acolo
          // cat timp pozitia curenta nu e buna si regina
          // mai poate fi dusa cu o linie mai sus
          while (!buna && x[k]<n)
                {
                  // mut regina mai sus cu un rand/o linie
                  x[k]++; 
                  // testez conditiile de continuare k->k+1
                  if (ConditiiContinuare(k)) buna=true;
                  
                }
          if (buna) // daca varianta pentru regina k este buna...
             if (k==n) // daca am ajuns la ultima regina...
                 ScrieSolutia(); // atunci afisam solutia
             else // daca nu am ajuns la ultima, 
                  {
                    k++; // trecem la urmatoarea regina
                    x[k]=0; // si o asezam sub tabla
                  }
          else
              k--; // daca nu (mai) gasim o varianta buna
              // atunci ne intoarcem la regina anterioara
      }   
	
}

Rezultat: