隣り合う２数の差は３以上、１つおいた数との差も３以上の順列は何通りあるか？

次の問題を考えています。
（http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm）

１からNまでのN個の整数で、
　ア）隣り合う２数の差は３以上、１つおいた数との差も３以上　
という条件を満たす順列は、何通りあるだろうか？
ただし、順番を逆にしたものもそれぞれ１つずつ数えるものとします。

（より一般的には次のような問題です。
１からNまでのN個の整数で、
　イ）隣り合う２数の差はD以上、１個おいた数との差もD以上、… 、D - 2個おいた数との差もD以上　
という条件を満たす順列は、何通りあるだろうか？
例えば、N = 9、D = 3 のとき、
[3, 6, 9, 2, 5, 8, 1, 4, 7]
[7, 4, 1, 8, 5, 2, 9, 6, 3]
の２通りあります。)

この問題の答えを速く求めるコードを考えてください。
以下、答えを求めるのが大変遅いコードです。

N = 11
D = 3

def check(a, i)
  j = 1
  d_max = [i, D - 1].min
  while (a[i] - a[i - j]).abs >= D && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= D
end

(D..N).each{|n|
  cnt = 0
  (1..n).to_a.permutation{|a|
    i = 1
    while check(a, i) && i < n - 1
      i += 1
    end
    if check(a, i)
      cnt += 1
    end
  }
  p [n, cnt]
}

出力結果
[3, 0]
[4, 0]
[5, 0]
[6, 0]
[7, 0]
[8, 0]
[9, 2]
[10, 40]
[11, 792]

（追記）
D = 3 のとき、N = 12 までならすぐ求まるコードを
回答に載せました。