Web based solver

Str8ts discussion with Jeff Widderich and Andrew Stuart.
Stellen Sie hier Fragen an Str8ts-Erfinder Jeff Widderich und Andrew Stuart.

Moderatoren: Syndicate, Andrew

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Web based solver

Beitrag von Robo » Montag 29. Januar 2018, 10:20

Here is another solver, purely browser-based.

https://is.gd/solverBeta1

It includes chain evaluation (including chain visualization) and finds all solutions.
Currently, more chains than perhaps necessary are evaluated, I still have a number of missing algorithms on my todo-list that would avoid some chains.

Let me know your feedback or questions.
I hope this can revive some strategy and/or software development discussions.

The solver is written in F# / Websharper. I still plan to put it on github after some more polishing.

Robo

Leren
Beiträge: 5
Registriert: Dienstag 30. Januar 2018, 20:37

Re: Web based solver

Beitrag von Leren » Dienstag 30. Januar 2018, 21:08

Hi Robo,

As I said in Andrew's Str8ts forum your solver appears to incorporate Trial and Error, which you can reduce the reliance on if you incorporate SI's.

The term SI was coined by Ben. It refers to a short chain where the overall logic may less complicated that some single row/column eliminations (which are usually referred to as CEs (Careful Eliminations). In my solver I have limited my SI's to 4 cells in the pattern, although I do remember Ben refering to a chain of length 6 as an easy SI, so you can see that the boundary between SI's and chains is vague. Also with my SI's there are no fancy nodes, (such as XWings or UR threats just individual candidates).

I try to keep my puzzles to those solvable with no more than one SI. It's not reasonable to expect a manual solver to spot more than one SI and they don't like this kid of puzzle.

Hope this helps, Leren

Leren
Beiträge: 5
Registriert: Dienstag 30. Januar 2018, 20:37

Re: Web based solver

Beitrag von Leren » Dienstag 30. Januar 2018, 21:57

Hi Again Robo,

I have another question about your solver. There is an option called Hone search. What is this ?

I'm pretty sure that Hone has solving tricks that I haven't figured out yet, and I'm always keen to improve my own solver.

Leren

hone
Beiträge: 29
Registriert: Sonntag 7. Februar 2016, 13:30

A fast solver

Beitrag von hone » Dienstag 30. Januar 2018, 22:32

@Leren

Robo´s solver indeed is trial/error based once all standard tools are exhausted. Using sophisticated complexity measures, it determines the most promising undecided High/Low compartments and if this is exhausted uses candidates.

I was surprised how this solver handled some of my ultra puzzles. Although one has to try all possibilties to ensure uniqueness, the results were there in a few seconds. Funnily enough, I use a similar approach, but only for generating. For solving harder patterns I use neighbourhood operations and never had the idea to use trial/error approaches.
Now applying my generator as a solver, the results were also available in a few seconds. In most cases it was only necessary to try two or three high/low ranges to solve the patterns and determine all dead ends.

You mention that users would prefer puzzles with few SI´s. I am not so sure. The discussions mostly live up at such contributions and not on those solvable with standard tools. Also if the latter contain some nice big wings it only makes sense if they come early. Otherwise there will be, nearly inevitably, obvious shortcut possibilities via SI/UR in developed grids.

Greetings
hone

hone
Beiträge: 29
Registriert: Sonntag 7. Februar 2016, 13:30

Re: Web based solver

Beitrag von hone » Dienstag 30. Januar 2018, 22:48

Hi Leren

cross posting, didn't see your last one.

Retrieve CanisMajor and let it run with and without "hone search" setting. "Without" the solver needs chaining. But at the first chain nodes one can remove 9 from CJ8 and - here more important - the 4 from B3.

hone

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Web based solver

Beitrag von Robo » Mittwoch 31. Januar 2018, 08:35

Hi Leren,
Welcome to this forum.
Hone's explanation is completely correct.
I use a number of CE algorithms, including high-low checks; BCA; x-wings/fishes; and optionally UR (not all cases covered yet though).
Until a couple of weeks ago, I also used (as a last resort before chain trials) exhaustive search of each row/column. I then learned from hone about his fast two-level search, which I implemented as a replacement of my flat exhaustive search.
I still have a number of algorithms on my todo list, including SI.
If I understand correctly what you and hone said about SI, then SI are not really what I was used to call chains (i.e. two alternative assumptions, one leading to an invalid situation), but look-aheads that lead to certain eliminations. Or, to express it differently, chains that merge back. Instead of a chain tree I would have a chain network.
So I have an interesting challenge here of adapting my software design in an elegant way.
(Which is the real fun in this whole exercise :-))
robo

Leren
Beiträge: 5
Registriert: Dienstag 30. Januar 2018, 20:37

Re: Web based solver

Beitrag von Leren » Freitag 2. Februar 2018, 09:27

Hi Hone,

I did as you said with Canis Major and noted the "Hone Search" eliminations. Perhaps you put me out of my misery and explain the logic underlying these eliminations - I can't understand them at all.

I'll stick by my assertion that the majority of solvers do not like multiple SI puzzles, and nobody at all likes long chainy puzzles. In fact, when I am creating puzzles I turn my general chaining routines off, so none of my puzzles requires long chaining.

The more astute solvers generally are the ones that make posts, but I've learn't, as a casual puzzle creator, that there is a silent majority of not quite so astute solvers who do like extremes, but at the lower difficulty level. For really difficult puzzles I suspect that they suffer in silence. Even the astute solvers sometimes say that they enjoy the variation of solving more relaxing extremes.

I've just loaded a new puzzle - solvable without chains or UR's, If you like multiple SI's. Enjoy.
Zuletzt geändert von Leren am Freitag 2. Februar 2018, 11:18, insgesamt 2-mal geändert.

hone
Beiträge: 29
Registriert: Sonntag 7. Februar 2016, 13:30

Re: Web based solver

Beitrag von hone » Freitag 2. Februar 2018, 12:14

Hi Leren,
Regarding the CanisMajor eliminations (position 0:17 node 106):
The first one should be quite straightforward, where the single cell compartment A8 has only the two candidates 8 and 9. If CJ8 would have a 9, then it also would have an 8 and no candidates left in A8. So all 9´s can be removed from CJ8. Translating these "CE"-methods in computer algorithms is not so straightforward but can be achieved by analyzing value range combinations.
In this case A8 has ranges [8] and [9], and CJ8 has ranges [1-7],[2-81 and [3-9]. To ease the use each range can be represented by its lowest value; together with the compartment length this is unique. There are 6 combinations of ranges between the two compartments ( [8,1],[8,2],[8,3],[9,1],[9,2] and [9,3]). An obvious condiion is that there is no overlap of the range values in each tuple. So [8,2],[8,3] and [9,3] have to be discarded due to overlaps so that only [8,1],[9,1] and [9,2] survive.

Next step is to analyze if there are candidates and ranges missing in each of the combined value sets. Here the 9 of CJ8 appears nowhere and can be eliminated; also range 3 from CJ8.

Otherwise if there are candidates which appear in each combo, they will become sure values of at least the line if they aren´t already.

Vice versa there is the additional precondition for range combos, that each combo set contains all current sure values of the line.

The second elimination (4 from B3) requires range combo analysis but also a sequence check. It is simply to question: Does a valid permutation for B3=4 exist? Here none can be found. This is more or less the same method as a human solver implicitly uses.

Btw those sequence checks cover most of the standard tools. I do not search for multiples anymore and never started with hidden ones.

Hope this helped
hone

Leren
Beiträge: 5
Registriert: Dienstag 30. Januar 2018, 20:37

Re: Web based solver

Beitrag von Leren » Freitag 2. Februar 2018, 21:49

Hi Hone, perhaps I should apologise for being so thick and wasting your time. Since this is a new day I am a bit more awake and I simply put Canis Major into my solver to see what it did.

Removing the 9's from CJ8 was simple. I call this easy compartment interaction Stranded by a Cell. Obviously if CJ8 contains 9 it has to contain 8, so there are no candidates in A8.

Removing 4 from B3 is more interesting. I call this one a Hidden Large Gap Cell. If ABC3 contains 4 HJ4 must contain 2, so C3 would be 14, making it a Large Gap Cell in ABC3, so 4 can be eliminated elsewhere in ABC3.

I suppose the real issue is why Robo's solver applies these two moves at the same time. My solver proceeds one move at a time and provides a full explanation of each elimination on a logsheet, so I'm used to that.

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Web based solver

Beitrag von Robo » Montag 5. Februar 2018, 16:05

Hi Leren,
You can see every single elimination explained in detail in the yellow pop-up boxes.
However, the hone line search (at least the way I have implemented it) is just an (intelligent) exhaustive search of the row or column. So there is not much to explain on that one by the solver.
Maybe the real issue is the difference between a mathematical and an engineering approach to the problem :-)
robo

Antworten