\(S\) と \(T\) に含まれる W, B の個数が一致しない場合答えは No です。以下では一致する場合を考えます。W の個数を \(W\)、B の個数を \(B\) とします。

空きマスは必ず連続した位置にあることに注意すると、マスの状態としてあり得るものは \(\frac{(N+1)!}{B!W!}=O(\sqrt{N}2^N)\) 通りです。（計算量解析はやや難しいため証明略）
これは \(N=14,B=W=7\) のときに最大の \(51480\) となります。また、各状態に対し、次の一手としてありえるものは \(N-1\) 通りです。

状態数、次の一手の数がともに十分小さいため、この問題はBFSにより解くことができます。

計算量は全体で(hashmapを用いることでexpected) \(O(N^{1.5}2^N)\) となります。

類題：8 puzzle (AOJ)