男女平等な席替え（Ruby）

アルゴリズム・パズルです。

男女15人ずつ、計30人のクラスがあります。
横 6、縦 5 の長方形に配置された机に30人が座るとき、どの生徒の席でも前後左右のいずれかに異性の席があるように座るそのしかたは、全部で何とおりになるでしょうか。
ただし、座り方は個人についてではなく、男女の区別だけを考えます。またパターンの上下左右反転、回転などは別物と考えます。

　
Ruby で解いてみました。コードです。
q69.rb

W, H = 6, 5
Num = W * H
desks = Array.new(Num, nil)
co = 0

check = ->(po) {
  return true if po < 0
  sex = desks[po]
  [1, -W, -1, W].map do |dif|
    nxt = po + dif
    next if nxt < 0
    next if nxt >= Num
    next if po % W == 0 and dif == -1
    next if po % W == W - 1 and dif == 1
    desks[nxt] == 1 - sex
  end.compact.any?
}

sit_down = ->(po, boy, girl) {
  if po == Num
    co += 1 if (Num - W...Num).map {|i| check.(i)}.all?
  else
    if boy < Num / 2
      desks[po] = 0
      sit_down.(po + 1, boy + 1, girl) if check.(po - W)
    end
    if girl < Num / 2
      desks[po] = 1
      sit_down.(po + 1, boy, girl + 1) if check.(po - W)
    end
  end
}
sit_down.(0, 0, 0)
puts co

結果。

$ time ruby q69.rb
13374192

real	5m9.299s
user	5m9.256s
sys	0m0.000s

5分も時間がかかっているのが問題ですが、このアルゴリズム（バックトラック法）だと自分にはうまい高速化の方法が浮かびませんでした。模範解答を見るとメモ化を使って 2秒ほどで解いているようですが、かなりごちゃごちゃしたコードです。なかなかむずかしい。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問