sudoku solving algorithm

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

sudoku solving algorithm

Postby the mishanator » Wed Dec 08, 2010 8:07 am UTC

So i've written a basic sudoku game. (here 'tis)
the way my algorithm for generating new boards works is as follows:
1) at nine distinct exclusive positions, place random integers (1-9)
2) use backtracking algorithm to solve board.

this works just fine except sometimes the randomly generated board is hard to solve, so my application ends up hanging for like an hour while it gets solved, the supposition at least is that eventually it will solve since the random points i pick are like this:
Image

anyway it happens that the program hangs, and eventually the user will get sick of waiting for a new board to be generated, and the thing crashes and it's really not pretty. what i would like (and i realize this is a cheap solution) is to have a timeout of some sort built into the board generating function, so like if within 5 seconds a board hasn't been generated, try again... i've never done this sort of thing and my online searches haven't been too fruitful, so can someone please help me?

the particular section of code would be this:
Board.cpp lines 68-84

Code: Select all

void Board::genBoard() {
        for (int i = 0; i < 9; i++) { // clear the board
                for (int j = 0; j < 9; j++) {
                        solution[i][j] = 0;
                }
        }
        solution[2][0] = rand() % 9 + 1;
        solution[1][3] = rand() % 9 + 1;
        solution[0][7] = rand() % 9 + 1;
        solution[3][1] = rand() % 9 + 1;
        solution[4][4] = rand() % 9 + 1;
        solution[5][6] = rand() % 9 + 1;
        solution[6][2] = rand() % 9 + 1;
        solution[7][5] = rand() % 9 + 1;
        solution[8][8] = rand() % 9 + 1;
        solve(solution); // solve function implements backtracking algorithm.
}


thanks.

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: sudoku solving algorithm

Postby Meteorswarm » Wed Dec 08, 2010 8:19 am UTC

http://en.wikipedia.org/wiki/Dancing_Links might be a faster algorithm to solve it; Wikipedia claims a solution in less than a second for 3x3x3 sudoku
The same as the old Meteorswarm, now with fewer posts!

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Wed Dec 08, 2010 8:20 am UTC

it usually solves in less than a second... just sometimes not. hehe.

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: sudoku solving algorithm

Postby keeperofdakeys » Wed Dec 08, 2010 9:18 am UTC

You presumably have some kind of loop in the solve function, correct? If you do, then store the time the loop starts and check how much time has passed at each iteration, at some point you can jump out of the loop if too much time goes by. With your current construct, this may require adding a second argument to the solve function (you could probably do something hacky, like make it disable timing if the second argument is 0 as well). You could then use the return value to check if it finished solving it.

There is also the alternative, which is try making a proper board generator. Also I hope that solve button doesn't use your guessing algorithm, as it finds an answer, not the answer.

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Wed Dec 08, 2010 9:20 am UTC

Also I hope that solve button doesn't use your guessing algorithm, as it finds an answer, not the answer.


why would that be a problem? it shows a solution, there is no "the answer"

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: sudoku solving algorithm

Postby keeperofdakeys » Wed Dec 08, 2010 9:42 am UTC

The purpose of the game is to solve it by gradually filling in the squares using logic. Using this process, you will either end-up with a game that can't be solved or a complete board. If it is complete, then that one solution is the solution that people would expect to see. If it can't be solved through logic, then what is the point in one of many possible answers? You might find people will put in a problem they are working on by hand, but want to check there answers. If your program gave a different answer to them, they would believe they did something wrong when, in fact, they were right.

As an aside, you can also test boards that you generate to see if they are solvable by hand (although any decent generation algorithm should take that into account).

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Wed Dec 08, 2010 9:45 am UTC

oh... i dont think i was clear about the games purpose. it generates boards that are solutions, then randomly removes numbers based on the difficulty level and the user solves it.

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Re: sudoku solving algorithm

Postby masher » Wed Dec 08, 2010 12:01 pm UTC

the mishanator wrote:oh... i dont think i was clear about the games purpose. it generates boards that are solutions, then randomly removes numbers based on the difficulty level and the user solves it.


But unless you are careful on how you remove the numbers, you can generate a puzzle that has more than one solution.

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Wed Dec 08, 2010 8:57 pm UTC

Again, I don't see any problem with the user inputting a new solution... it checks for validity, not if it's the same as the solution the algorithm came up with.

distractedSofty
Posts: 253
Joined: Tue Jul 06, 2010 5:29 pm UTC

Re: sudoku solving algorithm

Postby distractedSofty » Wed Dec 08, 2010 10:20 pm UTC

the mishanator wrote:Again, I don't see any problem with the user inputting a new solution... it checks for validity, not if it's the same as the solution the algorithm came up with.

The point is, if a Sudoku grid has more than one valid completion, then it has no solution, since Sudoku is a logic game. Consider an end state in which the user has logically filled in the whole grid, and is left with 4 boxes at the corners of a square, with the same 2 possible values for each. Since there is no information as to which number can go in which box, the puzzle cannot be solved.

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: sudoku solving algorithm

Postby Kurushimi » Wed Dec 08, 2010 11:21 pm UTC

Yeah, when there is more than one solution, the user won't know if he got it right or not when checking the answer with the one you display. You'd have to, like, display every single possible solution.

You could try to not remove too many. I heard that with 18 or 19 numbers on the board a solaveable Sudoku is guaranteed to have a unique solution. ...though those games may be pretty easy...

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: sudoku solving algorithm

Postby keeperofdakeys » Thu Dec 09, 2010 12:19 am UTC

distractedSofty wrote:
the mishanator wrote:Again, I don't see any problem with the user inputting a new solution... it checks for validity, not if it's the same as the solution the algorithm came up with.

The point is, if a Sudoku grid has more than one valid completion, then it has no solution, since Sudoku is a logic game. Consider an end state in which the user has logically filled in the whole grid, and is left with 4 boxes at the corners of a square, with the same 2 possible values for each. Since there is no information as to which number can go in which box, the puzzle cannot be solved.

His algorithm brtue-forces the answer, therefore it is actually possible for his program to return answers that are different from the unique solution.

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Thu Dec 09, 2010 12:42 am UTC

so your saying there are cases where the user will find the board to be invalid? thats impossible, then they solved it wrong.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: sudoku solving algorithm

Postby Thesh » Thu Dec 09, 2010 12:47 am UTC

If there are multiple solutions, then it cannot be solved through logic and the solver will have to use guess and check at some point.
Summum ius, summa iniuria.

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Thu Dec 09, 2010 12:58 am UTC

thats what backtracking is, guess and check (at least in this case). anyway i did set a timeout so if it doesnt find one in a second it retries.

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Re: sudoku solving algorithm

Postby masher » Thu Dec 09, 2010 1:03 am UTC

the mishanator wrote:so your saying there are cases where the user will find the board to be invalid? thats impossible, then they solved it wrong.


Consider this starting board:

Code: Select all

1 2 3 | 4 5 6 | 7 8 9
7 8 9 | 1 2 3 | 4 5 6
4 5 6 | 7 8 9 | 1 2 3
------+-------+------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
------+-------+------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1


You take out a few numbers to create a puzzle

Code: Select all

1 2   | 4 5   | 7 8 9
7 8 9 | 1 2   | 4 5 
4 5   | 7 8 9 | 1 2 
------+-------+------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
------+-------+------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1


That puzzle is unsolvable (by logic) as it also has the following solution:

Code: Select all

1 2 6 | 4 5 3 | 7 8 9
7 8 9 | 1 2 6 | 4 5 3
4 5 3 | 7 8 9 | 1 2 6
------+-------+------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
------+-------+------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1
Last edited by masher on Thu Dec 09, 2010 1:28 am UTC, edited 1 time in total.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: sudoku solving algorithm

Postby Thesh » Thu Dec 09, 2010 1:17 am UTC

masher wrote:That puzzle is unsolvable (by logic) as it also has the following solution:

Code: Select all

1 2 6 | 4 5 3 | 7 8 9
7 8 9 | 1 2 6 | 4 5 3
4 5 4 | 7 8 9 | 1 2 6
------+-------+------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
------+-------+------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1


That's not valid, you have two fours in the first square and third column. I think you have to remove more than a few numbers to have a puzzle with multiple solutions.
Summum ius, summa iniuria.

masher
Posts: 821
Joined: Tue Oct 23, 2007 11:07 pm UTC
Location: Melbourne, Australia

Re: sudoku solving algorithm

Postby masher » Thu Dec 09, 2010 1:29 am UTC

Thesh wrote:That's not valid, you have two fours in the first square and third column. I think you have to remove more than a few numbers to have a puzzle with multiple solutions.


Fixed. It was a typo; you should now be able to see the multiple solution.

distractedSofty
Posts: 253
Joined: Tue Jul 06, 2010 5:29 pm UTC

Re: sudoku solving algorithm

Postby distractedSofty » Thu Dec 09, 2010 3:10 am UTC

the mishanator wrote:thats what backtracking is, guess and check (at least in this case). anyway i did set a timeout so if it doesnt find one in a second it retries.

To put it another way, if I asked you the question "What is the single root of [imath]x^2-2x-8[/imath]?", you would tell me that the question was wrong and that I was either after two roots, or the single positive root, or the equation was wrong, or something else. What you couldn't do would be to argue that your answer of 2 was correct.

To answer the original question, the best way to generate a legal board (imo) is to have a 9 element list for each square, denoting the possible values the square could take. Then, randomly choose a value from the list for the first square, and update the lists in the same row, column and box to remove that value as a valid value. Repeat for the rest of the squares. No backtracking, and a predictable running time, obviating the need for a timeout. This is pretty much your algorithm, but with a constrained random function. (not great for solving, however).

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: sudoku solving algorithm

Postby thoughtfully » Thu Dec 09, 2010 4:00 am UTC

In the solving process, I think one of the solutions becomes "known" first, and then the rest follows. The orignal state is irrelevant; a check for solution checks that all the cells are filled and none of the constraints are violated. I was working on this problem a few weeks ago, I may have to go back to it now..

I suppose that isn't always the case. Obviously it isn't for a highly underdetermined board, when some arbitrary choices are necessary just to get anywhere. That test does save on memory and is forgiving to not quite perfect board generators, at least.

It seems to me now that generating the boards might be a more interesting problem than solving them :)
Oh bother, just when I was starting to get stuff done again!
Last edited by thoughtfully on Thu Dec 09, 2010 4:05 am UTC, edited 3 times in total.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: sudoku solving algorithm

Postby jaap » Thu Dec 09, 2010 9:34 am UTC

distractedSofty wrote:To answer the original question, the best way to generate a legal board (imo) is to have a 9 element list for each square, denoting the possible values the square could take. Then, randomly choose a value from the list for the first square, and update the lists in the same row, column and box to remove that value as a valid value. Repeat for the rest of the squares. No backtracking, and a predictable running time, obviating the need for a timeout.

This does not work. You either need backtracking, or some set of clever rules that anticipate all the problems that could arise.
For example, if you are filling the board row by row, left to right, then you can get in trouble on the second row:

Code: Select all

123 456 789
456 123 ...
... ... ...

Each of the numbers placed so far are valid choices according to your rules, but it is not possible to complete the row.

As others have said, a sudoku problem is only valid if it has a unique solved grid. A sudoku generator will have to check that the partly emptied grid still only has the solution it was created from, that the removal of numbers hasn't introduced ambiguities. An example with 6 removals was shown earlier but it can happen even by removing 4 numbers:

Code: Select all

123 456 789
456 789 123
78. .31 456

31. .78 564
564 123 897
897 564 231

231 645 978
645 897 312
978 312 645

The blanks must be 2 or 9, but there are two ways to fill them.

I wrote a sudoku generator applet some years ago, which you can find here. At first I tried starting with an empty grid, adding numbers until there is a unique solution, and then removing some if possible as long as the solution remains unique. This turned out to be slower than generating a full grid and removing numbers from there.

User avatar
Vault
Posts: 169
Joined: Mon Nov 10, 2008 5:00 pm UTC
Location: Just past the event horizon
Contact:

Re: sudoku solving algorithm

Postby Vault » Thu Dec 09, 2010 5:25 pm UTC

Peter Norvig actually has an awesome essay about Sudoku solving on his website. (right here) He uses a combination of constraint propagation and depth first search. He also makes it look super easy.

distractedSofty
Posts: 253
Joined: Tue Jul 06, 2010 5:29 pm UTC

Re: sudoku solving algorithm

Postby distractedSofty » Thu Dec 09, 2010 6:03 pm UTC

jaap wrote:This does not work. You either need backtracking, or some set of clever rules that anticipate all the problems that could arise.
For example, if you are filling the board row by row, left to right, then you can get in trouble on the second row:

Code: Select all

123 456 789
456 123 ...
... ... ...

Each of the numbers placed so far are valid choices according to your rules, but it is not possible to complete the row.

Well, "some set of clever rules" is "if your list elimination leaves a single valid value for a square, update all the lists it could effect to remove it as a value". You could do this recursively, or some other cool way. (Depends on your data structure for the lists)

(I was thinking you could avoid this rule when I posted before, but I didn't really think it through)

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Fri Dec 10, 2010 3:12 am UTC

oh... i understand. see i'm not too familiar with sudoku, and i didnt know that to be valid it must have a unique solution.

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: sudoku solving algorithm

Postby tetsujin » Fri Dec 10, 2010 10:59 pm UTC

jaap wrote:As others have said, a sudoku problem is only valid if it has a unique solved grid. A sudoku generator will have to check that the partly emptied grid still only has the solution it was created from, that the removal of numbers hasn't introduced ambiguities. An example with 6 removals was shown earlier but it can happen even by removing 4 numbers:

Code: Select all

123 456 789
456 789 123
78. .31 456

31. .78 564
564 123 897
897 564 231

231 645 978
645 897 312
978 312 645

The blanks must be 2 or 9, but there are two ways to fill them.


Whoops! This is incorrect in the example you just gave... Because there's only one unknown in each 3x3 grid, you can deduce the missing numbers by looking at which digit is missing from that 3x3 grid.

The example you want is to take two rows (y1, y2) and two columns (x1, x2) in the grid (A) such that:
  • floor(y1/3) = floor(y2/3)
  • floor(x1/3) != floor (x2/3)
  • A(x1, y1) = A(x2, y2), A(x1, y2) = A(x2, y1)

Now you have two distinct solutions for those four squares: because after the values there are blanked out, both of those values are missing from all rows, columns, and 3x3 grids from which a box was blanked.

I believe there is another problem with the approach distractedSofty proposed:
To answer the original question, the best way to generate a legal board (imo) is to have a 9 element list for each square, denoting the possible values the square could take. Then, randomly choose a value from the list for the first square, and update the lists in the same row, column and box to remove that value as a valid value. Repeat for the rest of the squares. No backtracking, and a predictable running time, obviating the need for a timeout. This is pretty much your algorithm, but with a constrained random function. (not great for solving, however).


Difficult Sudoku puzzles don't necessarily lend themselves well to this kind of approach. There may be cases where looking at a single point in terms of row, column, and grid does not yield a specific value for a square: But you can still solve the grid by various types of elimination. For instance:

Code: Select all

_ _ _   3 _ 4   _ _ 7
_ _ _   _ _ _   _ _ X
_ 5 _   _ _ _   _ _ _

_ _ _   2 _ 3   _ _ _
_ _ _   _ _ _   _ 5 _
_ _ _   1 _ _   _ _ _

_ _ _   4 _ _   _ _ 1
_ _ _   _ _ _   _ _ 2
5 _ _   _ _ _   _ _ _


With nothing more than the information above, you can locate all the missing '5's on the board. This is because X is the only place a 5 could possibly be on the right-most column of the board. (We don't know where the 5 in the bottom-right grid will be located, but we know it's in column 7!) But distractedSofty's algorithm will never create this sort of challenge. It will keep adding squares to the row, column, and grid of X until it makes the choice of X completely obvious based on the digits whose positions are already exactly known.

Another approach might be to start with a full, valid grid and remove one digit at a time, checking (via a solve, I guess) that this doesn't introduce ambiguities into the puzzle... Or the puzzle generator could emulate how players solve the puzzles - remove a given digit only if there's some solver-heuristic that can be used to conclusively put that digit back again - basically generate, in reverse, the sequence of steps a player will use to re-populate the grid. This approach would also have the benefit of being easy to control the difficulty of the resulting puzzle (by picking the set of heuristics that is used to validate each step - and checking which ones were actually used over the course of generating the puzzle)...
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

distractedSofty
Posts: 253
Joined: Tue Jul 06, 2010 5:29 pm UTC

Re: sudoku solving algorithm

Postby distractedSofty » Sat Dec 11, 2010 1:41 am UTC

tetsujin wrote:Difficult Sudoku puzzles don't necessarily lend themselves well to this kind of approach.

tetsujin wrote:Another approach might be to start with a full, valid grid and remove one digit at a time...


My algorithm was only to generate the full valid grids. With the error pointed out by jaap fixed, it does that with no problems.

Reading it now, I may have misread the OP: Were you planning to just have the 9 givens, and nothing else? Or did you have some strategy for adding blanks to a completed grid? (purely randomly or otherwise)

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: sudoku solving algorithm

Postby the mishanator » Sat Dec 11, 2010 7:01 am UTC

purely randomly.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests