The Houses and Utilities Crossing Problem

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

The edges that connect each utility (green disks) to each house (blue squares) are in a single color. Each house in turn has a spectrum of colored edges that connect it to each utility. The red points are crossing points of utility lines. The object is to minimize the number of crossings for a particular set of utilities and houses by shifting their locations.

[more]

The minimal known number of crossings for 6, 7, 8, …, 14 houses and utilities is 1, 2, 4, 8, 16, 24, 36, 54, 77-81. The exact value of the last, for seven houses and seven utilities, has been a long unsolved question.

[less]

Contributed by: Ted Erickson (August 2008)
Open content licensed under CC BY-NC-SA


Snapshots


Details

detailSectionParagraph


Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send