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


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)
