Hi guys!
I want to create a java sudoku but I'm stuck with the backtracking algorithm to get the available numbers to insert in the current cell. Can someone point me to a method that gives me anint[]
with all available numbers for the current cell?
Thanks!
Depends what you're doing. You say "backtracking", which implies to me that you're after brute-forcing it rather than human-style solution. If that's the case, use Knuth's reduction to exact set cover (although I advise against trying to use his Dancing Links datastructure in Java: it just doesn't type well at all).
If, OTOH, you're trying to do manual solution, then you have to decide what reasoning rules you wish to use. Some are givens, such as "If there's an n in the same row, it can't be an n", but those such as Swordfish or Nishio are optional. You won't solve all published puzzles without them, but you'll be able to generate interesting puzzles.
This is the first time I see this problem, but I
gut an idea about how to solve it and I would like
to see if it has already been tried, or if someone
knows that it will not work.
1. Fill all empty spots with random numbers so that
every 3x3 has all 9 numbers.
2. Take first (next) 3x3 and swap two numbers where
there are more then two pairs of the same number
in two rows. Resume at 2.
Do you think that this simple algorithm will find
its way to a solution in the vast space of possible
states, or will it end up in a local optimum?
> You say "backtracking", which implies to me that you're after brute-forcing it rather than human-style solution.
> If, OTOH, you're trying to do manual solution, ... Nishio are optional.
By the definition of Nishio at http://www.palmsudoku.com/pages/techniques-11.php it is exactly the classic backtracking algorithm as per Prolog - try each possible assignment in turn, proceed until either a conflict occurs (in which case backtrack to the previous assignment you had a choice over) or until all constraints are met and you have a solution.
Though use the simple row/column/box rules first to prune the search space to a managable size.
Pete
> By the definition of Nishio at http://www.palmsudoku.com/pages/techniques-11.php it is exactly the classic backtracking algorithm
I'd only come across definitions of Nishio in terms of backtracking until a couple of days ago. There's a paper by David Eppstein (Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku), however, which shows that Nishio can be treated as bipartite matching.
Interesting paper - http://arxiv.org/abs/cs.DS/0507053 - though at a quick read it seems closer to a generalisation of the pairs/triples techniques than nishio.
Pity my parents are coming for the weekend and I have to spend the evening catching up on housework rather than playing with the idea.
Oddly enough, my maths prof. has published one book on sudoku along with many on graph theory, but I hadn't read anything relating the two: http://www.gresham.ac.uk/publications.asp?PageId=53&professorid=10
Pete
> Do you think that this simple algorithm will find
> its way to a solution in the vast space of possible
> states, or will it end up in a local optimum?
You can not count on this to work. Your intuition is that since you are swapping elements that were duplicates either in a row or column, that you are "fixing that problem" and thus getting closer to a solution. But the mere fact that A was a duplicate in row 1 and thus has to be removed does not mean that when you swap it with B that B does not now also confilit with something Both in row1 and also with something in the column that A used to be in. You could make things worse by your operation.
On the other hand as long as you randomly choose among elements that are known to be out of order,the probability that your algorithm will find the solution is of course 1 because as long as you are randomly swapping things that are known to be wrong you will eventually by chance alone trip over the proper sequence of swaps that solve the problem.
Of course, the same could be said for the algorithm that ignores looking at the elements and just swaps elements at random. That algorithm will also eventually solve the problem.
> At a quick read it seems closer to a generalisation of the pairs/triples techniques than nishio.
I've heard that X-Wing and Swordfish are specialisations of Nishio. I don't implement any of them yet, so I haven't checked.
The definition of Nishio at the link you posted is wrong. An accurate definition is found at http://www.simes.clara.co.uk/programs/sudokutechnique8.htm
I never heard of this puzzle before either, but it is quite easy to solve
using brute force backtracking. I hacked a small algorithm for it that
keeps track of the taken digits per row, per column and per small
3x3 square.
It solved this [url=http://www.sudoku.com/]example puzzle[/url] in 2453 backtracking calls;
The solving time took a fraction of a second.
I think this puzzle is equivalent (big Oh wise speaking) to the n-queens
puzzle ... If someone wants me to post the spoiler/hack, *and* if it's not
a homework assignment, let me know.
kind regards,
Jos
> You can not count on this to work.
My intuition seams to be right this time. I implemented
it and it solved the problem, using 204 switches in
average. The algorithm seams to step strait towards a
solution since the space of possible layouts is about
(6!)^9 = 5.2*10^25 when 3 numbers in each 3x3 are locked
on average. I might have been unclear last time, but I
think following text is more clear.
1. Fill all empty spots with random numbers so that
every 3x3 has all 9 numbers. Now define the score of
the board to be the sum of duplicate numbers in every
row and column.
2. Pick one of 3x3's at random. Find a pair in this 3x3,
such that when the two numbers change place, the score
is unchanged or lower. If the score is zero we are done,
else resume at 2.
A simple and fast algorithm. What more is needed in
this case?!
> The definition of Nishio at the link you posted is wrong. An accurate definition is found at http://www.simes.clara.co.uk/programs/sudokutechnique8.htm
It's still attempting a unification then rejecting it if it yeilds inconsistencies, so I don't see a significant difference between that and prolog's mechanism.
Pete
> I think this puzzle is equivalent (big Oh wise speaking) to the n-queens puzzle ...
n^2 x n^2 Sudoku is NP-complete. Therefore n x n Sudoku is also NP-complete. n-queens is in P.
> It's still attempting a unification then rejecting it if it yeilds inconsistencies, so I don't see a
> significant difference between that and prolog's mechanism.
It's considerably less powerful. It also has tighter complexity bounds.
> > I think this puzzle is equivalent (big Oh wise
> speaking) to the n-queens puzzle ...
>
> n^2 x n^2 Sudoku is NP-complete. Therefore n x n
> Sudoku is also NP-complete. n-queens is in P.
I must be missing something obvious here; care to enlighten me?
kind regards,
Jos
> > I must be missing something obvious here; care to enlighten me?
>
> I was informing you that your hunch was wrong unless P = NP.
Yep, so much I understood, by I don't understand the NP-ness for that
Sudoku puzzle ... maybe I've just got my brain-off-day ;-)
kind regards,
Jos
Both reduce to exact set cover with a number of subsets of size 4.
n-queens: universal set is Rows U Cols U Diagonals. Each possible placement of a queen is in one row, one col and two diagonals. In addition for each diagonal there is a subset containing only that diagonal.
Sudoku: universal set is Cells U ((Rows U Cols U Boxes) x Values). Each possible placement of a value in a cell is in one cell, one row x value, one col x value and one box x value.
The constraints are fairly different. Instead of no more than one per diagonal, you have exactly one per box. Intuitively you'd expect fewer solutions. Moreover, if you take into account the way the reduction scales, n-queens has a universal set of O(n) and O(n^2) subsets. nxn Sudoku has a universal set of O(n^2) and O(n^3) subsets. It's perhaps surprising that they're in different complexity classes, but not that they have different asymptotic costs.
> It's perhaps surprising that they're in different complexity
> classes, but not that they have different asymptotic costs.
Yup, that's where I went wrong; especially when I typed in my
brute force hack: it resembled that n-queens problem so much
that I simply stopped thinking, (erroneously) concluding that both
problems have the same big-Oh behaviour ;-)
kind regards,
Jos
> > It's still attempting a unification then rejecting
> it if it yeilds inconsistencies, so I don't see a
> > significant difference between that and prolog's
> mechanism.
>
> It's considerably less powerful. It also has tighter
> complexity bounds.
Don't see that at all.
If you have say, 3 possible digits for a given cell.
A prolog engine will select one, check all dependent constraints, and if any fail reject it , otherwise report sucess.
The description given of nishio is to select one possible value, check all dependent constraints, and if any fail reject it , otherwise report sucess.
What is the difference that you're thinking between these? Is it just you're assuming the prolog engine isn't optimised to test only dependent constraints, or that you can't chain one unification after another in nishio?
Pete
> The description given of nishio is to select one possible value, check all dependent constraints, and if any fail reject it , otherwise report sucess.
?! Did you actually read the link I posted in reply 7? Because you still seem to be talking about the inaccurate definition from the link you posted in reply 3.
"For each candidate for a cell, it asks the question:
If I put this number in this cell, will this prevent me from completing the other placements of this number?
If the answer if yes, then that candidate can be eliminated."
Is your understanding that Nishio is limited to the constraints dealing with the same number, not all constraints?