### Arranging numbers in a grid

The National Council of Teachers of Mathematics is the largest organization for math educators in the United States, and they post a math problem on Twitter every Friday. Usually, these problems are not very difficult, but the problem for February 17, 2012 was quite challenging.

Friday Math Problem: Arrange the numbers 1 – 16 in a 4 by 4 grid so that consecutive numbers are not touching. How many ways are there?

— NCTM (@NCTM) February 17, 2012

The definition of “touching” was later clarified for the purpose of this problem. Two squares are considered to be touching if they meet along an edge, or if they just meet at a corner point. For example, the first solution in this picture is valid, but the second is invalid, because the consecutive numbers 4 and 5 are touching at a corner.

I challenge my readers (all three of you) to find the number of solutions. You will probably need to write a computer program to do this. I will post my solution on July 31.