Problema Turnurilor

Cerință:

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

Indicație de rezolvare:

Aranjarea turnurilor 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. Un turn poate fi plasat pe tabla de șah daca pentru fiecare turn aranjat deja, acesta nu se afla pe aceeași coloana sau linie cu niciunul dintre ei.

Implementare:

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)) 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 tura nr. " & i & " pe linia " & x(i) & " si coloana " & i)
        Next i
        Console.ReadLine()
    End Sub
 
    Sub Main()
        Console.WriteLine("Problema Turelor")
        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++

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <cmath>
 
using namespace std;
 
int x[51];
int k, n, nsol;
bool buna;
 
bool ConditiiContinuare(int k)
{
     // aici testam ca tura k sa nu se atace 
     // pe linie sau pe diagonala cu vreuna 
     // din turele dinaintea sa
     bool atac=false; 
     int i=1;
     while (!atac && i<k)
           if (x[i]==x[k])
              atac=true;
           else i++;
     return !atac;
}
 
void ScrieSolutia()
{
     nsol++;
     cout<<"Solutie "<<nsol<<" este:\n";
     for (int i=1; i<=n; i++)
         cout<<"  Asezati tura nr. "<<i<<" pe linia "
             <<x[i]<<" si coloana "<<i<<"\n";
     getchar();
}
 
int main()
{
    cout<<"Problema turelor\n";
    cout<<"Dati numarul n: ";
    cin>>n;
    k=1; // plecam cu prima tura
    x[k]=0; // asezam tura aceasta sub tabla
    nsol=0; // numarul de solutii
    while (k>0) // cat timp inca mai avem ture pe tabla
      {
          buna=false; // deocamdata tura nu sta bine acolo
          // cat timp pozitia curenta nu e buna si tura
          // mai poate fi dusa cu o linie mai sus
          while (!buna && x[k]<n)
                {
                  // mut tura 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 tura k este buna...
             if (k==n) // daca am ajuns la ultima tura...
                 ScrieSolutia(); // atunci afisam solutia
             else // daca nu am ajuns la ultima, 
                  {
                    k++; // trecem la urmatoarea tura
                    x[k]=0; // si o asezam sub tabla
                  }
          else
              k--; // daca nu (mai) gasim o varianta buna
              // atunci ne intoarcem la tura anterioara
      }          
}    
 

Rezultat: