Social Question

LostInParadise's avatar

Any suggestions for my sudoku solving computer program?

Asked by LostInParadise (29005points) 1 month ago
12 responses
“Great Question” (1points)

I just started looking at sudoku puzzles and wrote a program to try to solve them. The algorithm is fairly simple.

For each square, find the possible values that it can have based on what row, column and box it is in. If there is only one remaining value then use that number. This part is a generalization of the idea of adding to a row, column or box that has one missing value.

If there is more than one possible value, then for each value, check to see if there are no other members of the row, column or box that can use it. If that is the case then assign that value to the square.

After all the squares have been examined, start over again and keep doing passes until no more changes are made.

I tried this on a puzzle that was listed as moderately difficult, and the program solved it. I suspect that the program will not be able to solve expert level programs, but I will give it a try when I get the chance.

I can’t think of any way of improving the algorithm. Any ideas?

Observing members: 0
Composing members: 0

Answers

gorillapaws's avatar

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.

LostInParadise's avatar

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.

elbanditoroso's avatar

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

gorillapaws's avatar

@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.

LostInParadise's avatar

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.

gorillapaws's avatar

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.

gorillapaws's avatar

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.

LostInParadise's avatar

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.

LuckyGuy's avatar

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.

LostInParadise's avatar

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.

LostInParadise's avatar

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.

LostInParadise's avatar

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.

Answer this question

Login

or

Join

to answer.

Mobile | Desktop


Send Feedback   

`