Forcing Chains implementation

Ruud · Site Admin

Well, I've finally figured out what's missing in my tables implementation.

In building the implication tables, I kept the focus on the positive implications of each assertion, using the negative implications only as 'links' to the next positive implication.

This prevented me from using these to perform the double-negative verasity test. That's probably what keeps me from solving these last 4 puzzles.

Uniqueness tests 1-4 are implemented and fully operational.

I'll let you know when I've cracked these last 4.

Ruud.

Bob Hanson · Posted: Sat Nov 05, 2005 8:47 pm Post subject:

So, to finish off this thread in terms of Sudoku Assistant, I've now got the forward and reverse logic in there that you can demonstate, and I can verify that they are, indeed, identical. Step for step, word for word identical.

Ruud, you should be able to get this implemented. If you aren't solving those last three by now, fire the puzzle into http://www.stolaf.edu/people/hansonr/sudoku, click on Solve, and then go back to see the steps. You should be able to see just where it does something that you are not doing, and that should provide your solution. It MUST be something subtle in your algorithm -- not checking for FFF? in a CELL, for example. (Row, column, block on a specific value, but also FFF? for the N values in a given cell. Maybe?)

In my case, the breakthrough was when I abandoned a piece that I THOUGHT was working but was actually introducing errors and making the solutions impossible.

Good luck. Shouldn't be long now....

Bob
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

The last glitches in the tabling code have been fixed now.

Finally, "agressive" propagation of implications does the trick. Top870 now completely solved.

However, it works now so fine, that it does not need any verity/verasity search. Every puzzle is now solved with conflict detection only.

It would be nice to see the verity/verasity seach kick in once and a while. The routine is now not only based on T&E, it actually behaves like T&E. Horrible!

I'd like to have it collect all deductions that can be made from the tables, and then report the deduction that is either the most efficient, or has the shortest chains. This is much too slow.

Any ideas from the forum?

Ruud.

Bob Hanson · Posted: Mon Nov 07, 2005 8:56 pm Post subject:

Congratulations, Ruud! WE HAVE CONVERGENCE! Very Happy

That's really all there is to it, isn't it? How marvelous!

So, do we call this "trial and error"?

I'm assuming you mean ?FFFF --> TFFFF in terms of "agressive" propagation. Really just "that last little missing detail" I think.

Hmm. Collect all. I implemented this in Sudoku Assistant just this morning in terms of looking for magic cells. I figured that people might want all magic cells, not just the first found, so there I needed to go through all the possibilities. Yes, VERY slow. I think this is probably what xyzzy was thinking about in terms of a catalog/hypothesis program working so slowly.

I would say that a compromise position would be to deliver a "first-found" logic trail, the way Sudoku Assistant does, but then, if the user desires, and can wait the extra few seconds, allow the option of delivering the "best" or "shortest". This user is looking for something special, I think, and it is reasonable to ask them to wait.

But even with that, at least with the Medusa chains, there isn't really one "unique" cycle that is developed -- it's a grand synthesis of all the implications. So it's really not clear to me that there IS a "simplest" way. Finding the "shortest cycle" is a good challenge for some mathematician, I think. Maybe there's a "shortest path" from "a" to "z" here. Could be an interesting challenge.

I think the thing to realize is that we are talking about the REALLY difficult puzzles here. How many actual puzzles people really solve would be expected to be at this level? I suspect a very small percentage. All the "reasonable" ones fall far earlier, mostly with strong chain/weak link incompatibility issues of the sort outlined at Glenn Fowler's site.

One question: In your implementation, are you doing subset elimination, box row/column exclusion, etc. FIRST, or are you using only this logical chain analysis and simple cross-hatch scanning?

Again, congratulations,
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Bob Hanson · Posted: Mon Nov 07, 2005 10:33 pm Post subject:

what fun!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Mon Nov 07, 2005 11:25 pm Post subject:

rubylips · Posted: Mon Nov 07, 2005 11:33 pm Post subject:

rubylips · Posted: Mon Nov 07, 2005 11:38 pm Post subject:

Ruud · Site Admin

Bob Hanson · Posted: Tue Nov 08, 2005 12:06 pm Post subject:

shortest path: I think there are two issues here.

1) shortest path for a specific elimination

--should not be too difficult; Medusa chains provide the complete set of
all possible "routes" from one end to the other leading to a specific
elimination. So a quick run though the possibilities should give the
shortest route. I think this would be very very quick.

2) shortest path for ANY possible elimination

--much slower -- must do (1) for each possible elimination each time.

One could provide (1) or (2) as an option and let the user decide which is more important.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

There are actually 3 issues here:

1. Shortest path for a specific elimination
2. Shortest path for any possible elimination (at a given state)
3. Shortest path to the complete solution

If we want these techniques to be more than just 'T&E renamed', we should exploit the fact that we've gathered so much information about the state of the puzzle.

1. Is easy indeed.

2. Is more difficult, but doable. My program first scans for errors, but it should also scan for verities in the remaining candidates. This would be a lot more complicated than comparing errors to errors and verities to verities.

3. Is the real challenge. Not only would we have to compare the path length, but sometimes you would sacrifice a shorter chain in favor of a longer chain that gives you an easier path to the final solution. In some of the more difficult puzzles, the solver needs to revisit the tables 7 times or more. It would show true intelligence if it can find a single chain that may be a little longer, but allows solving the remainder of the puzzle with singles only.

xyzzy · Posted: Fri Nov 11, 2005 12:05 am Post subject:

It's not that hard to do this. Check out some AI text on finding shortest paths, this is an old problem. What you want to do is use an A* search. I already wrote this kind of search to see if it was faster than a depth first search (it's not).

Ruud · Site Admin

I'm not sure I really want to know what an A* search is....

My tabling/forced chains implementation has now entered a new stage. I've rewritten the code in such a way that the DLX nodes are dynamically updated by the other solving methods, when they eliminate candidates, force or pin cells, etc.

This now allows me to use the DLX nodes to do the tabling. Because this piece of code is so extremely fast, it can build the tables much faster than the method I've used so far. (I think)

Has anyone been on this path? If so, what are the pitfalls that I can expect? Also: I'd like to visualise the DLX process, so I can follow it's progress. Any ideas?

Ruud.

Bob Hanson · Posted: Fri Nov 11, 2005 5:48 pm Post subject:

can you describe in SIMPLE terms the Dancing Links process?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr