I'm just doing a nearest neighbor approximation for now, which seems really good.įor example, on a board where the total path length from the words themselves was 930, the nearest neighbor path length was 1060, and the path length from sorting by anything else was around 1400. Words can be produced by many paths, the best one is the one that's worth the most points.įor a board full of basic tiles these distinctions don't matter, because paths only yield one word and all paths yielding a word are worth the same amount of points. It's a little more complicated than that because we don't actually visit words, we visit paths.Ī path can yield multiple words (either/or tiles), and it's not just any path producing a word that we visit, the path has to be a best path for a word. We want to find the shortest path visiting each word exactly once. Visiting a word adds on a fixed amount of length equal to the word's path length (but you could incorporate this into the edges). The best path is a travelling salesman problem where words are vertices and edge lengths are the distances from a word's last tile to another word's first tile. Everything knows about the model (but as little as possible).Įverything is made to be generalizable, so it would be easy to extend the solution to support new tile types, different board sizes (as long as they're rectangular), different allowed moves (like only diagonals, or weird jumps), or other languages.Īny number of special tiles are allowed, and invalid tiles are handled gracefully by simply being ignored.

The view knows nothing about the presenter, it just fires events for the presenter to subscribe to and handle. I'm using the Model-View-Presenter pattern. The solution uses a trie, which offers the big benefit of short-circuiting the recursion/DFS-ing when a string doesn't appear as a prefix in the dictionary (and therefore adding more tiles to it can't produce words).Īs a minor optimization, previous search results are used to skip down into the trie in successive searches (making use of the fact that the strings from the latter are necessarily prefixed by the strings from the former, given how we're traversing the board). Solver library available as a NuGet Package. Wordament solver that handles an arbitrary number of special tiles, finds the many-to-many word-path relationships, and approximates a best path.