Solve a Hopido puzzle

From Rosetta Code
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.


Related tasks



11l

Translation of: Python
V neighbours = [[2, 2], [-2, 2], [2, -2], [-2, -2], [3, 0], [0, 3], [-3, 0], [0, -3]]
V cnt = 0
V pWid = 0
V pHei = 0

F is_valid(a, b)
   R -1 < a & a < :pWid & -1 < b & b < :pHei

F iterate(&pa, x, y, v)
   I v > :cnt
      R 1

   L(i) 0 .< :neighbours.len
      V a = x + :neighbours[i][0]
      V b = y + :neighbours[i][1]
      I is_valid(a, b) & pa[a][b] == 0
         pa[a][b] = v
         V r = iterate(&pa, a, b, v + 1)
         I r == 1
            R r
         pa[a][b] = 0
   R 0

F solve(pz, w, h)
   V pa = [[-1] * h] * w
   V f = 0
   :pWid = w
   :pHei = h
   L(j) 0 .< h
      L(i) 0 .< w
         I pz[f] == ‘1’
            pa[i][j] = 0
            :cnt++
         f++

   L(y) 0 .< h
      L(x) 0 .< w
         I pa[x][y] == 0
            pa[x][y] = 1
            I 1 == iterate(&pa, x, y, 2)
               R (1, pa)
            pa[x][y] = 0
   R (0, pa)

V r = solve(‘011011011111111111111011111000111000001000’, 7, 6)
I r[0] == 1
   L(j) 6
      L(i) 7
         I r[1][i][j] == -1
            print(‘   ’, end' ‘’)
         E
            print(‘ #02’.format(r[1][i][j]), end' ‘’)
      print()
E
   print(‘No solution!’, end' ‘’)
Output:
    01 25    17 03
 27 13 10 07 14 11 08
 24 21 18 02 22 19 16
    06 26 12 09 04
       23 20 15
          05

AutoHotkey

SolveHopido(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){
	if (R&&C)							; if neighbors (not first iteration)
	{
		Grid[R, C] := ">" num 					; place num in current neighbor and mark it visited ">"
		row:=R, col:=C						; move to current neighbor
	}

	num++								; increment num
	if (num=max)							; if reached end
		return map(Grid)					; return solution
 
	if locked[num]							; if current num is a locked value
	{
		row := StrSplit((StrSplit(locked[num], ",").1) , ":").1	; find row of num
		col := StrSplit((StrSplit(locked[num], ",").1) , ":").2	; find col of num
		if SolveHopido(Grid, Locked, Max, row, col, num)	; solve for current location and value
			return map(Grid)				; if solved, return solution
	}
	else
	{
		for each, value in StrSplit(Neighbor(row,col), ",")
		{
			R := StrSplit(value, ":").1
			C := StrSplit(value, ":").2
 
			if (Grid[R,C] = "")				; a hole or out of bounds
			|| InStr(Grid[R, C], ">")			; visited
			|| Locked[num+1] && !(Locked[num+1]~= "\b" R ":" C "\b") ; not neighbor of locked[num+1]
			|| Locked[num-1] && !(Locked[num-1]~= "\b" R ":" C "\b") ; not neighbor of locked[num-1]
			|| Locked[num]					; locked value
			|| Locked[Grid[R, C]]				; locked cell
				continue
 
			if SolveHopido(Grid, Locked, Max, row, col, num, R, C)	; solve for current location, neighbor and value
				return map(Grid)			; if solved, return solution
		}
	}
	num--								; step back
	for i, line in Grid
		for j, element in line
			if InStr(element, ">") && (StrReplace(element, ">") >= num)
				Grid[i, j] := 0
}
;--------------------------------
;--------------------------------
;--------------------------------
Neighbor(row,col){
	return Trim( ""
	. ","  row ":" col-3
	. ","  row ":" col+3
	. ","  row-3 ":" col
	. ","  row+3 ":" col
	
	. ","  row+2 ":" col+2
	. ","  row+2 ":" col-2
	. ","  row-2 ":" col+2
	. ","  row-2 ":" col-2
	, ",")
}
;--------------------------------
map(Grid){
	for i, row in Grid
	{
		for j, element in row
			line .= (A_Index > 1 ? "`t" : "") element
		map .= (map<>""?"`n":"") line
		line := ""
	}
	return StrReplace(map, ">")
}
Examples:
;--------------------------------
Grid := [["",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 ,"","",""]]
;--------------------------------
; find locked cells, find max value 
Locked := []
max := 1
for i, line in Grid
	for j, element in line
		if (element >= 0)
			max++ 	, list .= i ":" j "`n"
	
random, rnd, 1, %max%
loop, parse, list, `n, `r
	if (A_Index = rnd)
	{
		row := StrSplit(A_LoopField, ":").1
		col := StrSplit(A_LoopField, ":").2
		Grid[row,col] := 1
		Locked[1] := row ":" col "," Neighbor(row, col)
		break
	}
;--------------------------------
MsgBox, 262144, ,% SolveHopido(Grid, Locked, Max, row, col)
return
Outputs:
	17	24		16	25	
22	8	11	21	7	10	20
13	2	5	14	1	4	15
	18	23	9	19	26	
		12	3	6		
			27

C#

The same solver can solve Hidato, Holy Knight's Tour, Hopido and Numbrix puzzles.
The input can be an array of strings if each cell is one character. The length of the first row must be the number of columns in the puzzle.
Any non-numeric value indicates a no-go.
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.

using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static System.Linq.Enumerable;

public class Solver
{
    private static readonly (int dx, int dy)[]
        //other puzzle types elided
        hopidoMoves = {(-3,0),(0,-3),(0,3),(3,0),(-2,-2),(-2,2),(2,-2),(2,2)},

    private (int dx, int dy)[] moves;
        
    public static void Main()
    {
        Print(new Solver(hopidoMoves).Solve(false,
            ".00.00.",
            "0000000",
            "0000000",
            ".00000.",
            "..000..",
            "...0..."
        ));
    }

    public Solver(params (int dx, int dy)[] moves) => this.moves = moves;

    public int[,] Solve(bool circular, params string[] puzzle)
    {
        var (board, given, count) = Parse(puzzle);
        return Solve(board, given, count, circular);
    }

    public int[,] Solve(bool circular, int[,] puzzle)
    {
        var (board, given, count) = Parse(puzzle);
        return Solve(board, given, count, circular);
    }

    private int[,] Solve(int[,] board, BitArray given, int count, bool circular)
    {
        var (height, width) = (board.GetLength(0), board.GetLength(1));
        bool solved = false;
        for (int x = 0; x < height && !solved; x++) {
            solved = Range(0, width).Any(y => Solve(board, given, circular, (height, width), (x, y), count, (x, y), 1));
            if (solved) return board;
        }
        return null;
    }

    private bool Solve(int[,] board, BitArray given, bool circular,
        (int h, int w) size, (int x, int y) start, int last, (int x, int y) current, int n)
    {
        var (x, y) = current;
        if (x < 0 || x >= size.h || y < 0 || y >= size.w) return false;
        if (board[x, y] < 0) return false;
        if (given[n - 1]) {
            if (board[x, y] != n) return false;
        } else if (board[x, y] > 0) return false;
        board[x, y] = n;
        if (n == last) {
            if (!circular || AreNeighbors(start, current)) return true;
        }
        for (int i = 0; i < moves.Length; i++) {
            var move = moves[i];
            if (Solve(board, given, circular, size, start, last, (x + move.dx, y + move.dy), n + 1)) return true;
        }
        if (!given[n - 1]) board[x, y] = 0;
        return false;

        bool AreNeighbors((int x, int y) p1, (int x, int y) p2) => moves.Any(m => (p2.x + m.dx, p2.y + m.dy).Equals(p1));
    }

    private static (int[,] board, BitArray given, int count) Parse(string[] input)
    {
        (int height, int width) = (input.Length, input[0].Length);
        int[,] board = new int[height, width];
        int count = 0;
        for (int x = 0; x < height; x++) {
            string line = input[x];
            for (int y = 0; y < width; y++) {
                board[x, y] = y < line.Length && char.IsDigit(line[y]) ? line[y] - '0' : -1;
                if (board[x, y] >= 0) count++;
            }
        }
        BitArray given = Scan(board, count, height, width);
        return (board, given, count);
    }

    private static (int[,] board, BitArray given, int count) Parse(int[,] input)
    {
        (int height, int width) = (input.GetLength(0), input.GetLength(1));
        int[,] board = new int[height, width];
        int count = 0;
        for (int x = 0; x < height; x++)
            for (int y = 0; y < width; y++)
                if ((board[x, y] = input[x, y]) >= 0) count++;
        BitArray given = Scan(board, count, height, width);
        return (board, given, count);
    }

    private static BitArray Scan(int[,] board, int count, int height, int width)
    {
        var given = new BitArray(count + 1);
        for (int x = 0; x < height; x++)
            for (int y = 0; y < width; y++)
                if (board[x, y] > 0) given[board[x, y] - 1] = true;
        return given;
    }

    private static void Print(int[,] board)
    {
        if (board == null) {
            WriteLine("No solution");
        } else {
            int w = board.Cast<int>().Where(i => i > 0).Max(i => (int?)Ceiling(Log10(i+1))) ?? 1;
            string e = new string('-', w);
            foreach (int x in Range(0, board.GetLength(0)))
                WriteLine(string.Join(" ", Range(0, board.GetLength(1))
                    .Select(y => board[x, y] < 0 ? e : board[x, y].ToString().PadLeft(w, ' '))));
        }
        WriteLine();
    }

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

C++

#include <vector>
#include <sstream>
#include <iostream>
#include <iterator>
#include <stdlib.h>
#include <string.h>

using namespace std;

struct node
{
    int val;
    unsigned char neighbors;
};

class nSolver
{
public:
    nSolver()
    {
	dx[0] = -2; dy[0] = -2; dx[1] = -2; dy[1] =  2;
	dx[2] =  2; dy[2] = -2; dx[3] =  2; dy[3] =  2;
	dx[4] = -3; dy[4] =  0; dx[5] =  3; dy[5] =  0; 
	dx[6] =  0; dy[6] = -3; dx[7] =  0; dy[7] =  3;
    }

    void solve( vector<string>& puzz, int max_wid )
    {
	if( puzz.size() < 1 ) return;
	wid = max_wid; hei = static_cast<int>( puzz.size() ) / wid;
	int len = wid * hei, c = 0; max = len;
	arr = new node[len]; memset( arr, 0, len * sizeof( node ) );

	for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
	{
	    if( ( *i ) == "*" ) { max--; arr[c++].val = -1; continue; }
	    arr[c].val = atoi( ( *i ).c_str() );
	    c++;
	}

	solveIt(); c = 0;
	for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
	{
	    if( ( *i ) == "." )
	    {
		ostringstream o; o << arr[c].val;
		( *i ) = o.str();
	    }
	    c++;
	}
	delete [] arr;
    }

private:
    bool search( int x, int y, int w )
    {
	if( w > max ) return true;

	node* n = &arr[x + y * wid];
	n->neighbors = getNeighbors( x, y );

	for( int d = 0; d < 8; d++ )
	{
	    if( n->neighbors & ( 1 << d ) )
	    {
		int a = x + dx[d], b = y + dy[d];
		if( arr[a + b * wid].val == 0 )
		{
		    arr[a + b * wid].val = w;
		    if( search( a, b, w + 1 ) ) return true;
		    arr[a + b * wid].val = 0;
		}
	    }
	}
	return false;
    }

    unsigned char getNeighbors( int x, int y )
    {
	unsigned char c = 0; int a, b;
	for( int xx = 0; xx < 8; xx++ )
	{
	    a = x + dx[xx], b = y + dy[xx];
	    if( a < 0 || b < 0 || a >= wid || b >= hei ) continue;
	    if( arr[a + b * wid].val > -1 ) c |= ( 1 << xx );
	}
	return c;
    }

    void solveIt()
    {
	int x, y, z; findStart( x, y, z );
	if( z == 99999 ) { cout << "\nCan't find start point!\n"; return; }
	search( x, y, z + 1 );
    }

    void findStart( int& x, int& y, int& z )
    {
	for( int b = 0; b < hei; b++ )
	    for( int a = 0; a < wid; a++ )
		if( arr[a + wid * b].val == 0 ) 
		{ 
		    x = a; y = b; z = 1;
		    arr[a + wid * b].val = z;
		    return;
		}
    }

    int wid, hei, max, dx[8], dy[8];
    node* arr;
};

int main( int argc, char* argv[] )
{
    int wid; string p;
    p = "* . . * . . * . . . . . . . . . . . . . . * . . . . . * * * . . . * * * * * . * * *"; wid = 7;
    istringstream iss( p ); vector<string> puzz;
    copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) );
    nSolver s; s.solve( puzz, wid );
    int c = 0;
    for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
    {
	if( ( *i ) != "*" && ( *i ) != "." )
	{
	    if( atoi( ( *i ).c_str() ) < 10 ) cout << "0";
	    cout << ( *i ) << " ";
	}
	else cout << "   ";
	if( ++c >= wid ) { cout << endl; c = 0; }
    }
    cout << endl << endl;
    return system( "pause" );
}
Output:
   01 04    12 03
27 16 19 22 15 18 21
05 08 11 02 07 10 13
   23 26 17 20 25
      06 09 14
         24

D

Translation of: C++

From the refactored C++ version with more precise typing. This tries all possible start positions. The HopidoPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time.

import std.stdio, std.conv, std.string, std.range, std.algorithm, std.typecons;


struct HopidoPuzzle {
    private alias InputCellBaseType = char;
    private enum InputCell : InputCellBaseType { available = '#', unavailable = '.' }
    private alias Cell = uint;
    private enum : Cell { unknownCell = 0, unavailableCell = Cell.max } // Special Cell values.

    // Neighbors, [shift row, shift column].
    private static immutable int[2][8] shifts = [[-2, -2], [2, -2], [-2, 2], [2, 2],
                                                 [ 0, -3], [0,  3], [-3, 0], [3, 0]];

    private immutable size_t gridWidth, gridHeight;
    private immutable Cell nAvailableCells;
    private /*immutable*/ const InputCell[] flatPuzzle;
    private Cell[] grid; // Flattened mutable game grid.

    @disable this();


    this(in string[] rawPuzzle) pure @safe
    in {
        assert(!rawPuzzle.empty);
        assert(!rawPuzzle[0].empty);
        assert(rawPuzzle.all!(row => row.length == rawPuzzle[0].length)); // Is rectangular.

        // Has at least one start point.
        assert(rawPuzzle.join.representation.canFind(InputCell.available));
    } body {
        //immutable puzzle = rawPuzzle.to!(InputCell[][]);
        immutable puzzle = rawPuzzle.map!representation.array.to!(InputCell[][]);

        gridWidth = puzzle[0].length;
        gridHeight = puzzle.length;
        flatPuzzle = puzzle.join;
        nAvailableCells = flatPuzzle.representation.count!(ic => ic == InputCell.available);

        grid = flatPuzzle
               .representation
               .map!(ic => ic == InputCell.available ? unknownCell : unavailableCell)
               .array;
    }


    Nullable!(string[][]) solve() pure /*nothrow*/ @safe
    out(result) {
        if (!result.isNull)
            assert(!grid.canFind(unknownCell));
    } body {
        // Try all possible start positions.
        foreach (immutable r; 0 ..  gridHeight) {
            foreach (immutable c; 0 .. gridWidth) {
                immutable pos = r * gridWidth + c;
                if (grid[pos] == unknownCell) {
                    immutable Cell startCell = 1; // To lay the first cell value.
                    grid[pos] = startCell;        // Try.
                    if (search(r, c, startCell + 1)) {
                        auto result = zip(flatPuzzle, grid)
                                      //.map!({p, c} => ...
                                      .map!(pc => (pc[0] == InputCell.available) ?
                                                  pc[1].text :
                                                  InputCellBaseType(pc[0]).text)
                                      .array
                                      .chunks(gridWidth)
                                      .array;
                        return typeof(return)(result);
                    }
                    grid[pos] = unknownCell; // Restore.
                }
            }
        }

        return typeof(return)();
    }


    private bool search(in size_t r, in size_t c, in Cell cell) pure nothrow @safe @nogc {
        if (cell > nAvailableCells)
            return true; // One solution found.

        foreach (immutable sh; shifts) {
            immutable r2 = r + sh[0],
                      c2 = c + sh[1],
                      pos = r2 * gridWidth + c2;
            // No need to test for >= 0 because uint wraps around.
            if (c2 < gridWidth && r2 < gridHeight && grid[pos] == unknownCell) {
                grid[pos] = cell;        // Try.
                if (search(r2, c2, cell + 1))
                    return true;
                grid[pos] = unknownCell; // Restore.
            }
        }

        return false;
    }
}


void main() @safe {
    // enum HopidoPuzzle to catch malformed puzzles at compile-time.
    enum puzzle = ".##.##.
                   #######
                   #######
                   .#####.
                   ..###..
                   ...#...".split.HopidoPuzzle;

    immutable solution = puzzle.solve; // Solved at run-time.
    if (solution.isNull)
        writeln("No solution found.");
    else
        writefln("One solution:\n%(%-(%2s %)\n%)", solution);
}
Output:
One solution:
 .  1  4  . 12  3  .
27 16 19 22 15 18 21
 5  8 11  2  7 10 13
 . 23 26 17 20 25  .
 .  .  6  9 14  .  .
 .  .  . 24  .  .  .

Elixir

Translation of: 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}]
 
board = """
. 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 . . .
"""
HLPsolver.solve(board, adjacent)
Output:
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:
    5 25    17  3
27 13 10  7 14 11  8
24 21 18  4 22 19 16
    6 26 12  9  2
      23 20 15
          1

Go

Translation of: Java
package main

import (
    "fmt"
    "sort"
)

var board = []string{
    ".00.00.",
    "0000000",
    "0000000",
    ".00000.",
    "..000..",
    "...0...",
}

var moves = [][2]int{
    {-3, 0}, {0, 3}, {3, 0}, {0, -3},
    {2, 2}, {2, -2}, {-2, 2}, {-2, -2},
}

var grid [][]int

var totalToFill = 0

func solve(r, c, count int) bool {
    if count > totalToFill {
        return true
    }
    nbrs := neighbors(r, c)
    if len(nbrs) == 0 && count != totalToFill {
        return false
    }
    sort.Slice(nbrs, func(i, j int) bool {
        return nbrs[i][2] < nbrs[j][2]
    })

    for _, nb := range nbrs {
        r = nb[0]
        c = nb[1]
        grid[r][c] = count
        if solve(r, c, count+1) {
            return true
        }
        grid[r][c] = 0
    }
    return false
}

func neighbors(r, c int) (nbrs [][3]int) {
    for _, m := range moves {
        x := m[0]
        y := m[1]
        if grid[r+y][c+x] == 0 {
            num := countNeighbors(r+y, c+x) - 1
            nbrs = append(nbrs, [3]int{r + y, c + x, num})
        }
    }
    return
}

func countNeighbors(r, c int) int {
    num := 0
    for _, m := range moves {
        if grid[r+m[1]][c+m[0]] == 0 {
            num++
        }
    }
    return num
}

func printResult() {
    for _, row := range grid {
        for _, i := range row {
            if i == -1 {
                fmt.Print("   ")
            } else {
                fmt.Printf("%2d ", i)
            }
        }
        fmt.Println()
    }
}

func main() {
    nRows := len(board) + 6
    nCols := len(board[0]) + 6
    grid = make([][]int, nRows)
    for r := 0; r < nRows; r++ {
        grid[r] = make([]int, nCols)
        for c := 0; c < nCols; c++ {
            grid[r][c] = -1
        }
        for c := 3; c < nCols-3; c++ {
            if r >= 3 && r < nRows-3 {
                if board[r-3][c-3] == '0' {
                    grid[r][c] = 0
                    totalToFill++
                }
            }
        }
    }
    pos, r, c := -1, 0, 0
    for {
        for {
            pos++
            r = pos / nCols
            c = pos % nCols
            if grid[r][c] != -1 {
                break
            }
        }
        grid[r][c] = 1
        if solve(r, c, 2) {
            break
        }
        grid[r][c] = 0
        if pos >= nRows*nCols {
            break
        }
    }
    printResult()
}
Output:
             1 22    14 21             
         18 10  7 17 11  8 16          
          5 24 27  4 23 26 13          
             2 19  9 15 20             
                6 25 12                
                   3            

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

Java

Works with: Java version 8
import java.util.*;

public class Hopido {

    final static String[] board = {
        ".00.00.",
        "0000000",
        "0000000",
        ".00000.",
        "..000..",
        "...0..."};

    final static int[][] moves = {{-3, 0}, {0, 3}, {3, 0}, {0, -3},
    {2, 2}, {2, -2}, {-2, 2}, {-2, -2}};
    static int[][] grid;
    static int totalToFill;

    public static void main(String[] args) {
        int nRows = board.length + 6;
        int nCols = board[0].length() + 6;

        grid = new int[nRows][nCols];

        for (int r = 0; r < nRows; r++) {
            Arrays.fill(grid[r], -1);
            for (int c = 3; c < nCols - 3; c++)
                if (r >= 3 && r < nRows - 3) {
                    if (board[r - 3].charAt(c - 3) == '0') {
                        grid[r][c] = 0;
                        totalToFill++;
                    }
                }
        }

        int pos = -1, r, c;
        do {
            do {
                pos++;
                r = pos / nCols;
                c = pos % nCols;
            } while (grid[r][c] == -1);

            grid[r][c] = 1;
            if (solve(r, c, 2))
                break;
            grid[r][c] = 0;

        } while (pos < nRows * nCols);

        printResult();
    }

    static boolean solve(int r, int c, int count) {
        if (count > totalToFill)
            return true;

        List<int[]> nbrs = neighbors(r, c);

        if (nbrs.isEmpty() && count != totalToFill)
            return false;

        Collections.sort(nbrs, (a, b) -> a[2] - b[2]);

        for (int[] nb : nbrs) {
            r = nb[0];
            c = nb[1];
            grid[r][c] = count;
            if (solve(r, c, count + 1))
                return true;
            grid[r][c] = 0;
        }

        return false;
    }

    static List<int[]> neighbors(int r, int c) {
        List<int[]> nbrs = new ArrayList<>();

        for (int[] m : moves) {
            int x = m[0];
            int y = m[1];
            if (grid[r + y][c + x] == 0) {
                int num = countNeighbors(r + y, c + x) - 1;
                nbrs.add(new int[]{r + y, c + x, num});
            }
        }
        return nbrs;
    }

    static int countNeighbors(int r, int c) {
        int num = 0;
        for (int[] m : moves)
            if (grid[r + m[1]][c + m[0]] == 0)
                num++;
        return num;
    }

    static void printResult() {
        for (int[] row : grid) {
            for (int i : row) {
                if (i == -1)
                    System.out.printf("%2s ", ' ');
                else
                    System.out.printf("%2d ", i);
            }
            System.out.println();
        }
    }
}
             1 22    14 21             
         18 10  7 17 11  8 16          
          5 24 27  4 23 26 13          
             2 19  9 15 20             
                6 25 12                
                   3                   

Julia

Uses the Hidato puzzle solver module, which has its source code listed here in the Hadato task.

using .Hidato       # Note that the . here means to look locally for the module rather than in the libraries

const hopid = """
 . 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 . . . """

const hopidomoves = [[-3, 0], [0, -3], [-2, -2], [-2, 2], [2, -2], [0, 3], [3, 0], [2, 2]]

board, maxmoves, fixed, starts = hidatoconfigure(hopid)
printboard(board, " 0", "  ")
hidatosolve(board, maxmoves, hopidomoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
Output:

  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
    4 15     5 16
 1 22 25  2 21 24 27
14 11  8 17 12  9  6
    3 20 23 26 19
      13 10  7
         18

Kotlin

Translation of: Java
// version 1.2.0

val board = listOf(
    ".00.00.",
    "0000000",
    "0000000",
    ".00000.",
    "..000..",
    "...0..."
)

val moves = listOf(
    -3 to 0, 0 to  3,  3 to 0,  0 to -3,
     2 to 2, 2 to -2, -2 to 2, -2 to -2
)

lateinit var grid: List<IntArray>
var totalToFill = 0

fun solve(r: Int, c: Int, count: Int): Boolean {
    if (count > totalToFill) return true
    val nbrs = neighbors(r, c)
    if (nbrs.isEmpty() && count != totalToFill) return false
    nbrs.sortBy { it[2] }
    for (nb in nbrs) {
        val rr = nb[0]
        val cc = nb[1]
        grid[rr][cc] = count
        if (solve(rr, cc, count + 1)) return true
        grid[rr][cc] = 0
    }
    return false
}

fun neighbors(r: Int, c: Int): MutableList<IntArray> {
    val nbrs = mutableListOf<IntArray>()
    for (m in moves) {
        val x = m.first
        val y = m.second
        if (grid[r + y][c + x] == 0) {
            val num = countNeighbors(r + y, c + x) - 1
            nbrs.add(intArrayOf(r + y, c + x, num))
        }
    }
    return nbrs
}

fun countNeighbors(r: Int, c: Int): Int {
    var num = 0
    for (m in moves)
        if (grid[r + m.second][c + m.first] == 0) num++
    return num
}

fun printResult() {
    for (row in grid) {
        for (i in row) {
            print(if (i == -1) "   " else "%2d ".format(i))
        }
        println()
    }
}

fun main(args: Array<String>) {
    val nRows = board.size + 6
    val nCols = board[0].length + 6
    grid = List(nRows) { IntArray(nCols) { -1} }
    for (r in 0 until nRows) {
        for (c in 3 until nCols - 3) {
            if (r in 3 until nRows - 3) {
                if (board[r - 3][c - 3] == '0') {
                    grid[r][c] = 0
                    totalToFill++
                }
            }
        }
    }
    var pos = -1
    var rr: Int
    var cc: Int
    do {
        do {
            pos++
            rr = pos / nCols
            cc = pos % nCols
        }
        while (grid[rr][cc] == -1)

        grid[rr][cc] = 1
        if (solve(rr, cc, 2)) break
        grid[rr][cc] = 0
    }
    while (pos < nRows * nCols)

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

Mathematica/Wolfram Language

Uses shortest tours on graphs to solve it:

puzz = ".00.00.\n0000000\n0000000\n.00000.\n..000..\n...0...";
puzz //= StringSplit[#, "\n"] & /* Map[Characters];
puzz //= Transpose /* Map[Reverse];
pos = Position[puzz, "0", {2}];
moves = Select[Select[Tuples[pos, 2], MatchQ[EuclideanDistance @@ #, 2 Sqrt[2] | 3] &], OrderedQ];
g = Graph[UndirectedEdge @@@ moves];
ord = Most[FindShortestTour[g][[2]]];
Graphics[MapThread[Text, {Range[Length[ord]], VertexList[g][[ord]]}]]
Output:

Shows a graphical solution.

Nim

Translation of: Go
import algorithm, sequtils, strformat

const Moves = [(-3, 0), (0,  3), ( 3, 0), ( 0, -3),
               ( 2, 2), (2, -2), (-2, 2), (-2, -2)]

type

  Hopido = object
    grid: seq[seq[int]]
    nRows, nCols: int
    totalToFill : Natural

  Neighbor = (int, int, int)


proc initHopido(board: openArray[string]): Hopido =
  result.nRows = board.len + 6
  result.nCols = board[0].len + 6
  result.grid = newSeqWith(result.nRows, repeat(-1, result.nCols))

  for row in 0..board.high:
    for col in 0..board[0].high:
      if board[row][col] == '0':
        result.grid[row + 3][col + 3] = 0
        inc result.totalToFill


proc countNeighbors(hopido: Hopido; row, col: Natural): int =
  for (x, y) in Moves:
    if hopido.grid[row + y][col + x] == 0:
      inc result


proc neighbors(hopido: Hopido; row, col: Natural): seq[Neighbor] =
  for (x, y) in Moves:
    if hopido.grid[row + y][col + x] == 0:
      let num = hopido.countNeighbors(row + y, col + x) - 1
      result.add (row + y, col + x, num)


proc solve(hopido: var Hopido; row, col, count: Natural): bool =

  if count > hopido.totalTofill: return true

  var nbrs = hopido.neighbors(row, col)
  if nbrs.len == 0 and count != hopido.totalToFill:
    return false

  nbrs.sort(proc(a, b: Neighbor): int = cmp(a[2], b[2]))

  for (row, col, _) in nbrs:
    hopido.grid[row][col] = count
    if hopido.solve(row, col, count + 1):
      return true
    hopido.grid[row][col] = 0


proc findSolution(hopido: var Hopido) =
  var pos = -1
  var row, col: Natural

  while true:
    while true:
      inc pos
      row = pos div hopido.nCols
      col = pos mod hopido.nCols
      if hopido.grid[row][col] != -1:
        break
    hopido.grid[row][col] = 1
    if hopido.solve(row, col, 2):
      break
    hopido.grid[row][col] = 0
    if pos >= hopido.nRows * hopido.nCols:
      break


proc print(hopido: Hopido) =
  for row in hopido.grid:
    for val in row:
      stdout.write if val == -1: "   " else: &"{val:2} "
    echo()


when isMainModule:

  const Board = [".00.00.",
                 "0000000",
                 "0000000",
                 ".00000.",
                 "..000..",
                 "...0..."]

  var hopido = initHopido(Board)
  hopido.findSolution()
  hopido.print()
Output:
                                       
                                       
                                       
             1 22    14 21             
         18 10  7 17 11  8 16          
          5 24 27  4 23 26 13          
             2 19  9 15 20             
                6 25 12                
                   3                   
                                       
                                 

Perl

#!/usr/bin/perl

use strict;             # http://www.rosettacode.org/wiki/Solve_a_Hopido_puzzle
use warnings;

$_ = do { local $/; <DATA> };
s/./$&$&/g;             # double chars
my $w = /\n/ && $-[0];
my $wd = 3 * $w + 1;    # vertical gap
my $wr = 2 * $w + 8;    # down right gap
my $wl = 2 * $w - 8;    # down left gap
place($_, '00');
die "No solution\n";

sub place
  {
  (local $_, my $last) = @_;
  (my $new = $last)++;
  /$last.{10}(?=00)/g   and place( s/\G00/$new/r, $new ); # right
  /(?=00.{10}$last)/g   and place( s/\G00/$new/r, $new ); # left
  /$last.{$wd}(?=00)/gs and place( s/\G00/$new/r, $new ); # down
  /(?=00.{$wd}$last)/gs and place( s/\G00/$new/r, $new ); # up
  /$last.{$wr}(?=00)/gs and place( s/\G00/$new/r, $new ); # down right
  /(?=00.{$wr}$last)/gs and place( s/\G00/$new/r, $new ); # up left
  /$last.{$wl}(?=00)/gs and place( s/\G00/$new/r, $new ); # down left
  /(?=00.{$wl}$last)/gs and place( s/\G00/$new/r, $new ); # up right
  /00/ and return;
  print "Solution\n\n", s/  / /gr =~ s/0\B/ /gr;
  exit;
  }

__DATA__
. 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:
Solution

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

Phix

Simple brute force approach.

with javascript_semantics
sequence board
 
integer limit, tries
 
constant ROW = 1, COL = 2
constant moves = {{-2,-2},{-2,2},{2,-2},{2,2},{-3,0},{3,0},{0,-3},{0,3}}
 
function solve(integer row, integer col, integer n)
integer nrow, ncol
    tries+= 1
    if n>limit then return 1 end if
    for move=1 to length(moves) do
        nrow = row+moves[move][ROW]
        ncol = col+moves[move][COL]*3
        if nrow>=1 and nrow<=length(board) 
        and ncol>=1 and ncol<=length(board[row])
        and board[nrow][ncol]=' ' then
            board[nrow][ncol-1..ncol] = sprintf("%2d",n)
            if solve(nrow,ncol,n+1) then return 1 end if
            board[nrow][ncol-1..ncol] = "  "
        end if
    end for
    return 0
end function
 
procedure Hopido(sequence s, integer w, integer h)
    integer rx, ry
    atom t0 = time()
    board = split(s,'\n')
    limit = 0
    for x=1 to h do
        for y=3 to w*3 by 3 do
            if board[x][y]='0' then
                board[x][y] = ' '
                limit += 1
            end if
        end for
    end for
    while 1 do
        rx = rand(h)
        ry = rand(w)*3
        if board[rx][ry]=' ' then exit end if
    end while
    board[rx][ry] = '1'
    tries = 0
    if solve(rx,ry,2) then
        puts(1,join(board,"\n"))
        printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})
    else
        puts(1,"no solutions found\n")
    end if
end procedure
 
constant board1 = """
  .  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  .  .  ."""
Hopido(board1,7,6)

The best and worse cases observed were:

  . 13 22  . 14 11  .
  6  3 25  7  4  1 27
 23 20 17 12 21 18 15
  .  8  5  2 26 10  .
  .  . 24 19 16  .  .
  .  .  .  9  .  .  .
solution found in 46 tries (0.00s)
  . 20 11  . 19 22  .
  2  5  8  1  4  7 27
 10 13 16 21 12 15 18
  . 25  3  6 26 23  .
  .  .  9 14 17  .  .
  .  .  . 24  .  .  .
solution found in 67702 tries (0.09s)

Picat

import sat. 
main =>	
    Grid = {{0,1,1,0,1,1,0},
	    {1,1,1,1,1,1,1},
	    {1,1,1,1,1,1,1},
	    {0,1,1,1,1,1,0},
	    {0,0,1,1,1,0,0},
	    {0,0,0,1,0,0,0}},
    NR = len(Grid), NC = len(Grid[1]),
    Es = [{(R,C), (R1,C1), _} : R in 1..NR, C in 1..NC, R1 in 1..NR, C1 in 1..NC, % Edges 
          ((R1 = R, abs(C1 - C) = 3); (C1 = C, abs(R1 - R) = 3); % horizontal hop
           (abs(R1 - R) = 2, abs(C1 - C) = 2)),                  % diagonal hop 
          Grid[R,C] = 1, Grid[R1,C1] = 1], 
    hcp_grid(Grid, Es), % find a Hamiltion cylce on the vertices in Grid through the edges in Es
    solve(vars(Es)), 
    % Write the solution as a matrix, starting at the base tile 6|4:
    M = {{0: _ in 1..NC} : _ in 1..NR}, 
    R1 = 6, C1 = 4, I = 0,
    do
        I := I + 1, M[R1,C1] := I, Stop = 0,
        foreach({(R1,C1), (R2,C2), 1} in Es,  break(Stop == 1)) 
            R1 := R2, C1 := C2, Stop := 1 
        end
    while ((R1,C1) != (6,4)),
    foreach(R in 1..NR, C in 1..NC)
        if M[R,C] = 0 then print("   ") else printf("%2d ", M[R,C]) end,
        if C = NC then nl end
    end.

Output:

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

Prolog

This is a pure prolog implementation (no cuts,etc..), the only libary predicate used is select/3 witch is pure.

hopido(Grid,[C|Solved],Xs,Ys) :-	
	select(C,Grid,RGrid),
	solve(RGrid,C,Solved,Xs,Ys).
	
solve([],_,[],_,_).	
solve(Grid,p(X,Y),[p(X1,Y1)|R],Xs,Ys) :- 
	valid_move(X,Y,Xs,Ys,X1,Y1),
	select(p(X1,Y1),Grid,NextGrid),
	solve(NextGrid,p(X1,Y1),R,Xs,Ys).	
	
valid_move(X,Y,Xs,_,X1,Y)   :- j3(X,X1,Xs).			% right	(3,0)
valid_move(X,Y,Xs,_,X1,Y)   :- j3(X1,X,Xs).			% left (-3,0)
valid_move(X,Y,_,Ys,X,Y1)   :- j3(Y,Y1,Ys).			% up (0,3).
valid_move(X,Y,_,Ys,X,Y1)   :- j3(Y1,Y,Ys).  			% down (0,-3).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X,X1,Xs), j2(Y,Y1,Ys).  	% up-right (2,2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X1,X,Xs), j2(Y,Y1,Ys).  	% up-left (-2,2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X1,X,Xs), j2(Y1,Y,Ys).  	% down-left (-2,-2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X,X1,Xs), j2(Y1,Y,Ys).  	% down-right (2,-2).

j2(O,N,[O,_,N|_]).
j2(O,N,[_|T]) :- j2(O,N,T).

j3(O,N,[O,_,_,N|_]).
j3(O,N,[_|T]) :- j3(O,N,T).

To test send in a list of p/2 terms that represent points that can be hopped to (order is not important).

The grid coords can be anything so need to specify the valid coordinates as a list (in this case numbers between 0 and 6).

puzzle([	
           p(1,0),p(2,0)       ,p(4,0),p(5,0),
    p(0,1),p(1,1),p(2,1),p(3,1),p(4,1),p(5,1),p(6,1),	
    p(0,2),p(1,2),p(2,2),p(3,2),p(4,2),p(5,2),p(6,2),
           p(1,3),p(2,3),p(3,3),p(4,3),p(5,3),
                  p(2,4),p(3,4),p(4,4),
                         p(3,5)
]).
	
test :-
	puzzle(P),
	XYs = [0,1,2,3,4,5,6],
	hopido(P,S,XYs,XYs),
	maplist(writeln,S).
Output:
?- time(test).
p(1,0)
p(4,0)
p(4,3)
p(1,3)
p(3,5)
p(5,3)
p(5,0)
p(2,0)
p(4,2)
p(1,2)
p(3,4)
p(5,2)
p(2,2)
p(4,4)
p(6,2)
p(3,2)
p(0,2)
p(2,4)
p(2,1)
p(5,1)
p(3,3)
p(1,1)
p(4,1)
p(2,3)
p(0,1)
p(3,1)
p(6,1)
% 356,635 inferences, 0.062 CPU in 0.081 seconds (78% CPU, 5715268 Lips)
true

Python

from sys import stdout

neighbours = [[2, 2], [-2, 2], [2, -2], [-2, -2], [3, 0], [0, 3], [-3, 0], [0, -3]]
cnt = 0
pWid = 0
pHei = 0


def is_valid(a, b):
    return -1 < a < pWid and -1 < b < pHei


def iterate(pa, x, y, v):
    if v > cnt:
        return 1

    for i in range(len(neighbours)):
        a = x + neighbours[i][0]
        b = y + neighbours[i][1]
        if is_valid(a, b) and pa[a][b] == 0:
            pa[a][b] = v
            r = iterate(pa, a, b, v + 1)
            if r == 1:
                return r
            pa[a][b] = 0
    return 0


def solve(pz, w, h):
    global cnt, pWid, pHei

    pa = [[-1 for j in range(h)] for i in range(w)]
    f = 0
    pWid = w
    pHei = h
    for j in range(h):
        for i in range(w):
            if pz[f] == "1":
                pa[i][j] = 0
                cnt += 1
            f += 1

    for y in range(h):
        for x in range(w):
            if pa[x][y] == 0:
                pa[x][y] = 1
                if 1 == iterate(pa, x, y, 2):
                    return 1, pa
                pa[x][y] = 0

    return 0, pa

r = solve("011011011111111111111011111000111000001000", 7, 6)
if r[0] == 1:
    for j in range(6):
        for i in range(7):
            if r[1][i][j] == -1:
                stdout.write("   ")
            else:
                stdout.write(" {:0{}d}".format(r[1][i][j], 2))
        print()
else:
    stdout.write("No solution!")
Output:

   01 25    17 03   
27 13 10 07 14 11 08
24 21 18 02 22 19 16
   06 26 12 09 04   
      23 20 15      
         05     

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

Raku

(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:

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

REXX

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

No particular effort was made to reduce the elapsed time in solving the puzzle.

/*REXX program solves a Hopido puzzle,  it also displays the puzzle  and  the solution. */
call time 'Reset'                                /*reset the REXX elapsed timer to zero.*/
maxR=0;    maxC=0;    maxX=0;     minR=9e9;      minC=9e9;    minX=9e9;    cells=0;    @.=
parse arg xxx                                    /*get the cell definitions from the CL.*/
xxx=translate(xxx, , "/\;:_", ',')               /*also allow other characters 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              /*the START cell. */
                   if _\=='' then call err "cell at"  r  c  'is already occupied with:' _
                   @.r.c=x;   c=c+1;    cells=cells+1                 /*assign a mark.  */
                   if x==.              then iterate                  /*is a hole?  Skip*/
                   if \datatype(x,'W')  then call err 'illegal marker specified:' x
                   minX=min(minX,x);    maxX=max(maxX,x)              /*min and max  X. */
                   end   /*while marks¬='' */
               end       /*while xxx  ¬='' */
call show                                        /* [↓]  is 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'            /*   "      column   "   "    "    "   */
pMoves=words(Nr)                                 /*the number of possible moves.  */
                   do i=1  for pMoves;   Nr.i=word(Nr, i);   Nc.i=word(Nc,i);   end  /*i*/
if \next(2,!r,!c)  then call err  'No solution possible for this Hopido puzzle.'
say 'A solution for the Hopido exists.';      say;               call show
etime= format(time('Elapsed'), , 2)              /*obtain the elapsed time (in seconds).*/
if etime<.1  then say 'and took less than  1/10  of a second.'
             else say 'and took'       etime         "seconds."
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
err:  say;      say '***error*** (from Hopido): '  arg(1);          say;           exit 13
/*──────────────────────────────────────────────────────────────────────────────────────*/
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=#     /*let's try this move.  */
                               if #==cells        then leave    /*is this the last move?*/
                               if next(##,nr,nc)  then return 1
                               @.nr.nc=.                        /*undo the above move.  */
                               iterate                          /*go & try another move.*/
                               end
           if @.nr.nc==#  then do                               /*this a fill-in move ? */
                               if #==cells        then return 1 /*this is the last move.*/
                               if next(##,nr,nc)  then return 1 /*a fill-in move.       */
                               end
           end   /*t*/
return 0                                                        /*This ain't working.   */
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: 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=max(2,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.

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

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         

Wren

Translation of: Kotlin
Library: Wren-sort
Library: Wren-fmt
import "./sort" for Sort
import "./fmt" for Fmt

var board = [
    ".00.00.",
    "0000000",
    "0000000",
    ".00000.",
    "..000..",
    "...0..."
]

var moves = [
    [-3, 0], [0,  3], [ 3, 0], [ 0, -3],
    [ 2, 2], [2, -2], [-2, 2], [-2, -2]
]

var grid = []
var totalToFill = 0

var countNeighbors = Fn.new { |r, c|
    var num = 0
    for (m in moves) if (grid[r + m[1]][c + m[0]] == 0) num = num + 1
    return num
}

var neighbors = Fn.new { |r, c|
    var nbrs = []
    for (m in moves) {
        var x = m[0]
        var y = m[1]
        if (grid[r + y][c + x] == 0) {
            var num = countNeighbors.call(r + y, c + x) - 1
            nbrs.add([r + y, c + x, num])
        }
    }
    return nbrs
}

var solve // recursive
solve = Fn.new { |r, c, count|
    if (count > totalToFill) return true
    var nbrs = neighbors.call(r, c)
    if (nbrs.isEmpty && count != totalToFill) return false
    var cmp = Fn.new { |n1, n2| (n1[2] - n2[2]).sign }
    Sort.insertion(nbrs, cmp) // stable sort
    for (nb in nbrs) {
        var rr = nb[0]
        var cc = nb[1]
        grid[rr][cc] = count
        if (solve.call(rr, cc, count + 1)) return true
        grid[rr][cc] = 0
    }
    return false
}

var printResult = Fn.new {
    for (row in grid) {
        for (i in row) {
            if (i == -1) {
                System.write("   ")
            } else {
                Fmt.write("$2d ", i)
            }
        }
        System.print()
    }
}

var nRows = board.count + 6
var nCols = board[0].count + 6
grid = List.filled(nRows, null)
for (r in 0...nRows) {
    grid[r] = List.filled(nCols, -1)
    for (c in 3...nCols - 3) {
        if (r >= 3 && r < nRows - 3) {
            if (board[r - 3][c - 3] == "0") {
                grid[r][c] = 0
                totalToFill = totalToFill + 1
            }
        }
    }
}
var pos = -1
var r
var c
while (true) {
    while (true) {
        pos = pos + 1
        r = (pos / nCols).truncate
        c = pos % nCols
        if (grid[r][c] != -1) break
    }
    grid[r][c] = 1
    if (solve.call(r, c, 2)) break
    grid[r][c] = 0
    if (pos >= nRows * nCols) break
}
printResult.call()
Output:
                                      
             1 22    14 21             
         18 10  7 17 11  8 16          
          5 24 27  4 23 26 13          
             2 19  9 15 20             
                6 25 12                
                   3

zkl

This solution uses the code from Solve_a_Numbrix_puzzle#zkl

hi:=  // 0==empty cell, X==not a cell
#<<<
"   X 0 0 X 0 0 X
    0 0 0 0 0 0 0
    0 0 0 0 0 0 0
    X 0 0 0 0 0 X
    X X 0 0 0 X X
    X X X 0 X X X";
#<<<
adjacent:=T( T(-3,0),
      T(-2,-2),   T(-2,2),
    T(0,-3),         T(0,3),
       T(2,-2),   T(2,2),
             T(3,0) );

puzzle:=Puzzle(hi,adjacent);
puzzle.print_board();
puzzle.solve();
println();
puzzle.print_board();
println();
Output:
Number of cells = 27
   __ __    __ __    
__ __ __ __ __ __ __ 
__ __ __ __ __ __ __ 
   __ __ __ __ __    
      __ __ __       
         __          

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