Crossword Generator

[Qwerkey]

This program creates a crossword grid and fills it with words.  The filling routine is quite simple and a number of tries are required before a completed grid is produced.

The program creates a standard 15x15 grid with the following rules:

• Words can be only between 4 and 10 letters long
• The grid is 2-fold symmetric (if you rotate it through 180 degrees, it'll be the same)
• There must be perfect contiguousness

The routine for checking contiguousness is fairly simple, but I believe that it will trap faulty grids: if you discover a noncontiguous grid, please let me know.  The routine for placing the blanks is also fairly simple and some grids do not have the standard crossword look (although all are acceptable).

The method for filling the grid with words is a simple blundering process: a random word of the correct length is tried: if all its squares are blank then this word is added: if some of its squares are already filled and the word does not fit, another word is tried.  If (as is likely) the grid cannot be successfully filled, then another grid is generated and the process begins again.

This blundering process takes some time to achieve a completely filled grid, and some efforts have been made to improve the chance of success.  The dictionary used was created from two readily available on the web: quite a large number of words are thus contained in the dictionary.  You may find (as I do) that a completed grid uses some seemingly improbable words, but somebody has judged them acceptable.  The dictionary also includes some phrases.

When selecting words from the dictionary, the program makes some judgement of how likely the word is to cross successfully.  A word which would produce a cross word ending with unlikely letters like Q or Z is avoided.  And a word which would be less likely to cross with another in the middle (letters like J and X) are also avoided.

So you will notice that a completed grid has words which favour the common letters like E in the crossing positions.  The Qs, J's, K's et cetera will only appear at the start of words or in non-crossing positions.

The longest words are placed first, as fitting the shorter words to existing ones has a better chance.

The program is multilingual, and you can choose which language to use.  The alternatives are:

• British English
• US English
• German
• Spanish
• French
• Italian
• Dutch

Running the program

Extract the folder "Crossword Generator" from the .zip file and place the folder in your QB64 folder (be careful not to create an extra folder layer).  Open the "Multilingual Crossword Generator.bas" in the IDE (with "Output EXE to Source Folder" checked).  [The source folder contains another .bas file which is an older version (English only) of the program].

You will be presented with a Menu List to choose your language.  Although I have constructed this Options Menu to look like an InForm program (Windows native look), there is no mouse function available.  Press the Spacebar to change the language and Return to select your language.


The program will generate a grid and slowly fill with words.  When a word can no longer be found to fit, asterisks are filled in that place - it is unlikely that the grid will be successfully filled - and the program waits for keyboard input.  If you press the Spacebar, another grid will be generated and again words will be added.  If you press "f" when the filling stops, the program will quickly generate new grids and try to fill and the process will continue until a filled grid is obtained. Then the program will again wait for keyboard input.  Spacebar will create another grid, "f" will revert to the step-by-step method.  Esc will quit.

It takes a number of attempts to produce a completely filled grid, and on my Core i5 PC this takes some seconds (dependent upon the language, and if you've a slower machine you may have to wait for longer).

The process to fill the grid clearly has no intelligence to find words that will allow crossing words to be found in a small number of attempts.  An actual human compiler will be careful to think in advance.  Also, there may be some cases where the program, as is, is rejecting acceptable words.  So if you're sufficiently interested, you may like to create a rather cleverer program.

You may well suggest that a naive bystanding youngster would say of this program "But it doesn't do anything!".  This innocent would be correct: the emperor is entirely unclothed.

Multilingual Program now included (Updated 13/09/19)

[Qwerkey]

Memo after a couple of hours of posting the above (for those who may have tried the program):  I just didn't give the program enough chances to find suitable words and the program was very sluggish.  Optimised program now included above.  Apologies for anyone who tried the program before this optimisation.

[petoro]

I have checked it 20 or 25 times. Alas, it hasn't completed any crossword up to now.

Eagerly awaiting for the new version.

[Petr]

That's the perfect idea! Nice graphic design. Thanks for sharing.

[Qwerkey]

I have checked it 20 or 25 times. Alas, it hasn't completed any crossword up to now.

Eagerly awaiting for the new version.

Apologies again, Petoro.  Please try the new version and let me know if working satisfactorily (remember to press "f" when waiting for key input and let it cycle: it's still unlikely to fill the grid in step-by-step mode).

[petoro]

Wow, the old version worked very well and fast by pressing "f" key while paused. It was already very fast at finding a good and complete example.

The new version is even better, faster and cleverer. Amazing. Thank u very much.

[Qwerkey]

Petoro, thank you for your kind words.  I would offer to make a version using the Spanish language, but the program may use only A-Z without accents (ASC values between 64 and 90).  If you could obtain a Spanish dictionary with accented letters converted to nearest unaccented equivalent eg 'a' instead of 'á', i instead of 'í', n instead of 'ñ', I would be able to do such a version.

Please forgive my ignorance, but are there Spanish language crosswords, and if so do they use accented characters?  In English, any accented letters are changed to the closest non-accented version.  Personally, I think that such words should not be allowed in English crosswords (the words should keep their accents and therefore would not cross properly).

[petoro]

Petoro, thank you for your kind words.  I would offer to make a version using the Spanish language, but the program may use only A-Z without accents (ASC values between 64 and 90).  If you could obtain a Spanish dictionary with accented letters converted to nearest unaccented equivalent eg 'a' instead of 'á', i instead of 'í', n instead of 'ñ', I would be able to do such a version.

Please forgive my ignorance, but are there Spanish language crosswords, and if so do they use accented characters?  In English, any accented letters are changed to the closest non-accented version.  Personally, I think that such words should not be allowed in English crosswords (the words should keep their accents and therefore would not cross properly).

Spanish crosswords don't use accented characters. Not sure if some use the "ñ". I will see later if I can find Spanish dictionaries in some text format.

Thank you

[petoro]

I have found a Spanish .txt dictionary sorted by letter here (dict_rae_txt):

https://www.giusseppe.net/blog/archivo/2015/10/29/diccionario-de-la-rae-en-modo-texto-plano/

Alas, it lacks conjugations (which are frequent in Spanish crosswords) and needs conversion in order to avoid accents and discard "ñ" words.

Also it needs to be ordered by number of characters in order to suit your needs...


Petoro

[Qwerkey]

Petoro thanks.  All I need is a dictionary in text format (which you have kindly given me a reference for).  I have routines to convert into the files needed for the program.  I may also be able to handle the accented character conversions (I may need the help of QB64's Expert in All Things, Steve McNeill).  Leave it with me, I'll see what can be done (I shall love doing it - you may have noticed that I love all things words-related).

Richard

[petoro]

Petoro thanks.  All I need is a dictionary in text format (which you have kindly given me a reference for).  I have routines to convert into the files needed for the program.  I may also be able to handle the accented character conversions (I may need the help of QB64's Expert in All Things, Steve McNeill).  Leave it with me, I'll see what can be done (I shall love doing it - you may have noticed that I love all things words-related).

Richard

It is very kind from your part to dedicate your attention to this. Please take your time.

Have a good weekend.

[bplus]

Nice work Qwerkey!

Are you working up a list of clues to match with words? I am eager to see what half these words mean! ;-))

[Qwerkey]

Petoro, there will be hours of fun working with the spanish dictionary.

I shall convert the accented letters as:

á -> a
é -> e
í -> i
ó -> o
ú -> u
ü -> u
ñ -> n

Do you want me to do the ñ conversion, or remove all ñ words?

[petoro]

I am sorry for not being of much help on this task of dictionary conversion. I am somewhat stuck at programming.

Perhaps one should avoid ñ's and ü's in order to not make a very complex/slow algorithm. Anyway, those letters are very rare. Also, it would not be very correct to change them. It would be really good to discard Ñ's and Ü's. Thank you very much,

[SMcNeill]

Petoro, there will be hours of fun working with the spanish dictionary.

I shall convert the accented letters as:

á -> a
é -> e
í -> i
ó -> o
ú -> u
ü -> u
ñ -> n

Do you want me to do the ñ conversion, or remove all ñ words?

If you got your list of words from the website linked above, you can do the conversion quickly, like so:

Code: QB64: [Select]

1. OPEN "a.txt" FOR BINARY AS #1
2. OPEN "a-converted.txt" FOR OUTPUT AS #2
3. DO
4.     LINE INPUT #1, text$
5.     ReplaceAll text$, CHR$(195) + CHR$(161), "a"
6.     ReplaceAll text$, CHR$(195) + CHR$(173), "i"
7.     ReplaceAll text$, CHR$(195) + CHR$(177), "n"
8.     ReplaceAll text$, CHR$(195) + CHR$(179), "o"
9.     ReplaceAll text$, CHR$(195) + CHR$(169), "e"
10.     PRINT #2, text$
11. LOOP UNTIL EOF(1)
12. PRINT "Converted!"
13.  
14.  
15.  
16. SUB ReplaceAll (text$, find$, replace$)
17.     DO
18.         l = INSTR(text$, find$)
19.         IF l THEN
20.             text$ = LEFT$(text$, l - 1) + replace$ + MID$(text$, l + LEN(find$) + 1)
21.         END IF
22.     LOOP UNTIL l = 0
23. END SUB

Since the page is saved in unicode, most of the accented characters  are stored as 2-byte values, with the first byte being CHR$(195) basically representing the command for "draw from the extended set".  If I missed any, just determine which line the offending character falls out, print the ASCII values out to the screen, and then plug the 2-number combo into the replace routine above and let it do all the work for you.  No need for "hours of fun", when you can let the computer do it in moments.  ;)