53 minutes ago · Tech · hide · 0 comments

I have always been curious if the difficulty of solving puzzles is the same for humans and AI. So I decided to measure the time a basic Python solver took to get the solution for 9x9 sudoku levels, grouped in Easy, Medium, Hard and Diabolical, obtained from the Sudoku Exchange Puzzle Bank. These puzzles were automatically generated, and their difficulty was assigned based on the cost of the actions a human follows. The actions can be one of hidden singles, pairs, X-Wings, Swordfish, and forcing chains, and each has a numeric cost. I used two solvers: a pure-Python heuristic backtracking solver and the Z3 SMT solver. The Python solver is a traditional backtracking solver that prioritizes the empty cell with the fewest candidates (MRV heuristic). And it seems that, on average, this solver takes longer to handle more human-difficult puzzles. The second solver was the Z3 SMT solver, which uses a series of black-box heuristics. I wasn't sure how smart an SMT solver would be in solving the…

No comments yet. Log in to reply on the Fediverse. Comments will appear here.