Sudoku Challenge

Solve the given sudoku.

Input

One sudoku puzzle. Squares are given in left-to-right, top-to-bottom order. A digit stands for itself, whereas a period indicates a square that is to be filled. You should not assume anything about other characters, i.e., they should be ignored. The input is guaranteed to have exactly one solution.

Output

The solution to the given sudoku (with all squares filled). Nine lines, each containing one row of the solved sudoku.

Sample Input 1

1.45..89.
.963..5.1
53.41....
6......25
2.9...3.7
48......6
....37.54
9.7..563.
.45..12.9

Sample Output 1

124576893
796328541
538419762
671893425
259164387
483752916
862937154
917245638
345681279

Sample Input 2

9...28.575...192.3.3.5...6..8.2..395...7.6...341..5.2..6...7.3.1.895...475.46...9

Sample Output 2

916328457
574619283
832574961
687241395
295736148
341895726
469187532
128953674
753462819

All Submissions
Best Solutions


Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jul 07, 2009
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

there should be 0 instead of period to show empty positions...

I was trying to fill in as much of the grid with a few basic sudoku strategies, reducing the number of possibilities for each cell, then if it was not solved, recurse on all possibilities in a cell which had the least possibilities to see if it could be solved from there... returning true if one of them was true, false otherwise

I thought that was brute force, but was probably mistaken.

It ended up being the fastest solution so far... (Probably just because of bit operations)

What would my solution be classified as, and is Knuth's way theoretically faster? (I can't tell what it does by looking)

meh. Knuth's solution uses "Dancing Links", which involves shuffling pointers in order to avoid extensive amounts of modification that would ordinarily be made when recursing. It's just a way of speeding up really dumb brute force. The pointers and templates do add some overhead though, there's probably a way to speed it up.

Come on, this is ridiculous. My submission works for both of these given test-cases but works for none of the actual 50 cases. Can there be multiple solutions, because my program does not consider this.

BTW, according to a couple of sudoku websites, multiple-solution sudokus are considered invalid...

The magic algorithm I implemented (by D. E. Knuth himself) says there's only one solution to each case. Therefore, there is only one solution to each case. I guarantee it! How do you think Daniel got 49/50 if there are multiple solutions?! The only thing ridiculous here is that you're blaming the test data for your own failure.

The example cases were among the easiest I could find.

OMG! My "solution" fails so badly it's funny...

can't belive brute force actually worked that well...

WHAT? No way. The last twenty were supposed to be some of the hardest sudoku known.
I'm reducing the value.

Just make it not partial.

you get partial marks because there is also the question of efficiency - you can make a correct but slow algorithm. Thus you'll get some points for this, but making it faster is quite difficult, and hence worth more points.


I would assume the same applies to this.

I really think that we can make an exception considering brute force worked that well. It's just going to encourage people to go for the partial points instead of the complete 10 points.

I'm still thinking about what to do with this problem. Perhaps I will make it 16x16... (the issue here is that the judge is simply too fast)

I disagree. It may be fast for some languages, but others (like Ruby) are far slower here.

In Ruby, primes takes 3 ms on my computer. It takes eight times that amount here.

Well - how much slower?
My C++ solution passes every case in no more than 12 ms. Unless Ruby is hundreds of times slower than C++ (honestly, I see no reason why it should be more than 10-20 times slower, and you just pointed out that Primes was 8 times slower), the choice of algorithm should be more important here than the choice of language.

Hmm, Ruby is significantly slower - an algorithm similar to Daniel's took 18 seconds on case #48. (whereas his took about 1.1s)

However, using Ruby 1.9 sped this up to about 8 seconds. When I try to use it in the judge I get SIGABRT, though...