Skip to content

Instantly share code, notes, and snippets.

@Glorfindel83

Glorfindel83/KnightsTour3Picture.java

Last active May 30, 2019 10:41
Show Gist options
  • Save Glorfindel83/d5a9f1771671207437988a798547a536 to your computer and use it in GitHub Desktop.
Save Glorfindel83/d5a9f1771671207437988a798547a536 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
KnightsTour3Picture.java
package net.mathoverflow;
import java.awt.Point;
// See https://mathoverflow.net/a/332788/70594
public class KnightsTour3Picture {
public static void main(String[] args) throws Exception {
System.out.println("<!DOCTYPE html>");
System.out.println("<html>");
System.out.println("<body>");
System.out.println("<svg height=\"" + center.y * 2 + "\" width=\"" + center.x * 2 + "\">");
// Grid
int start = UNIT / 2, end = UNIT * HALF_SIZE * 2 - UNIT / 2;
for (int i = start; i <= end; i += UNIT) {
String color = ((UNIT * HALF_SIZE - i) * 2 / UNIT) % 3 == 0 ? "#BBB" : "#DDD";
System.out.println("\t<line stroke=\"" + color + "\" x1=\"" + start + "\" y1=\"" + i + "\" x2=\"" + end
+ "\" y2=\"" + i + "\" />");
System.out.println("\t<line stroke=\"" + color + "\" x1=\"" + i + "\" y1=\"" + start + "\" x2=\"" + i
+ "\" y2=\"" + end + "\" />");
}
// Missing points
for (int i = UNIT * HALF_SIZE - 3 * UNIT * (HALF_SIZE / 3); i < end; i += UNIT * 3) {
if (i == 0)
continue;
for (int j = UNIT * HALF_SIZE - 3 * UNIT * (HALF_SIZE / 3); j < end; j += UNIT * 3) {
if (j == 0)
continue;
System.out
.println("\t<circle fill=\"gray\" cx=\"" + i + "\" cy=\"" + j + "\" r=\"" + UNIT / 8 + "\" />");
}
}
// Winding
int wx = center.x + UNIT * 3 / 2, wy = center.y + UNIT * 3 / 2;
StringBuilder windings = new StringBuilder(
"\t<path stroke=\"black\" fill=\"none\" d=\"M" + wx + " " + wy + " ");
wx -= UNIT * 3;
windings.append("L" + wx + " " + wy + " ");
wy -= UNIT * 3;
windings.append("L" + wx + " " + wy + " ");
// Tour
for (int winding = 0; winding <= MAX_WINDINGS; winding++) {
for (Direction direction_ : Direction.values()) {
direction = direction_;
switch (direction) {
case RIGHT:
wx += UNIT * 3 * (2 + winding * 2);
if (winding == MAX_WINDINGS) {
wx -= UNIT * 3;
}
windings.append("L" + wx + " " + wy + " ");
for (int i = 0; i < winding; i++) {
new Box(i == 0 ? 0x9 : 0xC);
new Box(0xE);
}
new Box(0xC);
break;
case DOWN:
wy += UNIT * 3 * (2 + winding * 2);
windings.append("L" + wx + " " + wy + " ");
for (int i = 0; i < winding; i++) {
new Box(0xF);
new Box(0x1);
}
new Box(0xF);
break;
case LEFT:
wx -= UNIT * 3 * (3 + winding * 2);
windings.append("L" + wx + " " + wy + " ");
new Box(0x1);
new Box(0x6);
for (int i = 0; i < winding; i++) {
new Box(0x5);
new Box(0x3);
}
break;
case UP:
wy -= UNIT * 3 * (3 + winding * 2);
windings.append("L" + wx + " " + wy + " ");
new Box(0x5);
new Box(0xA);
for (int i = 0; i < winding; i++) {
new Box(0x9);
new Box(0x7);
}
break;
}
if (winding == MAX_WINDINGS)
break;
}
}
windings.append("\" />");
System.out.println("\" />");
System.out.println(points);
System.out.println(windings);
System.out.println("</svg>");
System.out.println("</body>");
System.out.println("</html>");
}
private static final int UNIT = 30, HALF_SIZE = 12, MAX_WINDINGS = 3;
private static final Point center = new Point(UNIT * HALF_SIZE, UNIT * HALF_SIZE);
private static boolean first = true;
private static final StringBuilder points = new StringBuilder();
// Center position of current box
private static int cx = 0, cy = 0;
private static Direction direction;
// Cf. https://i.stack.imgur.com/WGZ9R.png
private static class Box {
// This is the path the knight will take through the box (direction and starting position depend on the box id).
private static final int[] X = { -1, 0, 1, -1, 1, 0, -1, 1 }, Y = { -1, 1, -1, 0, 1, -1, 1, 0 };
// Boxes 0 and 1 start at X[0], Y[0]; boxes 2 and 3 at X[5], Y[5], etc.
private static final int[] START = { 0, 5, 2, 7, 4, 1, 6, 3 };
private static final String[] COLORS = { "black", "#F80", "black", "#FF0", "black", "#880", "#F0F", "#0F0",
"black", "#080", "#808", "black", "#0FF", "black", "#08F", "#F00" };
// The box id is a hexadecimal digit
private Box(int id) {
boolean forward = id % 2 == 0;
int start = START[id / 2], x = 0, y = 0;
for (int i = 0; i < 8; i++) {
x = center.x + UNIT * (cx + X[(start + (forward ? i : (8 - i))) % 8]);
y = center.y + UNIT * (cy + Y[(start + (forward ? i : (8 - i))) % 8]);
points.append("\n\t<circle fill=\"" + COLORS[id] + "\" cx=\"" + x + "\" cy=\"" + y + "\" r=\""
+ UNIT / 8 + "\" />");
if (i == 0) {
if (first) {
System.out.println("\t<circle fill=\"" + COLORS[id] + "\" cx=\"" + x + "\" cy=\"" + y
+ "\" r=\"" + UNIT / 3 + "\" />");
first = false;
} else {
// Close transition path
System.out.print("L" + x + " " + y + " ");
System.out.println("\" />");
}
// Own path
System.out.print("\t<path stroke=\"" + COLORS[id] + "\" fill=\"none\" d=\"M");
} else {
System.out.print("L");
}
System.out.print(x + " " + y + " ");
}
System.out.println("\" />");
System.out.print("\t<path stroke=\"grey\" fill=\"none\" d=\"M" + x + " " + y + " ");
switch (direction) {
case RIGHT:
cx += 3;
break;
case DOWN:
cy += 3;
break;
case LEFT:
cx -= 3;
break;
case UP:
cy -= 3;
break;
}
}
}
private enum Direction {
RIGHT, DOWN, LEFT, UP
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment