以前、「スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）」という記事を書きましたが、解を列挙するのではなく、解の数を数えるだけなら一瞬で終わらせるプログラムがあります。
「clang++ -O3 -std=c++11 magicsquare4.cc」などとしてコンパイルしてから実行します。実行時間は一瞬です。
このプログラムの欠点は、コンパイルにかなりの時間がかかることです（TANSTAAFL）。手元の環境では、コンパイルに4分くらいかかりました（説明するのは野暮ですが、これはネタです）。
C++のconstexprを使っています。複数のコンパイラがconstexprをサポートしていますが、このコードをコンパイルできるのは、私が試したところではClang 3.3のみです（Ubuntuでは「sudo apt-get install clang-3.3」などとしてインストールできます）。ステップ数に上限が導入されたClang 3.4以降や、途中経過を記憶してメモリを圧迫するgccではコンパイルできません。
Clang 3.3でサポートされるconstexprの関数には、大ざっぱに言えばreturn文しか書けないので、マスに数が入るかどうかをチェックする関数を作り、「数がすでに使われていなければ次のマスを試し、使われていれば1だけ大きい数を再帰的に試す」ということを、return文の条件演算子で実現しています。
このコードは私が直接書いたものではなく、私が書いたプログラムが生成したものです（手で直接書くのは大変です）。同じプログラムで5×5の場合も生成しましたが、試すのはやめた方がいいでしょう（constexprを消してコンパイル・実行すれば、正しいことは確認できます）。