Paths in a grid 4×4

Question

Suppose you have a grid of 4×4, and you can move on this according to the next rules:
1. You can start in any of the 16 squares on the grid.
2. You can not pass through the same square twice (no repeat squares).
3. If you are in a square, you can move to another square that have not been visited yet and that is its neighbour (i.e., you can not leave the grid and the only permissed moves are right, left, down, up, down to the left, down to the right, up to the left, up to the right, and no repeat squares).

How would you program a code that calculates all the paths that are permited along the grid?

I have some experience in coding in C and Python, but it could be in any other language.

This is a question that I considered interesting, and I saw something about n-ary trees, but I don not know how to use them to solve this "problem". Thanks for trying!

Answer 1

By the way, this question is inspired in the game "Wordament", developed by Microsoft