Utilizzo di una struttura dei dati dell'albero in VBA

Question

Sto ottenendo più familiarità con VBA e sto tentando di eseguire un programma di apprendimento automatico per TIC TAC Toe. Non voglio solo il codice duro delle possibilità di vincere.

Il meglio che ho inventato per un programma di apprendimento della macchina è quello di avere una struttura ad albero con tutte le mosse possibili che possono essere fatte, quindi hanno il computer tagliare i rami dell'albero ogni volta che perde con quel ramo. .

Ad esempio con il seguente modo di denotare dove le persone hanno giocato, e l'ordine le lettere sono scritte come l'ordine il gioco ha progredito

a|b|c
-----
d|e|f
-----
g|h|i

.

abdgfce - significa che il computer vince, A è stato giocato per primo, B Secondo, D Terzo ....

Vorrei avere un albero di dati che sembra:

Livello 0: A (il computer inizia sempre con A)

Livello 1: tutte le lettere tranne A, come è già stato giocato

Livello 2: per ogni lettera di livello 0, tutte le lettere tranne quella a destra prima di esso e A

E così via per tutti i livelli dell'albero fino a quando non sono più mosse possibili.

Ho provato a cercare modi per implementare questa struttura in VBA ma il sito Web Microsoft non era di aiuto e i forum parlano solo di alberi binari o ordinanti. Qualcuno mi indicherebbe nella giusta direzione o dammi alcuni puntatori di cosa dovrei provare? Qual è un modo migliore per risolvere questo problema se questa soluzione non è fattibile?

Grazie,

karim

Answer 1

Ci sono "solo" 362.880 vie per riempire i nove posti in una tabella TIC-TAC-TOE.Il set completo può essere generato nella colonna A posizionando:

abcdefghi

in cella B1 e in esecuzione GetString ():

Dim ll As Long
Dim CurrentRow As Long

Sub GetString()
    Dim InString As String
    InString = Sheets("Sheet1").Range("B1")
    ActiveSheet.Columns(1).Clear
    CurrentRow = 1
    Application.ScreenUpdating = False
        Call GetPermutation("", InString)
    Application.ScreenUpdating = True
End Sub

Sub GetPermutation(x As String, y As String)
    '   The source of this algorithm is unknown
    Dim i As Long, j As Long
    j = Len(y)
    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
End Sub

.

Certamente, la maggior parte dei giochi finirà prima che tutti i nove posti siano riempiti.Se il computer perde, tale articolo viene rimosso, ecc.

Edit # 1:

wayne G. dunn ha suggerito che il numero di varianti può essere ridotto.Il computer (giocatore n. 1) ha nove posti possibili che posizionano il suo x. giocatore # 2 ha otto possibili posti per posizionarle o. ecc.

Questo rendisce 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 o 9 fattoriale.

Tuttavia, il gioco può finire prima che tutti i nove posti siano riempiti.Quindi molte delle varianti 362880 possono essere scartate ............ Solo non so quanti.