Playground Documentation Challenges Full Docs

rule("bijective")

Functions between enumerated types that take every value once

Overview

In grid puzzles every house has one colour and every colour is in one house. With enumerated types the first half is already there: color(2) -> red and color(2) -> blue contradict each other, and refuting all colours but one of house 2 gives the last one. rule("bijective", f) adds the second half for a function f: [D -> C] between enumerated types of the same size.

rule("bijective", functionAtom1, functionAtom2, …)
functionAtom1, …
Functions f: [D -> C] between enumerated types of the same size, each declared a bijection.

Basic examples

Row and column

The Einstein puzzle in the repository (library/puzzles/einstein_enum.fl) is solved this way in about a hundred lines of code: properties are functions color: [House -> Color], clues are conditional axioms, and the solution is a sequence of refutations.

▶ Run

Details

  • Injectivity. f(a) -> c and f(b) -> c with different values a, b of D contradict each other.
  • Exhaustion by column. When f(h) -> c is refuted (or h already has another value) for every h but one, f(k) -> c follows. By row, the values already taken by other houses are excluded too.

Both are schemas of the declaration — Injective and Column, axioms of a lock of its own — and decide works with them: the value of a cell is found from the facts about the other cells of its row and column, by the tables of the functions applied to it. A label on the declaration holds the schemas, to pass to a call of a theorem proved under another bijection. Like every rule, the declaration is an axiom of the theory: the function is a bijection.