Some time ago, I wrote a Sudoku solver in Haskell, as many others have done - it was a good practice project. It uses a simple brute force algorithm: find an empty square (if there is no empty square then the puzzle is solved), determine what values can go in the empty square, and then for each possible value put the value in the square and solve the resultant grid recursively. It all works very well, and takes about three seconds to solve the puzzle that was claimed in 2012 to be the hardest Sudoku puzzle ever devised.
As I enjoy doing Killer Sudoku puzzles, I then turned my attention to extending the solver so that it can solve Killer Sudokus too. If you're not familiar with this variant, I should explain that a Killer Sudoku grid is divided into regions, each of which includes between 2 and 9 squares and has a total associated with it. In a valid solution, the squares in each region all contain different values, which add up to the total of that region. This is in addition to the normal Sudoku rules, which say that each of the values 1 to 9 must appear once in each row, column and box; and the additional information given by the regions means that it is not necessary for a Killer grid to be seeded with some of the values in the solution.
I implemented this by extending the algorithm that solves regular puzzles to work polymorphically on both regular and Killer puzzles. At its heart, this means that working out which numbers can go in a particular empty square needs to take into account the constraints of the region that contains the square, as well as of the row, column and box.
I have individually tested each of the functions that are part of the solution, and they all seem to work; but when I run the solver on an example Killer puzzle it never terminates, and I don't understand why. Solving a regular puzzle still completes, though. So my questions are:
Is there anything in the code (https://github.com/hicksjduk/sudoku-haskell/blob/main/sudoku.hs) that I haven't spotted, and which would make the solver hang?
What tools can I use to examine the execution of my code, and find out what is causing the hang?
For information, I run the solver by loading the code file into ghci, and then running one of the following commands:
sudoku puzzleto solve a regular puzzlesudoku killerPuzzleto solve a killer puzzle
Thank you to those who have responded. It seems clear now that there is nothing wrong with my algorithm, except that it is not efficient enough to run in an acceptable time. I know this because I have run it against a Killer puzzle which is rated "Easy" on the website where I found it, and although it took a few minutes the correct solution was found. (The puzzle I was originally using is rated "Outrageous", and still takes longer to solve than I am prepared to wait.)
I had already implemented an optimization aimed at solving the squares with the fewest options first - the list of regions is sorted in ascending order of the number of possible values each region can contain, and when looking for an empty square the squares are searched in the order their regions appear in that sorted region list. But as most regions can contain all the possible values, that clearly isn't enough.
Comparing the algorithm applied to a standard puzzle with that applied to a Killer puzzle, it seems clear that the extra constraint (related to the region) on the values that can appear in a square is the part that is taking a lot of extra time, so I think that that is where my optimization efforts need to be concentrated. I have tried another optimization, by caching the results of the
combinationsfunction, but it doesn't seem to have made much of a difference.So as and when time permits, I will keep on looking for further optimizations, and if I find one I will update this answer.