[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