Solve a Hopido puzzle

From Rosetta Code
Jump to: navigation, search
Task
Solve a Hopido puzzle
You are encouraged to solve this task according to the task description, using any language you may know.

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:

. 0 0 . 0 0 .
0 0 0 0 0 0 0
0 0 0 0 0 0 0
. 0 0 0 0 0 .
. . 0 0 0 . .
. . . 0 . . .

Extra credits are available for other interesting designs.

Realated Tasks:

Contents

[edit] Icon and Unicon

Minor variant of Solve_a_Holy_Knight's_tour. Works in Unicon only.

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

Sample run:

->hopido <hopido1.in
Input with 27 cells:
                                 
                                 
           _  _     _  _         
        _  _  _  _  _  _  _      
        _  _  _  _  _  _  _      
           _  _  _  _  _         
              _  _  _            
                 1               
                                 
                                 
Output with 27 cells:
                                 
                                 
           3 21    13 22         
       25  9  6 26 10  7 27      
       20 17 14  2 18 15 12      
           4 24  8  5 23         
             19 16 11            
                 1               
                                 
                                 
->

[edit] Perl 6

Using the solver from Solve_a_Hidato_puzzle.

my @adjacent = [3, 0],
[2, -2], [2, 2],
[0, -3], [0, 3],
[-2, -2], [-2, 2],
[-3, 0];
 
solveboard q:to/END/;
. 0 0 . 0 0 .
0 0 0 0 0 0 0
0 0 0 0 0 0 0
. 0 0 0 0 0 .
. . 0 0 0 . .
. . . 1 . . .
END
Output:
   21  4    20  3   
26 12 15 25 11 14 24
17  6  9 18  5  8 19
   22 27 13 23  2   
      16  7 10      
          1         
59 tries

[edit] Racket

This solution uses the module "hidato-family-solver.rkt" from Solve a Numbrix puzzle#Racket. The difference between the two is essentially the neighbourhood function.

#lang racket
(require "hidato-family-solver.rkt")
 
(define hoppy-moore-neighbour-offsets
'((+3 0) (-3 0) (0 +3) (0 -3) (+2 +2) (-2 -2) (-2 +2) (+2 -2)))
 
(define solve-hopido (solve-hidato-family hoppy-moore-neighbour-offsets))
 
(displayln
(puzzle->string
(solve-hopido
#(#(_ 0 0 _ 0 0 _)
#(0 0 0 0 0 0 0)
#(0 0 0 0 0 0 0)
#(_ 0 0 0 0 0 _)
#(_ _ 0 0 0 _ _)
#(_ _ _ 0 _ _ _)))))
 
Output:
 _  2 20  _  3 19  _
 7 10 13  6  9 12  5
15 22 25 16 21 24 27
 _  1  8 11  4 18  _
 _  _ 14 23 26  _  _
 _  _  _ 17  _  _  _

[edit] REXX

This REXX program is a slightly modified version of the REXX Hidato program.

/*REXX program solves a Hopido puzzle, displays puzzle and the solution.*/
call time 'Reset' /*reset the REXX elapsed timer. */
maxr=0; maxc=0; maxx=0; minr=9e9; minc=9e9; minx=9e9; cells=0; @.=
parse arg xxx; /*get cell definitions from C.L. */
xxx=translate(xxx, , "/\;:_", ',') /*also allow other chars as comma*/
 
do while xxx\=''; parse var xxx r c marks ',' xxx
do while marks\=''; _=@.r.c
parse var marks x marks
if datatype(x,'N') then x=x/1 /*normalize X*/
minr=min(minr,r); maxr=max(maxr,r)
minc=min(minc,c); maxc=max(maxc,c)
if x==1 then do;  !r=r;  !c=c; end /*start cell.*/
if _\=='' then call err "cell at" r c 'is already occupied with:' _
@.r.c=x; c=c+1; cells=cells+1 /*assign mark*/
if x==. then iterate /*hole? Skip.*/
if \datatype(x,'W') then call err 'illegal marker specified:' x
minx=min(minx,x); maxx=max(maxx,x) /*min & max X*/
end /*while marks¬='' */
end /*while xxx ¬='' */
call showGrid /* [↓] used for making fast moves*/
Nr = '0 3 0 -3 -2 2 2 -2' /*possible row for the next move.*/
Nc = '3 0 -3 0 2 -2 2 -2' /* " col " " " " */
pMoves=words(Nr) /*the number of possible moves. */
do i=1 for pMoves; Nr.i=word(Nr,i); Nc.i=word(Nc,i); end /*fast moves*/
if \next(2,!r,!c) then call err 'No solution possible for this Hopido puzzle.'
say 'A solution for the Hopido exists.'; say; call showGrid
et=format(time('Elapsed'),,2) /*get REXX elapsed time (in secs)*/
if et<.1 then say 'and took less than 1/10 of a second.'
else say 'and took' et "seconds."
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────ERR subroutine──────────────────────*/
err: say; say '***error!*** (from Hopido): ' arg(1); say; exit 13
/*──────────────────────────────────NEXT subroutine─────────────────────*/
next: procedure expose @. Nr. Nc. cells pMoves; parse arg #,r,c; ##=#+1
do t=1 for pMoves /* [↓] try some moves.*/
parse value r+Nr.t c+Nc.t with nr nc /*next move coördinates*/
if @.nr.nc==. then do; @.nr.nc=# /*a move.*/
if #==cells then leave /*last 1?*/
if next(##,nr,nc) then return 1
@.nr.nc=. /*undo the above move. */
iterate /*go & try another move*/
end
if @.nr.nc==# then do /*is this a fill-in ? */
if #==cells then return 1 /*last 1.*/
if next(##,nr,nc) then return 1 /*fill-in*/
end
end /*t*/
return 0 /*This ain't working. */
/*──────────────────────────────────SHOWGRID subroutine─────────────────*/
showGrid: if maxr<1 | maxc<1 then call err 'no legal cell was specified.'
if minx<1 then call err 'no 1 was specified for the puzzle start'
w=length(cells); do r=maxr to minr by -1; _=
do c=minc to maxc; _=_ right(@.r.c,w); end /*c*/
say _
end /*r*/
say; return

output when the input is:
1 4 1 \2 3 . . . \3 2 . . . . . \4 1 . . . . . . . \5 1 . . . . . . . \6 2 . . \6 5 . .

     .  .     .  .
  .  .  .  .  .  .  .
  .  .  .  .  .  .  .
     .  .  .  .  .
        .  .  .
           1

A solution for the Hopido exists.

     5 12     4 11
  8 22 25  7 21 24 27
 13 16 19  2 15 18  3
     6  9 23 26 10
       14 17 20
           1

and took less than  1/10  of a second.

[edit] Ruby

This solution uses HLPsolver from here

require 'HLPsolver'
 
ADJACENT = [[-3, 0], [0, -3], [0, 3], [3, 0], [-2, -2], [-2, 2], [2, -2], [2, 2]]
 
board1 = <<EOS
. 0 0 . 0 0 .
0 0 0 0 0 0 0
0 0 0 0 0 0 0
. 0 0 0 0 0 .
. . 0 0 0 . .
. . . 1 . . .
EOS

t0 = Time.now
HLPsolver.new(board1).solve
puts " #{Time.now - t0} sec"

Which produces:

Problem:
     0  0     0  0   
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
     0  0  0  0  0   
        0  0  0      
           1         

Solution:
     3 12     4 11   
  8 18 21  7 17 20  6
 13 24 27 14 23 26 15
     2  9 19  5 10   
       22 25 16      
           1         

 0.001 sec

[edit] Tcl

Works with: Tcl version 8.6
package require Tcl 8.6
 
oo::class create HopidoSolver {
variable grid start limit
constructor {puzzle} {
set grid $puzzle
for {set y 0} {$y < [llength $grid]} {incr y} {
for {set x 0} {$x < [llength [lindex $grid $y]]} {incr x} {
if {[set cell [lindex $grid $y $x]] == 1} {
set start [list $y $x]
}
incr limit [expr {$cell>=0}]
}
}
if {![info exist start]} {
return -code error "no starting position found"
}
}
method moves {} {
return {
0 -3
-2 -2 -2 2
-3 0 3 0
-2 2 2 2
0 3
}
}
method Moves {g r c} {
set valid {}
foreach {dr dc} [my moves] {
set R [expr {$r + $dr}]
set C [expr {$c + $dc}]
if {[lindex $g $R $C] == 0} {
lappend valid $R $C
}
}
return $valid
}
 
method Solve {g r c v} {
lset g $r $c [incr v]
if {$v >= $limit} {return $g}
foreach {r c} [my Moves $g $r $c] {
return [my Solve $g $r $c $v]
}
return -code continue
}
 
method solve {} {
while {[incr i]==1} {
set grid [my Solve $grid {*}$start 0]
return
}
return -code error "solution not possible"
}
method solution {} {return $grid}
}
 
proc parsePuzzle {str} {
foreach line [split $str "\n"] {
if {[string trim $line] eq ""} continue
lappend rows [lmap {- c} [regexp -all -inline {(.)\s?} $line] {
string map {" " -1 "." -1} $c
}]
}
set len [tcl::mathfunc::max {*}[lmap r $rows {llength $r}]]
for {set i 0} {$i < [llength $rows]} {incr i} {
while {[llength [lindex $rows $i]] < $len} {
lset rows $i end+1 -1
}
}
return $rows
}
proc showPuzzle {grid name} {
foreach row $grid {foreach cell $row {incr c [expr {$cell>=0}]}}
set len [string length $c]
set u [string repeat "_" $len]
puts "$name with $c cells"
foreach row $grid {
puts [format "  %s" [join [lmap c $row {
format "%*s" $len [if {$c==-1} list elseif {$c==0} {set u} {set c}]
}]]]
}
}
set puzzle [parsePuzzle {
. 0 0 . 0 0 .
0 0 0 0 0 0 0
0 0 0 0 0 0 0
. 0 0 0 0 0 .
. . 0 0 0 . .
. . . 1 . . .
}]
showPuzzle $puzzle "Input"
HopidoSolver create hop $puzzle
hop solve
showPuzzle [hop solution] "Output"
Output:
Input with 27 cells
     __ __    __ __   
  __ __ __ __ __ __ __
  __ __ __ __ __ __ __
     __ __ __ __ __   
        __ __ __      
            1         
Output with 27 cells
      3  6    23  7   
  27 11 14 26 10 13 25
   5 17 20  4 16 19 22
      2  9 12 24  8   
        15 18 21      
            1         
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox