Yesterday I was crafting some puzzles for my girlfriends, and I was looking for letter-based ones where I a secret word would be revealed once solved.
With this same goal, I had already once worked on an open-source JS word search generator: https://lucas-c.github.io/wordfind/
(pour les francophones, vous trouverez quelques autres générateurs de jeux de lettres / chiffres dans cet article sur linuxfr.org)
This time I started crafting Masyu puzzles into letter shapes, but then I realized Sudokus would be a perfect pick, with digits replaced by letters ! Those are sometimes named Wordokus.
Hence I wrote a Wordoku generator in Python, where the secret word appears in the diagonal starting from the top-left: secret_word_sudokulike_grid_generator.py
# ./secret_word_sudokulike_grid_generator.py ensemble ..L.|...J EMLS|BNKJ BNK.|...L BNKJ|EMSL --------- --------- ....|.... MLSB|JENK J..E|.S.M JKNE|LSBM --------- solution: --------- S..K|.... SBJK|MLEN L..N|KB.S LEMN|KBJS --------- --------- .J.M|.KLB NJEM|SKLB .S.L|..ME KSBL|NJME
Because I wanted to be able to generate grids for any size, even for prime number sizes like 7, this program can drop the constraint of the boxes for those cases: the generated grid is a pseudo-sudoku, where the only rules are that columns & rows must contain all letters.
# ./secret_word_sudokulike_grid_generator.py --no-boxes-constraint ensemble E . M . . L . . E D M S N L Q B . N . M . . S L Q N D M B E S L B E . . . . . N B E S L Q D M N . . . . . . . . solution: N S B E L Q D M D . L B . N . S D Q L B M N E S . M E . . . N . L M E D S B N Q S B . . E . . D S B Q N E M L D . . . Q D S B . M L N Q D S B E
You can see that the word
ENSEMBLE appears on the diagonal in the solution.
On the technical side, the script is relatively straightforward. I only needed a fast sudoku solver. I used Ali Assaf's excellent one, that he describes in this article: https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
Using the fact that Sudoku puzzles may be described as an exact cover problem, he implemented Donald Knuth « Algorithm X » with Dancing Links ( how poetic ! )
Kudos to him for writing this. The code is under the GNU GPL license.
At some point I tried to optimize the code using Numpy & Numba,
but I faced many issues with the later lib:
no support for
I started looking at at contributing by implementing those,
but Numba's internal code is quite complex. 😞
In the end I did not bother improving the performances: even for a large grid like the size-12 one at the top of this article, the script execution times is between 10s and 10min, which is totally OK for my needs.
EDIT [2019/10/05]: I discovered that this lind of puzzle was sometimes called « SudoLettre » in French.