この論文がナインメンズモリスの解法みたい。面倒臭そうなんでやらないけど。
ちなみに、総当りだと10^30通りぐらいらしい。

http://www.msri.org/publications/books/Book29/files/gasser.pdf