An Improved Framework of Backtracking Algorithm to Solve Sudoku

Abstract: Sudoku is a pretty popular number game. The goal of this game is to fill a 9x9 matrix with unique numbers, and there should not be repeated numbers in each row, column, or block. There are several possible algorithms to automatically solve Sudoku boards; the most notable is the backtracking algorithm, that takes a brute-force approach to finding solutions for each board configuration. The backtracking algorithm uses an array of the legal numbers in the cell to attempt a solution before it moves on to the next cell. If a solution cannot be found, it backtracks and attempts to solve the board again with a different guess choice. The more errors the solver makes, the more backtracks it must perform, which decreases its overall efficiency and increases its effective runtime. We analysed the difference in the algorithm performance by comparing the number of recursive backtracks between sequential and randomly distributed guesses. Analysis show that using values that are given in a shuffled array significantly reduces the number of backtracks done by the solver and, as a result, improve the total effective efficiency of the algorithm as a whole.

Keywords: Sudoku solver, backtracking algorithm, algorithm design and analysis