CODEWITHSUNDEEP
javarecursionsudokubacktracking
Rob
Rob

Reputation: 303

Sudoku solver, special case solving

I'm working on a sudoku solver with recursive backtracking which is pretty much finished except for one thing. If I would put duplicates somewhere within the puzzle (For example 1,1 in the top corner) it can go on forever trying to find a solution even though it's not a solvable puzzle.

Any help is greatly appreciated!

Rob

Upvotes: 1

Views: 555

Answers (5)

Michael
Michael

Reputation: 644

To implement the Validate class, couldn't you just write Validate.validate(); inside of your solve method? Hope it helps.

Upvotes: 1

user1181445
user1181445

Reputation:

This isn't necessarily the answer but it should help you. I have done this sort of thing before for a macro program and it was the highest rated one available.

A Sudoku solver can be quite a challenge. The only way to tell if a move is right is if it is absolute or if it is proved later on. This can lead to be quite a challenge as the end is based off of the current situation and moves. This means that you can handle this as a permutation. You can go through each square and figure out what possible numbers it has. From there, you could get one or two defined squares. Based off of this, there are many possible ways to get to an end point.

An 'end point' would be defined when the puzzle is solved (no errors - every square filled) or there is a fault.

Based off of this, you can treat each move as a node then build a tree system surrounding the possible moves.

For example:

8 7 1   2 _ _   6 9 3
2 9 6   3 8 7   1 _ _

This is just a small example, but based off of it, respectively sweeping through each row, then each column we can generate possible numbers:

(5, 1) -> [4, 5]
(6, 1) -> [4, 5]
(8, 2) -> [4, 5]
(9, 2) -> [4, 5]

Based off of this, and the solutions given to us, we can see that there is exactly 4 possible solutions:

8 7 1   2 4 5   6 9 3
2 9 6   3 8 7   1 4 5

-or-

8 7 1   2 5 4   6 9 3
2 9 6   3 8 7   1 4 5

-or-

8 7 1   2 4 5   6 9 3
2 9 6   3 8 7   1 5 4

-or-

8 7 1   2 5 4   6 9 3
2 9 6   3 8 7   1 5 4

Though that is not enough information to solve the whole puzzle and figure out which is 'correct', this can be standardized and used to create a similar system and soon find a solution.

So you could add all 4 of these possibilities to a tree, each branching from the original:

8 7 1   2 _ _   6 9 3
2 9 6   3 8 7   1 _ _

and then deal with them recursively.

Hope this helps!

Upvotes: 1

Basic
Basic

Reputation: 41

Regarding duplicates, i would suggest to keep a list of possible numbers for each cell, and when you are trying to solve a cell, you would compare this list against matching row, column and box, that way you will prevent creating duplicates. With this you can solve easier puzzles without backtracking. And if you get stuck, then use backtracking to continue...

Upvotes: 2

pgras
pgras

Reputation: 12770

You want to detect an invalid situation, so you should check for it even before calling your solver. Your solver on itself will not create invalid solutions...

Upvotes: 2

Cruncher
Cruncher

Reputation: 7812

Well the way you know to backtrack is when your puzzle hits a contradictions, so at every step you should run a "validate" method, and if the puzzle is illegal then the last move that you made was illegal.

When you find that your move is illegal you can recursively backtrack and keep going.

Also, note that this is the rather naive approach, maybe some sudoku experts have a better algorithm, but this brute force should do the trick.

Upvotes: 2

Related Questions