Sudoku ai Agent

For this project I programmed a “Monster Sudoku” agent in C++. This agent is able to solve any NxN sized Sudoku board. In order to determine what move the agent should take next, I implemented six different heuristics: Minimum Remaining Value (MRV), Least Constraining Value (LCV), Forward Checking, Degree, MRV with a Degree tie breaker, and Norvig’s Sudoku heuristic. I evaluated the performance of this agent by keeping track of the number of backtracks and trail pushes performed by the agent while solving any given puzzle. Analyzing the performance of my agent across many different sized boards I observed a few different patterns. On normal 9x9 Sudoku puzzles, it appeared that the Norvig hueristic performed the best with an average of 5 backtracks and 2500 trail pushes. On boards of larger sizes, a mixture of Norvig’s hueristic, MRV, and LCV provided the most efficient solution with an average of 31 backtracks and 7000 trail pushes.