Chciałem zobaczyć odpowiedzi na to (obecnie nieistniejące) pytanie , ale nigdy nie zostało ono poprawione / poprawione.

Biorąc pod uwagę zestaw 6-stronnych kostek Boggle (konfiguracja skradziona z tego pytania ), określ w ciągu dwóch minut czasu przetwarzania, która konfiguracja planszy pozwoli uzyskać najwyższy możliwy wynik. (tj. które kości, w której lokalizacji, z której strony do góry pozwala na największą pulę słów punktowanych?)

CEL

• Twój kod powinien działać przez nie więcej niż 2 minuty (120 sekund). W tym czasie powinien automatycznie przestać działać i wydrukować wyniki.

• Ostatecznym wynikiem wyzwania będzie średni wynik Boggle z 5 przebiegów programu.

  • W przypadku remisu zwycięzcą zostanie wybrany algorytm, który znajdzie więcej słów.
  • W przypadku remisu zwycięzcą zostanie wybrany algorytm, który znajdzie więcej długich (8+) słów.

ZASADY / OGRANICZENIA

• To jest wyzwanie kodowe; długość kodu nie ma znaczenia.

• Odwołaj się do tego linku, aby uzyskać listę słów (użyj ISPELL "english.0"listy - na liście SCOWL brakuje niektórych dość popularnych słów).

  • Ta aukcja może być odsyłana / importowana / czytana w twoim kodzie w dowolny sposób.
  • Liczone ^([a-pr-z]|qu){3,16}$będą tylko słowa pasujące do wyrażenia regularnego . (Jedynie małe litery, 3-16 znaków, qu muszą być użyte jako jednostka.)

• Słowa powstają przez połączenie sąsiednich liter (poziomej, pionowej i ukośnej), aby przeliterować słowa we właściwej kolejności, bez użycia jednej kości więcej niż raz w jednym słowie.

  • Słowa muszą składać się z 3 liter lub więcej; krótsze słowa nie przyniosą punktów.
  • Duplikaty liter są dopuszczalne, ale nie kości.
  • Słowa, które rozciągają się między krawędziami / krzyżują się z jednej strony planszy na drugą, są niedozwolone.

• Ostateczny wynik Boggle ( nie wyzwanie ) to suma wartości punktowych dla wszystkich znalezionych słów.

  • Wartość punktowa przypisana do każdego słowa zależy od jego długości. (patrz poniżej)
  • Normalne zasady Boggle odejmują / dyskontują słowa znalezione przez innego gracza. Załóżmy, że nie bierze w tym udziału żaden inny gracz, a wszystkie znalezione słowa liczą się do całkowitego wyniku.
  • Jednak słowa znalezione więcej niż jeden raz w tej samej siatce należy liczyć tylko raz.

• Twoja funkcja / program musi ZNAJDŹ układ optymalny; zwykłe zakodowanie z góry ustalonej listy nie wystarczy.

• Twój wynik powinien stanowić siatkę 4x4 idealnej planszy do gry, listę wszystkich znalezionych słów dla tej planszy oraz wynik Boggle odpowiadający tym słowom.

KONFIGURACJA UMIERA

A  A  E  E  G  N
E  L  R  T  T  Y
A  O  O  T  T  W
A  B  B  J  O  O
E  H  R  T  V  W
C  I  M  O  T  U
D  I  S  T  T  Y
E  I  O  S  S  T
D  E  L  R  V  Y
A  C  H  O  P  S
H  I  M  N  Qu U
E  E  I  N  S  U
E  E  G  H  N  W
A  F  F  K  P  S
H  L  N  N  R  Z
D  E  I  L  R  X

STANDARDOWY TABELA PUNKTOWANIA BOGGLE

Word length => Points
<= 2 - 0 pts
   3 - 1  
   4 - 1  
   5 - 2  
   6 - 3  
   7 - 5
>= 8 - 11 pts
*Words using the "Qu" die will count the full 2 letters for their word, not just the 1 die.

PRZYKŁADOWA WYDAJNOŚĆ

A  L  O  J  
V  U  T  S  
L  C  H  E  
G  K  R  X

CUT
THE
LUCK
HEX
....

140 points

Jeśli potrzebne są dalsze wyjaśnienia, zapytaj!

C, średnio 500+ 1500 1750 punktów

Jest to stosunkowo niewielka poprawa w stosunku do wersji 2 (patrz uwagi na temat poprzednich wersji poniżej). Istnieją dwie części. Po pierwsze: Zamiast losowego wybierania plansz z puli, program wykonuje teraz iterację po każdej planszy w puli, używając każdej z nich przed powrotem na szczyt puli i powtarzania. (Ponieważ pula jest modyfikowana podczas tej iteracji, nadal będą deski wybierane dwa razy z rzędu lub gorzej, ale nie jest to poważny problem.) Druga zmiana polega na tym, że program śledzi teraz zmiany puli , a jeśli program działa zbyt długo bez poprawiania zawartości puli, określa, że ​​wyszukiwanie „utknęło w martwym punkcie”, opróżnia pulę i zaczyna od nowa. Nadal robi to, dopóki nie miną dwie minuty.

Początkowo myślałem, że zastosuję jakieś wyszukiwanie heurystyczne, aby wyjść poza zakres 1500 punktów. Komentarz @ mellamokb na temat 4527-punktowej tablicy doprowadził mnie do wniosku, że jest dużo miejsca do poprawy. Używamy jednak stosunkowo małej listy słów. Tablica z 4527 punktami zdobywała punkty za pomocą YAWL, która jest najbardziej inkluzywną listą słów dostępną na rynku - jest nawet większa niż oficjalna lista słów Scrabble w USA. Mając to na uwadze, ponownie zbadałem tablice znalezione przez mój program i zauważyłem, że wydaje się, że istnieje ograniczony zestaw tablic powyżej około 1700. Na przykład miałem wiele przebiegów, które odkryły tablicę z wynikiem 1726, ale zawsze była to dokładnie ta sama tablica, która została znaleziona (ignorując obroty i odbicia).

Jako kolejny test uruchomiłem mój program, używając YAWL jako słownika, i po kilkunastu uruchomieniach znalazłem tablicę 4527-punktową. Biorąc to pod uwagę, wysuwam hipotezę, że mój program znajduje się już w górnej granicy przestrzeni wyszukiwania, a zatem planowane przeze mnie przepisywanie wprowadziłoby dodatkową złożoność przy bardzo niewielkim zysku.

Oto moja lista pięciu najlepszych tablic, które mój program znalazł za pomocą listy english.0słów:

1735 :  D C L P  E I A E  R N T R  S E G S
1738 :  B E L S  R A D G  T I N E  S E R S
1747 :  D C L P  E I A E  N T R D  G S E R
1766 :  M P L S  S A I E  N T R N  D E S G
1772:   G R E P  T N A L  E S I T  D R E S

Wierzę, że „grep board” z 1772 r. (Jak to nazywałem), z 531 słowami, jest tablicą z największą liczbą możliwych punktów przy tej liście słów. Ponad 50% dwuminutowych uruchomień mojego programu kończy się na tej płycie. Zostawiłem też program uruchomiony na noc, nie znajdując nic lepszego. Więc jeśli istnieje tablica o wyższej punktacji, prawdopodobnie musiałaby mieć jakiś aspekt, który pokona technikę wyszukiwania programu. Na przykład plansza, w której każda możliwa mała zmiana układu powoduje ogromny spadek wyniku, może nigdy nie zostać wykryta przez mój program. Mam przeczucie, że taka tablica prawdopodobnie nie istnieje.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#define WORDLISTFILE "./english.0"

#define XSIZE 4
#define YSIZE 4
#define BOARDSIZE (XSIZE * YSIZE)
#define DIEFACES 6
#define WORDBUFSIZE 256
#define MAXPOOLSIZE 32
#define STALLPOINT 64
#define RUNTIME 120

/* Generate a random int from 0 to N-1.
 */
#define random(N)  ((int)(((double)(N) * rand()) / (RAND_MAX + 1.0)))

static char const dice[BOARDSIZE][DIEFACES] = {
    "aaeegn", "elrtty", "aoottw", "abbjoo",
    "ehrtvw", "cimotu", "distty", "eiosst",
    "delrvy", "achops", "himnqu", "eeinsu",
    "eeghnw", "affkps", "hlnnrz", "deilrx"
};

/* The dictionary is represented in memory as a tree. The tree is
 * represented by its arcs; the nodes are implicit. All of the arcs
 * emanating from a single node are stored as a linked list in
 * alphabetical order.
 */
typedef struct {
    int letter:8;   /* the letter this arc is labelled with */
    int arc:24;     /* the node this arc points to (i.e. its first arc) */
    int next:24;    /* the next sibling arc emanating from this node */
    int final:1;    /* true if this arc is the end of a valid word */
} treearc;

/* Each of the slots that make up the playing board is represented
 * by the die it contains.
 */
typedef struct {
    unsigned char die;      /* which die is in this slot */
    unsigned char face;     /* which face of the die is showing */
} slot;

/* The following information defines a game.
 */
typedef struct {
    slot board[BOARDSIZE];  /* the contents of the board */
    int score;              /* how many points the board is worth */
} game;

/* The wordlist is stored as a binary search tree.
 */
typedef struct {
    int item: 24;   /* the identifier of a word in the list */
    int left: 16;   /* the branch with smaller identifiers */
    int right: 16;  /* the branch with larger identifiers */
} listnode;

/* The dictionary.
 */
static treearc *dictionary;
static int heapalloc;
static int heapsize;

/* Every slot's immediate neighbors.
 */
static int neighbors[BOARDSIZE][9];

/* The wordlist, used while scoring a board.
 */
static listnode *wordlist;
static int listalloc;
static int listsize;
static int xcursor;

/* The game that is currently being examined.
 */
static game G;

/* The highest-scoring game seen so far.
 */
static game bestgame;

/* Variables to time the program and display stats.
 */
static time_t start;
static int boardcount;
static int allscores;

/* The pool contains the N highest-scoring games seen so far.
 */
static game pool[MAXPOOLSIZE];
static int poolsize;
static int cutoffscore;
static int stallcounter;

/* Some buffers shared by recursive functions.
 */
static char wordbuf[WORDBUFSIZE];
static char gridbuf[BOARDSIZE];

/*
 * The dictionary is stored as a tree. It is created during
 * initialization and remains unmodified afterwards. When moving
 * through the tree, the program tracks the arc that points to the
 * current node. (The first arc in the heap is a dummy that points to
 * the root node, which otherwise would have no arc.)
 */

static void initdictionary(void)
{
    heapalloc = 256;
    dictionary = malloc(256 * sizeof *dictionary);
    heapsize = 1;
    dictionary->arc = 0;
    dictionary->letter = 0;
    dictionary->next = 0;
    dictionary->final = 0;
}

static int addarc(int arc, char ch)
{
    int prev, a;

    prev = arc;
    a = dictionary[arc].arc;
    for (;;) {
        if (dictionary[a].letter == ch)
            return a;
        if (!dictionary[a].letter || dictionary[a].letter > ch)
            break;
        prev = a;
        a = dictionary[a].next;
    }
    if (heapsize >= heapalloc) {
        heapalloc *= 2;
        dictionary = realloc(dictionary, heapalloc * sizeof *dictionary);
    }
    a = heapsize++;
    dictionary[a].letter = ch;
    dictionary[a].final = 0;
    dictionary[a].arc = 0;
    if (prev == arc) {
        dictionary[a].next = dictionary[prev].arc;
        dictionary[prev].arc = a;
    } else {
        dictionary[a].next = dictionary[prev].next;
        dictionary[prev].next = a;
    }
    return a;
}

static int validateword(char *word)
{
    int i;

    for (i = 0 ; word[i] != '\0' && word[i] != '\n' ; ++i)
        if (word[i] < 'a' || word[i] > 'z')
            return 0;
    if (word[i] == '\n')
        word[i] = '\0';
    if (i < 3)
        return 0;
    for ( ; *word ; ++word, --i) {
        if (*word == 'q') {
            if (word[1] != 'u')
                return 0;
            memmove(word + 1, word + 2, --i);
        }
    }
    return 1;
}

static void createdictionary(char const *filename)
{
    FILE *fp;
    int arc, i;

    initdictionary();
    fp = fopen(filename, "r");
    while (fgets(wordbuf, sizeof wordbuf, fp)) {
        if (!validateword(wordbuf))
            continue;
        arc = 0;
        for (i = 0 ; wordbuf[i] ; ++i)
            arc = addarc(arc, wordbuf[i]);
        dictionary[arc].final = 1;
    }
    fclose(fp);
}

/*
 * The wordlist is stored as a binary search tree. It is only added
 * to, searched, and erased. Instead of storing the actual word, it
 * only retains the word's final arc in the dictionary. Thus, the
 * dictionary needs to be walked in order to print out the wordlist.
 */

static void initwordlist(void)
{
    listalloc = 16;
    wordlist = malloc(listalloc * sizeof *wordlist);
    listsize = 0;
}

static int iswordinlist(int word)
{
    int node, n;

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 1;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            return 0;
    }
}

static int insertword(int word)
{
    int node, n;

    if (!listsize) {
        wordlist->item = word;
        wordlist->left = 0;
        wordlist->right = 0;
        ++listsize;
        return 1;
    }

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 0;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            break;
    }

    if (listsize >= listalloc) {
        listalloc *= 2;
        wordlist = realloc(wordlist, listalloc * sizeof *wordlist);
    }
    n = listsize++;
    wordlist[n].item = word;
    wordlist[n].left = 0;
    wordlist[n].right = 0;
    if (wordlist[node].item > word)
        wordlist[node].left = n;
    else
        wordlist[node].right = n;
    return 1;
}

static void clearwordlist(void)
{
    listsize = 0;
    G.score = 0;
}


static void scoreword(char const *word)
{
    int const scoring[] = { 0, 0, 0, 1, 1, 2, 3, 5 };
    int n, u;

    for (n = u = 0 ; word[n] ; ++n)
        if (word[n] == 'q')
            ++u;
    n += u;
    G.score += n > 7 ? 11 : scoring[n];
}

static void addwordtolist(char const *word, int id)
{
    if (insertword(id))
        scoreword(word);
}

static void _printwords(int arc, int len)
{
    int a;

    while (arc) {
        a = len + 1;
        wordbuf[len] = dictionary[arc].letter;
        if (wordbuf[len] == 'q')
            wordbuf[a++] = 'u';
        if (dictionary[arc].final) {
            if (iswordinlist(arc)) {
                wordbuf[a] = '\0';
                if (xcursor == 4) {
                    printf("%s\n", wordbuf);
                    xcursor = 0;
                } else {
                    printf("%-16s", wordbuf);
                    ++xcursor;
                }
            }
        }
        _printwords(dictionary[arc].arc, a);
        arc = dictionary[arc].next;
    }
}

static void printwordlist(void)
{
    xcursor = 0;
    _printwords(1, 0);
    if (xcursor)
        putchar('\n');
}

/*
 * The board is stored as an array of oriented dice. To score a game,
 * the program looks at each slot on the board in turn, and tries to
 * find a path along the dictionary tree that matches the letters on
 * adjacent dice.
 */

static void initneighbors(void)
{
    int i, j, n;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        n = 0;
        for (j = 0 ; j < BOARDSIZE ; ++j)
            if (i != j && abs(i / XSIZE - j / XSIZE) <= 1
                       && abs(i % XSIZE - j % XSIZE) <= 1)
                neighbors[i][n++] = j;
        neighbors[i][n] = -1;
    }
}

static void printboard(void)
{
    int i;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        printf(" %c", toupper(dice[G.board[i].die][G.board[i].face]));
        if (i % XSIZE == XSIZE - 1)
            putchar('\n');
    }
}

static void _findwords(int pos, int arc, int len)
{
    int ch, i, p;

    for (;;) {
        ch = dictionary[arc].letter;
        if (ch == gridbuf[pos])
            break;
        if (ch > gridbuf[pos] || !dictionary[arc].next)
            return;
        arc = dictionary[arc].next;
    }
    wordbuf[len++] = ch;
    if (dictionary[arc].final) {
        wordbuf[len] = '\0';
        addwordtolist(wordbuf, arc);
    }
    gridbuf[pos] = '.';
    for (i = 0 ; (p = neighbors[pos][i]) >= 0 ; ++i)
        if (gridbuf[p] != '.')
            _findwords(p, dictionary[arc].arc, len);
    gridbuf[pos] = ch;
}

static void findwordsingrid(void)
{
    int i;

    clearwordlist();
    for (i = 0 ; i < BOARDSIZE ; ++i)
        gridbuf[i] = dice[G.board[i].die][G.board[i].face];
    for (i = 0 ; i < BOARDSIZE ; ++i)
        _findwords(i, 1, 0);
}

static void shuffleboard(void)
{
    int die[BOARDSIZE];
    int i, n;

    for (i = 0 ; i < BOARDSIZE ; ++i)
        die[i] = i;
    for (i = BOARDSIZE ; i-- ; ) {
        n = random(i);
        G.board[i].die = die[n];
        G.board[i].face = random(DIEFACES);
        die[n] = die[i];
    }
}

/*
 * The pool contains the N highest-scoring games found so far. (This
 * would typically be done using a priority queue, but it represents
 * far too little of the runtime. Brute force is just as good and
 * simpler.) Note that the pool will only ever contain one board with
 * a particular score: This is a cheap way to discourage the pool from
 * filling up with almost-identical high-scoring boards.
 */

static void addgametopool(void)
{
    int i;

    if (G.score < cutoffscore)
        return;
    for (i = 0 ; i < poolsize ; ++i) {
        if (G.score == pool[i].score) {
            pool[i] = G;
            return;
        }
        if (G.score > pool[i].score)
            break;
    }
    if (poolsize < MAXPOOLSIZE)
        ++poolsize;
    if (i < poolsize) {
        memmove(pool + i + 1, pool + i, (poolsize - i - 1) * sizeof *pool);
        pool[i] = G;
    }
    cutoffscore = pool[poolsize - 1].score;
    stallcounter = 0;
}

static void selectpoolmember(int n)
{
    G = pool[n];
}

static void emptypool(void)
{
    poolsize = 0;
    cutoffscore = 0;
    stallcounter = 0;
}

/*
 * The program examines as many boards as it can in the given time,
 * and retains the one with the highest score. If the program is out
 * of time, then it reports the best-seen game and immediately exits.
 */

static void report(void)
{
    findwordsingrid();
    printboard();
    printwordlist();
    printf("score = %d\n", G.score);
    fprintf(stderr, "// score: %d points (%d words)\n", G.score, listsize);
    fprintf(stderr, "// %d boards examined\n", boardcount);
    fprintf(stderr, "// avg score: %.1f\n", (double)allscores / boardcount);
    fprintf(stderr, "// runtime: %ld s\n", time(0) - start);
}

static void scoreboard(void)
{
    findwordsingrid();
    ++boardcount;
    allscores += G.score;
    addgametopool();
    if (bestgame.score < G.score) {
        bestgame = G;
        fprintf(stderr, "// %ld s: board %d scoring %d\n",
                time(0) - start, boardcount, G.score);
    }

    if (time(0) - start >= RUNTIME) {
        G = bestgame;
        report();
        exit(0);
    }
}

static void restartpool(void)
{
    emptypool();
    while (poolsize < MAXPOOLSIZE) {
        shuffleboard();
        scoreboard();
    }
}

/*
 * Making small modifications to a board.
 */

static void turndie(void)
{
    int i, j;

    i = random(BOARDSIZE);
    j = random(DIEFACES - 1) + 1;
    G.board[i].face = (G.board[i].face + j) % DIEFACES;
}

static void swapdice(void)
{
    slot t;
    int p, q;

    p = random(BOARDSIZE);
    q = random(BOARDSIZE - 1);
    if (q >= p)
        ++q;
    t = G.board[p];
    G.board[p] = G.board[q];
    G.board[q] = t;
}

/*
 *
 */

int main(void)
{
    int i;

    start = time(0);
    srand((unsigned int)start);

    createdictionary(WORDLISTFILE);
    initwordlist();
    initneighbors();

    restartpool();
    for (;;) {
        for (i = 0 ; i < poolsize ; ++i) {
            selectpoolmember(i);
            turndie();
            scoreboard();
            selectpoolmember(i);
            swapdice();
            scoreboard();
        }
        ++stallcounter;
        if (stallcounter >= STALLPOINT) {
            fprintf(stderr, "// stalled; restarting search\n");
            restartpool();
        }
    }

    return 0;
}

Uwagi do wersji 2 (9 czerwca)

Oto jeden ze sposobów wykorzystania początkowej wersji mojego kodu jako punktu wyjścia. Zmiany w tej wersji składają się z mniej niż 100 linii, ale potroiły średni wynik gry.

W tej wersji program utrzymuje „pulę” kandydatów, składającą się z N najwyżej ocenianych tablic wygenerowanych do tej pory przez program. Za każdym razem, gdy generowana jest nowa plansza, jest ona dodawana do puli i usuwana jest tablica o najniższych wynikach w puli (która może równie dobrze być właśnie dodaną tablicą, jeśli jej wynik jest niższy niż obecny). Pula jest początkowo zapełniana losowo generowanymi płytkami, po czym utrzymuje stały rozmiar przez cały czas działania programu.

Główna pętla programu polega na wybraniu losowej planszy z puli i zmianie jej, określeniu wyniku nowej planszy, a następnie umieszczeniu jej w puli (jeśli osiąga wystarczającą liczbę punktów). W ten sposób program nieustannie udoskonala tablice z najlepszymi wynikami. Główną czynnością jest wprowadzanie stopniowych, przyrostowych ulepszeń, ale wielkość puli pozwala również programowi znajdować wieloetapowe ulepszenia, które tymczasowo pogarszają wynik tablicy, zanim będzie ona w stanie poprawić.

Zazwyczaj ten program dość szybko znajduje dobre maksimum lokalne, po którym przypuszczalnie jakiekolwiek lepsze maksimum jest zbyt odległe, aby je znaleźć. I tak po raz kolejny nie ma sensu uruchamiać programu dłużej niż 10 sekund. Można to poprawić, np. Wykrywając tę ​​sytuację przez program i rozpoczynając nowe wyszukiwanie od nowej puli kandydatów. Przyniosłoby to jednak jedynie niewielki wzrost. Właściwa heurystyczna technika poszukiwania byłaby prawdopodobnie lepszą drogą eksploracji.

(Uwaga dodatkowa: Widziałem, że ta wersja generuje około 5 tys. Tablic / s. Ponieważ pierwsza wersja zazwyczaj generowała 20 tys. Tablic / s, początkowo byłem zaniepokojony. Po profilowaniu odkryłem jednak, że spędziłem dodatkowy czas na zarządzaniu listą słów. Innymi słowy, było to całkowicie spowodowane tym, że program znalazł o wiele więcej słów na tablicę. W związku z tym rozważałem zmianę kodu w celu zarządzania listą słów, ale biorąc pod uwagę, że ten program używa tylko 10 z przydzielonych 120 sekund, takich optymalizacja byłaby bardzo przedwczesna).

Uwagi do wersji 1 (2 czerwca)

To bardzo, bardzo proste rozwiązanie. Wszystko, co robi, generuje losowe plansze, a następnie po 10 sekundach generuje tę z najwyższym wynikiem. (Domyślnie ustawiłem 10 sekund, ponieważ dodatkowe 110 sekund dozwolone przez specyfikację problemu zazwyczaj nie poprawia ostatecznego rozwiązania, na które warto było czekać.) Jest to więc bardzo głupie. Ma jednak całą infrastrukturę, aby stanowić dobry punkt wyjścia do bardziej inteligentnego wyszukiwania, a jeśli ktoś chce skorzystać z niej przed upływem terminu, zachęcam go do tego.

Program rozpoczyna się od odczytania słownika w strukturze drzewa. (Forma nie jest tak zoptymalizowana, jak mogłaby być, ale jest wystarczająca do tych celów.) Po innej podstawowej inicjalizacji zaczyna generować tablice i oceniać je. Program sprawdza około 20 000 płyt na sekundę na mojej maszynie, a po około 200 000 płyt losowe podejście zaczyna działać na sucho.

Ponieważ w danym momencie oceniana jest tylko jedna tablica, dane punktacji są przechowywane w zmiennych globalnych. To pozwala mi zminimalizować ilość stałych danych, które muszą być przekazywane jako argumenty do funkcji rekurencyjnych. (Jestem pewien, że da to niektórym ludziom pokrzywkę i przepraszam.) Lista słów jest przechowywana jako drzewo wyszukiwania binarnego. Każde znalezione słowo należy wyszukać na liście słów, aby duplikaty słów nie były liczone dwukrotnie. Lista słów jest jednak potrzebna tylko podczas procesu oceny, więc jest odrzucana po znalezieniu wyniku. Dlatego pod koniec programu wybrana tablica musi zostać ponownie oceniona, aby można było wydrukować listę słów.

Ciekawostka: średni wynik losowo wygenerowanej planszy Boggle, według oceny english.0, wynosi 61,7 punktu.

VBA (średnia obecnie wynosi 80-110 punktów, niedokończone)

Oto mój proces pracy, ale nie jest on najlepszy z możliwych; moja absolutnie najlepsza ocena znaleziona na dowolnej planszy po wielu testowych testach wynosi około 120. Nadal musi być jakiś lepszy ogólny porządek i jestem pewien, że w wielu miejscach można uzyskać większą wydajność.

• 2012.05.09:
  • Oryginalny post
• 2012.05.10 - 2012.05.18:
  • Poprawiony algorytm oceniania
  • Poprawiona logika wyszukiwania ścieżek
• 2012.06.07 - 2012.06.12 :
  • Zmniejszono limit słów do 6 z 8. Pozwala na większą liczbę plansz z mniejszymi słowami. Wygląda na to, że nieznacznie poprawił się średni wynik. (10-15 sprawdzonych płyt na bieg w porównaniu z 1 do 2)
  • Zgodnie z sugestią chleba, stworzyłem strukturę drzewa, w której mieści się lista słów. Znacząco przyspiesza to sprawdzanie słów na tablicy.
  • Grałem ze zmianą maksymalnego rozmiaru słowa (szybkość vs. wynik) i jeszcze nie zdecydowałem, czy 5 lub 6 jest dla mnie lepszą opcją. 6 wyników w 100-120 sprawdzonych płytach, a 5 wyników w 500-1000 (obie nadal znajdują się znacznie poniżej innych podanych dotychczas przykładów).
  • Problem : Po wielu kolejnych uruchomieniach proces zaczyna się zwalniać, więc nadal jest trochę pamięci do zarządzania.

Prawdopodobnie niektórym z was wygląda to okropnie, ale jak powiedziałem, WIP. Jestem bardzo otwarty na konstruktywną krytykę! Przepraszam za bardzo długie ciało ...

Moduł klasy kości :

Option Explicit

Private Sides() As String

Sub NewDie(NewLetters As String)
    Sides = Split(NewLetters, ",")
End Sub

Property Get Side(i As Integer)
    Side = Sides(i)
End Property

Moduł klasy drzewa :

Option Explicit

Private zzroot As TreeNode


Sub AddtoTree(ByVal TreeWord As Variant)
Dim i As Integer
Dim TempNode As TreeNode

    Set TempNode = TraverseTree(TreeWord, zzroot)
    SetNode TreeWord, TempNode

End Sub

Private Function SetNode(ByVal Value As Variant, parent As TreeNode) As TreeNode
Dim ValChar As String
    If Len(Value) > 0 Then
        ValChar = Left(Value, 1)
        Select Case Asc(ValChar) - 96
            Case 1:
                Set parent.Node01 = AddNode(ValChar, parent.Node01)
                Set SetNode = parent.Node01
            Case 2:
                Set parent.Node02 = AddNode(ValChar, parent.Node02)
                Set SetNode = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set parent.Node26 = AddNode(ValChar, parent.Node26)
                Set SetNode = parent.Node26
            Case Else:
                Set SetNode = Nothing
        End Select

        Set SetNode = SetNode(Right(Value, Len(Value) - 1), SetNode)
    Else
        Set parent.Node27 = AddNode(True, parent.Node27)
        Set SetNode = parent.Node27
    End If
End Function

Function AddNode(ByVal Value As Variant, NewNode As TreeNode) As TreeNode
    If NewNode Is Nothing Then
        Set AddNode = New TreeNode
        AddNode.Value = Value
    Else
        Set AddNode = NewNode
    End If
End Function
Function TraverseTree(TreeWord As Variant, parent As TreeNode) As TreeNode
Dim Node As TreeNode
Dim ValChar As String
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            Set TraverseTree = TraverseTree(Right(TreeWord, Len(TreeWord) - 1), Node)
            If Not TraverseTree Is Nothing Then
                Set TraverseTree = parent
            End If
        Else
            Set TraverseTree = parent
        End If
    Else
        If parent.Node27.Value Then
            Set TraverseTree = parent
        Else
            Set TraverseTree = Nothing
        End If
    End If
End Function

Function WordScore(TreeWord As Variant, Step As Integer, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            WordScore = WordScore(Right(TreeWord, Len(TreeWord) - 1), Step + 1, Node)
        End If
    Else
        If parent.Node27 Is Nothing Then
            WordScore = 0
        Else
            WordScore = Step
        End If
    End If
End Function

Function ValidWord(TreeWord As Variant, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            ValidWord = ValidWord(Right(TreeWord, Len(TreeWord) - 1), Node)
        Else
            ValidWord = False
        End If
    Else
        If parent.Node27 Is Nothing Then
            ValidWord = False
        Else
            ValidWord = True
        End If
    End If
End Function

Private Sub Class_Initialize()
    Set zzroot = New TreeNode
End Sub

Private Sub Class_Terminate()
    Set zzroot = Nothing
End Sub

Moduł klasy TreeNode :

Option Explicit

Public Value As Variant
Public Node01 As TreeNode
Public Node02 As TreeNode
' ... - Reduced to limit size of answer.
Public Node26 As TreeNode
Public Node27 As TreeNode

Moduł główny :

Option Explicit

Const conAllSides As String = ";a,a,e,e,g,n;e,l,r,t,t,y;a,o,o,t,t,w;a,b,b,j,o,o;e,h,r,t,v,w;c,i,m,o,t,u;d,i,s,t,t,y;e,i,o,s,s,t;d,e,l,r,v,y;a,c,h,o,p,s;h,i,m,n,qu,u;e,e,i,n,s,u;e,e,g,h,n,w;a,f,f,k,p,s;h,l,n,n,r,z;d,e,i,l,r,x;"
Dim strBoard As String, strBoardTemp As String, strWords As String, strWordsTemp As String
Dim CheckWordSub As String
Dim iScore As Integer, iScoreTemp As Integer
Dim Board(1 To 4, 1 To 4) As Integer
Dim AllDice(1 To 16) As Dice
Dim AllWordsTree As Tree
Dim AllWords As Scripting.Dictionary
Dim CurWords As Scripting.Dictionary
Dim FullWords As Scripting.Dictionary
Dim JunkWords As Scripting.Dictionary
Dim WordPrefixes As Scripting.Dictionary
Dim StartTime As Date, StopTime As Date
Const MAX_LENGTH As Integer = 5
Dim Points(3 To 8) As Integer

Sub Boggle()
Dim DiceSetup() As String
Dim i As Integer, j As Integer, k As Integer

    StartTime = Now()

    strBoard = vbNullString
    strWords = vbNullString
    iScore = 0

    ReadWordsFileTree

    DiceSetup = Split(conAllSides, ";")

    For i = 1 To 16
        Set AllDice(i) = New Dice
        AllDice(i).NewDie "," & DiceSetup(i)
    Next i

    Do While WithinTimeLimit

        Shuffle

        strBoardTemp = vbNullString
        strWordsTemp = vbNullString
        iScoreTemp = 0

        FindWords

        If iScoreTemp > iScore Or iScore = 0 Then
            iScore = iScoreTemp
            k = 1
            For i = 1 To 4
                For j = 1 To 4
                    strBoardTemp = strBoardTemp & AllDice(k).Side(Board(j, i)) & "  "
                    k = k + 1
                Next j
                strBoardTemp = strBoardTemp & vbNewLine
            Next i
            strBoard = strBoardTemp
            strWords = strWordsTemp

        End If

    Loop

    Debug.Print strBoard
    Debug.Print strWords
    Debug.Print iScore & " points"

    Set AllWordsTree = Nothing
    Set AllWords = Nothing
    Set CurWords = Nothing
    Set FullWords = Nothing
    Set JunkWords = Nothing
    Set WordPrefixes = Nothing

End Sub

Sub ShuffleBoard()
Dim i As Integer

    For i = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        Board(Int((i - 1) / 4) + 1, 4 - (i Mod 4)) = Int(6 * Rnd() + 1)
    Next i

End Sub

Sub Shuffle()
Dim n As Long
Dim Temp As Variant
Dim j As Long

    Randomize
    ShuffleBoard
    For n = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        j = CLng(((16 - n) * Rnd) + n)
        If n <> j Then
            Set Temp = AllDice(n)
            Set AllDice(n) = AllDice(j)
            Set AllDice(j) = Temp
        End If
    Next n

    Set FullWords = New Scripting.Dictionary
    Set CurWords = New Scripting.Dictionary
    Set JunkWords = New Scripting.Dictionary

End Sub

Sub ReadWordsFileTree()
Dim FSO As New FileSystemObject
Dim FS
Dim strTemp As Variant
Dim iLength As Integer
Dim StartTime As Date

    StartTime = Now()
    Set AllWordsTree = New Tree
    Set FS = FSO.OpenTextFile("P:\Personal\english.txt")

    Points(3) = 1
    Points(4) = 1
    Points(5) = 2
    Points(6) = 3
    Points(7) = 5
    Points(8) = 11

    Do Until FS.AtEndOfStream
        strTemp = FS.ReadLine
        If strTemp = LCase(strTemp) Then
            iLength = Len(strTemp)
            iLength = IIf(iLength > 8, 8, iLength)
            If InStr(strTemp, "'") < 1 And iLength > 2 Then
                AllWordsTree.AddtoTree strTemp
            End If
        End If
    Loop
    FS.Close

End Sub

Function GetScoreTree() As Integer
Dim TempScore As Integer

    If Not WithinTimeLimit Then Exit Function

    GetScoreTree = 0

    TempScore = AllWordsTree.WordScore(CheckWordSub, 0)
    Select Case TempScore
        Case Is < 3:
            GetScoreTree = 0
        Case Is > 8:
            GetScoreTree = 11
        Case Else:
            GetScoreTree = Points(TempScore)
    End Select

End Function

Sub SubWords(CheckWord As String)
Dim CheckWordScore As Integer
Dim k As Integer, l As Integer

    For l = 0 To Len(CheckWord) - 3
        For k = 1 To Len(CheckWord) - l
            If Not WithinTimeLimit Then Exit Sub

            CheckWordSub = Mid(CheckWord, k, Len(CheckWord) - ((k + l) - 1))

            If Len(CheckWordSub) >= 3 And Not CurWords.Exists(CheckWordSub) Then
                CheckWordScore = GetScoreTree

                If CheckWordScore > 0 Then
                    CurWords.Add CheckWordSub, CheckWordSub
                    iScoreTemp = iScoreTemp + CheckWordScore
                    strWordsTemp = strWordsTemp & CheckWordSub & vbNewLine
                End If

                If Left(CheckWordSub, 1) = "q" Then
                    k = k + 1
                End If
            End If

        Next k
    Next l

End Sub

Sub FindWords()
Dim CheckWord As String
Dim strBoardLine(1 To 16) As String
Dim Used(1 To 16) As Boolean
Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer
Dim StartSquare As Integer
Dim FullCheck As Variant

    n = 1
    For l = 1 To 4
        For m = 1 To 4
            If Not WithinTimeLimit Then Exit Sub
            strBoardLine(n) = AllDice(n).Side(Board(m, l))
            n = n + 1
        Next m
    Next l

    For i = 1 To 16
        For k = 1 To 16

            If Not WithinTimeLimit Then Exit Sub
            If k Mod 2 = 0 Then
                For j = 1 To 16
                    Used(j) = False
                Next j

                Used(i) = True
                MakeWords strBoardLine, Used, i, k / 2, strBoardLine(i)
            End If

        Next k
    Next i

    For Each FullCheck In FullWords.Items
        SubWords CStr(FullCheck)
    Next FullCheck

End Sub

Function MakeWords(BoardLine() As String, Used() As Boolean, _
    Start As Integer, _
    Direction As Integer, CurString As String) As String
Dim i As Integer, j As Integer, k As Integer, l As Integer

    j = 0

    Select Case Direction
        Case 1:
            k = Start - 5
        Case 2:
            k = Start - 4
        Case 3:
            k = Start - 3
        Case 4:
            k = Start - 1
        Case 5:
            k = Start + 1
        Case 6:
            k = Start + 3
        Case 7:
            k = Start + 4
        Case 8:
            k = Start + 5
    End Select

    If k >= 1 And k <= 16 Then
        If Not WithinTimeLimit Then Exit Function

        If Not Used(k) Then
            If ValidSquare(Start, k) Then
                If Not (JunkWords.Exists(CurString & BoardLine(k))) And Not FullWords.Exists(CurString & BoardLine(k)) Then
                    Used(k) = True
                    For l = 1 To MAX_LENGTH
                        If Not WithinTimeLimit Then Exit Function
                        MakeWords = CurString & BoardLine(k)
                        If Not (JunkWords.Exists(MakeWords)) Then
                            JunkWords.Add MakeWords, MakeWords
                        End If
                        If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
                            FullWords.Add MakeWords, MakeWords
                        ElseIf Len(MakeWords) < MAX_LENGTH Then
                            MakeWords BoardLine, Used, k, l, MakeWords
                        End If
                    Next l
                    Used(k) = False
                End If
            End If
        End If
    End If

    If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
        FullWords.Add MakeWords, MakeWords
        Debug.Print "FULL - " & MakeWords
    End If

End Function

Function ValidSquare(StartSquare As Integer, EndSquare As Integer) As Boolean
Dim sx As Integer, sy As Integer, ex As Integer, ey As Integer

    If Not WithinTimeLimit Then Exit Function

    sx = (StartSquare - 1) Mod 4 + 1
    ex = (EndSquare - 1) Mod 4 + 1

    sy = Int((StartSquare - 1) / 4 + 1)
    ey = Int((EndSquare - 1) / 4 + 1)

    ValidSquare = (sx - 1 <= ex And sx + 1 >= ex) And (sy - 1 <= ey And sy + 1 >= ey) And StartSquare <> EndSquare

End Function

Function WithinTimeLimit() As Boolean
    StopTime = Now()
    WithinTimeLimit = (Round(CDbl(((StopTime - StartTime) - Int(StopTime - StartTime)) * 86400), 0) < 120)
End Function

Szybkie spojrzenie na rozmiar przestrzeni wyszukiwania.

   16! => 20922789888000 Dice Permutations
(6^16) =>  2821109907456 Face Permutations
 59025489844657012604928000 Boggle Grids 

Zmniejszenie, aby wykluczyć powtórzenie na każdej kości.

              16! => 20922789888000 Dice Permutations
(4^4)*(5^6)*(6^5) => 31104000000 Unique Face Permutations
   650782456676352000000000 Boggle Grids 

@breadbox przechowuje słownik jako sprawdzanie tabeli mieszania O (1).

EDYTOWAĆ

Best Board (do tej pory byłem świadkiem)

L  E  A  N
S  E  T  M
T  S  B  D
I  E  G  O

Score: 830
Words: 229
SLEETIEST  MANTELETS
MANTEELS  MANTELET  MATELESS
MANTEEL  MANTELS  TESTEES  BETISES  OBTESTS  OBESEST
SLEETS  SLEEST  TESTIS  TESTES  TSETSE  MANTES  MANTEL  TESTAE  TESTEE
STEELS  STELES  BETELS  BESETS  BESITS  BETISE  BODGES  BESEES  EISELS
GESTES  GEISTS  OBTEST
LEANT  LEATS  LEETS  LEESE  LESES  LESTS  LESBO  ANTES  NATES  SLEET  SETAE
SEATS  STIES  STEEL  STETS  STEAN  STEAM  STELE  SELES  TAELS  TEELS  TESTS
TESTE  TELES  TETES  MATES  TESTA  TEATS  SEELS  SITES  BEETS  BETEL  BETES
BESET  BESTS  BESIT  BEATS  BODGE  BESEE  DOGES  EISEL  GESTS  GESTE  GESSE
GEITS  GEIST  OBESE
LEAN  LEAT  LEAM  LEET  LEES  LETS  LEST  LESS  EATS  EELS  ELSE  ETNA  ESES
ESTS  ESSE  ANTE  ANTS  ATES  AMBO  NATS  SLEE  SEEL  SETA  SETS  SESE  SEAN
SEAT  SEAM  SELE  STIE  STET  SEES  TAEL  TAES  TEEL  TEES  TEST  TEAM  TELE
TELS  TETS  TETE  MATE  MATS  MAES  TIES  TEAT  TEGS  SELS  SEGO  SITS  SITE
BEET  BEES  BETA  BETE  BETS  BEST  BEAN  BEAT  BEAM  BELS  BOGS  BEGO  BEGS
DOGE  DOGS  DOBS  GOBS  GEST  GEIT  GETS  OBES
LEA  LEE  LET  LES  EAN  EAT  EEL  ELS  ETA  EST  ESS  ANT  ATE  NAT  NAE  NAM
SEE  SET  SEA  SEL  TAN  TAE  TAM  TEE  TES  TEA  TEL  TET  MNA  MAN  MAT  MAE
TIE  TIS  TEG  SEG  SEI  SIT  BEE  BET  BEL  BOD  BOG  BEG  DOG  DOB  ITS  EGO
GOD  GOB  GET  OBS  OBE
EA  EE  EL  ET  ES  AN  AT  AE  AM  NA  ST  TA  TE  MA
TI  SI  BE  BO  DO  IT  IS  GO  OD  OB

Mój wpis znajduje się tutaj na Dream.In.Code ~ 30ms na przeszukiwanie płyty (na maszynie 2-rdzeniowej, powinno być szybsze z większą liczbą rdzeni)