Local search for solving sudoku puzzles

Sudoku puzzles, logic puzzles traditionally represented by 9x9 grids, have been studied by many researchers looking to understand different types of search approaches better, especially as Sudoku puzzles are NP-complete for variable-sized grids. Many papers have focused on constraint- satisfaction to solve Sudoku puzzles with good success, using the constraints that each number one through nine can only appear once in any given column, row, or 3x3 sub-square for a 9x9 Sudoku puzzle. In contrast, this paper looks to explore the effectiveness of using local search algorithms to solve Sudoku puzzles. Here, we present our strategy and experience implementing four local-search algorithms using two different search heuristics and their ability to solve a set of 9x9 Sudoku puzzles of varying difficulty. Additionally, we provide discussions on our results and an overview of the challenges and successes we had.