Problema Nebunilor

Cerință: Se dau N nebuni și o tablă de șah de dimensiune NxN. Să se găsească toate modalitățile de a aranja toți nebunii astfel încât oricare doi nebuni să nu se atace. Doi nebuni se atacă dacă se află pe aceeași 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 nebunilor pe tabla de șah este o problemă clasică de backtracking. Metoda de rezolvare cu backtracking presupune generarea tuturor soluțiilor si testarea lor daca sunt valide sau nu. Un nebun poate fi plasat pe tabla de șah daca pentru fiecare nebun aranjat deja, acesta nu se afla pe aceeași diagonala 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 (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 nebunul nr. ” & i & ” pe linia ” & x(i) & ” si coloana ” & i)
Next i
Console.ReadLine()
End Sub

    Sub Main()
Console.WriteLine(“Problema Nebunilor”)
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

Rezultat: