ある場所にピースが置けるかどうかは
隣のピースとの合致を総当りで見るしかない

順番に埋めていく限りはどの順番で当てはめても
1辺ずつの照合になるから最悪手はおよそ4*N!だろう

ちょっと問題を変えて、4つのピースを十字型に
並べてから真ん中に5つ目を当てはめると言う手順で
同時に4辺の合致判定をしたと認めるならば
4乗根くらい探索効率があがるはずだがどうかね