This problem is a familar context involving perimeters and squares that requires careful analysis. There are opportunities to experiment but a need to think ahead.
Arrange nine large squares into a $3 \times 3$ array and colour the edges - counting from $1$ to $12$ this time.
Rearrange the nine squares in a haphazard way to enable you to colour the edges in a different colour (counting $1$ to $12$).
"Does this mean we cannot do it?"
or
When any pair is successful challenge them to repeat the task:
"Well done. Would you be able to do this again without making any "false moves"?"
"Can we use more colours when we have $16$ squares?"
"How about with $25$ squares...?"
Can you anticipate where certain squares will have to go in future rounds?
Lots of paper squares so students do not have to worry about making mistakes.
A $4 \times 4$ array is probably easier.
Can students do all three colourings without rearranging the squares?
Will it always be possible to add an extra colour as the squares get larger?
For a 3D version of this problem students could try Inside Out