Puzzle Generation Algorithm
The definition of the planarity puzzle does not depend on how the planar graphs in the puzzle are generated, but the original implementation uses the following algorithm:
- Generate a set of random lines in a plane such that no two lines are parallel and no three lines meet in a single point.
- Calculate the intersections of every line pair.
- Create a graph with a vertex for each intersection and an edge for each line segment connecting two intersections (the arrangement of the lines).
If a graph is generated from lines, then the graph will have exactly vertices (each line has vertices, and each vertex is shared with one other line) and edges (each line contains edges). The first level of Planarity is built with lines, so it has vertices and edges. Each level after is generated by one more line than the last. If a level was generated with lines, then the next level has more vertices and more edges.
The best known algorithms from computational geometry for constructing the graphs of line arrangements solve the problem in time, linear in the size of the graph to be constructed, but they are somewhat complex. Alternatively and more simply, it is possible to index each crossing point by the pair of lines that cross at that point, sort the crossings along each line by their -coordinates, and use this sorted ordering to generate the edges of the planar graph, in near-optimal time. Once the vertices and edges of the graph have been generated, they may be placed evenly around a circle using a random permutation.
Read more about this topic: Planarity
Famous quotes containing the words puzzle and/or generation:
“Scholars and artists thrown together are often annoyed at the puzzle of where they differ. Both work from knowledge; but I suspect they differ most importantly in the way their knowledge is come by. Scholars get theirs with conscientious thoroughness along projected lines of logic; poets theirs cavalierly and as it happens in and out of books. They stick to nothing deliberately, but let what will stick to them like burrs where they walk in the fields.”
—Robert Frost (1874–1963)
“Women born at the turn of the century have been conditioned not to speak openly of their wedding nights. Of other nights in bed with other men they speak not at all. Today a woman having bedded with a great general feels free to tell us that in bed the general could not present arms. Women of my generation would have spared the great general the revelation of this failure.”
—Jessamyn West (1907–1984)