Woops, stupid mistake, should be

stateStack.pop()

to do a DFS instead of BFS =)

"This kata helped me discover a very useful fact = avoid using copy.deepcopy"
Same here =)

Woops, "for value in grid" at the end should be "for value in crtGrid" ; surprised it still worked.

I confirm there are not any, I just modified my code to return after finding one solution, it passes the fixed tests and rarely the random ones too (I had to spam "Attempt" a hundred times).
EDIT: my code prechecks that the initial number of filled squares is higher than 17 (otherwise we are sure there are multiple solutions), maybe that's the issue. There should be cases with more than 17 squares filled and multiple solutions.

Woops, forgot to remove this:

if (board[row][col] != 0):
    return backtrack(board, used, nbUsed, pos + 1)

This solution passed by chance after repeatingly clicking "Attempt" (and I did not submit it, dunno why it appears here). It has 2 issues:

• limited number of distinct characters used to floodFill a piece (if nb of pieces > 76, which sometimes happens in the random tests, it fails).
• perf is not good enough.

Proper version that fixes both issues looks exactly like lechevalier's one.

drawPiece is actually wrong, a test case like this would make it fail:

 +-+
++ |
|  |
+--+

Proper version (I think) is in my python solution.

Thanks for this discussion.

"you are in a building, there are different rooms (without any door linking them... :o ), extract the shape of each individual room as delimited by its walls. Only closed rooms are valid."
This should really be in the description, it's much clearer (there's no reason to keep "+--+" for pieces, but it makes sense if it's a wall).

I think I have the easy solution, I'll practice Python just for the occasion =)

As I suspected, they're not.

Could you please explain this? Is it O(n√n) worst case?

Here's a test case to make this fail =)

std::array<int, 6 * 10> alol = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
                                0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19,
                                0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
Assert::That(solve(alol), Equals(190));

(can be easily generated for any maxControl)

Ok I kinda solved the kata, so now I have access to the solutions, and I agree with you that ice1000's solution is quite unreadable =P I'll try to make sense of it tomorrow.
EDIT: aaand I give up.