Representing the board as binary integers simplifies the implementation and reduces the computational complexity by parallel computation. In this problem, since it’s a 2D board, it’s good to represent it as an integer with \(H \times (W + 1)\) bits, for example, by adding a sentinel to the right end.

For the search method, recursive DFS or enumerating all permutations are conceivable. In the latter case, itertools.permutations is convenient in Python.

AC Code (Python) Recursive DFS

AC Code (Python) Using itertools’s permutations

[References] Past similar problems (Problems that can be solved by treating 2D boards as binary integers)

Problem Editorial

Problem Editorial