K
#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.