Problem 096

[suitti]

I was going to simply solve the 50 sudoku problems by hand. That would be 'pencil and paper', right? I started the first one (the one that has the solution given, no less). It turned out that the simple rule i was using by hand was enough to solve it. So i coded that rule up. It turns out that this one rule solves 11 of the 50 puzzles. I was hooked. I've coded a second rule, and now my program solves 39 of 50. I could solve the remaining 11 by hand, but i'm hopelessly hooked. I even discovered that one of the sudoku games on my desktop allows me to enter a puzzle and solve it from there (which would be cheating, of course). And, i used it to check to see if a partial solution wasn't totally wrong. That is to say, there was only one remaining solution. It seemed to take forever. My program gets the answers it gets roughly instantly, at least so far.

So i wasn't going to write a solver, probably because the problem looked daunting. But now, i'm more or less amazed that something close to 5,000 people have written solvers...

Anyway, chipping away at it a bit at a time hasn't been all that difficult, so far.

[GenePeer]

But now, i'm more or less amazed that something close to 5,000 people have written solvers...

Don't be. I solved this with brute-force which didn't require much thought, and my guess is that's the route most of the 5000 took. It's not solving the same way, people do. Now that you mention it, I might try to write a real "solver".

[Fogmeister]

I'm looking forward to getting stuck into this one.

Should be quite fun.

[Fogmeister]

OK, I've written an algorithm that can solve most of them.

The exceptions are...

6, 21, 23, 25, 29, 49 and 50.

The rest get solved with no problems. These though get to the unsolvable state where there are already all 9 numbers taken in the column, row or mini square.

I think I've got a solution for it though.

It's been fun though

[mdean]

What I've got so far is kind of cool and kind of ugly. I think my grid detection is off at the moment right now. I need to troubleshoot that in the morning. My next goal is to get that working and have it solve problem 1 correctly.

Update: All right, revision 1 successfully solves 40/50 puzzles (6,7,10,25,42,43,47,48,49,50 unsolved). Now I have a feeling things are going to get tricky.

[Sintex]

Ok I am kinda new to this,
But this one is blowing my mind, I have a feeling on how I will do it however the Problem i have now is sorting out the Data as it comes in,
Fun times !!!!!

[mdean]

Heh. My current problem is keeping track of where everything is. A lot of the code I just did right now is going to be a major problem if I have to troubleshoot it.

[jfren484]

I'm at the same point as mdean (my algorithm solves all but 6, 7, 10, 25, 42, 43, 47, 48, 49, and 50). At this point I am trying to solve number 6 by hand to see what to add to my algorithm, but I'm suspecting I'm at the point where a guess needs to be taken. I just wish I knew if that was the case.

[PurpleBlu3s]

I wrote a solver for this which got stuck at the third one (I didn't try and beyond that at that point), and I couldn't work out what was wrong with my algorithm for so long. A month or so later, I try again, and discover that the addition of two characters '-1' in the right place made everything work...

Definitely a fun problem.

[rayfil]

I just wish I knew if that was the case

All can be solved without guessing with the computer. Doing it by hand, experts might be able to solve them all without guessing but some may be too hard for the average person.

[eppie]

I just wish I knew if that was the case.

A few years ago (before I knew about project Euler), I challenged myself to write a sudoku solver that solves puzzles like I do. Not brute force, but using logic and rules. For this problem I wrote a half smart/ half brute force program. I put problem 6 into my old program and looked at the log. It solved it using four methods (it always tries the easy ones first):
-Square can only be one value
-Only one square in a group (box, row, col) can be a particular number
-"pointing pairs"
-"line box reduction" (google the names if you don't know what they are)

So the answer is that puzzle 6 does not need brute force

[Fogmeister]

Well, I took this problem to the next level...

viewtopic.php?f=26&t=2880

LOL!

I've just launched the Sudoku Wiki app on the iPhone AppStore.

http://www.oliverfoggin.com/sudoku-wiki/

http://itunes.apple.com/gb/app/sudoku-w ... 63647?mt=8

[paulwise3]

using four methods (it always tries the easy ones first):
-Square can only be one value
-Only one square in a group (box, row, col) can be a particular number
-"pointing pairs"
-"line box reduction" (google the names if you don't know what they are)
So the answer is that puzzle 6 does not need brute force

I programmed rules that solved 34 out of 50. Was going to use brute force for the rest, but eppie got me thinking. Thanx for the tips, I will give it another try!

Update: Doing some extra checks I thought were superfluous, took me to solve 42 out of 50. And fast, within a second! My wife will kill me if I use this for our morning paper sudoku...
I hope one of the tips above will get me through all fifty...

[Bubbler]

I'm trying to make a sudoku solver by logic which now includes following techniques:
1) Naked single - A cell has only one candidate
2) Hidden single - A digit has only one possible position in a house(row, column, or box)
3) Locked candidates - Includes "pointing pairs/triples" and "line/box reduction"
4) Naked pair - Two cells in a house having 2 identical candidates (#10, #42 and a few others require this)
5) Naked triple - Three cells in a house having a subset of 3 candidates (#50 requires this)

...And the last boss is #7, and a full solver found on the Net says, to solve that grid, a technique of even higher level is needed! Now I'm going on for this technique (it's called X-wing) in my code to finish this one.

Good luck for others - both solving by hand (I bet someone will be stuck at #7) and by coding the logic.

[Oliver1978]

I did all the grids with pen an paper. Oldschool. Like a boss. Entered my result. No dice. Re-checked my numbers with a sudoku solver. All numbers were correct. Yet, no dice.

Could somebody have a look? I've double- and triple-checked. I can't seem to find a typo or anything else

[Georg]

Yes.

[StevoJohn]

Managed to come up with a solution in C# that solves all of them in 4ms. Pretty chuffed with that.