\(k\) は盤面上の # の数なので最初に計算できます。

全てのマスについて、そこがヘビの端 (\((x_1, y_1)\)) であるとした場合を考えて深さ優先探索をします。今の再帰過程に含まれるマスと、. のマスは避けて、隣接 \(4\) 方向のマスに全て再帰させます。
深さ優先探索で再帰が \(k\) 段目に来た場合、そこまでの再帰過程で通ったマスが正しい答えの一つです。
再帰を潜るごとに配列の最後にマスの座標を追加し、再帰から戻るごとに配列の最後を削除すれば再帰中のどこでも再帰過程に通ったマスの列が得られます。

深さ優先探索にかかる時間は、ゆるめに見積もっても以下の通りです :

• 始点は \(4 \times 4 = 16\) 通り
• 始点からの再帰方向は高々 \(4\) 個
• 始点以外からの再帰方向は、一つ前のマスにはいけないので
  • マス目の角 (4か所) にいるときは高々1通り
  • マス目の辺 (8か所) にいるときは高々2通り
    
  • マス目の内部 (4か所) にいるときは高々3通り
    

よって調べるパスの数は多くとも \(16 \times 4 \times 1^4 \times 2^8 \times 3^4 = 1327104\) であるため十分間に合います。 (実際はもっと少ないです)