Sudoku solutions: a comparative analysis of breadth-first search, depth-first search, and human approaches

Abstract

Sudoku is a puzzle that has a unique solution. No matter how many methods are used, the result will always be the same. The player thought that the number of givens or clues, the initial value on the Sudoku puzzles, would significantly determine the difficulty level, which is not necessarily correct. This research uses two search algorithms, breadth-first search (BFS) and depth-first search (DFS), to solve a set of Sudoku puzzles based on the number of givens. The Sudoku puzzles are chosen based on the number of givens between 32 and 35. In cases where Sudoku puzzles are considered medium or intermediate difficulty, the solutions generated by both algorithms will be compared with the human-solving approach. The research aims to determine whether humans tend to solve Sudoku puzzles with solutions resembling those generated by BFS or DFS. Furthermore, if all three approaches-human, BFS, DFS-yield comparable solutions, the Sudoku puzzle has only one unique solution.