A recent article about Sudoku inspired me to write a puzzle solver. I know there are existing programs but I wanted to see how easily I could manage one from scratch. It turned out to be a bit more nuanced than I originally expected and it ended up being a lot of fun.

http://www.metro.co.uk/weird/903532-mathematician-arto-inkala-creates-worlds-hardest-sudoku-everest

The challenge.
1) Use only your code. No reusing code from other Sudoku solvers.
2) Use any language you like.
3) It should be able to solve ANY Sudoku puzzle but the benchmark will be the one in the link above.
4) Measure your execution time in milliseconds

http://www.sudoku.name/rules/en

My current execution time is 6264 milliseconds. I'll post my source around the end of the month.

This was my AI class project. We coded it in lisp. It honestly wasn't too hard. I'll post time later.

How do you take input?

You can do it however you like. I use a grid of buttons that accept a keypress when they have focus. If you wanted to load the puzzle from a file that's fine too.

File io it is.

Did you look up any ideas on how to tackle this? I haven't started yet, but I have a feeling this is going to be complicated. Just want to know if that would be cheating.

PS. I feel like doing recursion.

I did not look up any ideas. I'd recommend trying to figure out your own method.

has MiniWookie out-programmed you yet? The day is coming...

He's getting there. Already knows how to use the DVR better than I do.

I'm working on it now... I've had a lot going on these last few days so progress has been slow. But I will say getting the basics down was quite easy.

http://www.youtube.com/watch?v=mJtoVXXcArQ&feature=plcp
4159 ms

I spent 30 minutes coding up a solution.

It runs instantly but doesn't find all the answers..

http://pastebin.com/BBauCpy5

I stored all 1,2,3,4,5,6,7,8,9 against each grid point as a possible answer for that grid point. If any of these numbers comes up as the answer for a "neighbour" gridpoint, then I remove it as a possible answer from this gridpoint.

I also look at all numbers that are a possible answer of a neighbouring gridpoint, and the gridpoint has a possible answer that isn't possible in it's neighbours, then I set that possible answer as the answer.

I must need to add some additional logic to get the solution.

edit: it would be easier if I used branch and bound by "guessing" possible gridpoint numbers (ones that have high probability of being right) and then using recursion + dynamic programming.

However I wanted to solve it the way a human would solve it.

I think there are some puzzles that require guessing and then retracing if you are wrong. I might be wrong though.

In other news, I don't like dealing with arrays/lists in python.

You guys might want to learn to play Sudoku first. I don't know everything you've done but you can't just look at neighboring spaces. you have to think about it not repeating across a left to right line or an up to down line.

MiniEye, you clearly do not understand the delicate intricacies of New Zealand style Sudoku.