Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Will_Ness

Will_Ness Will_Ness

Niner since 2010

  • C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 5 of n

    , STL wrote

    [Will_Ness]
    > ... only using some limited, localized what-if analysis

    Your "5:5 goes RT (if were UP => NO_ROOM("3"))" is what my guessing, teamed up with confinement analysis, determines. I don't know how to implement that any more efficiently. (If you do, I encourage you to try!)

    > It is possible that the search might be improved by using the heuristic
    > of working near the known frontier first, with iterative deepening in number of steps considered

    Agreed. My guessing is expensive because it amplifies the amount of other expensive analysis (mainly confinement) that's run.

     

    yes, "localized what-if analysis" is of course guessing - limited by the virtue of being performed by a human with very limited backtracking capacity. Not being able to keep in mind more than a few moves is what I refer to "localized" here (closeness to frontier), and is what forces me to consider only very shallow moves - what the iterative deepening would achieve, which would suspend (not abort) expensive solve() computation(s) in progress. Or you could use a good scheduler for a massively parallel solution that would run all of them at once, Smiley to take care of that automagically.

    I've since seen more puzzle examples, on "puzzle-nurikabe dot com", where unfortunately the initial frontier expansion stops very early on, and extensive guesswork is unavoidable. There another heuristic sometimes works wonders, which I'm having troubles formalizing - painting all the (remaining) cells initially black, and expanding the islands from there, trying "to get away with as much as possible" guided by square condition mostly, at first, and then trying to push a few cells around to correct the problems which appear.

  • C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 5 of n

    I've solved both "hard" wikipedia example and the 9-th "nikoli" example from Stephan's zip file by human reasoning, Smiley without need for "global" backtracking (i.e. "guessing) - only using some limited, localized what-if analysis, and some spatial reasoning for the "9" puzzle. The GIF step-by-step slides are here (please sort by name before viewing).

    It is possible that the search might be improved by using the heuristic of working near the known frontier first, with iterative deepening in number of steps considered, instead of demanding a complete answer (solved/contradiction) for each randomly picked point (sure looks like exponential explosion there).

    Our goal is to add more knowns to the grid, so we need not pursue guesses which still hasn't produced a definitive determination one way or the other after some threshold number of steps - better abort in the middle and try another guess, in hopes it'll produce its answer fairly quickly, and the new known thus found may well lead to a cascade of new knowns to be found semi-automatically (i.e. with extend/(n-1) projection/surround moves which are very easy to make).