Kreuzworträtsel Gitter erstellen
-
Hallo,
ich bin leidenschaftlicher Rätselrater und möchte daher einen Kreuzworträtselgenerator programmieren in C++.
Dazu habe ich folgendes Problem zum Aufbau eines leeren Rätselgitters, dh es sollen nur die Felder, die die Fragen aufnehmen vorhanden sein und in welcher Richtung das Lösungswort eingetragen werden muss.
Das "leere" Gitter soll folgende Bedingungen erfüllen:
1. Größe des Rätsels fest vorgegeben
2. jedes Feld nimmt entweder einen Buchstaben oder 1 Frage auf (es gibt also keine leeren Felder)
3. zu jedem Wort gibt es genau eine Frage, die in dem entsprechenden benachbarten Feld untergebracht ist(4. eine freie zusammenhängende Reihe (senkrecht/waagerecht) mit mind. 2 Buchstaben enthält ein Wort) muss nicht unbedingt sein
Frage: Wie sollte ich am besten an die Sache herangehen?
Eine Möglichkeit scheint mir ein Backtracking-Algorithmus sein, aber nach welchen Bedingungen soll ich die Felder für die Fragen setzen.
mori
PS: Falls jemand nicht weiß, welche Art Rätsel ich meine. Das Schwedenrätsel aus der Wikipedia:
http://de.wikipedia.org/wiki/Kreuzwortr%C3%A4tsel
-
Um das Kreuzworträtsel zu füllen, würde ich, um es schon mal sauber zu machen, eine "Wort"-Klasse und eine "Kreuzworträtsel"-Klasse anlegen. Das Kreuzworträtsel kann ja theoretisch aus einem zweidimensionalen char-Array "herstellen"; die Fragen muss man dann mit Zahlen repräsentieren oder irgendwie da reinpfriemeln...wie auch immer.
Als nächstes würde ich das Rätsel in vertikale Spalten unterteilen (sehr rechenintensiv 
)und einen Algorithmus bauen, der immer prüft, wie viele Felder ein "Wort" benötigt (vertikal (wortlänge) und horizontal (1)) und dann die passenden "Wörter" auswählt. Wie man die leeren Felder dann macht, ist egal. Man kann ja z.B. noch ein zweites Kreuzworträtsel-Objekt machen und da alle Buchstaben rauslöschen, sodass man nur noch die Zahlen übrig hat.Gut, dann fröhliche Weihnachten :xmas1: und viel Spaß beim Kreuzworträtseln,
LauritzG
-
mori schrieb:
Eine Möglichkeit scheint mir ein Backtracking-Algorithmus sein, aber nach welchen Bedingungen soll ich die Felder für die Fragen setzen.
Ich gehe davon aus, daß Du das 8-Damen-Problem schon gelöst hast.
Ich würde mich gar nicht an ein Schwedenrätsel trauen, sondern nur an ein amerikanisches Kreuzworträtsel (,wobei ich netterweise die Trennstriche schon drucken würde), zumal dabei die Vernetzung größer sein wird und auch mal längere Fragen möglich sind, wie "Wie heißt der Bürgermeister von Wesel? (Weskamp)" (muß man ja wissen).Auch würde ich wenn ich mich an ein Schwedenrätsel wagen würde, trotzdem vorher ein Amirätsel implementieren, um genug zu lernen für den Endsieg. Im Prinzip Backtracking, dabei für waagerecht und senkrecht unabhängig mitschreiben, welche Felder schon benutzt sind, es entsteht eine schräge "Küste" zwischen belegt und nicht-belegt. (Dieselbe Küste, die der Löser hat.) Nee, ist Unfug. Ich nehme alles zurück.
Mit so wenig Ahnung, wie ich davon habe, könnte ich nur genetische Algorithmen gegen das Problem werfen. Qualitätsmaß sind Vernetzung und tausendfach die Anzahl der Leerplätze.
Ich denke, ich würde erstmal eine Woche lang oder mehr Schwedenrätsel per Hand erstellen. Dabei muß0 sich einfach genug Durchblick ergeben, wie ich das programmtechnisch ansetzen sollte. Muß. Wenn nicht, halt zwei Wochen oder drei.
-
volkard schrieb:
Ich denke, ich würde erstmal eine Woche lang oder mehr Schwedenrätsel per Hand erstellen. Dabei muß0 sich einfach genug Durchblick ergeben, wie ich das programmtechnisch ansetzen sollte. Muß. Wenn nicht, halt zwei Wochen oder drei.
So viel ich weiss werden die durchaus noch von Menschen zusammengestellt. Habe mal irgendwo was gesehen, wo ein Mann das als Job hatte. Kann aber nicht mehr sagen, wo und wann das war. Kann mir aber durchaus vorstellen, dass die Zeitungsfirmen da durchaus Leute angeheuert haben, die die Dinger von Hand erstellen und keine Programmierer, die das ausprogrammieren.
Ich würde wahrscheinilch auch was mit Backtracking versuchen, auch wenn das bei so grossen Feldern ja recht mühsam werden kann..
-
Also ich würde vermuten, dass du vor allem erstmal eine wahnsinnig umfangreiche Datenbank mit Frage-Antwort-Kombinationen brauchst. Besonders viele kurzen Wörter mit 1-6 Buchstaben. Dann wird mit ein paar langen Wörtern ein Grundgerüst erstellt (meinetwegen von Hand) und dann irgendwie (das Wie ist dann der Trick) der Rest mit passenden Wörtern aus der Datenbank gefüllt.
Das ist zumindest meine Vermutung nachdem ich mal während eines Krankenhausaufenthaltes ein Kreuzworträtselheftchen durchgebracht habe. Die langen Wörter (>6 Buchstaben) sind immer andere, sie geben dem Rätsel Struktur. Der Rest ist immer das gleiche Füllmaterial, manchmal sogar mehrmals das gleiche in einem einzigen Rätsel.
-
drakon schrieb:
So viel ich weiss werden die durchaus noch von Menschen zusammengestellt.
Ja, die guten sind noch per Hand, so scheint es. Um so interessanter ist es, mal einen guten Bot zu bauen. Da steckt für denjenigen, der es gut schafft, ein mehrfaches Einkommen drin.
-
Danke erstmal für die Antworten.
drakon schrieb:
Als nächstes würde ich das Rätsel in vertikale Spalten unterteilen (sehr rechenintensiv
)und einen Algorithmus bauen, der immer prüft, wie viele Felder ein "Wort" benötigt (vertikal (wortlänge) und horizontal (1)) und dann die passenden "Wörter" auswählt. Wie man die leeren Felder dann macht, ist egal. Man kann ja z.B. noch ein zweites Kreuzworträtsel-Objekt machen und da alle Buchstaben rauslöschen, sodass man nur noch die Zahlen übrig hat.Wegen der Komplexität des Problems, habe ich die Erstellung des Gitters und die "Lösung" (Füllen mit Wörtern) getrennt.
Bisher folgender Aufbau:
1. Grid-Klasse: liefert mir eine std::list<list_entry> mit den Positionen für Beschreibungsfelder und "Dummy-Wörtern".
struct list_entry { int len; // laenge int dir; // richtung int x; // start x-pos for word int y; // start y-pos for word int dx; // position for description int dy; // position for description std::string descr; std::string word; };zur Zeit habe ich zu Testzwecken einen einfachen trivialen Ansatz gewählt.
Zuerst fülle ich die erst Zeile mit Beschreibungen und "Wörtern";
00 = leere Felder
| = Buchstabe für senkrechtes Wort
- = Buchstabe für waagerechtes Wort
+ = sowohl als auchZahlen grösser Null sind Beschreibungsfelder
04,32, |, |,08,16,16,16,16,16, -, -, +, +, -, |, |, |, |, |, 00,00, |, |,00, |, |, |, |, |, 00,00, *, *,00, |, |, |, |, |, 00,00,00,00,00, |, *, |, *, |, 00,00,00,00,00, |,00, *,00, |, 00,00,00,00,00, *,00,00,00, *, 00,00,00,00,00,00,00,00,00,00, 00,00,00,00,00,00,00,00,00,00, 00,00,00,00,00,00,00,00,00,00,Dann die erste Spalte:
04,32, |, |,08,16,16,16,16,16, -, -, +, +, -, |, |, |, |, |, -, -, +, +, *, |, |, |, |, |, 02,00, *, *,00, |, |, |, |, |, 01, -, -, -, *, |, *, |, *, |, 04,00,00,00,00, |,00, *,00, |, -, -, -, *,00, *,00,00,00, *, 04,00,00,00,00,00,00,00,00,00, -, -, -, *,00,00,00,00,00,00, 01, -, -, -, *,00,00,00,00,00,Dann der übrige Rest:
04,32, |, |,08,16,16,16,16,16, -, -, +, +, -, +, +, +, +, +, -, -, +, +,01, +, +, +, +, +, 02,16,01, +, -, +, +, +, +, +, 01, +, -, +,16, |,16, |,16, |, 04, |,16,01, +, +, +,16, |, |, -, +, +,16, |,01, +, +, +,16, 04,01, +, +, +, -, +, +, +, +, -, -, +, +, +,01, +, +, +, +, 01, -, +, +,01, -, +,01, +, +,Dabei werden Sterne(Wortendemarkierungen), die im Wege sind einfach gelöscht.
Wie man an diesem Beispiel sieht, kommen durchaus brauchbare Lösungen heraus.
Aber bei weitem nicht immer. Bei dieser Variante ist eben nur garantiert, dass keine leeren Felder enstehen.Leider ist damit nicht garantiert, dass sich die Wörter überschneiden. Auch kommt es zu isolierten Worten (Wörter die durch Beschreibungsfelder komplett vom Rest des Rätsels getrennt sind).
Frage: Irgendwelche Ideen, wie ich auf dieser Grundlage das Gitter besser generieren kann??
2. Crosswordklasse: füllt die std::list<list_entry> mit Worten und der Beschreibung (das funkioniert bereits)
Beispiel: (für ein 10x10 felder grosses Rätsel)
Solved 47: ---------------- ZP FERIENGAST OLEA UTRUM SAMHARA HIT E R K Y TNS RA GDP H UOE ELEGIKER QUALM ZITA DKB RA ZN 1: (0,0) (0,1) dir=1 len=10 word= FERIENGAST = Urlauber 2: (1,0) (2,0) dir=0 len=3 word= ZRE = Auto-Z. Zaire 3: (4,0) (3,0) dir=0 len=5 word= PIAST = Angeh÷riger eines poln. Herrscherhauses 4: (5,0) (5,1) dir=0 len=5 word= NUMEN = Gottheit (lat.) 5: (6,0) (6,1) dir=0 len=3 word= GTH = Auto-Z. Gotha 6: (7,0) (7,1) dir=0 len=4 word= ARAR = Wadi in Saudi-Arabien 7: (8,0) (8,1) dir=0 len=3 word= SUR = Nebenfluss der Aare 8: (9,0) (9,1) dir=0 len=5 word= TMAKA = Nebenfluss der Wolga 9: (4,2) (5,2) dir=1 len=5 word= UTRUM = Begriff aus der Sprachwissenschaft 10: (0,3) (0,2) dir=1 len=4 word= OLEA = rauchende Schwefelsõuren 11: (1,3) (1,4) dir=0 len=3 word= HYD = griech.: Wasser 12: (2,3) (3,3) dir=1 len=7 word= SAMHARA = afrik. Staat 13: (0,4) (1,4) dir=1 len=3 word= HIT = zugkrõftiges Angebot, Objekt 14: (4,4) (4,5) dir=0 len=4 word= THEM = engl.: sich 15: (6,4) (6,5) dir=0 len=5 word= SUIZA = span.: Schweiz 16: (8,4) (8,5) dir=0 len=5 word= REETZ = Stadt in der Neumark 17: (0,5) (0,6) dir=1 len=3 word= GDP = Abk.: gesamtdt. Partei 18: (2,5) (2,6) dir=0 len=4 word= PEAK = engl.: Berggipfel 19: (3,5) (4,5) dir=1 len=3 word= TNS = Trõger der Erbanlagen 20: (7,5) (7,6) dir=0 len=3 word= OKI = jap. Insel 21: (3,6) (3,7) dir=0 len=3 word= LLB = Abk.: legum baccalaureus 22: (5,6) (6,6) dir=1 len=3 word= UOE = Abk.: und ÷fters 23: (9,6) (9,7) dir=0 len=3 word= RAN = nord. Herrin des Meeres 24: (0,7) (0,8) dir=1 len=5 word= QUALM = Schwaden 25: (1,7) (2,7) dir=1 len=8 word= ELEGIKER = Klagelieddichter 26: (5,8) (6,8) dir=1 len=4 word= ZITA = Frauenname 27: (0,9) (1,9) dir=1 len=3 word= DKB = Auto-Z. Dinkelsb³hl 28: (4,9) (5,9) dir=1 len=2 word= RA = Papyrusboot Thor Heyerdahls 29: (7,9) (8,9) dir=1 len=2 word= ZN = chem. Z. f³r Zinkmori
PS: Das Gitter zu Pkt. 1 ist das selbe, was unter Pkt.2 mit Wörtern gefüllt wurde.
-
Das ist nicht mein Quote.
-
@drakon: per hand und per generator gibt es beides und teilweise auch zusammen. Handarbeit kommt heutzutage meistens nur noch dann ins Spiel, wenn Wunsch- bzw. Pflichtbegriffe ins Kreuzworträtsel integriert werden sollen. Oder bei Querdenker-Rätseln zum um die Ecke denken.
@volkard bzgl. "mal einen guten bot bauen":
Es gibt bereits rund ein Dutzend Kreuzworträtselgeneratoren auf dem Markt. Wieso glaubst du, dass die ALLE stümperhaft oder zumindest nicht gut programmiert haben?@SeppJ.: Deine Vermutung ist goldrichtig. Das Wesentliche ist eine riesengroße Datenbank. Mit nur 10.000 oder 20.000 Begriffen braucht man erst gar nicht anzufangen. Man bekommt zwar komplette Rätsel hin, aber die Qualität ist leider unter aller Sau.
@mori: Sorry, aber die Begriffe aus deiner Datenbank sind absolut nicht zumutbar. Mal ehrlich, ... wieviele der 29 Fragen sind für Normalsterbliche beantwortbar? Zwei? Vier? Nur ganze drei Begriffe haben mehr als 5 Buchstaben, zwei Drittel sind Füllwörter. Einige Erdkundefragen und Kfz-Kennzeichen sind seit 20 oder 30 Jahren veraltet und nicht mehr gültig. Ich möchte dich bei deinem Projekt nicht entmutigen, aber überprüf doch bitte mal, wieviele der Begriffe im Duden oder in der Wikipedia zu finden sind. Wenn du dir mit so einer Vorgehensweise Erfolg erhoffst, wirst du dir zwar eine Menge Arbeit, aber keine Freunde in der Rätselgemeinde machen. Egal wie gut programmiert dein zukünftiger Rätselgenerator sein mag.
Rätselhafte Grüße, Andreas.
P.S.: ich weiß, wovon ich schreibe --->
www.raetsel4u.de
www.raetselfieber.de
www.kreuzifix.de
-
@ andydoubleyou : Das bei meinem Beispiel so viele kleine Worte vorkommen, liegt einfach an der von mir so gewollten Einstellung, da diese Gittererstellung für meinen Generator schwieriger ist.
Was die Qualität der Datenbank angeht, ist beim 1. Beispiel nur so viel Schrott dabei, weil ich zum Testen keine Filtereinstellungen verwende.
anderes Beispiel gefällig:
FA WI K CABARET L DW STATER BEACHTLICH NE ABISKO NR NEK SE MUT SWEBEN DS NERR RE CHR ABS LUEBBECKE 1: (0,0) (1,0) dir=0 len=10 word= FADENNUDEL = Teigware 2: (3,0) (2,0) dir=0 len=8 word= ABWAERTS = nach unten 3: (4,0) (5,0) dir=0 len=10 word= WETTBEWERB = Konkurrenz 4: (7,0) (6,0) dir=0 len=8 word= ITALIKER = alte Bewohner Italiens 5: (9,0) (8,0) dir=0 len=7 word= KLECKSE = Spritzer, Fleck (Mz.) 6: (7,1) (7,2) dir=0 len=3 word= TIS = Nebenfluss des Jenissei 7: (9,1) (9,2) dir=0 len=5 word= RHOEN = Gebirge in Mitteldeutschland 8: (0,2) (0,1) dir=1 len=7 word= CABARET = Musicalfilm 9: (3,2) (4,2) dir=1 len=6 word= STATER = altgriech. M³nze 10: (0,4) (0,3) dir=1 len=10 word= BEACHTLICH = stattlich 11: (3,4) (4,4) dir=1 len=6 word= ABISKO = Naturschutzgebiet in Schweden 12: (0,5) (0,6) dir=1 len=3 word= MUT = Draufgõngertum 13: (3,5) (4,5) dir=1 len=3 word= NEK = it. Popsõnger 14: (7,5) (7,6) dir=0 len=4 word= BRAC = jugoslawische Adriainsel 15: (3,6) (4,6) dir=1 len=6 word= SWEBEN = westgerman. V÷lkergruppe 16: (0,7) (0,8) dir=1 len=2 word= RE = zur³ck 17: (3,7) (4,7) dir=1 len=4 word= NERR = hollõnd. Maler 18: (8,7) (8,8) dir=0 len=2 word= BK = Zeichen f. chemisches Element Berkelium 19: (9,7) (9,8) dir=0 len=2 word= SE = Abk.: South East 20: (2,8) (3,8) dir=1 len=3 word= CHR = Abk.: Christus 21: (6,8) (7,8) dir=1 len=3 word= ABS = dt. Bankier 22: (0,9) (1,9) dir=1 len=9 word= LUEBBECKE = Stadt in NRWmori
-
#include <stdio.h> #include <string.h> #define GROESSFELDX 16 // war 5 s unten war 10 #define GROESSFELDY 16 #define NUM_WORDS 33 // war 152 long int runs=0; unsigned char screen[GROESSFELDX][GROESSFELDY]; unsigned char screeno[GROESSFELDX][GROESSFELDY]; int wordnum; struct { unsigned char word[30]; unsigned int len; unsigned int taken; } words[NUM_WORDS]; long best_score; int fieldnotfull; void backupfield(long score) { int x=0, y=0; while ( y < GROESSFELDY) { x=0; while ( x < GROESSFELDX) { //if ( screen[x][y]==' ') return ; x++; } y++; } fieldnotfull=0; y=0; while ( y < GROESSFELDY) { x=0; while ( x < GROESSFELDX) { screeno[x][y]=screen[x][y]; x++; } y++; } best_score=score; system("cls\n"); y=0; while ( y < GROESSFELDY+2) { x=0; while ( x < GROESSFELDX+2) { if ( y== GROESSFELDY+1 || y==0) printf("-"); else if ( x==0 || x == GROESSFELDX+1) printf("|"); else printf("%c",toupper(screeno[x-1][y-1])); x++; } printf("\n"); y++; } printf("%d\n",best_score); } int crossword(int rec_depth, long score ) { int n; unsigned char wordbuf[50]; //if ( rec_depth < 30)printf("%d ",rec_depth); if ( score >= best_score || fieldnotfull==1 ) backupfield(score); if ( rec_depth > NUM_WORDS ) return 0; long score2=0; int y=0, x=0; int horv=0; int wordnum; wordnum=0; while ( wordnum < NUM_WORDS && words[wordnum].taken==1)wordnum++; if ( wordnum==NUM_WORDS) return 1; //while ( wordnum < NUM_WORDS) if ( rec_depth > 0 && rand()%(score+1)==0) return 1; repeat: if ( kbhit()) return ; if ( rand()%2==0) horv='h'; else horv='v'; x=rand()%GROESSFELDX, y=rand()%GROESSFELDY; wordnum=0; while ( words[wordnum].taken==1 && wordnum < NUM_WORDS )wordnum++; if ( wordnum==NUM_WORDS) return 1; do { wordnum=rand()%NUM_WORDS; }while ( words[wordnum].taken==1 ); //printf("binda %d\n", wordnum); score2=0; if ( horv=='h' ) { if ( x+words[wordnum].len >= GROESSFELDX ) { x++; goto repeat; } n=0; while ( n < words[wordnum].len && x+n < GROESSFELDX ) { if ( screen[x+n][y]!= words[wordnum].word[n] && screen[x+n][y]!=' ' ) { x++; score2=0; goto repeat; } if ( screen[x+n][y]==words[wordnum].word[n] && words[wordnum].taken==0) score2+=100; if ( screen[x][y+n]==' ') score2++; n++; } if ( n!= words[wordnum].len) score2=0; n=0; while ( n < words[wordnum].len && n+x < GROESSFELDX) { wordbuf[n]=screen[x+n][y]; screen[x+n][y]= words[wordnum].word[n]; n++; } int old_wordnum; int wbuflen; wbuflen=words[wordnum].len; old_wordnum=wordnum; //wordnum++; words[wordnum].taken=1; if ( rec_depth==0 || score2 > 100) { if (score+score2>5000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>2000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>1000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>400) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>300) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>200) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>100) crossword(rec_depth+1,score+score2+words[wordnum].len/40); /* if ( */if (score+score2>=0) crossword(rec_depth+1,score+score2+words[wordnum].len/40); /* ==0) return 0; */ // else } { int n2=0; n2=0; while ( n2 < wbuflen && n2+x < GROESSFELDX ) screen[x+n2][y]=wordbuf[n2],n2++; score2=0; words[old_wordnum].taken=0; //wordnum=old_wordnum; x++; goto repeat; } } if ( horv=='v' ) { if ( y+words[wordnum].len >= GROESSFELDY ) { x++; goto repeat; } n=0; while ( n < words[wordnum].len && y+n < GROESSFELDY ) { if ( screen[x][y+n]!= words[wordnum].word[n] && screen[x][y+n]!=' ' ) { x++; score2=0; goto repeat; } if ( screen[x][y+n]==words[wordnum].word[n] && words[wordnum].taken==0) score2+=100; if ( screen[x][y+n]==' ') score2++; n++; } if ( n!= words[wordnum].len) score2=0; n=0; while ( n < words[wordnum].len && n+y < GROESSFELDY) { wordbuf[n]=screen[x][y+n]; screen[x][y+n]= words[wordnum].word[n]; n++; } int old_wordnum; int wbuflen; wbuflen=words[wordnum].len; words[wordnum].taken=1; old_wordnum=wordnum; //wordnum++; if ( rec_depth==0 || score2 > 100) { if (score+score2>5000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>2000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>1000) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>400) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>300) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>200) crossword(rec_depth+1,score+score2+words[wordnum].len/40); if (score+score2>100) crossword(rec_depth+1,score+score2+words[wordnum].len/40); /* if ( */if (score+score2>=0) crossword(rec_depth+1,score+score2+words[wordnum].len/40); /* ==0) return 0; */ // else } { int n2=0; n2=0; while ( n2 < wbuflen && n+y < GROESSFELDY ) screen[x][y+n2]=wordbuf[n2],n2++; score2=0; words[old_wordnum].taken=0; //wordnum=old_wordnum; x++; goto repeat; } } /* wordnum++; while ( words[wordnum].taken==1 && wordnum < NUM_WORDS )wordnum++; if ( wordnum==NUM_WORDS) return 1; wordnum%=NUM_WORDS; */ return 1; } int main(void) { FILE *input; int wc; unsigned char cpstring[30]; wc=0; input=fopen(".\\words.txt","rb"); while ( wc < NUM_WORDS ) { fscanf(input,"%s\n",cpstring); strcpy(words[wc].word,cpstring); words[wc].len=strlen(cpstring); words[wc].taken=0; wc++; } wordnum=0; fclose(input); int x=0,y=0; while ( y < GROESSFELDY ) { x=0; while ( x < GROESSFELDX) { screen[x][y]=' '; screeno[x][y]=' '; x++; } y++; } best_score=0; fieldnotfull=1; crossword(0,0); system("cls\n"); y=0; while ( y < GROESSFELDY+2) { x=0; while ( x < GROESSFELDX+2) { if ( y== GROESSFELDY+1 || y==0) printf("-"); else if ( x==0 || x == GROESSFELDX+1) printf("|"); else printf("%c",toupper(screeno[x-1][y-1])); x++; } printf("\n"); y++; } } /* #include <fcntl.h> #include <stdio.h> #include <stdlib.h> #include <string.h> struct { unsigned char wort[255]; }woerter[250000]; int main(int argc, char *argv[]) { FILE *input, *output; unsigned char c; unsigned long int n; unsigned long int wc; unsigned char cmpstring[255]; if ( argc!=2) return 1; input=fopen(argv[1],"rb"); if ( input==NULL) { printf("Datei nicht gefunden!"); return 1; } wc=0; while (1) { n=0; while (!isalpha(c=fgetc(input))&& !feof(input)) { } do { if ( feof(input)) { fclose(input); printf("%d\n", wc); goto writelist; } cmpstring[n]=tolower(c); n++; if ( n==254) break; } while (isalpha(c=fgetc(input))&& !feof(input)&&n < 254); cmpstring[n]='\0'; if ( n > 2 ) // { // n=0; while ( n < wc) { if ( strcmp(cmpstring,woerter[n].wort)==0) { break; } n++; } if ( n==wc) { strcpy(woerter[n].wort,cmpstring); wc++; } if ( wc==250000) { printf("Mindestens eine viertel Million Woerter!"); return 2; } } } // writelist: if ( wc > 0) { output=fopen(".\\wortliste.txt","wb"); while (wc > 0) { wc--; fprintf(output,"%s\n", woerter[wc].wort ); } fclose(output); } return 0; } */Es dürfte halt für ein Schwedenrätsel nur horizontale mit vertikalen Buchstaben und umgekehrt überkreuzen. So findet es halt auch teilweise Buchstabenübereinstimmungen in Wörtern und versucht, so viele wie möglich ins so und so große Raster zu quetschen.
Der Trick besteht wohl hauptsächlich darin, daß das Backtracking nur dann tiefer gräbt, wenn bereits eine (oder mehrere?) Überkreuzungen gefunden wurden.
