How would you write tests for testing a solution to some rather complex algorithm like the N Queens problem? What I mean is what should be the right approach for testing an algorithm that
has many solutions (you don't know / don't care how many of them exist),
you can only have a small subset of all the possible solutions, and
verifying that a solution is correct can be a little bit tricky (maybe comparable in complexity with the algorithm itself).
I know that these conditions are not present in the N-Queens problem itself, but I mentioned it to provide sort of an example.