i-am-tom / holmes

A reference library for constraint-solving with propagators and CDCL.
https://hackage.haskell.org/package/holmes
MIT License
303 stars 14 forks source link

Produce solutions where the order doesn't matter #17

Open L7R7 opened 2 years ago

L7R7 commented 2 years ago

First off, thanks for your work on this library and for providing such extensive docs. It was super easy for me to get started!

I'm currently experimenting with a constellation where the order of the elements in the solution doesn't matter. I'm pretty sure I'm missing something here, so maybe you can help me out.

data M = A | B | C | D deriving (Bounded, Eq, Enum, Ord, Generic, Hashable, Show)

solve :: IO [[Defined M]]
solve = do
  let guesses = 3 `from` [A .. D]
  guesses `whenever` \solution -> and' [distinct solution]

run :: IO ()
run = solve >>= traverse_ print . take 3

This will print

[Exactly A,Exactly B,Exactly C]
[Exactly A,Exactly B,Exactly D]
[Exactly A,Exactly C,Exactly B]

However, I'd like to add a constraint that makes the solver treat the first and the third solution as equal solutions (and therefore delete one of them from the set of possible solutions). I could map over the solution afterwards, but this doesn't help in making the computation run faster. That's why I want to include it in the constraints.

Is there a way to do that?

L7R7 commented 2 years ago

I came up with this variant:

solve :: IO [[Defined (Set M)]]
solve = do
  let allValues = [A .. D]
  let setsOfThree = filter (\s -> S.size s == 3) $ nub $ (\a b c -> S.fromList [a, b, c]) <$> allValues <*> allValues <*> allValues
  let guesses = 1 `from` setsOfThree
  guesses `whenever` \solution -> and' []

which uses Sets as inputs instead of single elements. I don't know how well that will work well for data types with higher cardinality