[Algo] Esercizio BackTracking

[Pablitos23]

Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le matrici n×n con valori in {a, b, c} tali che due elementi adiacenti (per riga o colonna) abbiano valori differenti. Ad esempio se n = 2, le matrici da stampare sono:

ab  ab  ab  ac  ac  ac  ba  ba  ba  bc  bc  bc  ca  ca  ca  cb  cb  cb 
ba  bc  ca  ca  cb  ba  ab  ac  cb  cb  ca  ab  ac  ab  bc  bc  ba  ac

La complessità dell'algoritmo deve essere O(n2S(n)), dove S(n) è il numero di matrici da stampare.

La mia idea sarebbe quella di non memorizzare l'array in un array bidimensionale, ma in un array monodimensionale.
Lo pseudocodice potrebbe essere:

Matrix( n:lato matrix , h: lunghezza pref. , S: array )
   if nxn == h then
      print(S , n)
   else
      for i<-1 to nxn do
         for y in {a,b,c} do
            if ( isSafe( S , y ) ) then
               S[h+1] <- y
               Matrix( n, h+1, S )

print( S:array, n: dimensione lato )
   for i<-1 to nxn do
      print(S[i])
      if ( i%n == 0 ) then print(\n)

Adesso mi manca la procedura isSafe per controllare che è possibile aggiungere l'elemento in quella posizione.
Può andare come algoritmo? Rispetta la complessità ?

Buona domenica

[apatriarca]

Siccome stai inserendo i valori una riga per volta è sufficiente guardare il valore precedente sulla riga (stando attento al caso in cui sia nella prima colonna) e quello precedente nella colonna. Mi sembra possa andare bene.

[Pablitos23]

Penso così possa andare.

isSafe( S: array stringa, y: lettera da inserire, h: index, n: lato matrix ) -> boolean
  
   boolean f = true

   if h>1 and S[h-1] == y then f = false
   else if h>n and S[h-n] == y then f = false

   return false

La chiamata ad isSafe nella funzione matrix sarà:

isSafe(S,y,h+1,n)

Vanno bene le condizioni? Avrei potuto anche congiungerle con un or.

[apatriarca]

Direi che devi restituire \(f\). Se no così sarà sempre falsa..

[Pablitos23]

Chiedo venia è stato un errore di distrazione. Si conclude quindi con

return f

.