Exercises based on problems with multiple solutions

[hickford]

Hi. I was thinking about suggesting an exercise based on the n-queens problem:

Place n queens on an n by n chessboard such that no queen threatens another.

However the 'make up new exercises' instructions assume that a problem will have a unique solution for every input. In particular, it asks for "a set of sample test inputs and outputs that make up a reasonable test suite".

The n-queen problem has multiple solutions (4426165368 for n=8). Each is equally valid. You can't choose a particular solution for an n=8 test case.

You could constrain the n-queens problem to have a unique solution by demanding the lexicographically-minimum solution, but this would require people "to follow one very specific way to solve the problem", which makes for a less interesting exercise.

Has this been discussed before?

I could imagine a test suite for an unconstrained n-queens exercise, but it would need to do property-based testing rather than example-based testing.

---

Other interesting problems with multiple solutions:

• Finding a knight's tour on a chessboard

I like these kind of problems, because they permit more freedom and creativity in their solution.

[rsslldnphy]

Wouldn't it be possible to write an example-based test that would work for any given n, and then run the test for several values of n? Might not be quite as good as property based tests but probably sufficient and no more likely to lead to falsely succeeding tests than many other test suites?

Something like (and I apologise for the Clojure, I can't think in anything else these days):

(is true? (every? #(= 1 (count (filter queen? %))) rows))
(is true? (every? #(= 1 (count (filter queen? %))) columns))
(is true? (every? #(= 1 (count (filter queen? %))) diagonals))

[petertseng]

https://github.com/exercism/problem-specifications/blob/master/exercises/dominoes/description.md has multiple solutions, assuming tracks are asking for the chain, rather than whether there is a chain. Therefore https://github.com/exercism/problem-specifications/blob/master/exercises/dominoes/canonical-data.json advises in the comments about how to do the property-based testing.

https://github.com/exercism/problem-specifications/tree/master/exercises/diamond was originally for property-based testing, following http://blog.ploeh.dk/2015/01/10/diamond-kata-with-fscheck/ . Not all tracks did that.