A search based Sudoku solver

Abstract. Sudoku is a popular puzzle. In this paper we detail constraint satisfac-tion search algorithms used to solve Sudoku problems. We show that a good value ordering heuristic helps solving problems. We also show that Limited Discrep-ancy search is a good alternative to the traditional Forward Checking algorithm. We have also found a phase transition for 25x25 Sudoku. 1 Introduction Sudoku is a popular puzzle, that was first published in 1979, and that became popular inJapan before its international development. The goal of Sudoku is to put numbers from one to nine on a 9x9 grid. The grid is pre-assigned with numbers. The final positionmust have each number only once in each row and each column. Moreover nine 3x3 squares are also part of the grid, and each number must appear once and only once ineach square