sbv-11.4: SMT Based Verification: Symbolic Haskell theorem prover using SMT solving.
Copyright(c) Levent Erkok
LicenseBSD3
Maintainererkokl@gmail.com
Stabilityexperimental
Safe HaskellNone
LanguageHaskell2010

Documentation.SBV.Examples.Puzzles.Tower

Description

Synopsis

Modeling Towers

type Count a = Array Integer a Source #

Count of visible towers as an array.

type Grid a = Array (Integer, Integer) a Source #

The grid itself. The indexes are tuples, first coordinate increases as you go from left to right, and the second increases as you go from top to bottom.

type Problem a = (Count a, Count a, Count a, Count a, Grid a) Source #

The problem has 4 counts, from top, left, bottom, and right. And the grid itself.

problem :: Problem (Maybe Integer) Source #

Example problem. Encodes:

    - - 3 - - 4
  -     2       5
  -   2         -
  4             -
  2             -
  -             2
  3             -
    - - 3 4 - -

symProblem :: Problem (Maybe Integer) -> Symbolic (Problem SInteger) Source #

Given a concrete partial board, turn it into a symbolic board, by filling in the empty cells with symbolic variables.

Counting visible towers

visible :: [SInteger] -> SInteger Source #

Given a list of tower heights, count the number of visible ones in the given order. We simply keep track of the tallest we have seen so far, and increment the count for each tower we see if it's taller than the tallest seen so far.

Building constraints

tower :: Problem SInteger -> Symbolic () Source #

Build the constraints for a given problem. We scan the elements and add the required visibility counts for each row and column, viewed both in the correct order and in the backwards order.

Example run

example :: IO () Source #

Solve the puzzle descibed above. We get:

>>> example
  1 2 3 2 2 4
1 6 5 2 4 3 1 5
3 3 2 5 6 1 4 2
4 2 4 1 5 6 3 2
2 5 3 6 1 4 2 3
2 1 6 4 3 2 5 2
3 4 1 3 2 5 6 1
  3 2 3 4 2 1