user
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.

Related tasks

* A\* search algorithm
* Solve a Holy Knight's tour
* Knight's tour
* N-queens problem
* Solve a Hidato puzzle
* Solve a Holy Knight's tour
* Solve a Numbrix puzzle
* Solve the no connection puzzle
assistant
(formerly Perl 6)

This uses a Warnsdorff solver, which cuts down the number of tries by more than a factor of six over the brute force approach. This same solver is used in:

* Solve a Hidato puzzle
* Solve a Hopido puzzle
* Solve a Holy Knight's tour
* Solve a Numbrix puzzle
* Solve the no connection puzzle

```
my @adjacent = [3, 0],
      [2, -2],         [2, 2],
   [0, -3],                [0, 3],
      [-2, -2],        [-2, 2],
               [-3, 0];

solveboard q:to/END/;
    . _ _ . _ _ .
    _ _ _ _ _ _ _
    _ _ _ _ _ _ _
    . _ _ _ _ _ .
    . . _ _ _ . .
    . . . 1 . . .
    END

sub solveboard($board) {
    my $max = +$board.comb(/\w+/);
    my $width = $max.chars;

    my @grid;
    my @known;
    my @neigh;
    my @degree;
 
    @grid = $board.lines.map: -> $line {
        [ $line.words.map: { /^_/ ?? 0 !! /^\./ ?? Rat !! $_ } ]
    }
 
    sub neighbors($y,$x --> List) {
        eager gather for @adjacent {
            my $y1 = $y + .[0];
            my $x1 = $x + .[1];
            take [$y1,$x1] if defined @grid[$y1][$x1];
        }
    }

    for ^@grid -> $y {
        for ^@grid[$y] -> $x {
            if @grid[$y][$x] -> $v {
                @known[$v] = [$y,$x];
            }
            if @grid[$y][$x].defined {
                @neigh[$y][$x] = neighbors($y,$x);
                @degree[$y][$x] = +@neigh[$y][$x];
            }
        }
    }
    print "\e[0H\e[0J";

    my $tries = 0;

    try_fill 1, @known[1];

    sub try_fill($v, $coord [$y,$x] --> Bool) {
        return True if $v > $max;
        $tries++;

        my $old = @grid[$y][$x];

        return False if +$old and $old != $v;
        return False if @known[$v] and @known[$v] !eqv $coord;

        @grid[$y][$x] = $v;               # conjecture grid value

        print "\e[0H";                    # show conjectured board
        for @grid -> $r {
            say do for @$r {
                when Rat { ' ' x $width }
                when 0   { '_' x $width }
                default  { .fmt("%{$width}d") }
            }
        }


        my @neighbors = @neigh[$y][$x][];

        my @degrees;
        for @neighbors -> \n [$yy,$xx] {
            my $d = --@degree[$yy][$xx];  # conjecture new degrees
            push @degrees[$d], n;         # and categorize by degree
        }

        for @degrees.grep(*.defined) -> @ties {
            for @ties.reverse {           # reverse works better for this hidato anyway
                return True if try_fill $v + 1, $_;
            }
        }

        for @neighbors -> [$yy,$xx] {
            ++@degree[$yy][$xx];          # undo degree conjectures
        }

        @grid[$y][$x] = $old;             # undo grid value conjecture
        return False;
    }
     
    say "$tries tries";
}

```

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
```