Grid Cycles

Scroll for examples.

Imagine a person standing in each cell. Now tell each person to move simultaneously to an adjacent cell in the grid with the rule that each must not move in the oppose direction of a neighbor who is entering their cell; that is, no two people may simultaneously cross the same edge as they move to an adjacent cell.

This visualization illustrates the valid patterns in which all 36 people could move. It becomes immediately clear that the migration patterns on a 6 x 6 grid take the form of cycles moving either clockwise or counter-clockwise. Unlike musical chairs, each person must end up in a different adjacent cell.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  body {
    background: #222;
    overflow-x: hidden;
    width: 100%;
  }

.cell rect {
    fill: none;
    stroke: #444;
    stroke-width: 1px;
    stroke-opacity: 0.5;
    stroke-dasharray: none;
  }
  
  line {
    fill: none;
    stroke-width: 2px;
  }

</style>
<script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
<body>
</body>
<script>

var computing = false;

var worker = new Worker("./worker.js");

var svg,
    margin = { top: 20, left: 20, right: 20, bottom: 20},
    width = +Math.floor(d3.select("body").style("width").replace("px", "")) - 16,
    height = width;

// Grid size.
var N = 6;

var numPerLine = width >= 960 ? 5 : 1;

var spacing = Math.floor(width / numPerLine) - 1;

var exampleSize = spacing * 0.5;

var cellSize = Math.round(exampleSize / (N - 1));

var container = d3.select("body");

var lastExample;

container = container.append("div");

// Dispatcher.
worker.onmessage = function(event) {
  switch (event.data.type) {
    case "example":
      update(event.data.example);
      break;
    case "progress": // Updated whenever solutions are found.
      console.log(event.data.solution);
      break;
    case "paused":
      computing = false;
      maybeCompute();
      break;
    case "done":
      console.log("There are", event.data.solution, "examples.");
      worker.terminate();
      break;
  }
};

// Update with data or when no data is specified, update the progress bar only.
function update(data) {
  // Flow examples left to right and top to bottom.
  lastExample = container.append("svg")
      .datum(data)

var cell = lastExample
    .attr("width", spacing)
    .attr("height", spacing)
    .append("g")
      .classed("example", true)
      .attr("transform", (d, i) => "translate(" + (spacing / 4) + "," + spacing / 4 + ")")
    .selectAll(".row")
      .data((d) => d)
    .enter().append("g")
      .classed("row", true)
      .attr("transform", (d, i) => "translate(0," + i * cellSize + ")")
    .selectAll(".cell")
      .data((d) => d)
    .enter().append("g")
      .classed("cell", true)
      .attr("transform", (d, i) => "translate(" + i * cellSize + ",0)")
      .style("stroke", (d) => d.hex)
      .style("fill", (d) => d.hex)
      .style("stroke-dasharray", (d) => {
          return (d.orientation) ? [cellSize / 5, cellSize / 5, cellSize / 5].join(",") : null;
      });

cell.selectAll("rect")
      .data([0, 1, 2, 3])
    .enter().append("rect")
      .attr("x", (d, i) => {
        return ((i % 3 === 0) ? 0 : cellSize) - cellSize / 2;
      })
      .attr("y", (d, i) => {
        return ((i < 2) ? cellSize : 0) - cellSize/ 2;
      })
      .attr("width", cellSize)
      .attr("height", cellSize);
  
  cell.selectAll("line")
      .data((d) => d.edges)
    .enter().append("line")
      .attr("x1", (d, i) => {
        return (i % 3 === 0) ? 0 : cellSize;
      })
      .attr("x2", (d, i) => {
        return (i < 2) ? cellSize : 0;
      })
      .attr("y1", (d, i) => {
        return (i < 2) ? 0 : cellSize;
      })
      .attr("y2", (d, i) => {
        return (i % 3 === 0) ? 0 : cellSize;
      })
      .style("opacity", (d) => (d) ? 1 : 0);

cell.selectAll("circle")
      .data((d) => d.edges)
    .enter().append("circle")
      .attr("cx", (d, i) => {
        return (i % 3 === 0) ? 0 : cellSize;
      })
      .attr("cy", (d, i) => {
        return (i < 2) ? 0 : cellSize;
      })
      .attr("r", 0.1 * cellSize)
      .style("opacity", (d) => (d) ? 1 : 0);
}

computing = true;
worker.postMessage({ type: "start", n: N, limit: 1});

d3.select(window)
    .on("scroll", maybeCompute)
    .each(maybeCompute);

function maybeCompute() {
  if (!computing && lastExample && lastExample.node().getBoundingClientRect().top < height) {
    computing = true;
    worker.postMessage({ type: "resume"});
  }
}

</script>

https://d3js.org/d3.v4.min.js