Διαδρομές Βασιλιά με Περιορισμένες Κινήσεις

Σε μια σκακιέρα, ένας βασιλιάς επιτρέπεται να κινείται ένα τετράγωνο τη φορά μόνο:

• οριζόντια δεξιά,
• κάθετα κάτω, ή
• διαγώνια δεξιά-κάτω.
  

1. Σε μια «μικρή» σκακιέρα 4×44\times4, με αφετηρία την πάνω-αριστερή γωνία, με πόσες διαφορετικές διαδρομές μπορεί να φτάσει στην κάτω-δεξιά γωνία;
2. Με πόσες διαδρομές μπορεί να γίνει ένα αντίστοιχο ταξίδι σε κανονική σκακιέρα 8×8;