9 card logic puzzles

I was presented on my desk this week a parcel full of games and puzzles.

The first one I pulled out was a 9 card puzzle. This was something I remember getting when I was a kid and trying to work out.

However, I now look at these puzzles with a different level of understanding.

Where's wally logic puzzle

Mickey Mouse Logic Puzzle

The part I like about these is the tracability of these puzzles.

While they might seem simple, the math starts to get quite huge and remember I got these wrong, I have yet to solve these. 

Given is a puzzle game with nine square cards.
On each of the cards there are 4 pictures at top, right, bottom and left.

Goal: to lay out the nine cards in a 3x3 grid in such a way that all "inner" (complete) character are properly combined with adjacent cards, i.e. have a front and rear end.

Even though the puzzle looks simple at first glance, there is an extremely big number of combinations given that you can rotate each piece in 4 different ways.

Is there an algorithm that could be used to help get the answer.

There are only 9 pieces, and thus each potential solution is representable by a small structure (say a 3x3 array of pieces, each piece with it's rotation), so the exact description of the pieces isn't too important.

What you'd do by hand is to place a piece, say at the upper left side, and try to complete the square by fitting matching pieces into the rest. So you'd never consider any combinations where the first and second pieces don't match, cutting the search down considerably. This kind of idea is called backtracking. For it you need a description of the partial solution (the 3x3 grid with the filled in pieces and blank places, and the pieces not yet used; a specific order in which to fill the grid), a way of moving forward (place next piece if it fits, skip that one if it doesn't) and backwards (can't find any fits, undo last move and try the next possibility).

Obviously, you have to design a way to find out if a potential match exists (given the filled in neighbours, try all orientations of a piece in it's asigned place). For such a small problem this probably isn't performance critical, but if you'd try to solve, say 100x100 the case is different...

and now with the maths, The number of possibilities is: 9!*4^9 = 95126814720

Who knew a 3x3 puzzle could be that fun and have these possibilities to explore computational thinking. Students could even develop a program to help them solve this problem.