How to resolve the algorithm Solve a Hopido puzzle step by step in the Icon and Unicon programming language

Published on 12 May 2024 09:40 PM
#Icon and unicon

How to resolve the algorithm Solve a Hopido puzzle step by step in the Icon and Unicon programming language

Table of Contents

Problem Statement

Hopido puzzles are similar to Hidato. The most important difference is that the only moves allowed are: hop over one tile diagonally; and over two tiles horizontally and vertically. It should be possible to start anywhere in the path, the end point isn't indicated and there are no intermediate clues. Hopido Design Post Mortem contains the following: "Big puzzles represented another problem. Up until quite late in the project our puzzle solver was painfully slow with most puzzles above 7×7 tiles. Testing the solution from each starting point could take hours. If the tile layout was changed even a little, the whole puzzle had to be tested again. We were just about to give up the biggest puzzles entirely when our programmer suddenly came up with a magical algorithm that cut the testing process down to only minutes. Hooray!" Knowing the kindness in the heart of every contributor to Rosetta Code, I know that we shall feel that as an act of humanity we must solve these puzzles for them in let's say milliseconds. Example: Extra credits are available for other interesting designs.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Solve a Hopido puzzle step by step in the Icon and Unicon programming language

Source code in the icon programming language

global nCells, cMap, best
record Pos(r,c)

procedure main(A)
    puzzle := showPuzzle("Input",readPuzzle())
    QMouse(puzzle,findStart(puzzle),&null,0)
    showPuzzle("Output", solvePuzzle(puzzle)) | write("No solution!")
end

procedure readPuzzle()
    # Start with a reduced puzzle space
    p := [[-1],[-1]]
    nCells := maxCols := 0
    every line := !&input do {
        put(p,[: -1 | -1 | gencells(line) | -1 | -1 :])
        maxCols <:= *p[-1]
        }
    every put(p, [-1]|[-1])
    # Now normalize all rows to the same length
    every i := 1 to *p do p[i] := [: !p[i] | (|-1\(maxCols - *p[i])) :]
    return p
end

procedure gencells(s)
    static WS, NWS
    initial {
        NWS := ~(WS := " \t")
        cMap := table()     # Map to/from internal model
        cMap["#"] := -1;  cMap["_"] :=  0
        cMap[-1]  := " "; cMap[0]   := "_"
        }

    s ? while not pos(0) do {
            w := (tab(many(WS))|"", tab(many(NWS))) | break
            w := numeric(\cMap[w]|w)
            if -1 ~= w then nCells +:= 1
            suspend w
            }
end

procedure showPuzzle(label, p)
    write(label," with ",nCells," cells:")
    every r := !p do {
        every c := !r do writes(right((\cMap[c]|c),*nCells+1))
        write()
        }
    return p
end

procedure findStart(p)
    if \p[r := !*p][c := !*p[r]] = 1 then return Pos(r,c)
end

procedure solvePuzzle(puzzle)
    if path := \best then {
        repeat {
            loc := path.getLoc()
            puzzle[loc.r][loc.c] := path.getVal()
            path := \path.getParent() | break
            }
        return puzzle
        }
end

class QMouse(puzzle, loc, parent, val)

    method getVal(); return val; end
    method getLoc(); return loc; end
    method getParent(); return parent; end
    method atEnd(); return nCells = val; end

    method visit(r,c)
        if /best & validPos(r,c) then return Pos(r,c)
    end

    method validPos(r,c)
        v := val+1
        xv := (0 <= puzzle[r][c]) | fail
        if xv = (v|0) then {  # make sure this path hasn't already gone there
            ancestor := self
            while xl := (ancestor := \ancestor.getParent()).getLoc() do
                if (xl.r = r) & (xl.c = c) then fail
            return
            }
    end

initially
    val := val+1
    if atEnd() then return best := self
    QMouse(puzzle, visit(loc.r-3,loc.c),   self, val)
    QMouse(puzzle, visit(loc.r-2,loc.c-2), self, val)
    QMouse(puzzle, visit(loc.r,  loc.c-3), self, val)
    QMouse(puzzle, visit(loc.r+2,loc.c-2), self, val)
    QMouse(puzzle, visit(loc.r+3,loc.c),   self, val)
    QMouse(puzzle, visit(loc.r+2,loc.c+2), self, val)
    QMouse(puzzle, visit(loc.r,  loc.c+3), self, val)
    QMouse(puzzle, visit(loc.r-2,loc.c+2), self, val)
end

You may also check:How to resolve the algorithm Extend your language step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Copy a string step by step in the Emacs Lisp programming language
You may also check:How to resolve the algorithm Execute HQ9+ step by step in the C# programming language
You may also check:How to resolve the algorithm Color of a screen pixel step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm A+B step by step in the SQL PL programming language