Sometimes the mutable structures get passed around in the function arguments, so you might do a sequence of tail recursive calls and on each call you pass in the next board state to the same function. I would hope the Erlang Questions mailing list would help you if you posted a small example and explained your troubles to them. There are lots of very clever Erlang people there.
http://www.erlang.org/faq.html