Boggle solver | Reading room | Documentation for kdb+ and q - Kdb+ and q documentation

submited by
Style Pass
2021-06-08 22:00:03

Problem For a given set of Boggle™ dice, throw a board. Identify the words that can be found on it and sort them alphabetically (ascending) within score (descending).

Boggle boards have been made in different languages and sizes. There are old and new versions of English dice for the 4×4 board. Each die is defined by six letters.

In English the letter Q is almost always followed by the letter U. On the Boggle board the two letters appear as one – Qu – and are scored as two letters when counting word lengths.

Generating candidate words starts with each of the sixteen letters. There are a limited number of paths, because letters may not be re-used. So no solution word can have more than sixteen letters.

With NB we can extend any word path. Say our path position pairs are (0 0;1 0;0 1), that is to say, board positions 0 4 1. Then the possible extensions are NB 1 excluding 0 4.

Start with the 16 board positions, find their neighbors, repeat another 14 times, and we have all the paths through the board.

Leave a Comment