Any suggestions for my sudoku solving computer program?

Are you building a recursive tree structure? I didn’t fully follow your description (also my knowledge of sudoku is pretty limited). I’m not sure if you’re familiar with the A* pathfinding algorithm, but I would imagine a sudoku solver might follow a similar approach.

I took a brief look at your reference and it seems to be a way of optimizing a search. The computer algorithm I used is not very efficient. There is a lot of duplication, but it runs quickly. There are only 81 squares in total, and the only ones that need to be searched are the non-blank ones, which start off at a number less than 81 and the number keeps getting smaller as the squares are filled in.

On a higher level, what’s the joy in having a program solver Sudoku? I anjoy figureing them out myself.

@elbanditoroso “On a higher level, what’s the joy in having a program solver Sudoku? ”

Some might say that solving EVERY sudoku in the fastest possible way is even more fun than doing them manually, one-at-a-time.

@LostInParadise

I played a couple of rounds to refresh my memory of the rules, and I have a better understanding of your algorithm. A* works by tracking all possible solutions, but also uses a secondary huristic that prioritizes what is searched first. If your solution gets to a state where it cannot find any more solutions and hasn’t completed the puzzle, it could start pushing through a brute force search, guided by completing the boxes and rows that are closest to completion. It would make a guess and then try to complete the puzzle with the guess, if that failed it would try another possible digit in the box and attempt to complete the puzzle, iterating through in that manner until you have found a solution.

For instance, if there’s one box with 4. empty squares, pick the start with the box with the row or column that is closest to completion. then guess one of the 4 remaining numbers and test each one, playing out all other possible moves until a failure, then try the next remaining number for that first box and repeat.

Thanks for your explanation. I will have to look at A*. Taking guesses is messy, because you have to keep track of what you do after the guess so that you can backtrack if the guess does not work.

@elbanditoroso , I was just curious about the extent to which the puzzle solving could be mechanized.

Call the state where there is no guaranteed solution (exactly what you’ve already coded) a node. Then for each guess, you work through your algorithm again and it will either fail, win, or result in another ambiguous state with some number of total empty squares on the board (that’s your heuristic), that’s another node on the tree. Process all nodes in order of closest to completing a box/row/column. If no squares fully solve the puzzle, then move on to testing each ambiguous node, in order of the fewest total remaining empty squares (starting with the square with the fewest empty squares in its box/row/column.

I would guess a “depth-first” search would probably make the most sense. I think this is a factorial big O problem, but I’m not sure.

Also, you’re going to want to preserve in memory the board’s ambiguous state for each node’s guess, so you don’t have to constantly re-compute it.

Thanks again, but for the time being I will be concentrating on non-ambiguous results. What you outlined is going to take a fair amount of work, so it will have to be a project for another time.

I don’t have a good answer for you. I have some quick tricks I use when I am solving a sudoku.
I start with the number that has the most entries and jump to the 3×3 boxes where they are missing. I then work my way down the list.
Human tricks are really not necessary since your processor is so much faster – even if you are using brute force.

I really like that you are doing this.

I had the program count how many times it executed in the innermost loops for the one example. It came to about 15,000, not much work for a computer and humanly possible over the course of a few months.

The program required 6 passes through the examination of each square. The number of squares filled on each pass was about the same. As the program progresses there are fewer squares available to be filled but a greater likelihood of filling one of them.

Correction – about 20,000 times in inner loops, still a walk in the park for a computer, and doable by a human in less than a year.

The program completed a puzzle rated as hard. For a puzzle rated expert, it was only able to fill in 10 out of 22 blank squares.