5.254. orchard

DESCRIPTIONLINKSGRAPH
Origin

[Jackson1821]

Constraint

πš˜πš›πšŒπš‘πšŠπš›πš(π™½πšπ™Ύπš†,πšƒπšπ™΄π™΄πš‚)

Arguments
π™½πšπ™Ύπš†πšπšŸπšŠπš›
πšƒπšπ™΄π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚑-πšπšŸπšŠπš›,𝚒-πšπšŸπšŠπš›)
Restrictions
π™½πšπ™Ύπš†β‰₯0
πšƒπšπ™΄π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
πšƒπšπ™΄π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|πšƒπšπ™΄π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπšπ™΄π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚑,𝚒])
πšπš’πšœπšπš’πš—πšŒπš(πšƒπšπ™΄π™΄πš‚,πš’πš—πšπšŽπš‘)
πšƒπšπ™΄π™΄πš‚.𝚑β‰₯0
πšƒπšπ™΄π™΄πš‚.𝚒β‰₯0
Purpose

Orchard problemΒ [Jackson1821]:

β€œYour aid I want, Nine trees to plant, In rows just half a score, And let there be, In each row, threeβ€”Solve this: I ask no more!”

Example
10,πš’πš—πšπšŽπš‘-1𝚑-0𝚒-0,πš’πš—πšπšŽπš‘-2𝚑-4𝚒-0,πš’πš—πšπšŽπš‘-3𝚑-8𝚒-0,πš’πš—πšπšŽπš‘-4𝚑-2𝚒-4,πš’πš—πšπšŽπš‘-5𝚑-4𝚒-4,πš’πš—πšπšŽπš‘-6𝚑-6𝚒-4,πš’πš—πšπšŽπš‘-7𝚑-0𝚒-8,πš’πš—πšπšŽπš‘-8𝚑-4𝚒-8,πš’πš—πšπšŽπš‘-9𝚑-8𝚒-8

The 10 alignments of 3 trees correspond to the following triples of trees: (1,2,3), (1,4,8), (1,5,9), (2,4,7), (2,5,8), (2,6,9), (3,5,7), (3,6,8), (4,5,6), (7,8,9). FigureΒ 5.254.1 shows the 9 trees and the 10 alignments corresponding to the example.

Figure 5.254.1. Nine trees with 10 alignments of 3 trees
ctrs/orchard1
Symmetries
  • Items of πšƒπšπ™΄π™΄πš‚ are permutable.

  • Attributes of πšƒπšπ™΄π™΄πš‚ are permutable w.r.t. permutation (πš’πš—πšπšŽπš‘) (𝚑,𝚒) (permutation applied to all items).

  • One and the same constant can be added to the 𝚑 attribute of all items of πšƒπšπ™΄π™΄πš‚.

  • One and the same constant can be added to the 𝚒 attribute of all items of πšƒπšπ™΄π™΄πš‚.

Keywords

characteristic of a constraint: hypergraph.

geometry: geometrical constraint, alignment.

Arc input(s)

πšƒπšπ™΄π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πšŽπšŽπšœ1,πšπš›πšŽπšŽπšœ2,πšπš›πšŽπšŽπšœ3)

Arc arity
Arc constraint(s)
βˆ‘πšπš›πšŽπšŽπšœ1.𝚑*πšπš›πšŽπšŽπšœ2.𝚒-πšπš›πšŽπšŽπšœ1.𝚑*πšπš›πšŽπšŽπšœ3.𝚒,πšπš›πšŽπšŽπšœ1.𝚒*πšπš›πšŽπšŽπšœ3.𝚑-πšπš›πšŽπšŽπšœ1.𝚒*πšπš›πšŽπšŽπšœ2.𝚑,πšπš›πšŽπšŽπšœ2.𝚑*πšπš›πšŽπšŽπšœ3.𝚒-πšπš›πšŽπšŽπšœ2.𝚒*πšπš›πšŽπšŽπšœ3.𝚑=0
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πšπ™Ύπš†

Graph model

The arc generator πΆπΏπΌπ‘„π‘ˆπΈ(<) with an arity of three is used in order to generate all the arcs of the directed hypergraph. Each arc is an ordered triple of trees. We use the restriction < in order to generate one single arc for each set of three trees. This is required, since otherwise we would count more than once a given alignment of three trees. The formula used within the arc constraint expresses the fact that the three points of respective coordinates (πšπš›πšŽπšŽπšœ 1 .𝚑,πšπš›πšŽπšŽπšœ 1 .𝚒), (πšπš›πšŽπšŽπšœ 2 .𝚑,πšπš›πšŽπšŽπšœ 2 .𝚒) and (πšπš›πšŽπšŽπšœ 3 .𝚑,πšπš›πšŽπšŽπšœ 3 .𝚒) are aligned. It corresponds to the development of the expression:

πšπš›πšŽπšŽπšœ 1 .πš‘πšπš›πšŽπšŽπšœ 2 .𝚒1πšπš›πšŽπšŽπšœ 2 .πš‘πšπš›πšŽπšŽπšœ 2 .𝚒1πšπš›πšŽπšŽπšœ 3 .πš‘πšπš›πšŽπšŽπšœ 3 .𝚒1=0