Sudoku Solver.co.uk Challenge puzzles

vindaloo

I've been following the discussions re: fishy cycles etc. very closely.

This technique is enough to solve the 1st challenge puzzle on http://www.sudokusolver.co.uk, which is great news, but apparently not the second.

Well I'd like to point out that according to Pappocom's solver the 2nd challenge puzzle on sudoku solver is actually not a valid puzzle - i.e. it is not solvable by logic!! (presumably trial and error is required).

Pappocom includes things like nishio, X-wing and swordfish in his rules of "logic". In the puzzles he sets himself he only allows X-wing, but when using his program to solve other puzzles Nishio and swordfish are allowed (and possibly extensions of swordfish ala fishy cycles).

So as far as we know (at least according to Pappocom's definition) we seem to have covered all the rules of sudoku logic.

It would be interesting to find out if Pappocom has just implemented swordfish or a generalized fishy-cycles algorithm. Does anyone have any higher-order fishy-cycle puzzles to hand??

Vin.

Doug · Posted: Fri Jun 03, 2005 9:53 pm Post subject: Re: Challenge Puzzles

I have a couple of comments:

The algorithm that gets the 1st challenge problem isn't Fishy Cycles, but rather the algorithm Simple Forcing Chains. Now, Simple Forcing Chains is subsumed under Limited Implication Trees, which hasn't been implemented yet. It may be that it gets the 2nd challenge problem. (I doubt it, but am loathe to run through it by hand on that problem.)

Another thought. The "logic rule lists" that abound are, of course, supposed to be "human implementable". Already some of the rules out there are getting to the strenuous limits of what a human can do by hand, and certainly in their head. Fishy Cycles is certainly on the edge, and I think some would say over it. Yet, there is no guarantee that someone won't come up with a fairly simple rule, yet unknown, that enables the solution of the 2nd challenge. Just having the current rule lists fail, doesn't mean that the puzzle can't be "done by logic". Indeed, I have another algorithm that I'm thinking about which might also make a difference on that 2nd challenge.

I don't have Pappocom's solver. But it includes Nishio, eh? Then Limited Implication Trees should be fair game too. It can be viewed as an extension of Nishio.

Sorry, I don't have an example of a longer Fishy Cycle Puzzle. One could contrive one though, without too much difficulty. If I have some time later, I'll post one here.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

vindaloo · Posted: Fri Jun 03, 2005 10:13 pm Post subject: Re: Challenge Puzzles

PeteWake · Posted: Fri Jun 10, 2005 10:12 pm Post subject: What is trial by logic?

Hi - I run the sudokusolver.co.uk site. Challenge puzzle 2 on the site is a great one because it noone has yet given the solve method that cracks it by logic. Yet we know it has a unique solution (try it on the main page with the 'check and guess' box checked and the 'return first' solution unchecked).

Sudoku puzzles fall into a class of problems mathemeticians call 'NP-hard' - which means that noone has yet found a way of solving every option by logic alone. However, the other way of looking at this (I think) is that there is an unbounded set of logic rules. However I am not a logic professor so I can't say with 100% confidence that this is the case.

To me, the point at which logic is left behind and guesswork begins is very clear - it is the point at which my program has to save a snapshot of the grid, reduce one gridpoint to one of the remaining possibilities and continue knowing it might have to come back.

I am now just keen for some earnest programmers to submit javascript code to solve method E.. which I don't think is guessing.

Happy sudokuing,
Pete Wake

rallveird · Posted: Mon Jun 13, 2005 4:00 am Post subject:

If you put this sudoku (not symmetrical though) into the challenge-solver you get down to 56 to go. That's a lot of cells left.

vindaloo · Posted: Mon Jun 13, 2005 6:45 pm Post subject: Re: What is trial by logic?

Hi Pete,
thanks for your reply. Sorry I didn't see it earlier.

I'm not a logic professor either, but I do have a mathematics/logic background. You raise a very interesting point - I was wondering why you thought example 2 was solvable by logic and Pappocom didn't.

Here is my thinking:
Just because a sudoku (or some other problem) only has one solution, does not (in and of itself) imply that it is solvable by logic. The proof that sudoku is NP-complete actually shows us that in general sudoku is *not* solvable by logic. In other words you can have a sudoku with only 1 solution, but there is no fast way of getting there - other than by searching.

Also the daily telegraph puzzles only have 1 solution (unless a mistake has been made which sometimes happens), yet they are not solvable using logic - search/backtracking must be employed.

I must give a major caveat to everything I have said though - it is that basically the discussions I have given are general. In general 1-solution sudoku puzzles are not solvable using logic. But that doesn't mean that in any particular case there isn't some rule out there which can solve it - just that in general it isn't true.

Vin.

Doug · Posted: Mon Jun 13, 2005 9:20 pm Post subject:

I have a couple of comments. (And yes, I am a professional methematician.)

Technically speaking, in usual mathematical usage, all Sudoku is solvable by logic. Backtracking is logic. Even the longest brute force backtracking algorithm, such as trying a value in a cell, trying a new value in the next and so on till all possible values have been tried in all cells is a logic solution.

What is meant by "logic" in this forum is more the problem of finding fast algorithms which don't use a lot of memory. (That way the method of solving can be carried out by a person with only pencil and paper in a reasonable time.) What is saught here are computationally easy solutions. Guess and check is still logic in the mathematical sense. People are really searching for solutions of low computational complexity.

Now as the NP-hard means that as the board sizes get larger, 9x9, 15x15, 18x18,... NxN, ...., the percent of boards where such fast algorithms give rapid solutions will peter out and more nasty algorithms will be needed. That means that the complexity of the rules must increase as board sizes get larger. Eventually, the rules must get so hard that they will not be doable by hand, by the lonely human.

The interesting question is: for 9x9, how computationally complex do the solution techniques have to get? Can we find a set of rules which avoids "guess and check", and is doable by hand? My guess is that there are boards, which already may be known, which require rules that are too complex to be done by hand. Even so, at 9x9, the 10 or so "rules" that are used by the "logic" solvers do a good job on most boards. The question is can we get them all easily. My guess is no.

Also, looking for these fast algorithms is a bit interesting from the point of view of finding better approaches to NP-hard problems.

Incidentally, the problem of finding a solution to a particular sudoku, of size NxN, while NP-hard, has an easy check, so it's NP-complete. (The check of a putative solution runs really fast-- in polynomial time.) I think the problem of finding all solutions, (assuming we don't know existence or uniqueness) is probably NP-hard, but not NP-complete.

Oh, and one more thing. "Guess and check" is used very carelessly here. Technically, all the methods used can be viewed as guess and check. Take the simple rule: "only one possible cell in a row". This rule is the same as saying "Can 1 go in cell 1? No. Can 1 go in cell 2? No. Can 1 go in cell 3? No. And so on until it's found that 1 can only go in cell 8, say." (But you need to check cell 9 to make sure cell 8 is the only possability.) It's just easy to visually scan and do that guess and check by eye. Sorry to say, but logically speaking it's still guess and check. Just one that's easy to do by hand; one that "runs" quickly. The phrase "guess and check" as used here is ill-defined. Again, what people are looking for are rules of low computational complexity.

I hope that clarifies some things a bit.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

MadOverlord · Posted: Wed Jun 15, 2005 5:13 am Post subject:

tilps · Posted: Sun Jun 19, 2005 7:21 am Post subject:

hrmm, first order 'lookahead created' logic solves the second challenge problem here as well. Guess I should have a look at how.

jiffle · Posted: Tue Jun 21, 2005 5:05 pm Post subject:

Hi, please could somebody tell me how to solve the following using logic:

MadOverlord · Posted: Tue Jun 21, 2005 7:08 pm Post subject:

Solving it requires using Bowman Bingo techniques. Here's the solution path:

jiffle · Posted: Tue Jun 21, 2005 7:24 pm Post subject:

Thanks. Interesting to read about Bowman Bingo. My code solved it too, although not entirely with pure logic, and that's why I was wondering whether I was missing something. My code makes 'intelligent' guesses and aborts them when inconsistencies are detected (although the debug output is nowhere near as sophisticated as that shown above... it usually just sets an error flag when an out-of-range condition arises from a matrix operation [eg due to no candidates being found], at which point it aborts the current pass and redrives guessing from the next entry in the guess array). The inconsistency detection is rather more by luck than judgement although it seems to hand together suprisingly well!