|
|
|
This thread is locked; no one can reply to it.
|
| Sudoku solver |
|
Evert
Member #794
November 2000
 |
I was bored the other week and decided to write a sudoku solver (see http://en.wikipedia.org/wiki/Sudoku for information on this type of puzzle). I'm not really a big fan of the puzzle but thought it would be nice to write a computer programme to solve it. The algorithm I came up with uses logical bitwise operations to eliminate possibilities based on the constraints it knows about. This is very fast (it takes less than ten iterations on the puzzles I've tried it on), but I'd like to know if there are puzzles that it cannot solve (ie, any pieces of information I've neglected to use). The solution algorithm is fairly straightforward but some parts of it a re a bit icky. Don't expect the programme to help you find a solution if you're stuck on a problem though: it works too differently from the way humans think to be really helpful. If some of you would care to try it out and see if you can find puzzles that it doesn't solve, please do! The C source code is attached (removed; see post below for an updated version) and puzzles can be entered through text files on the commandline, eg ./sudoku sudoku.txt (you may want to redirect the output to a file or enlarge your terminal window). The file format looks like # I'm a comment! .7..1..9. 9..8....7 ..3.....6 .4...15.. .3.....1. ..27...6. 5.....6.. 6....5..2 .8..2..7. I may use the algorithm some time to create a puzzle generator, but probably not anytime soon... (and if someone feels that programming questions isn't quite the right place to put this, feel free to move the thread elsewhere). |
|
Simon Parzer
Member #3,330
March 2003
 |
Works for me. I've not tried it with very many puzzles though. |
|
CGamesPlay
Member #2,559
July 2002
 |
How hard would it be for a human to solve puzzles in this manner? The first time I tried [edit] -- Ryan Patterson - <http://cgamesplay.com/> |
|
Thomas Harte
Member #33
April 2000
 |
Quote: (ie, any pieces of information I've neglected to use). From briefly looking at the source code, you seem not to be considering subsets. For example, if you have a single 3x3 box and two squares which can both only contain 1 or 3 then you know that none of the other boxes in the 3x3 area can contain either 1 or 3. Obviously the same thing applies along columns and rows. Of course I may be wrong as I haven't extensively studied your source. I guess you'd look for a collection of n squares within a constrained set that has exactly n bits set when the logical or of all their squares is constructed. Any plan to support Killer sudoku (with the marked collections of squares and their sums) in the future? [My site] [Tetrominoes] |
|
Matthew Leverton
Supreme Loser
January 1999
 |
It couldn't solve: .15..96.7 .97.5.... ....1.... ..12....4 52.....61 6....42.. ....2.... ....8.59. 3.89..41.
|
|
Johan Halmén
Member #1,550
September 2001
|
c file said:
If all goes well, this reduction results in a few newly known Well, ML obviously came up with an unsolvable case. Without testing further I would have said that your method wouldn't work. I haven't done much Sudoku, but I guess the harder cases are those where you have to guess some numbers and then go many steps in advance, before you reach a dead end. And this kind of goes for your method, too. One can't just take one right step at a time. One has to take more steps and bang one's head in the wall and return. I've planned to make a Sudoku solver myself, as a part of a Sudoku puzzle generator, just like Evert. I'd do a semi-brute force thing. For each empty square I'd make a list of all possible numbers. Then I'd sort them. Least possibilities first, most possibilities last. Then I'd check each combinations. But it is actually the puzzle generator part that is more interesting. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest. |
|
Thomas Harte
Member #33
April 2000
|
Quote: I guess the harder cases are those where you have to guess some numbers and then go many steps in advance, before you reach a dead end. No, no, no, you never have to guess! Some people do, but you never have to - certainly not with any sudoku published here in the UK. [My site] [Tetrominoes] |
|
Johan Halmén
Member #1,550
September 2001
|
The question arises, is it possible to create a sudoku puzzle with only one solution and where you have to guess? And if it is possible, wouldn't such a puzzle be considered a difficult one? I mean, a clever solver doesn't actually write down the guesses, he memorizes the guesses and finds the dead ends or the right numbers before his short memory runs out. My short memory is not very good, so I have to write down the guesses. So it is not very obvious when one actually take guesses. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest. |
|
Evert
Member #794
November 2000
|
Quote: From briefly looking at the source code, you seem not to be considering subsets. For example, if you have a single 3x3 box and two squares which can both only contain 1 or 3 then you know that none of the other boxes in the 3x3 area can contain either 1 or 3. Obviously the same thing applies along columns and rows. I think this is done automatically if the two boxes are aligned in the same row or column, but you're right: I don't do this explicitly. I'll have to think how to do that elegantly using logical operators (I do scan for a bit being set only on one square, but that's pretty ugly). Quote: Any plan to support Killer sudoku (with the marked collections of squares and their sums) in the future? No plans for the immediate future, but feel free to rip apart my code and algorithm. Quote: It couldn't solve: Fascinating. It could solve it when I put the nine in the centre, but from looking at the output it's not yet clear to me what piece of information I'm missing. I'll investigate further. Quote: Without testing further I would have said that your method wouldn't work. Well, it's based on the assumption that there's always enough information to deduce what the next step will be. I think that should be true. Quote: I haven't done much Sudoku, but I guess the harder cases are those where you have to guess some numbers and then go many steps in advance, before you reach a dead end. And this kind of goes for your method, too. One can't just take one right step at a time. One has to take more steps and bang one's head in the wall and return. Ah, but you can detect what the right move will be from a number of options by checking if one of them leads to an impossible situation in a couple of moves. I think it should be possible to eliminate such moves from the outset if you use all available information you have. Which is sortof what my programme does: in one sweep it fills in all logically known numbers and updates its status information. In effect, it does much more than a human can in one sweep. Unfortunately that also makes it a bit hard to debug. Anyway, I'm going to take my post-Christmas sleep now... I'll have a crack at finding out why it doesn't solve Matthew's sudoku tomorrow. EDIT:
Have a look at the bitflags below the board (which are the local masks for each square). For the upper left 3x3 block, the numbers 6 and 3 only occur in the two rightmost columns of the lowest row. That means that all the other numbers that are flagged as `possible' on these locations can be eliminated (the 8, the 4 and the 2). This immediately gives the position of the 2 in the lowest 3x3 block as well as the position of the 4 and several other numbers. EDIT2: 987..4.21 .876..3.. 9..6..3.. .87...... 9.....3.. .87...321 987...3.. .87.5432. 98.65.3.. ------------------------------------------------------------------------------------------- |.8.....2. ........1 ....5....|......3.. .....4... 9........|...6..... .8.....2. ..7......|.8.....2. |.8...4.2. 9........ ..7......|...6..... ....5.... .8.....2.|........1 .8...432. .8....3..|.8...432. |.8...4.2. ...6..3.. ...6..3..|.87...... ........1 .87....2.|98....... .8..54.2. 98..5....|98765432. ------------------------------------------------------------------------------------------- |9.7...... .87...3.. ........1|.......2. ...6..... ....5....|987...3.. .87...3.. .....4...|987...3.. |....5.... .......2. .....4...|.87...... 9.....3.. .87......|9.....3.. ...6..... ........1|987...3.. |...6..... .87...3.. 9.....3..|........1 9.....3.. .....4...|.......2. .87.5.3.. 98..5.3..|987.5.3.. ------------------------------------------------------------------------------------------- |9.......1 .....4... 9..6.....|....5.... .......2. ......3.1|.87...3.. .87...3.. .8.6..3..|9876..3.1 |..7.....1 ..76..... .......2.|.....4... .8....... ......3.1|....5.... 9........ ...6..3..|..76..3.1 |......3.. ....5.... .8.......|9........ ..7...... ...6.....|.....4... ........1 .......2.|......... -------------------------------------------------------------------------------------------
Hmm... I implemented the missing information Thomas pointed out (it was pretty easy; I already had the special case for a bit being set only once and it was straightforward to extend that). However, it isn't enough 815 349 627 297 658 143 463 712 859 731 265 984 524 897 361 689 134 275 946 521 738 172 483 596 358 976 412 ) |
|
Peter Hull
Member #1,136
March 2001
|
I wrote my own solver in Javascript a while ago (when the craze hit my wife's family really badly...) My idea was to start there and add in more clever logic, but I found that it was not necessary - it seemed to be able to solve any puzzle in a couple of seconds. As far as I tested, it always works - anyway, see the code for yourself. What's more difficult is to solve it in such a way that it can be explained, step-by-step to a person. There are solvers on the web that will do this, but I forgot the URLs. Pete
|
|
Evert
Member #794
November 2000
|
If you remember one, let me know. I still can't figure out what piece of information I'm missing in the last output of my programme... |
|
Matthew Leverton
Supreme Loser
January 1999
|
Solve by logic: http://www.sudokusolver.co.uk/ But you'll see on that site that they have unique puzzles that (as far as they know) cannot be solved with logic. |
|
Evert
Member #794
November 2000
|
Ah! Cheers for that link, Matthew! I'm curious about the puzzles that cannot be solved by logical elimination alone though... I thought that if you have enough information (ie, there is a unique solution) you should always be able to determine what the next move should be... EDIT: Ok, I've fixed it. It now solves the Sudoku Matthew posted in seven iterations, without having to guess. |
|
Rash
Member #2,374
May 2002
 |
I assume you also have looked at the following? |
|
Evert
Member #794
November 2000
|
Quote: I assume you also have looked at the following?
Nope. |
|
Zaphos
Member #1,468
August 2001
|
Quote: I thought that if you have enough information (ie, there is a unique solution) you should always be able to determine what the next move should be... This is definitely the case -- a Sudoku with only one solution is a solution which, just by the givens, has been constrained such that no other answer is possible ... so there must be constraints against all other answers ...
|
|
Matthew Leverton
Supreme Loser
January 1999
|
Quote: I'm curious about the puzzles that cannot be solved by logical elimination alone though. Here are two unique puzzles that it cannot solve: .2....... ...6....3 .74.8.... .....3..2 .8..4..1. 6..5..... ....1.78. 5....9... .......4.
....9.5.. .9...6.81 4...7.... ..6..2.54 1.......2 28.3..6.. ....8...5 37.1...4. ..1.4....
|
|
Rash
Member #2,374
May 2002
|
"Guessing" is kind of ill-defined here. Since Sudoku solving has a finite state space one could always resort to brute force in the worst case. Sudoku is NP-complete, so the trick is to find a good heuristic. |
|
Zaphos
Member #1,468
August 2001
|
Quote: "Guessing" is kind of ill-defined here. I think there's an assumption that you either do local constraint propagation (meaning you only mark off what elements can't be what based on the values of elements in the same row, column, or group of 9), or you do some more-global constraint propagation (taking into account the values of elements NOT on the same row, column, or group of 9), and that global propagation involves 'guessing.' So what I was saying above was wrong -- you may have a single-solution Sudoku that requires some global constraint propagation, or guessing ... (sorry about that). Obviously if you consider any constraint propagation to be 'logic', you can solve any Sudoku 'by logic', because the puzzle must start out sufficiently constrained such that there is only one solution (at least, so says Wikipedia). But that doesn't mean that there must be a better method than 'guessing' to propagate those constraints. edit:
|
|
amarillion
Member #940
January 2001
 |
Sounds like you can write a nice scientific paper about this. Evert, you're doing a PhD are you not? -- |
|
Marcello
Member #1,860
January 2002
 |
Quote: (1) Evert's method demonstrates that P=NP
Looks like someone's gonna be rich. |
|
thematrixeatsyou
Member #6,183
September 2005
 |
If you have trouble solving one of those puzzles, remember these tricks: good food is t3h pwn <-- if anyone can find out how old this sig is they win an ascii penguin |
|
Evert
Member #794
November 2000
|
Quote:
Furthermore, I think that local constraint propagation takes polynomial time and Evert's method uses only local constraint propagation, so one of the following should be true:
It doesn't solve all of them. I'm still trying to formulate some constraints and patterns in terms of simple binary operators, which is a bit of a pain. It is satisfactory though, because the programme automatically applies them too for `simple' Sudoku's which it could solve before. Which is cool since over the past week some simple ones have gone down from about 10 iterations to 2 or 3 iterations (!) Quote: Sounds like you can write a nice scientific paper about this. Evert, you're doing a PhD are you not? Yes, but in astrophysics. I have no idea what goes on or has been done in the world of mathematics (or computer science) when it comes to Sudokus. Anyway, it's probably been done before. Maybe I'll put a description of the programme and algorithm on my webpage though. |
|
Torbjörn Josefsson
Member #1,048
September 2000
 |
It seems easier to solve it in Constraint Logic Programming Mine seems to solve these ones nicely, in half a sec The first one in ML's last post: 1 2 6 4 3 7 9 5 8 8 9 5 6 2 1 4 7 3 3 7 4 9 8 5 1 2 6 4 5 7 1 9 3 8 6 2 9 8 3 2 4 6 5 1 7 6 1 2 5 7 8 3 9 4 2 6 9 3 1 4 7 8 5 5 4 8 7 6 9 2 3 1 7 3 1 8 5 2 6 4 9
-- |
|
Evert
Member #794
November 2000
|
Quote: It seems easier to solve it in Constraint Logic Programming Sure. I just had the idea of doing it with bitmasks since it seemed a natural way to implement some of the constraints - and for local constraints, it is. It's a bit painfull with non-local constraints. What I'm mostly missing right now are X-Wing pattern recognition and its higher order relatives. I think I've figured out how to do these elegantly with bitmasks but I need to add some more bookkeeping because I don't have the information I need in a convenient format. |
|
|
