Algoritmo per la risoluzione di un cruciverba

[Enrico Corsaro]

Salve a tutti, mi rivolgo in particolare a coloro i quali si dilettano nel ragionare su algoritmi che possono risolvere determinati problemi.

Vengo subito al mio caso.

Ho un insieme di parole tutte note, e devo incastrarle in uno schema già pronto (quadrato o rettangolare che sia), fatto per queste parole, in cui trovo le caselle vuote e le caselle nere, come in un normale cruciverba.
L'obiettivo è trovare un metodo di inserimento di queste parole nello schema, rispettando ovviamente gli incastri, in modo da realizzare il minor numero di tentativi e cioè ottimizzando il procedimento per la velocità.
Si tratta ovviamente di fare dei tentativi perchè a differenza del normale cruciverba, non ho a disposizione i numeri sulle caselle con le relative definizioni. Ciò significa che almeno al primo inserimento tutte le parole hanno la stessa probabilità di essere collocate.

Qualsiasi idea, detta così semplicemente a parole, sarebbe di grande aiuto per me e quindi vi ringrazio in anticipo :D .

[yggdrasil]

tanto per iniziare:
risolvere un cruciverba come lo intendiamo noi umani è impossibile :O

riempire un cruciverba con le parole soluzioni note a priori è un altro discorso
il modo più semplice è usare il backtracking
provi tutte le diverse combinazioni di inserimento di una parola nei posti di una determinata lunghezza incrociando i risultati con quelli di altre parole
se ci sono solo 2 parole che si incrociano allora hai trovato il loro posto
e così avanti per tutte

[Enrico Corsaro]

E di fatto mi riferisco proprio al filling di uno schema già pronto. Non cerco necessariamente il sistema più semplice ma a quello più veloce.
Grazie intanto per questa rapida risposta!

[gugoXX]

E di fatto mi riferisco proprio al filling di uno schema già pronto. Non cerco necessariamente il sistema più semplice ma a quello più veloce.
Grazie intanto per questa rapida risposta!

Un algoritmo greedy partendo dalla parola piu' lunga dovrebbe essere fattibile.

[Enrico Corsaro]

intendi dire di collocare le parole partendo dalla più lunga (o dalle più lunghe) e andando via via verso le più corte?

[wlog]

E di fatto mi riferisco proprio al filling di uno schema già pronto. Non cerco necessariamente il sistema più semplice ma a quello più veloce.
Grazie intanto per questa rapida risposta!

Scordati un metodo veloce, il tuo problema è isomorfo all'ordinamento di un grafo (capacità di costruire una mappa biunivoca con un altro grafo). Esistono vari metodi, ma nessuno è veloce :D

[gugoXX]

intendi dire di collocare le parole partendo dalla più lunga (o dalle più lunghe) e andando via via verso le più corte?

si', e se la piu' lunga e' unica sei messo abbastanza bene.
dividerei l'algoritmo in 3 passi
1) raggruppare le parole da collocare suddividendole per lunghezza
2) cercherei le celle di partenza delle parole nello schema, associando a ciascuna cella la lunghezza della parola richiesta. (2 nel caso di celle che sono partenza sia di una verticale che di una orizzontale)
Quindi (memoria permettendo, ma direi che ce n'e' tanta), per ciascuna cella di partenza associerei una copia del vettore delle parole esattamente di quella lunghezza.

3) inizerei con un ciclo, sperando nella buona sorte:
Ricerca di tutte le celle la cui lista ha una sola parola (nel caso della piu' lunga singola, almeno quela dovrebbe esserci)
- Inserimento di tale parola nello schema, e cancellazione della parola appena messa dalla lista delle parole delle celle con partenza di pari lunghezza
- A seguito della parola scritta, dalla lista di alcune altre e' possibile che si debbano depennare parole che non possono piu' stare in quella posizione. Le cancello
Ricontinuo da 3 fino a che ho finito.

Nel caso di dubbi, ovvero se non ci fosse nessuna lista con solo una parola possibile, allora si dovrebbe partire con il backtracking, che non e' mai troppo semplice. In pratica devi iniziare a piazzare le parole "sperando". Nel caso in cui ti trovi in un passo bloccato, allora torni indietro fino all'ultima scelta e ne compi un'altra. Niente di speciale, ma occorre avere informazioni e strutture di appoggio in piu'

[wlog]

si', e se la piu' lunga e' unica sei messo abbastanza bene.
dividerei l'algoritmo in 3 passi
1) raggruppare le parole da collocare suddividendole per lunghezza
2) cercherei le celle di partenza delle parole nello schema, associando a ciascuna cella la lunghezza della parola richiesta. (2 nel caso di celle che sono partenza sia di una verticale che di una orizzontale)
Quindi (memoria permettendo, ma direi che ce n'e' tanta), per ciascuna cella di partenza associerei una copia del vettore delle parole esattamente di quella lunghezza.

3) inizerei con un ciclo, sperando nella buona sorte:
Ricerca di tutte le celle la cui lista ha una sola parola (nel caso della piu' lunga singola, almeno quela dovrebbe esserci)
- Inserimento di tale parola nello schema, e cancellazione della parola appena messa dalla lista delle parole delle celle con partenza di pari lunghezza
- A seguito della parola scritta, dalla lista di alcune altre e' possibile che si debbano depennare parole che non possono piu' stare in quella posizione. Le cancello
Ricontinuo da 3 fino a che ho finito.

Nel caso di dubbi, ovvero se non ci fosse nessuna lista con solo una parola possibile, allora si dovrebbe partire con il backtracking, che non e' mai troppo semplice. In pratica devi iniziare a piazzare le parole "sperando". Nel caso in cui ti trovi in un passo bloccato, allora torni indietro fino all'ultima scelta e ne compi un'altra. Niente di speciale, ma occorre avere informazioni e strutture di appoggio in piu'

Il tuo algoritmo assomiglia molto a quello di Dijkstra:

http://en.wikipedia.org/wiki/Shortest_Path_First

Da qualche parte sul sito del mio dipartimento dell'UvA (http://www.uva.nl/start.cfm) dovrebeb esserci qualcosa... mo cerco...

[cionci]

L'analogia la vedo, ma non vedo come rappresentare il concetto di intersezione multipla delle parole con gli archi del grafo o con la lista dei nodi.

[gugoXX]

L'analogia la vedo, ma non vedo come rappresentare il concetto di intersezione multipla delle parole con gli archi del grafo o con la lista dei nodi.

Piu' che a Dijkstra assomiglia all'algoritmo che avevo scritto per il risolutore di Sudoku. E' praticamente identico.

[DanieleC88]

Parlo da perfetto ignorante, ma mi viene in mente un approccio simile ad un risolutore di espressioni booleane che ho dovuto sviluppare per l'università: supponendo che il cruciverba abbia una sola configurazione finale possibile (il che è vero :D), si potrebbe provare ad inserire immediatamente le parole che sono forzate (le uniche di una certa lunghezza) e poi tentare una scelta per ognuna delle altre e si ripete l'inserimento, etc. In caso di conflitti si può fare un backtracking fino all'ultima scelta e tentare un'altra strada, fino a che non si trova una scelta soddisfacente.

Certo, sarebbe abbastanza dispendioso, forse ci sono metodi migliori... ma potrebbe anche funzionare. :)

[DanieleC88]

si', e se la piu' lunga e' unica sei messo abbastanza bene.
[...]
Niente di speciale, ma occorre avere informazioni e strutture di appoggio in piu'
Come non detto, mi era sfuggito questo post! :asd:

Sono arrivato tardi... :D
ciao ;)

[Enrico Corsaro]

Lo spreco di memoria non è un problema nel mio caso. Una struttura dati opportuna per velocizzare l'algoritmo si visiona in un secondo momento.

Avevo pensato già un pò a queste proposte fatte e tuttavia l'ordine computazionale rimarrebbe comunque molto elevato.

Io avevo pensato di suddividere l'insieme di parole in gruppi per numero di caratteri e iniziare a collocare le parole partendo dal gruppo che ne contiene in minor numero (rispettando eventuali incastri), in modo da avere già in partenza la probabilità più alta per ogni parola di essere collocata nel posto giusto. Di seguito a procedere collocando le parole del secondo gruppo meno numeroso. Nel caso in cui un incastro non dovesse funzionare, si varia l'ordine delle parole inserite.
Non penso comunque che l'ordine computazionale così venga ridotto, ma forse si velocizza di qualche fattore il tutto.

Aggiungo che questo sistema dovrebbe essere diciamo il più vicino possibile ad un modo di ragionare "umano", cioè all'atto pratico al modo in cui un amante della settimana enigmistica risolverebbe questo problema con carta e penna. Sostanzialmente, non avendo praticità con questi giochini di logica, non so se c'è qualche trucchetto o comunque qualche procedimento sicuro e rapido in particolare per riempire un cruciverba con delle parole già date. Voi come procedereste?

[wlog]

ciao,

comunque tu scriva l'algoritmo, se l'algoritmo è in grado di risolvere ogni problema sottopostogli, esisterà sempre una particolare coppia di parole/cruciverba che richiederà n! passi, quindi mettiti il cuore in pace :)

Backtracking con scelta locale greedy è il metodo migliore mi sa.

[wingman87]

Ciao, io per diletto ho scritto un programma per risolvere cruciverba, solo che come hai immaginato tu il tempo di risoluzione, quando il numero di parole nel dizionario e' elevato, diventa spropositato. Ad ogni modo il mio algoritmo e' suddiviso in varie parti ma il ragionamento e' il seguente: partendo dalla cella in alto a sinistra cerco, muovendomi verso destra e quando raggiungo la fine della riga passo alla successiva, la prima cella da cui possa partire una parola (prima orizzontale, poi verticale) e provo a infilarne una (e la escludo dalle infilabili successivamente), quando non trovo una parola infilabile torno indietro di un passo, escludo la parola appena usata (solo per questo passo) e provo a infilarne un'altra.

Comunque se ti interessa quando torno a casa te lo posto (se mi ricordo :) )

EDIT: ripensandoci forse nel tuo caso tu hai un dizionario composto solo dalle parole contenute nello schema. Se e' cosi' il metodo di risoluzione che ho usato e' piuttosto veloce (se si tratta di un comune cruciverba tipo settimana enigmistica).

[Enrico Corsaro]

ciao,

comunque tu scriva l'algoritmo, se l'algoritmo è in grado di risolvere ogni problema sottopostogli, esisterà sempre una particolare coppia di parole/cruciverba che richiederà n! passi, quindi mettiti il cuore in pace :)

Backtracking con scelta locale greedy è il metodo migliore mi sa.

Siamo d'accordo che l'ordine è il fattoriale, ma tra 1 fattore 1 e un fattore 0.2 per quanto non cambi l'ordine, c'è comunque una differenza sostanziale di velocità, quindi diciamo che se si riesce a trovare un modo per ridurre al minimo questo fattore, e ce ne dovrebbe essere uno solo possibile, allora è il caso che fa per me.

[astorcas]

Non è esattamente quello che cerchi ma da una lettura qui potresti trovare un paio di spunti.

http://webcrow.dii.unisi.it/webpage/index.html

[wingman87]

Sono tornato a casa e ho ritrovato il codice, te lo posto, spero possa servirti.
La classe che realizza l'algoritmo:
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
import java.io.*;

public class Cruciverba{

private class Coordinata{
int riga; //Si parte da zero!!! (riga zero -> prima riga)
int colonna; //Si parte da zero!!!
Coordinata(int riga,int colonna){ //Un comodo costruttore per creare velocemente una coordinata
this.riga=riga;
this.colonna=colonna;
}
private int compareTo(Coordinata c){
if(riga<c.riga)
return -1;
if(riga>c.riga)
return +1;
if(colonna<c.colonna)
return -1;
if(colonna>c.colonna)
return +1;
return 0;
}
}

private class Orientamento{
boolean verticale; //Se verticale è true -> verticale, altrimenti orizzontale
Orientamento(boolean verticale){ //Un comodo costruttore per creare velocemente un orientamento
this.verticale=verticale;
}
}

private char schema[][]; //[RIGHE][COLONNE] Si parte da zero!!! (riga zero -> prima riga)
//'#' per i quadrati neri, '.' per gli spazi vuoti
private String dizionario[]; //Dizionario completo
private String definizioniDizionario[];//Definizioni del dizionario, sono nello stesso ordine del dizionario
private String miniDizionari[][]; //[NUMERO_DI_LETTERE_DELLA_PAROLA][PAROLE]
private String daDisimpegnare[]; //Parole impegnate da writeWord(), vengono disimpegnate da writeWordNoCheck() e alla fine del riempimento (fill())

private int nPunti=0; //TEST
private boolean showLoading=false; //TEST

public void setShowLoading(boolean on){
showLoading=on;
}

public Cruciverba(String pathDizionario)throws IOException,FileNotFoundException{
loadDizionario(pathDizionario);
loadMiniDizionari();
}

//Funzione che carica una matrice (cruciverba) di caratteri dal file ('#' per i quadrati neri, '.' per gli spazi vuoti)
//Si assume che path sia un file di cruciverba valido.
public void loadCruciverba(String path)throws IOException,FileNotFoundException{
FileReader fR=new FileReader(path);
Scanner file=new Scanner(fR);

schema=new char[0][];
int numeroRiga=0;
while(file.hasNextLine()){
String rigaLetta=file.nextLine().toLowerCase();
char[][] tempSchema=new char[numeroRiga+1][];
for(int i=0;i<schema.length;i++)
tempSchema[i]=schema[i];
tempSchema[numeroRiga]=rigaLetta.toCharArray();

schema=tempSchema;
numeroRiga++;
}
fR.close();
}
//Funzione che salva una matrice (cruciverba) di caratteri dal file ('#' per i quadrati neri, '.' per gli spazi vuoti)
public void saveCruciverba(String path)throws IOException,FileNotFoundException{
FileWriter fW=new FileWriter(path,false);
PrintWriter file=new PrintWriter(fW);

for(char[] x:schema){
file.println(new String(x).toUpperCase());
}


fW.close();
}

//Funzione che riempie lo schema, restituisce true se ci riesce, false altrimenti.
public boolean fill(){
//INIZIO TEST
if(showLoading){
nPunti++;
System.out.print("\r"+genString('.',nPunti));
}
//FINE TEST
Orientamento orient=new Orientamento(true);
Coordinata c=new Coordinata(0,0);

try{
c=nextFreeSpace(orient); //Cerco il prossimo spazio in cui inserire una parola
}catch(NoMoreSpaceException e){ //Non ci sono altre parole da inserire: HO FINITO!
if(daDisimpegnare!=null) //Disimpegno tutte le parole che avevo impegnato con writeWord()
for(int i=0;i<daDisimpegnare.length;i++)
replace(miniDizionari[daDisimpegnare[i].length()],genString('#',daDisimpegnare[i].length()),daDisimpegnare[i]);
daDisimpegnare=null;
//INIZIO TEST
nPunti=0;
System.out.print("\r");
//FINE TEST
return true;
}
String regExpr=intersectingWord(c,orient); //Leggo la regExpr dello spazio in cui devo inserire una nuova parola
int lenParola=regExpr.length();
String[] possibiliParole=matchingWords(miniDizionari[lenParola],regExpr); //Cerco le parole che vi si incastrano

shuffleWords(possibiliParole); //Le mescolo (serve a non dare sempre la stessa soluzione)

for(int i=0;i<possibiliParole.length;i++){
String old=possibiliParole[i];
replace(miniDizionari[lenParola],old,genString('#',lenParola)); //Contrassegno la parola che sto per usare come impegnata
if(!possibiliParole[i].substring(0,1).equals("#") && writeWord(possibiliParole[i],c,orient,regExpr)){ //Se questa parola non è una parola già usata e si incastra
if(fill()){ //Provo a riempire tutto lo schema con quella parola incastrata
replace(miniDizionari[lenParola],genString('#',lenParola),old); //Se ci riesco disimpegno la parola e torno true
return true;
}else //Se non ci sono riuscito significa che nonostante la parola si incastrasse non era quella giusta
writeWordNoCheck(regExpr,c,orient); //Quindi riscrivo sullo schema quello che c'era originariamente

}
replace(miniDizionari[lenParola],genString('#',lenParola),old); //Disimpegno la parola

}
//INIZIO TEST
if(showLoading){
nPunti--;
System.out.print("\r"+genString('.',nPunti)+" ");
}
//FINE TEST
return false; //Torno false se non sono riuscito a mettere nessuna parola
}

//Funzione che carica il dizionario completo e le definizioni
//Questa funzione non gestisce le eccezioni dovute a problemi di I/O ma le rilancia al chiamante
private void loadDizionario(String path)throws IOException,FileNotFoundException{
FileReader fR=new FileReader(path);
Scanner file=new Scanner(fR);
ArrayList<String> parole=new ArrayList<String>();
ArrayList<String> definizioni=new ArrayList<String>();
while(file.hasNext()){
file.useDelimiter(" ");
parole.add(file.next().trim());
file.useDelimiter("\\s?\n");
definizioni.add(file.next().trim());
}
fR.close();
dizionario=(String[])parole.toArray(new String[0]);
definizioniDizionario=(String[])definizioni.toArray(new String[0]);
}

//Funzione che carica i mini-dizionari dal dizionario completo. (Si assume che il dizionario completo sia già stato caricato)
//Per iniziare poniamo che la lunghezza massima delle parole sia 30, quindi bisogna allocare lo spazio per 30 array
private void loadMiniDizionari(){
ArrayList<ArrayList<String>> miniDiz=new ArrayList<ArrayList<String>>();
for(int i=0;i<30;i++)
miniDiz.add(new ArrayList<String>());
for(int i=0;i<dizionario.length;i++)
miniDiz.get(dizionario[i].length()).add(dizionario[i]);
miniDizionari=new String[30][];
for(int i=0;i<30;i++)
miniDizionari[i]=(String[])miniDiz.get(i).toArray(new String[0]);
}

//Funzione che aggiunge all'array daDisimpegnare[] parola
private void addDaDisimpegnare(String parola){
if(daDisimpegnare==null)
daDisimpegnare=new String[0];
String[] nuovoVett=new String[daDisimpegnare.length+1];
for(int i=0;i<daDisimpegnare.length;i++)
nuovoVett[i]=daDisimpegnare[i];
nuovoVett[nuovoVett.length-1]=parola;
daDisimpegnare=nuovoVett;
}
//Funzione che toglie dall'array daDisimpegnare[] parola. Torna true se ha tolto qualcosa, false altrimenti
private boolean subDaDisimpegnare(String parola){
ArrayList<String> nuovoVett=new ArrayList<String>();
boolean trovato=false;
if(daDisimpegnare==null)
daDisimpegnare=new String[0];
for(int i=0;i<daDisimpegnare.length;i++){
if(trovato)
nuovoVett.add(daDisimpegnare[i]);
else if(!daDisimpegnare[i].equals(parola))
nuovoVett.add(daDisimpegnare[i]);
else
trovato=true;
}
int oldDim=daDisimpegnare.length;
daDisimpegnare=(String[])nuovoVett.toArray(new String[0]);
return(oldDim!=daDisimpegnare.length);
}

//Genera una stringa di n caratteri (n è ripetizioni e carattere è il char che viene ripetuto)
private static String genString(char carattere,int ripetizioni){
String ret="";
if(ripetizioni<0)
return ret;
for(int i=0;i<ripetizioni;i++)
ret+=carattere;
return ret;
}

//Funzione che sostituisce la prima occorrenza della key nel vettore con replacement
private void replace(String[] vett, String key, String replacement){
for(int i=0;i<vett.length;i++){
if(vett[i].equals(key)){
vett[i]=replacement;
break;
}
}
}


//Funzione che restituisce un array delle parole che matchano un'expr. regolare. Non restituisce due volte la stessa parola
private static String[] matchingWords(String[] dizionario, String regExpr){
ArrayList<String> ret=new ArrayList<String>();
for(int i=0;i<dizionario.length;i++)
if(dizionario[i].matches(regExpr))
if(ret.indexOf(dizionario[i])<0)
ret.add(dizionario[i]);
return (String[])ret.toArray(new String[0]);
}

//Funzione che mescola un array di stringhe
private static void shuffleWords(String[] dizionario){
Random dice=new Random();
for(int i=0;i<dizionario.length;i++){
int index=dice.nextInt(dizionario.length);
String temp=dizionario[index];
dizionario[index]=dizionario[0];
dizionario[0]=temp;
}
}

//Funzione che restituisce la parola (reg. expr.) che passa x un punto (in verticale o in orizzontale) data una coordinata
//Si assume che coord sia una cordinata interna allo schema
//Lancia NonIntersectingWordsException se non c'è una parola che interseca la coordinata (coord è una cella nera o la parola
// è di una sola lettera
private String intersectingWord(Coordinata coord, Orientamento orient){
if(getSchemaChar(coord)=='#')
throw new NonIntersectingWordsException("Cella nera");

String ret=""+getSchemaChar(coord);
Coordinata it=new Coordinata(coord.riga,coord.colonna); //it sta per iterator
if(orient.verticale){ //Se è in verticale concateno i caratteri in colonna spostandomi di riga
it.riga--;
while(it.riga>=0 && getSchemaChar(it)!='#'){
ret=getSchemaChar(it)+ret;
it.riga--;
}
it.riga=coord.riga+1;
while(it.riga<schema.length && getSchemaChar(it)!='#'){
ret=ret+getSchemaChar(it);
it.riga++;
}
}else{ //Se è in orizzontale concateno i caratteri in riga spostandomi di colonna
it.colonna--;
while(it.colonna>=0 && getSchemaChar(it)!='#'){
ret=getSchemaChar(it)+ret;
it.colonna--;
}
it.colonna=coord.colonna+1;
while(it.colonna<schema[coord.riga].length && getSchemaChar(it)!='#'){
ret=ret+getSchemaChar(it);
it.colonna++;
}
}
if(ret.length()==1)
throw new NonIntersectingWordsException("Una sola lettera");

return ret;
}

private char getSchemaChar(Coordinata coord){
return schema[coord.riga][coord.colonna];
}

//Funzione che restituisce un array di stringhe in formato reg. expr. con le parole che intersecano un'altra (x coordinate)
//Fa uso di intersectingWord() ma bisogna fare attenzione a non uscire dallo schema.
//Gestisce il NonIntersectingWordsException di intersectingWord.
//Si assume che coord e orient siano una coordinata valida (è la prima cella di una parola)
//Lancia NonIntersectingWordsException SOLO se al termine nessuna parola è stata trovata
private String[] intersectingWords(Coordinata coord, Orientamento orient){ //coord è l'inizio della parola, orient il suo orientamento
Orientamento orientToUse=new Orientamento(!orient.verticale);
ArrayList<String> ret=new ArrayList<String>();
String parola=intersectingWord(coord,orient);
if(orient.verticale)
for(int i=0;i<parola.length();i++){
try{
String temp=intersectingWord(new Coordinata(coord.riga+i,coord.colonna),orientToUse);
ret.add(temp);
}catch(NonIntersectingWordsException e){
}
}
else
for(int i=0;i<parola.length();i++){
try{
String temp=intersectingWord(new Coordinata(coord.riga,coord.colonna+i),orientToUse);
ret.add(temp);
}catch(NonIntersectingWordsException e){
}
}
if(ret.size()==0)
throw new NonIntersectingWordsException("Nessuna parola intersecante trovata");
return (String[])ret.toArray(new String[0]);
}

//Funzione che scrive una parola nella posizione indicata. Restituisce true se la parola è stata inserita con successo, false altrimenti
//Deve controllare che le parole che intersecano la parola appena inserita siano ancora valide ossia ci siano delle matchingWords
//rispetto alle loro espressioni regolari, se sì torna true, altrimenti cancella la parola appena inserita con writeWordNoCheck
//usando il valore di old e torna false. Si assume che coord e orient siano valori validi per la lunghezza di parola e old.
//Se inserendo le lettere si completa qualche parola intersecante bisogna impegnarla nel minidizionario corrispondente.
private boolean writeWord(String parola, Coordinata coord, Orientamento orient, String old){
Orientamento orientToUse=new Orientamento(!orient.verticale);
if(orient.verticale){
for(int i=0;i<parola.length();i++){
if(parola.charAt(i)!=old.charAt(i)){ //Non riscrivo i caratteri uguali
schema[coord.riga+i][coord.colonna]=parola.charAt(i);
try{
String parolaIntersecante=intersectingWord(new Coordinata(coord.riga+i,coord.colonna),orientToUse);
String possibiliParole[]=matchingWords(miniDizionari[parolaIntersecante.length()],parolaIntersecante);

boolean ok=false;
for(int j=0;j<possibiliParole.length;j++){
if(possibiliParole[j].indexOf("#")<0)
ok=true;
}
if(ok){
if(parolaIntersecante.indexOf(".")<0){ //Se ho completato una parola
replace(miniDizionari[parolaIntersecante.length()],parolaIntersecante,genString('#',parolaIntersecante.length()));
addDaDisimpegnare(parolaIntersecante);
}
}else{
writeWordNoCheck(old,coord,orient);
return false;
}
}catch(NonIntersectingWordsException e){

}

}
}
}else{
for(int i=0;i<parola.length();i++){
if(parola.charAt(i)!=old.charAt(i)){ //Non riscrivo i caratteri uguali
schema[coord.riga][coord.colonna+i]=parola.charAt(i);
try{
String parolaIntersecante=intersectingWord(new Coordinata(coord.riga,coord.colonna+i),orientToUse);
String possibiliParole[]=matchingWords(miniDizionari[parolaIntersecante.length()],parolaIntersecante);

boolean ok=false;
for(int j=0;j<possibiliParole.length;j++){
if(possibiliParole[j].indexOf("#")<0)
ok=true;
}
if(ok){
if(parolaIntersecante.indexOf(".")<0){ //Se ho completato una parola
replace(miniDizionari[parolaIntersecante.length()],parolaIntersecante,genString('#',parolaIntersecante.length()));
addDaDisimpegnare(parolaIntersecante);
}
}else{
writeWordNoCheck(old,coord,orient);
return false;
}
}catch(NonIntersectingWordsException e){

}

}
}
}

return true;
}

//Funzione che scrive una parola nella posizione indicata senza controllare la sua correttezza. (Serve a cancellare parole già inserite)
//Si assume che coord e orient siano valori validi per la lunghezza di parola.
//Se inserisce dei '.' dove prima c'era una parola completa deve disimpegnare quella parola dal minidizionario corrispondente.
private void writeWordNoCheck(String parola, Coordinata coord, Orientamento orient){
Orientamento orientToUse=new Orientamento(!orient.verticale);

if(orient.verticale){
for(int i=0;i<parola.length();i++){
if(parola.charAt(i)=='.'){
try{
String temp=intersectingWord(new Coordinata(coord.riga+i,coord.colonna),orientToUse);
if(temp.indexOf(".")<0){ //Se sto per cancellare una parola completa
if(subDaDisimpegnare(temp)) //Se era una parola impegnata
replace(miniDizionari[temp.length()],genString('#',temp.length()),temp); //Prima la disimpegno
}
}catch(NonIntersectingWordsException e){
}
}
schema[coord.riga+i][coord.colonna]=parola.charAt(i);
}
}else{
for(int i=0;i<parola.length();i++){
if(parola.charAt(i)=='.'){
try{
String temp=intersectingWord(new Coordinata(coord.riga,coord.colonna+i),orientToUse);
if(temp.indexOf(".")<0){ //Se sto per cancellare una parola completa
if(subDaDisimpegnare(temp)) //Se era una parola impegnata
replace(miniDizionari[temp.length()],genString('#',temp.length()),temp); //Prima la disimpegno
}
}catch(NonIntersectingWordsException e){
}
}
schema[coord.riga][coord.colonna+i]=parola.charAt(i);
}
}
}

//Funzione che trova il primo spazio libero (prima orizzontale, poi verticale) dove inserire la prossima parola (quindi uno spazio di almeno 2 lettere)
//Lancia NoMoreSpaceException se non ci sono più spazi liberi
//Fa uso della funzione seguente (nextOrientedFreeSpace())
//nextFreeSpace() deve essere ottimizzata in modo da cercare il posto più conveniente dove mettere la prossima parola in modo da
//incrementare il numero di intersezioni con altre parole e quindi permettere di capire più in fretta se le parole che si stanno
//inserendo non sono adatte allo schema
//A questo scopo la prima versione di nextFreeSpace deve ricercare il primo spazio libero verticale e quello orizzontale e restituire
//quello più "vicino all'origine" (Riga zero, Colonna zero). In caso di parità ritornare lo spazio orizzontale. Inoltre le righe hanno
//la priorità sulle colonne cioè la posizione [0][15] è più "vicina all'origine" della posizione [1][0]
private Coordinata nextFreeSpace(Orientamento orient){ //orient è un valore di ritorno aggiuntivo che dice in che verso è lo spazio libero
Coordinata cOriz=null;
Coordinata cVert=null;
try{
cOriz=nextOrientedFreeSpace(new Orientamento(false));
}catch(NoMoreSpaceException e){
}
try{
cVert=nextOrientedFreeSpace(new Orientamento(true));
}catch(NoMoreSpaceException e){
}
if(cOriz==null && cVert==null)
throw new NoMoreSpaceException("Sono finiti gli spazi vuoti!");
if(cOriz==null || cVert!=null && cVert.compareTo(cOriz)<0){
orient.verticale=true;
return cVert;
}
orient.verticale=false;
return cOriz;

}

//Lancia NoMoreSpaceException se non ci sono più spazi liberi nell'orientamento indicato
private Coordinata nextOrientedFreeSpace(Orientamento orient){ //orient indica in che verso va ricercato lo spazio libero
for(int r=0;r<schema.length;r++){
for(int c=0;c<schema[r].length;c++){
try{
String temp=intersectingWord(new Coordinata(r,c),orient);
if(temp.indexOf(".")>=0)
return new Coordinata(r,c);
}catch(NonIntersectingWordsException e){
}
}
}
throw new NoMoreSpaceException("Finiti spazi vuoti (orient.verticale="+orient.verticale+")");
}

//ECCEZIONI
private class NonIntersectingWordsException extends RuntimeException{
NonIntersectingWordsException(String msg){
super(msg);
}
}

private class NoMoreSpaceException extends RuntimeException{
NoMoreSpaceException(String msg){
super(msg);
}
}

}

Quella che la usa:
import java.util.Scanner;

class ProgettoCruciverba{

public static void main(String[] args){
Cruciverba c=null;
String schema="Schemi\\";
String pathSave="Soluzioni\\";
try{
c=new Cruciverba("Definizioni.txt");
}catch(Exception e){
System.out.println("Errore nell'apertura di Definizioni.txt");
System.out.println(e.getMessage());
return;
}
System.out.println("Dizionario Caricato");

Scanner tastiera=new Scanner(System.in);

System.out.println();
System.out.println("Si desidera mostrare il progresso della risoluzione(piu' lento)? (yes/no)");
if(tastiera.nextLine().equalsIgnoreCase("yes")){
c.setShowLoading(true);
System.out.println();
System.out.println("ATTIVATO!");
}else{
System.out.println();
System.out.println("NON ATTIVATO!");
}

while(true){
System.out.println();
System.out.println("Inserire il nome dello schema da risolvere (senza .txt):");
String inp1=tastiera.nextLine();
System.out.println();
try{
c.loadCruciverba(schema+inp1+".txt");
}catch(Exception e){
System.out.println("Errore nell'apertura di "+schema+inp1+".txt");
continue;
}

if(c.fill()){
System.out.println("Soluzione trovata. Inserire il nome del file su cui salvare la soluzione (senza .txt):");
String inp2=tastiera.nextLine();
try{
c.saveCruciverba(pathSave+inp2+".txt");
}catch(Exception e){
System.out.println();
System.out.println("Errore nel salvataggio di "+pathSave+inp2+".txt");
}
}
else
System.out.println("Nessuna soluzione trovata per questo schema");
}
}

}
So che non è molto elegante come codice ma una volta che mi sono reso conto della lentezza dell'algoritmo ho sospeso il progetto per tornarci qualora avessi avuto qualche idea per migliorarlo.
Ah, ti do anche degli schemi con cui l'ho testato e le soluzioni e il dizionario che mi sono scritto copiando le definizioni di un bel po' di cruciverba.

[Enrico Corsaro]

Vi ringrazio per le risposte...
grazie wingman anche per il codice, tuttavia non è ciò che al momento mi interessa, oltre a non essere nel linguaggio in cui devo lavorare, ma vedrò di darci comunque un occhio nel caso serva :).