Agreed. However simplified variants on problems like these are actually really effective interview questions. A few years ago, I was asked to solve the N-Rook-K

Agreed. However simplified variants on problems like these are actually really effective interview questions. A few years ago, I was asked to solve the N-Rook-Kings (pieces that attack like kings and rooks at the same time) problem, for 1 < N < 16, in half an hour. The catch was that I had to only count the solutions, not find them. The very inexperienced engineer that I was, wrote a highly-optimized (bit boards) solution that could solve N=12 in 6 seconds. But I got this solution after the fact, and it took me hours to write it. A more qualified software engineer would have found a proper combinatorial solution in minutes. In general, giving an actual NP-Complete problem in an interview question and expecting a good solution is unrealistic. However hiding an easy problem in a hard-looking one seems pretty effective.