sfenu

That's pretty much the Havel-Hakimi algorithm

Stop me if I'm wrong, but it seems misleading to ask whether or not the problem is in P. It seems to me that it is better to ask more generally whether the problem is tractable. There are a lot of games that are solvable in exponential time (not in P) that are still tractable because the branching factor is low enough that simple methods like minimax searches work well.

Take chess as an example. It's an EXP-TIME complete game with a branching factor of 35, and AI techniques win pretty much all of the time. In this case you're looking at a much simpler game (if you treat it as an expectiminimax problem, you alternate between turns with a branching factor of less than or equal to 4 and ones with a branching factor of less than or equal to 32). The game is much less complicated than chess. The game tree is really small, meaning that it should be tractable to most AI techniques.

Even though it is reasonable to 'solve' the problem, there are board setups that are unwinnable. Since the player has a lot more power over the game in placing tiles than the agent does in moving them, it is easier for the player to force the game to one of the unwinnable states than it is for the agent to prevent these things. Even if the agent is acting optimally, the player should still be able to win.

Here's the best solution I've heard for this:

The prisoners meet together and designate a leader. The leader will maintain a tally. They also designate one of the switches to not matter. The prisoners then use the following strategy:

When a prisoner is lead to the room, if the designated switch is off and it is the prisoner's first time flipping the relevant switch, it is turned on. Else, flip the irrelevant switch. If the prisoner is the designated leader, and the relevant switch is on, he adds a count to his tally and turns the relevant switch off. Otherwise he just flips the irrelevant switch. This way, once the leader has seen the light be on a sufficient number of times he can definitively say that they have all been in the room.