Two Hamiltonian path problem variants
I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).

It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the Permutation Reconstruction from Differences sequence problem.

The reduction is from Hamiltonian path on grid graphs (a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them; a grid graph can have holes, i.e. some nodes may be missing;  see "Hamilton Paths in Grid Graphs" by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter). Given a grid graph $G$ that fits in a $w \times w$ square, with nodes $u_i$ at coordinates $(x_{u_i},y_{u_i})$
and source, target nodes $s,t$; build a filled board of size $4n\times4n$ with all blocked cells except cells $(4x_{u_i},4y_{u_i})$ and target cell $(4x_t+1,4y_t)$. The initial frog position is $(4x_s,4y_s)$. This part of the board is called graph area. The first "logical" sequence of moves is the following sequence repeated $|V| - 1$ times:

(suppose that frog is in position $(x,y)$)


$(0,J_i)$: vertically jump to an empty part of the board (edge gadget)
$(-2,2)$: make a backward diagonal jump of length 2
$(0,p)$: vertically jump to another empty part of the board (on the same gadget)
$(2,2)$: make a forward diagonal jump of length 2
$(0,J_i+p)$: return to graph area in one of the cells $(x+4,y),(x-4,y),(x,y-4),(x,y+4)$


This forces the frog to make $n-1$ steps on the empty cells corresponding to the nodes of the original graph.

The sequence is followed by one horizontal step $(1,0)$ (that forces the last cell to be the one associated with the target node $t$) and a forced step that leads to a cleanup gadget. The sequence of jumps of the cleanup gadget allows it to visit all unvisited cells of the edge gadgets and completely fill the board.

This is a simple graphical outline of the gadgets used in the reduction:



Figure: Outline of a CFP instance (for better readability blocked cells are not shown, the cleanup gadget is not complete and space is compacted ). Black jumps represent the graph area traversal, green jumps represent the edge gadgets traversals, red jumps represent the vertical selection gadget traversal, blue jumps represent the horizontal hole gadget traversal.

The details can be found in the draft paper "The Crazy Frog Problem and Permutation Reconstruction from Differences" that can be download here.

The reduction is complex so perhaps it is wrong (or can be simplified), but I think that the results (if new?) are interesting ...