Nested Monte Carlo Tree Search as Applied to Samurai Sudoku

As Sudoku has come into prominence as a favorite logic puzzle, mathematicians and computer scientists alike have analyzed the game for interesting properties. The large search space presents a challenge for both generating and solving Sudoku puzzles without relying on techniques that simply permute a valid puzzle. These permutations result in puzzles that are essentially the same since they follow the same solution path. Many Sudoku generating or solving programs rely on brute-force methods to avoid this pitfall, but this is inefficient since there is no heuristic to navigate the huge search space. A nested Monte Carlo tree search has some basis in brute-force methods, but guides the search in order to achieve better results by using random games within nested search stages. In this paper, we show that when the nested Monte Carlo search algorithm is implemented for solving Samurai Sudoku, a version of Sudoku in which a standard Sudoku puzzle is placed with four other standard Sudoku puzzles overlapping on each of the corners, it performs better than a completely random brute-force algorithm. Additionally, an improvement to the nested Monte Carlo search is made by implementing a heuristic that is used at each level of search