Csdrhrt

I'm looking for algorithms to find all paths in a 4 x 4 matrix.

The rules are as follows

• You can move in any direction (up, down, left, right, and diagonally)


• The next square in the path must be a neighbour to the current square


• Each square can only be used once


• Each square in the path must be in the bounds of the matrix


• No squares are restricted


• Start squares don't matter


• End squares don't matter

Here is an example of a valid path

  _ _ _ _ 

 | |6| |8|  

 |-|-|-|-|  

 |5| |7|9|  

 |-|-|-|-|  

 |3|4|0| |  

 |-|-|-|-|  

 |2|1| | |  

 |-|-|-|-| 

EDIT - after writing this answer, I realised that I had forgotten that the question was not specifically about Boggle, but in the comments it turned out that the OP and I were talking about Boggle specifically.

EDIT 2 - I have posted a code solution of this in Ruby on Code Review: https://codereview.stackexchange.com/q/203292/22855

I figured out an algorithm on my own, because it was a lot of fun.

Not being well-versed in algorithms, I would love to know if this algorithm has a name. (Let me know in the comments or edit this answer if you know it, please).

(Note that we have a list of valid words - a dictionary - from which to look up chains of letters).

• Start at a given position on the board


• Put the position on a stack. The stack of positions represents a chain of letters (every position on the board has a letter, remember)


• Once the stack has two or more positions, check whether there are any words starting with those letters. If there are none, pop the stack and return (i.e. abandon the current search path - there is no point going down it further if it won't result in a valid word)


• Once the stack has three or more positions, check the letters (from the positions in the stack) against the dictionary and, if the word exists, add it to a set of words collected.


• Cycle through all the possible next positions in turn (N, NE, E, SE, S, SW, W, NW)


• If the next position is out of bounds (off the board) or is already somewhere in the stack, skip that position


• For a valid next position, the routine calls itself (i.e. starts at second point above) with the new position


• Before ending and returning to the previous call, the position is popped off the stack

The whole process is repeated for every position on the board as a starting position, but during processing, paths are aborted, as mentioned, to avoid looking through every possible path for a word that doesn't exist.

Also, in my implementation, my input board has "Q" as a single letter, but I have special handling for "Qu" by pushing a "U" after the "Q" on to the stack and checking to pop a "Q" in addition. ("Qu" counts as two letters in Boggle, but takes up a single side of a cube). That's just specific to my implementation, but it could probably be handled in other ways.