Premessa
Nella conclusione del precedente articolo, consideravo desiderabile la funzionalità di creare uno schema in modo automatico, ammettendo la mia difficoltà a implementarla.
Questo secondo articolo descrive come ho migliorato in tal senso il programma.
Teoria
Il fatto è che non concepivo la costruzione di uno schema come 'ricerca brutale', con una serie di tentativi 'ciechi', ma volevo implementare uno sviluppo per tentativi 'intelligenti' e limitati. Però non riuscivo a escogitare il sistema per 'tornare indietro' a rifare qualche passo.
Internet
Poiché avevo riconosciuto che mi mancava qualcosa, ho cercato in rete se qualcuno aveva messo a disposizione il proprio sorgente di creazione di uno schema di sudoku.
Ho dapprima trovato il sorgente in C++ del sudoku contenuto nella suite Portable Software/USB di SourceForge. In esso si esegue una costruzione 'brutale', però funziona, quindi l'ho scaricato e messo da parte.
Proseguendo la ricerca, ho trovato il sorgente in VB.Net di The ANZAC (Sudoku Algorithm: Generates a valid Sudoku in 0.0452 seconds) su CodeProject. In esso si esegue la costruzione intelligente che cercavo, con la fondamentale caratteristica di saper tornare indietro. Com'era da aspettarsi, la trovata è semplicissima, ancorché geniale. L'ho provata e ha funzionato. Quindi mi sono messo ad analizzarla per adattarla al mio programma.
Le modifiche
Il codice di Anzac sfrutta una struttura con i dati di ciascuna cella. Io ne ho cambiato nome e membri:
Public Structure Cella
Dim Riga As Integer
Dim Colonna As Integer
Dim Quadrante As Integer
Dim Valore As Integer
Dim Indice As Integer
End Structure
Di questa struttura sono fatti gli elementi di un vettore usato nella preparazione dello schema valido di sudoku nel metodo che io ho modificato e chiamato NewMatrix. Ho cambiato anche altri nomi, per capire il codice caso mai dovessi manutenerlo, ho tolto un Goto A che non mi piaceva per niente e ho fatto in modo che restituisse il vettore così creato.
La parte 'intelligente' sta nel vettore rimasti: per ogni cella sono 'leciti' dei numeri e altri no. Quindi si fornisce all'inizio una dotazione di partenza dei numeri leciti (tutti), da cui si rimuovono quelli non più leciti. Questo accorcia molto lo sviluppo perché diminuisce molto il numero dei tentativi falliti.
Annullare un tentativo è semplicissimo, si porta indietro il puntatore al tentativo corrente, ripristinando i dati della cella precedente e ricostruendo la dotazione iniziale di rimasti per la cella correntemente puntata. Più facile da leggere il codice, che spiegarlo.
Public Function NewMatrix() As Cella()
Dim celle(80) As Cella
Dim rimasti(80) As List(Of Integer)
Dim c As Integer = 1
Dim caso As New Random
For i As Integer = c To rimasti.Length - 1
rimasti(i) = New List(Of Integer)
For n As Integer = 1 To 9
rimasti(i).Add(n)
Next
Next
Do Until c = 81
Dim back As Boolean = False
Do
Dim i As Integer = 0
If rimasti(c).Count > 0 Then
i = caso.Next(0, rimasti(c).Count - 1)
End If
back = False
If Not rimasti(c).Count = 0 Then
Dim n As Integer = rimasti(c).Item(i)
If Conflicts(celle, Item(c, n)) = False Then
celle(c) = Item(c, n)
rimasti(c).RemoveAt(i)
c += 1
Else
rimasti(c).RemoveAt(i)
back = True
End If
Else
For n As Integer = 1 To 9
rimasti(c).Add(n)
Next
celle(c - 1) = Nothing
c -= 1
back = True
End If
Loop While back
Loop
Return celle
End Function
Quando si deve controllare se il numero casuale va bene, si valorizza una 'cella ipotetica':
Private Function Item(ByVal n As Integer, ByVal v As Integer) As Cella
Dim r, c, q As Integer ' riga e colonna e quadrante
Dim r1, q1 As Integer ' prime caselle di riga e quadrante
n += 1
r = n \ 9 + CType(IIf(n Mod 9 > 0, 1, 0), Integer)
c = n Mod 9 + CType(IIf(n Mod 9 = 0, 9, 0), Integer)
r1 = (r - 1) * 9 + 1
q1 = (r1 \ 27) * 27 + 1 + 3 * ((c - 1) \ 3)
q = 1 + (q1 \ 27) * 3 + (q1 Mod 27) \ 3
Item.Riga = r
Item.Colonna = c
Item.Quadrante = q
Item.Valore = v
Item.Indice = n - 1
End Function
In questo codice ho inserito i calcoli per trovare riga, colonna e quadrante di una cella, invece di usare i metodi appositamente sviluppati da The Anzac.
Questa cella ipotetica viene passata al metodo di controllo di conflitto, assieme al vettore che viene via via riempito:
Private Function Conflicts(ByVal CurrentValues As Cella(), ByVal test As Cella) As Boolean
For Each s As Cella In CurrentValues
If s.Riga <> 0 AndAlso s.Riga = test.Riga AndAlso s.Valore = test.Valore Then
Return True
End If
Next
For Each s As Cella In CurrentValues
If s.Colonna <> 0 AndAlso s.Colonna = test.Colonna AndAlso s.Valore = test.Valore Then
Return True
End If
Next
For Each s As Cella In CurrentValues
If s.Quadrante <> 0 AndAlso s.Quadrante = test.Quadrante AndAlso s.Valore = test.Valore Then
Return True
End If
Next
Return False
End Function
Questo bel lavoro di The Anzac - anche se i tempi non sono sempre quelli fantastici promessi su codeproject - viene sfruttato nel metodo che crea effettivamente lo schema di gioco:
Private Sub CreateNewSchema()
Dim i As Integer, title As String = Me.Text
Me.Text = "wait a moment..."
ClearCells()
For i = 1 To 81
cells(i).Visible = False
Next
Dim grid() As Cella = NewMatrix()
Dim totalCells As Integer = 42 - (7 * mDifficulty)
Dim caso As New Random
i = 0
Do While i < totalCells
Dim x As Integer = caso.Next(1, 82)
If cells(x).Text = "" Then
cells(x).Text = grid(x - 1).Valore.ToString
i += 1
End If
Loop
Me.Text = title
For i = 1 To 81
cells(i).Visible = True
Next
mbMode = True
LockCells()
End Sub
Non ho trovato un metodo che visualizzasse qualcosa per indicare che il programma sta lavorando (un WaitCursor, per esempio), così ho cambiato il titolo alla finestra. Poi ho svuotato e nascosto i pulsanti e ottenuto il vettore di celle dal metodo NewMatrix.
A questo punto interviene una mia ulteriore complicazione: il calcolo del numero delle celle visualizzate nello schema secondo un grado di difficoltà che all'inizio è medio. E' un'idea tratta dal codice C++, che faceva però una graduatoria diversa. Segue l'estrazione casuale delle caselle di cui valorizzare Text con il relativo numero tratto dal vettore ottenuto da Newmatrix.
In seguito a ciò non resta che ripristinare il testo della finestra, visualizzare tutte le celle, impostare la modalità gioco e gelare la situazione.
I nuovi menu
Ho quindi aggiunto, al menu New, cinque sottomenu, uno per ciascun grado di difficoltà e l'ultimo per la modalità setup. Sono contrassegnabili con il segno di spunta, per informare l'utente.
Tutto questo ha creato due inconvenienti: il menu rimaneva aperto per tutta la durata della creazione dello schema e il segno di spunta dell'impostazione precedente non spariva (chissà perché, mi figuravo che un insieme di sottomenu si comportasse come un insieme di opzioni). Per ovviare a ciò ho preparato un metodo di appoggio:
Private Sub UncheckMnuNew(ByVal currentMenu As MenuItem)
Static previous As MenuItem = mnuMedium
previous.Checked = False
previous = currentMenu
Me.Refresh()
End Sub
Sfruttando una variabile statica, che all'inizio ha il valore del menu corrispondente alla difficoltà di default, tolgo il segno di spunta dal menu precedente, assegno alla variabile il menu attuale e rinfresco la form, facendo sparire il brutto effetto di 'programma piantato'.
Fatto ciò, sostituire il metodo che gestiva il clic sul menu New con quelli che gestiscono i suoi vari sottomenu diventa un giochetto:
Private Sub mnuEasy_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) _
Handles mnuEasy.Click
UncheckMnuNew(mnuEasy)
mnuEasy.Checked = True
mDifficulty = 0
CreateNewSchema()
End Sub
Private Sub mnuMedium_Click(ByVal sender As Object, ByVal e As System.EventArgs) _
Handles mnuMedium.Click
UncheckMnuNew(mnuMedium)
mnuMedium.Checked = True
mDifficulty = 1
CreateNewSchema()
End Sub
Private Sub mnuHard_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) _
Handles mnuHard.Click
UncheckMnuNew(mnuHard)
mnuHard.Checked = True
mDifficulty = 2
CreateNewSchema()
End Sub
Private Sub mnuImpossible_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) _
Handles mnuImpossible.Click
UncheckMnuNew(mnuImpossible)
mnuEasy.Checked = True
mDifficulty = 3
CreateNewSchema()
End Sub
Private Sub mnuManual_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) _
Handles mnuManual.Click
UncheckMnuNew(mnuManual)
mbMode = False
ClearCells()
End Sub
Conclusione
Per finire, non mi è restato che completare il menu Instructions, cambiare il numero di versione nelle proprietà del progetto, compilare quest'ultimo e anche quello per il file cab, prima di godermi il mio nuovo programma sul mio Omnia.
Naturalmente, ho sostituito il file scaricabile dall'area download. Buon divertimento!