Boggle Solver in J

Search

The board is given as a character matrix. Paths are lists of indices into the flattened string. The equivalent graph indicating adjacent indices in the flattened string is used to expand paths. Paths that return to the same index, or don't fill out a prefix according to the dictionary are dropped as the search churns along.

Eventually, no more prefixes are available or all the squares have been visited and the search terminates via fixpoint ^: a:. Then, the exact words are selected, nubbed, sorted lexicographically, and sorted length-wise.

The lookups are done by binary search on sorted arrays (I.). This turns out to be good enough, though not blazing fast.

The Program

WL =: (<_1{.a.),~<;._2@(1!:1)@<@jpath@('~/code/joggle/'&,)
W =: = WS {~ (WS=: WL'collins-words.txt')&I.
P =: = PS {~ (PS=: WL'collins-prefixes.txt')&I.
G =: [: <@-.&_1"1 @ |: [: ;"_1 (<:3 3#:4-.~i.9)&(|.!._1)
QU =: {{ 'U' (1+I.b)} y #~ 1+b=. 'Q'=y }} ^: ('Q'&e.)
Q =: QU :. (#~ [: -. _1 |. 'QU'&E.)
L =: {{ <@Q"1 @: ({&u) }}
A =: [ ,"_ 0/ [ -.~ ] {::~ {:@[
E =: {{ ([: (#~ P @: (u L)) [: ; <@(A&v)"1) ^: (0<#) &. > }}
S =: {{ (,y) E (G i.$y) ^: a: <,.i.#,y }}
B =: {{ (\:#&>) /:~ ~. (#~ W) ; (,y) L"1 &.> S y }}

Random Boards

To demostrate the solver, we should get some boards. It would be possible to look up the standard boggle dice and go off those, but we can make more interesting boards instead.

The boards are interesting when they are varied and have good words. Long words are good, so we can get varied and long words by randomly selecting big words from the dictionary.

With a word in hand, we can take a random walk on a grid of some shape and place that word inside the board along the path. The remaining empty squares may then be filled with randomly uniformly chosen letters.

This method promotes less common letters while still ensuring the board has solutions. Totally random letters would lead to awful boards containing almost nothing.

BW =: Q^:_1 &.> (#~ 10<#&>) WS
RW =: {{try. (({~ ?@#) @ A&(G i.x)) ^: (<:y) ? */ x catch. x RW y end.}}
RB =: 4 : 0
  assert. (#y=.Q^:_1 y) <: n=.*/x
  x $ toupper (y,a.{~65+?(n-#y)$26) ((p-.~i.n),~p=.x RW #y)} n $ y
)
RL =: {{ y RB > ({~ ?@#) BW }}
SW =: 0 0 0 1 1 2 3 5 11 {~ 8 <. #

Example

10 {. ,.b;(+/SW&>s);s =: B b=: RL 4 4

   10 {. ,.b;(+/SW&>s);s =: B b=: RL 4 4
┌───────────┐
│EJTU       │
│KLRP       │
│GBAE       │
│BOIF       │
├───────────┤
│217        │
├───────────┤
│PUTREFIABLE│
├───────────┤
│FARTLEK    │
├───────────┤
│GOBBIER    │
├───────────┤
│ABRUPT     │
├───────────┤
│EARBOB     │
├───────────┤
│FAIBLE     │
├───────────┤
│GOBBLE     │
├───────────┤
│PREFAB     │
└───────────┘

Performance

Confirming lookup time

bonsai 'P < ''DRASTICALL''' [ require 'stats/bonsai'

   bonsai 'P < ''DRASTICALL''' [ require 'stats/bonsai'
┌────────┬──────────┬──────────┬──────────┐
│N = 2000│lower     │estimate  │upper     │
├────────┼──────────┼──────────┼──────────┤
│μ       │6.72e_7   │6.92e_7   │7.12117e_7│
├────────┼──────────┼──────────┼──────────┤
│σ       │4.57445e_7│4.66095e_7│4.74745e_7│
├────────┼──────────┼──────────┼──────────┤
│ols     │6.72354e_7│6.93717e_7│7.17568e_7│
├────────┼──────────┼──────────┼──────────┤
│R² (ols)│0.999942  │0.999943  │0.999973  │
└────────┴──────────┴──────────┴──────────┘

And a typicial solve time

('board';'# words'),:(;#@B) b =: 4 4 $ 'ODOEBIRNETYTKGNI' 
bonsai 'B b'

   ('board';'# words'),:(;#@B) b =: 4 4 $ 'ODOEBIRNETYTKGNI' 
┌─────┬───────┐
│board│# words│
├─────┼───────┤
│ODOE │177    │
│BIRN │       │
│ETYT │       │
│KGNI │       │
└─────┴───────┘
   bonsai 'B b'
┌────────┬───────────┬───────────┬───────────┐
│N = 325 │lower      │estimate   │upper      │
├────────┼───────────┼───────────┼───────────┤
│μ       │0.00184397 │0.00186432 │0.00188515 │
├────────┼───────────┼───────────┼───────────┤
│σ       │0.000169553│0.000188477│0.000206246│
├────────┼───────────┼───────────┼───────────┤
│ols     │0.0018498  │0.00186866 │0.00189463 │
├────────┼───────────┼───────────┼───────────┤
│R² (ols)│0.999931   │0.999979   │0.999992   │
└────────┴───────────┴───────────┴───────────┘