# Planarity

### 4 collaborators

Uri Wilensky (Author)
Josh Unterman (Author)
Seth Tisue (Author)
Jim Lyons (Team member)

### Tags

coolest models

Tagged by Josh Unterman almost 15 years ago

fun

Tagged by Michelle Wilkerson-Jerde almost 15 years ago

game

Tagged by Reuven M. Lerner over 10 years ago

Model group CCL | Visible to everyone | Changeable by group members (CCL)
Model was written in NetLogo 5.0.4 • Viewed 596 times • Downloaded 54 times • Run 6 times

## WHAT IS IT?

This is a puzzle game where you try to untangle a graph. (A graph is a collection of nodes connected by lines.) Try to reposition the nodes so that no two lines cross. The more nodes, the harder it gets!

## HOW IT WORKS

The game knows how to generate solvable graphs, and it also knows how to detect whether any lines intersect. The details are in the Code tab.

## HOW TO USE IT

Use the STARTING-LEVEL slider to choose the initial difficulty level. If you're a beginner, start at 1. Press SETUP to set up a new board, then press GO to play. Once the GO button is pressed, you can use your mouse to drag the nodes around.

Every level is solvable. One you find a solution, you will automatically be taken to the next level.

## THINGS TO NOTICE

The game only gives you solvable graphs. How might the game be able to guarantee this? (One answer is in the Code tab.)

Can you draw an example of an unsolvable graph on a piece of paper? How many nodes are in the smallest unsolvable graph?

On early levels, you can usually untangle the nodes without too much thought. On later levels, you'll probably need to develop some conscious strategies. What strategies do you find most effective? When your friends play, do they use the same strategies you do?

## THINGS TO TRY

See how high a level you can solve.

Try to solve each level in the fewest number of moves. (The tick counter shows you how many moves you've made.)

## EXTENDING THE MODEL

Are there any other ways of generating solvable graphs besides the SETUP-LEVEL? Does it matter what method is used? The more links you can make, the harder the level will be, but if you make too many links, the level might not be solvable at all!

Wherever two links intersect, add a small, brightly colored turtle to mark the intersection. (You'll need two breeds of turtle, one for the nodes, one for the markers. Intersecting Links Example has code for locating the intersection points.)

Make it possible to select multiple nodes and move them together.

## NETLOGO FEATURES

The nodes are turtles; the lines connecting them are links. The code does not make use of patches (other than to make a plain white background).

NetLogo does not have a primitive which detects whether two links intersect. To do the detection, the code uses the `subtract-headings` primitive and some math.

## RELATED MODELS

Intersecting Links Example -- has sample code for finding the point where two links intersect (unlike this model, which only determines whether that point exists or not)

## CREDITS AND REFERENCES

Thanks to Josh Unterman and Seth Tisue for their work on this model and to Jim Lyons for coding advice.

Original version created by John Tantalo, from an original concept by Mary Radcliffe. Tantalo's site is here: http://www.planarity.net/.

Solvable graphs are called "planar graphs" by mathematicians. See http://en.wikipedia.org/wiki/Planar_graph.

## HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

• Wilensky, U. (2007). NetLogo Planarity model. http://ccl.northwestern.edu/netlogo/models/Planarity. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

Copyright 2007 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

## Comments and Questions

Click to Run Model

```globals [
level    ;; determines how many nodes you have to untangle;
;; the formula is below
]

to setup
clear-all
set-default-shape turtles "circle"
ask patches [ set pcolor white ]      ;; plain white background
set level starting-level
setup-level
end

to setup-level
reset-ticks  ;; use tick counter as a move counter
clear-turtles  ;; when the turtles die, the links connecting them die too
;; create nodes and position them randomly
create-turtles 4 + level [
set color blue
setxy random-xcor random-ycor
]
;; Now we need to make some links.  We have to be careful that
;; the resulting graph has a solution.  Probably there are lots
;; of ways this could be done, but this was the simplest way we
;; could think of.
;; First make a bunch of links at random.
while [count links < count turtles] [
ask one-of turtles [
ask one-of other turtles [ attempt-link ]
]
]
;; Then fill in all remaining allowable links.
]
;; Now we have a graph which we know is solvable,
;; because the current layout is a solution.
;; Time to scramble the nodes around!
while [solved?] [ scramble ]
display
end

;; note that if the link already exists, nothing happens
if any-intersections? [ die ]
]
end

to scramble
;; The turtles agentset is always in random order,
;; so this makes a random layout.
layout-circle turtles (world-width / 2 - 1)
end

;; This procedure lets us find the next turtle,
;; or the turtle two over, and so on.

to-report turtle-plus [n]  ;; turtle procedure
report turtle ((who + n) mod count turtles)
end

to go
if mouse-down? [
;; find the closest node
let grabbed min-one-of turtles [distancexy mouse-xcor mouse-ycor]
;; loop until the mouse button is released
while [mouse-down?] [
ask grabbed [ setxy mouse-xcor mouse-ycor ]
display
]
;; use tick counter as a move counter
tick
;; check if the level is solved
if solved? [
user-message "You rock. Now try this..."
set level level + 1
setup-level
]
]
end

to-report solved?
report all? links [not any-intersections?]
end

to-report any-intersections?  ;; link procedure
report any? other links with [crossed? self myself]
end

;; store nodes in variables for easy access
let a1 [end1] of link-a
let a2 [end2] of link-a
let b1 [end1] of link-b
let b2 [end2] of link-b
let nodes (turtle-set a1 a2 b1 b2)
;; if the links share a node, they don't cross
if 4 > count nodes [ report false ]
;; but if two nodes are on top of each other, we will say
;; the links do cross (so you can't cheat that way)
if 4 > length remove-duplicates [list xcor ycor] of nodes
[ report true ]
;; if the ends of link-a are on opposite sides of link-b,
;; and the ends of link-b are on opposite sides of link-a,
;; then the links cross
report [subtract-headings towards a2 towards b1 < 0 xor
subtract-headings towards a2 towards b2 < 0] of a1
and [subtract-headings towards b2 towards a1 < 0 xor
subtract-headings towards b2 towards a2 < 0] of b1
end

; Copyright 2007 Uri Wilensky.
; See Info tab for full copyright and license.
```

There are 10 versions of this model.

Uri Wilensky almost 11 years ago Updated to NetLogo 5.0.4 Download this version
Uri Wilensky over 11 years ago Updated version tag Download this version
Uri Wilensky over 11 years ago Updated to version from NetLogo 5.0.3 distribution Download this version
Uri Wilensky about 12 years ago Updated to NetLogo 5.0 Download this version
Uri Wilensky over 13 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 13 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 13 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 13 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 13 years ago Model from NetLogo distribution Download this version
Uri Wilensky over 13 years ago Planarity Download this version

## Attached files

File Type Description Last updated
Planarity.png preview Preview almost 11 years ago, by Reuven M. Lerner Download

This model does not have any ancestors.

This model does not have any descendants.