[C#]Algoritmo per generare un cruciverba

[ercand]

Ciao a tutti, sto cercando di scrivere un semplice generatore di cruciverba.
Credevo fosse più "facile" ed invece mi sono impantanato quasi subito e sono qui a chiedere un po di aiuto per sbloccarmi.

Pensavo di creare una funzione da richiamare ricorsivamente e, ad ogni ricorsione, aggiungere una nuova parola alla griglia.
Purtroppo applicare questa idea è più difficile di quanto pensassi, fino ad ora ho scritto il seguente codice

class Coordinate
    {
        public int X { get; set; }
        public int Y { get; set; }

        public Coordinate(int x, int y)
        {
            X = x;
            Y = y;
        }
    }


    public enum Orientation
    {
        Horizontal,
        Vertical
    }

    class Crosswords
    {
        public delegate void DelegateUpgradeScheme(Scheme sender);
        public event DelegateUpgradeScheme HandleUpdateScheme;

        private List<String> dizionario;
        private int nRow = 20;
        private int nCoulumns = 20;
        public char[][] _scheme;

        public Crosswords()
        {
            ReadDictionary();
            ResetGrid();
        }
        public void Fill()
        {
            Scheme tempScheme = new Scheme(20, 20);
            Generate("", new Coordinate(0, 0), tempScheme, Orientation.Horizontal);
        }

        public void Generate(String lastWord, Coordinate coord, Scheme scheme, Orientation orient)
        {
            List<String> candidateWords = FindCandidates(lastWord, coord, scheme, orient);

            for (int i = 0; i < candidateWords.Count; i++)
            {
                Scheme tempScheme = new Scheme(scheme);
                WriteWord(candidateWords[i], tempScheme, coord, orient);
                
                // Aggiorna il form
         //       HandleUpdateScheme.Invoke(tempScheme);

                Generate(candidateWords[i][0].ToString(), coord, tempScheme, Orientation.Vertical);
            }

            return;
        }

        private void WriteWord(String word, Scheme scheme, Coordinate coord, Orientation orient)
        {
            if (orient == Orientation.Horizontal)
            {
                for (int i = 0; i < word.Length; i++)
                {
                    scheme.crossword[coord.X][coord.Y + i] = word[i];
                }

                // Se c'è ancora una casella libera dopo l'ultima lettera la contrassegno come "cella nera"
                if (coord.X + word.Length < scheme.Columns)
                {
                    scheme.crossword[coord.X][coord.Y + word.Length] = '#';
                }
            }
            else
            {
                for (int i = 0; i < word.Length; i++)
                {
                    scheme.crossword[coord.X + i][coord.Y] = word[i];
                }
                // Se c'è ancora una casella libera dopo l'ultima lettera la contrassegno come "cella nera"
                if (coord.X + word.Length < scheme.Rows)
                {
                    scheme.crossword[coord.X + word.Length][coord.Y] = '#';
                }
            }
        }

        private List<String> FindCandidates(String word, Coordinate coord, Scheme scheme, Orientation orient)
        {
            List<String> candidateWords = new List<String>();
            int lenght = 0;

            // Controlla il numero massimo di caratteri ce la parola può contenere
            if (orient == Orientation.Horizontal)
            {
                for (int i = 0 + coord.X; i < scheme.Columns; i++)
                {
                    if (scheme.crossword[coord.X][i] == '.')
                    {
                        lenght++;
                    }
                }
            }
            else
            {
                for (int i = 0 + coord.Y; i < scheme.Rows; i++)
                {
                    if (scheme.crossword[i][coord.Y] == '.')
                    {
                        lenght++;
                    }
                }
            }

            // Se la lunghezza è minore di 2 allora non ci sono possibili parole da inserire
            if (lenght < 2)
                return candidateWords;

            
            // Cicla sulle parole del dizionario e controlla quali possono essere messe
            foreach (String c in dizionario)
            {
                if (c.IndexOf(word) >= 0 && c.Length < lenght)
                {
                    candidateWords.Add(c);
                }
            }

            return candidateWords;
        }


        private void ResetGrid()
        {
            // Resetta la griglia riempendola di caratteri '.'
        }

        private void ReadDictionary()
        {
              //Legge da un file tutte le parole presenti nel mio dizionario
        }

Questa è la classe Scheme, crea semplicemente una griglia

class Scheme
    {
        public int Rows { get; set; }
        public int Columns { get; set; }
        
        public char[][] crossword;


        public Scheme(int rows, int columns)
        {
            Rows = rows;
            Columns = columns;
            ResetGrid();
        }

        public Scheme(Scheme scheme):this(scheme.Rows, scheme.Columns)
        {
            for (int i = 0; i < scheme.Rows;i++ )
            {
                for (int j = 0; j < scheme.Columns;j++ )
                {
                    crossword[i][j] = scheme.crossword[i][j];
                }
            }
        }

        private void ResetGrid()
        {
            char[][] tempCrossword = new char[Rows][];
            for (int i = 0; i < tempCrossword.Length; i++)
            {
                tempCrossword[i] = new char[Columns];
                for (int j = 0; j < tempCrossword[i].Length; j++)
                    tempCrossword[i][j] = '.';
            }
            crossword = tempCrossword;
        }
    }

Qualunque consiglio per riuscire a farmi sbloccare sarebbe ben accetto, grazie a tutti per l'aiuto

[Floris]

Ma le parole devono essere prese da un insieme predefinito o possono essere qualunque?

[ercand]

Le parole le prendo da un file txt dove sono elencato poco più di 100k parole.

[ercand]

Ho sperimentato un poco questi giorni e sono arrivato a scriveere questo

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;
using System.Text.RegularExpressions;

namespace CruciverbaNet
{
    class Coordinate
    {
        public int Row { get; set; }
        public int Column { get; set; }

        public Coordinate(int row, int column)
        {
            Row = row;
            Column = column;
        }

        public Coordinate(Coordinate coord) : this(coord.Row, coord.Column)
        {}

        public int CompareTo(Coordinate coord)
        {
            if (Column < coord.Column){
                return -1;
            }
            if (Column > coord.Column){
                return 1;
            }
            
            // Le coordinate sono sulla stessa colonne, controlla le riga
            if (Row < coord.Row){
                return -1;
            }
            if (Row > coord.Row){
                return 1;
            }
            return 0;
        }
    }

    public enum EnumOrientation
    {
        Horizontal,
        Vertical
    }

    class Orientation
    {
        public EnumOrientation Orient;

        public Orientation(EnumOrientation orient)
        {
            Orient = orient;
        }

        public Orientation(Orientation orient)
            : this(orient.Orient)
        {

        }
    }

    class Crosswords
    {
        public delegate void DelegateUpgradeScheme(Scheme sender);
        public event DelegateUpgradeScheme HandleUpdateScheme;

        private List<String> dizionario;
        private Dictionary<int, List<String>> dizionarioAlfabetico;
        private List<String> busyWords;
        private int nRow = 20;
        private int nCoulumns = 20;
        public char[][] _scheme;

        public Crosswords()
        {
            ReadDictionary();
            ResetGrid();
            busyWords = new List<String>();
        }

        public void Fill()
        {
            Scheme tempScheme = new Scheme(20, 20);
            Generate("", new Coordinate(0, 0), tempScheme, new Orientation(EnumOrientation.Vertical));
        }

        public bool Generate(String lastWord, Coordinate coord, Scheme scheme, Orientation orient)
        {
            Orientation tempOrient = new Orientation(orient);

            // Troviamo la prima cella libera
            Coordinate tempCoord = FindNextFreeSPace(tempOrient, scheme);

            // Se è null non ci sono piu celle libere, cruciverba riempito
            if (tempCoord == null){
                return true;
            }

            // Recuperiamo la parola che passa per la coordinata specificata
            String tempWord = intersectingWord(tempCoord, tempOrient.Orient, scheme);
            int tempWordLength = tempWord.Length;

            // Cerco le possibili parole candidate
            List<String> candidatesWord = new List<String>();

            while (tempWord.Length > 1 && tempWord[tempWord.Length - 1] == '.'){
                tempWord = tempWord.Substring(0, tempWord.Length - 1);
            }

            // Trovo le possibili parole che possono essere usate
            for (int i = 0; i < dizionario.Count; i++)
            {
                if (Regex.IsMatch(dizionario[i], "^" + tempWord) && dizionario[i].Length < tempWordLength)
                    if (busyWords.Contains(dizionario[i]) == false) // Controlliamo che non sia tra le parole gia usate
                        candidatesWord.Add(dizionario[i]);
            }

            Scheme tempScheme = new Scheme(scheme);
            for (int i = 0; i < candidatesWord.Count; i++)
            {
                if (WriteWord(candidatesWord[i], tempScheme, tempCoord, tempOrient.Orient))
                {
                    // Aggiorna il form
                    HandleUpdateScheme.Invoke(tempScheme);

                    // Aggiungo la parola lla lista di quelle gia usate
                    busyWords.Add(candidatesWord[i]);

                    // Se le parole non si interseca torna un passo indietro
                    if (Generate(candidatesWord[i][0].ToString(), new Coordinate(0, 0), tempScheme, new Orientation(EnumOrientation.Vertical)) == false)
                    {
                        tempScheme = new Scheme(scheme);
                        HandleUpdateScheme.Invoke(tempScheme);
                        busyWords.Remove(candidatesWord[i]);
                    }
                }

            }

            // Non è stata trovata nessuna combinazione, ritorno false
            return false;
        }

        public Coordinate FindNextFreeSPace(Orientation orient, Scheme scheme)
        {
            Coordinate coordVert = FindNextOrientedFreeSpace(EnumOrientation.Vertical, scheme);
            Coordinate coordHori = FindNextOrientedFreeSpace(EnumOrientation.Horizontal, scheme);

            // Se non sono state trovare ne spazi verticali ne orizzontali
            if (coordHori == null && coordVert == null) {
                return null;
            }
            else if ((coordHori == null || coordVert != null) && coordVert.CompareTo(coordHori) < 0) {
                orient.Orient = EnumOrientation.Vertical;
                return coordVert;
            }
            orient.Orient = EnumOrientation.Horizontal;
            return coordHori;
        }

        public Coordinate FindNextOrientedFreeSpace(EnumOrientation orient, Scheme scheme)
        {
            for (int i = 0; i < scheme.Rows; i++)
            {
                for (int j = 0; j < scheme.Columns; j++)
                {
                    String temp = intersectingWord(new Coordinate(i, j), orient, scheme);
                    if (temp != null && temp.IndexOf(".") >= 0)
                        return new Coordinate(i, j);
                }
            }
            return null;
        }

        /// <summary>
        /// Cerca la stringa passante per la coordinata e con l'orientamento specificato
        /// </summary>
        /// <param name="coord"></param>
        /// <param name="orient"></param>
        /// <param name="scheme"></param>
        /// <returns></returns>
        private String intersectingWord(Coordinate coord, EnumOrientation orient, Scheme scheme)
        {
            // E' una cella nera
            if (getSchemaChar(coord, scheme) == '#')
                return null;

            String result = "" + getSchemaChar(coord, scheme);
            Coordinate tempCoord = new Coordinate(coord.Row, coord.Column);
            if (orient == EnumOrientation.Vertical)
            {	//Se è in verticale concateno i caratteri in colonna spostandomi di riga
                tempCoord.Row--;
                while (tempCoord.Row >= 0 && getSchemaChar(tempCoord, scheme) != '#')
                {
                    result = getSchemaChar(tempCoord, scheme) + result;
                    tempCoord.Row--;
                }
                tempCoord.Row = coord.Row + 1;
                while (tempCoord.Row < scheme.crossword.Length && getSchemaChar(tempCoord, scheme) != '#')
                {
                    result = result + getSchemaChar(tempCoord, scheme);
                    tempCoord.Row++;
                }
            }
            else
            {	//Se è in orizzontale concateno i caratteri in riga spostandomi di colonna
                tempCoord.Column--;
                while (tempCoord.Column >= 0 && getSchemaChar(tempCoord, scheme) != '#')
                {
                    result = getSchemaChar(tempCoord, scheme) + result;
                    tempCoord.Column--;
                }
                tempCoord.Column = coord.Column + 1;
                while (tempCoord.Column < scheme.crossword[coord.Row].Length && getSchemaChar(tempCoord, scheme) != '#')
                {
                    result = result + getSchemaChar(tempCoord, scheme);
                    tempCoord.Column++;
                }
            }
            // Una sola lettera
            if (result.Length == 1)
                return null;

            return result;
        }

        private char getSchemaChar(Coordinate coord, Scheme scheme)
        {
            return scheme.crossword[coord.Row][coord.Column];
        }


        private bool WriteWord(String word, Scheme scheme, Coordinate coord, EnumOrientation orient)
        {
            if (orient == EnumOrientation.Horizontal)
            {
                bool ok = true;

                for (int i = 0; i < word.Length; i++)
                {
                    String intersectedWord = intersectingWord(new Coordinate(coord.Row, coord.Column + i), EnumOrientation.Vertical, scheme);

                    while (intersectedWord.Length > 0 && intersectedWord[intersectedWord.Length - 1] == '.')
                    {
                        intersectedWord = intersectedWord.Substring(0, intersectedWord.Length - 1);
                    }
                    int howManyMatch = 0;

                    // Controlla se esistono parole compatibili con quella che incrociamo
                    for (int j = 0; j < dizionario.Count && howManyMatch == 0; j++)
                    {
                        if (Regex.IsMatch(dizionario[j], intersectedWord))
                        {
                            howManyMatch++;
                        }
                    }
                    if (howManyMatch == 0)
                    {
                        ok = false;
                    }
                }
				
                // La parola è compatibile, la scrivo nello schema
                if (ok == true)
                {
                    for (int i = 0; i < word.Length; i++)
                        scheme.crossword[coord.Row][coord.Column + i] = word[i];

                    // Se c'è ancora una casella libera dopo l'ultima lettera la contrassegno come "cella nera"
                    if (coord.Row + word.Length < scheme.Columns)
                    {
                        scheme.crossword[coord.Row][coord.Column + word.Length] = '#';
                    }
                }
                else
                    return false;

            }
            else
            {
                bool ok = true;

                for (int i = 0; i < word.Length; i++)
                {
                    String intersectedWord = intersectingWord(new Coordinate(coord.Row + i, coord.Column), EnumOrientation.Horizontal, scheme); // Parola che interseca la coordinata attuale

                    if (intersectedWord.IndexOf(".") < 0) // Se le celle sono tutte occupate
                        continue;

                    int toSubtract = 0;
                    while (intersectedWord.Length -toSubtract> 0 && intersectedWord[intersectedWord.Length - 1 - toSubtract] == '.') {
                        ++toSubtract;
                    }
                    intersectedWord = intersectedWord.Substring(0, intersectedWord.Length - toSubtract);

                    int howManyMatch = 0;

                    if (intersectedWord.Length > 0 && intersectedWord[0]!= '.')
                    {
                        int codeChar = Convert.ToInt32(intersectedWord[0]);
                        int wordCount = dizionarioAlfabetico[codeChar].Count;
                        String regExpWord = "^" + intersectedWord + word[i];

                        // Controlla se esistono parole compatibili con quella che incrociamo
                        for (int j = 0; j < wordCount && howManyMatch == 0; j++)
                        {
                            if (Regex.IsMatch(dizionarioAlfabetico[codeChar][j], regExpWord))
                            {
                                howManyMatch++;
                            }
                        }
                    }
                    else
                    {
                        int codeChar = Convert.ToInt32(word[i]);
                        int wordCount = dizionarioAlfabetico[codeChar].Count;
                        String regExpWord = "^" + intersectedWord + word[i];

                        // Controlla se esistono parole compatibili con quella che incrociamo
                        for (int j = 0; j < wordCount && howManyMatch == 0; j++)
                        {
                            if (Regex.IsMatch(dizionarioAlfabetico[codeChar][j], regExpWord))
                            {
                                howManyMatch++;
                            }
                        }
                    }

                    if (howManyMatch == 0) {
                        ok = false;
						return false;
                    }
                }

                

                // La parola è compatibile, la scrivo nello schema
                if (ok == true) {
                    for (int i = 0; i < word.Length; i++)
                        scheme.crossword[coord.Row + i][coord.Column] = word[i];

                    // Se c'è ancora una casella libera dopo l'ultima lettera la contrassegno come "cella nera"
                    if (coord.Row + word.Length < scheme.Columns) {
                        scheme.crossword[coord.Row + word.Length][coord.Column] = '#';
                    }
                }
                else
                    return false;
            }

            // é la parola è stata inserita correttamente
            return true;
        }
    }
}

Purtroppo questo codice è LENTO, infatti non sono riusco a portare a termine neanche un cruciverba, purtroppo questo non mi permette neanche di capire se quello che ho scritto funzioni o meno.
Se qualcuno avesse qualche suggerimento da darmi o indirizzarmi su una via "migliore" sarebbe molto gradito .

Grazie per l'aiuto