Planarity

4 collaborators

Uri Wilensky (Author)

Josh Unterman (Author)

Seth Tisue (Author)

Jim Lyons (Team member)

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 AND LICENSE

CC BY-NC-SA 3.0

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.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

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.
  ask turtles [
    ask other turtles [ attempt-link ]
  ]
  ;; 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 

to attempt-link  ;; link procedure
  ;; note that if the link already exists, nothing happens
  create-link-with myself [
    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 

to-report crossed? [link-a link-b]
  ;; 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.

Uploaded by	When	Description	Download
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	over 12 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	almost 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	almost 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	almost 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	almost 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	almost 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	almost 14 years ago	Planarity	Download this version

Attached files

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

This model does not have any ancestors.

This model does not have any descendants.

NetLogo