Skip to content

Instantly share code, notes, and snippets.

@Glorfindel83

Glorfindel83/KnightsTour.java

Created May 31, 2019 09:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Glorfindel83/10529e6746e6091b854df23a173f3a1c to your computer and use it in GitHub Desktop.
Save Glorfindel83/10529e6746e6091b854df23a173f3a1c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
KnightsTour.java
package net.mathoverflow;
import java.util.HashMap;
import java.util.Map;
public class KnightsTour {
private static final int SIZE = 5; // odd number >= 5
private static final int MAX_WINDINGS = 4, UNIT = 16, HALF_BOARD_SIZE = (MAX_WINDINGS + 1) * SIZE - 1;
private static final java.awt.Point center = new java.awt.Point(UNIT * HALF_BOARD_SIZE, UNIT * HALF_BOARD_SIZE);
public static void main(String[] args) throws Exception {
// Compute tours on boxes
Board board = new Board(SIZE, SIZE).moveTo(new Point(0, 0));
tourPoints = new Point[board.numberOfFreeSquares];
for (int x = 0; x < board.width; x++) {
for (int y = 0; y < board.width; y++) {
Point point = new Point(x, y);
if (board.isOccupied(point))
continue;
computeToursFrom(board, point);
}
}
// Draw picture
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 + "\">");
// Patterns
System.out.println("\t<defs>");
System.out.println("\t<pattern id=\"grayed-out\" patternUnits=\"userSpaceOnUse\" width=\"3\" height=\"3\">");
System.out.println("\t\t<line stroke=\"#DDD\" x1=\"0\" y1=\"0\" x2=\"3\" y2=\"3\"/>");
System.out.println("\t</pattern>");
System.out.println("\t</defs>");
// Grid
int gridStart = UNIT / 2, gridEnd = UNIT * HALF_BOARD_SIZE * 2 - UNIT / 2;
for (int i = gridStart; i <= gridEnd; i += UNIT) {
boolean boxStart = ((UNIT * HALF_BOARD_SIZE - i) * 2 / UNIT) % SIZE == 0;
if (boxStart && firstBoxStart == null) {
firstBoxStart = i;
}
String color = boxStart ? "#BBB" : "#DDD";
System.out.println("\t<line stroke=\"" + color + "\" x1=\"" + gridStart + "\" y1=\"" + i + "\" x2=\""
+ gridEnd + "\" y2=\"" + i + "\" />");
System.out.println("\t<line stroke=\"" + color + "\" x1=\"" + i + "\" y1=\"" + gridStart + "\" x2=\"" + i
+ "\" y2=\"" + gridEnd + "\" />");
}
// Missing points
for (int i = firstBoxStart; i < gridEnd; i += UNIT * SIZE) {
if (i == 0)
continue;
for (int j = firstBoxStart; j < gridEnd; j += UNIT * SIZE) {
if (j == 0)
continue;
System.out.println("\t<rect style=\"fill: url(#grayed-out)\" x=\"" + i + "\" y=\"" + j + "\" height=\""
+ UNIT + "\" width=\"" + UNIT + "\" />");
}
}
// Winding
int wx = center.x + UNIT * SIZE / 2, wy = center.y + UNIT * SIZE / 2;
StringBuilder windings = new StringBuilder(
"\t<path stroke=\"black\" fill=\"none\" d=\"M" + wx + " " + wy + " ");
wx -= UNIT * SIZE;
windings.append("L" + wx + " " + wy + " ");
wy -= UNIT * SIZE;
windings.append("L" + wx + " " + wy + " ");
// Tour
Point start, end;
for (int winding = 0; winding <= MAX_WINDINGS; winding++) {
for (Direction direction : Direction.values()) {
switch (direction) {
case RIGHT:
wx += UNIT * SIZE * (2 + winding * 2);
if (winding == MAX_WINDINGS) {
wx -= UNIT * SIZE;
}
windings.append("L" + wx + " " + wy + " ");
for (int i = 0; i < winding; i++) {
print(new Point(0, SIZE - 2), new Point(SIZE - 1, SIZE - 1), "#0FF");
bx++;
print(new Point(1, SIZE - 2), new Point(SIZE - 2, SIZE - 1), "#08F");
bx++;
}
print(new Point(0, SIZE - 2), new Point(SIZE - 1, 0), "#808");
bx++;
break;
case DOWN:
wy += UNIT * SIZE * (2 + winding * 2);
for (int i = 0; i < winding; i++) {
print(new Point(1, 1), new Point(0, SIZE - 2), "#F00");
by++;
print(new Point(1, 0), new Point(0, SIZE - 1), "#F80");
by++;
}
print(new Point(1, 1), new Point(SIZE - 1, SIZE - 2), "#F08");
by++;
break;
case LEFT:
wx -= UNIT * SIZE * (3 + winding * 2);
for (int i = 0; i < winding + 1; i++) {
print(new Point(SIZE - 2, 0), new Point(1, 1), "#880");
bx--;
print(new Point(SIZE - 1, 0), new Point(0, 1), "#DD0");
bx--;
}
break;
case UP:
wy -= UNIT * SIZE * (3 + winding * 2);
print(new Point(SIZE - 2, 0), new Point(SIZE - 2, 1), "#80F");
by--;
for (int i = 0; i < winding; i++) {
print(new Point(SIZE - 1, SIZE - 1), new Point(SIZE - 1, 1), "#0F0");
by--;
print(new Point(SIZE - 2, SIZE - 1), new Point(SIZE - 2, 1), "#080");
by--;
}
print(new Point(SIZE - 1, SIZE - 1), new Point(1, 0), "#F0F");
by--;
break;
}
windings.append("L" + wx + " " + wy + " ");
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 void print(Point start, Point end, String color) {
Point[] tour = tours.get(start).get(end);
int x = 0, y = 0;
for (Point point : tour) {
x = center.x + UNIT * (bx * SIZE + point.x - SIZE / 2);
y = center.y + UNIT * (by * SIZE + point.y - SIZE / 2);
points.append(
"\n\t<circle fill=\"" + color + "\" cx=\"" + x + "\" cy=\"" + y + "\" r=\"" + UNIT / 8 + "\" />");
if (point.equals(start)) {
if (first) {
System.out.println("\t<circle fill=\"" + color + "\" 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=\"" + color + "\" 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 + " ");
}
private static void computeToursFrom(Board board, Point point) throws Exception {
tourPoints[0] = point;
tours.put(tourPoints[0], new HashMap<>());
loop(board.moveTo(tourPoints[0]), tourPoints[0], 1);
}
private static int bx = 0, by = 0;
private static boolean first = true;
private static Integer firstBoxStart;
private static final StringBuilder points = new StringBuilder();
private static Point[] tourPoints;
private static final Map<Point, Map<Point, Point[]>> tours = new HashMap<>();
private static void loop(Board board, Point point, int move) throws Exception {
if (board.numberOfFreeSquares == 0) {
Point finalPoint = tourPoints[tourPoints.length - 1];
if (!tours.get(tourPoints[0]).containsKey(finalPoint)) {
Point[] tour = new Point[tourPoints.length];
System.arraycopy(tourPoints, 0, tour, 0, tourPoints.length);
tours.get(tourPoints[0]).put(finalPoint, tour);
// System.out.println(point.x + ", " + point.y);
}
return;
}
for (int direction = 0; direction < 8; direction++) {
Point newPoint = new Point(point.x + DX[direction], point.y + DY[direction]);
Board newBoard = board.moveTo(newPoint);
if (newBoard == null)
continue;
tourPoints[move] = newPoint;
loop(newBoard, newPoint, move + 1);
}
}
private static final int[] DX = { 1, 2, 2, 1, -1, -2, -2, -1 }, DY = { -2, -1, 1, 2, 2, 1, -1, -2 };
/**
* <pre>
* column
* 1248....
* 0
* r 1
* o 2
* w 3
* 4
* </pre>
*/
private static class Board implements Cloneable {
public Board(int width, int height) {
this.width = width;
this.height = height;
numberOfFreeSquares = width * height;
rows = new long[height];
}
public final int width, height;
public int numberOfFreeSquares;
public long[] rows;
public boolean isOccupied(Point point) {
if (point.x < 0 || point.x >= width || point.y < 0 || point.y >= height)
return true;
return (rows[point.y] & (1 << point.x)) != 0;
}
public Board moveTo(Point point) throws Exception {
if (isOccupied(point))
return null;
Board board = (Board)super.clone();
board.rows = new long[rows.length];
System.arraycopy(rows, 0, board.rows, 0, rows.length);
board.rows[point.y] |= (1 << point.x);
board.numberOfFreeSquares--;
return board;
}
}
private static class Point {
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object object) {
if (!(object instanceof Point))
return false;
Point point = (Point)object;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return x + (y << 16);
}
@Override
public String toString() {
return "(" + (bx * SIZE + x) + ", " + (by * SIZE + y) + ")";
}
public final int x, y;
}
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