Hamilton Path アルゴリズム

こちらの記事で、Fabrice TIERCELIN氏が回答しているpythonコードをprocessingに変換しました。

// Source - https://stackoverflow.com/a
// Original author: Fabrice TIERCELIN (Python version, CC BY-SA 4.0)
// Ported to Processing (Java) by ChatGPT for Hextomino

Hamiltonian h;

void setup() {
  size(800, 800);
  background(0);
  // グリッドサイズを指定（例：20x20）
  h = new Hamiltonian(20, 20, 0, 0);
  h.generate(500);      // Python の h.generate(500) 相当
  h.printPath();        // コンソールに ASCII 表示
  noLoop();
}

void draw() {
  background(0);
  translate(40, 40);
  h.drawPath(30, 30);   // cellSize=30, node半径=30
}

// =======================
// Hamiltonian クラス本体
// =======================

enum Dir {
  NOWHERE,
  NORTH,
  EAST,
  SOUTH,
  WEST
}

class Point {
  int x, y;
  Point(int x, int y) { this.x = x; this.y = y; }
  
  boolean equals(Point other) {
    return other != null && this.x == other.x && this.y == other.y;
  }
}

class Pair {
  Point a, b;
  Pair(Point a, Point b) { this.a = a; this.b = b; }
  
  boolean equals(Pair other) {
    if (other == null) return false;
    return this.a.equals(other.a) && this.b.equals(other.b);
  }
}

class Hamiltonian {
  int gw, gh;          // grid width / height
  Point start;
  Dir[][] grid;
  ArrayList<Point> currLoop;
  boolean[][] inLoop;  // ループ内かどうかのフラグ
  
  Hamiltonian(int width, int height, int startX, int startY) {
    this.gw = width;
    this.gh = height;
    this.start = new Point(startX, startY);
    grid = new Dir[gw][gh];
    inLoop = new boolean[gw][gh];
    currLoop = new ArrayList<Point>();
    
    // zig-zag 初期パス
    for (int i = 0; i < gw; i++) {
      for (int j = 0; j < gh; j++) {
        grid[i][j] = zigZag(i, j);
      }
    }
    grid[start.x][start.y] = Dir.NOWHERE;
  }
  
  // Python: generate(self, count)
  void generate(int count) {
    for (int i = 0; i < count; i++) {
      Pair sp = splitGrid();
      if (sp == null) continue;    // 安全のため
      modifyPath(sp);
      Pair tu = mendGrid(sp);
      modifyPath(tu);
    }
  }
  
  // Python: _modify_path
  void modifyPath(Pair spl) {
    if (spl == null) return;
    Point ptA = spl.a;
    Point ptB = spl.b;
    Dir pta = grid[ptA.x][ptA.y];
    Dir ptb = grid[ptB.x][ptB.y];
    
    Dir orientation = pta;
    if (orientation == Dir.NORTH || orientation == Dir.SOUTH) {
      // 縦方向 → 横方向に変更
      if (ptA.x < ptB.x) {
        pta = Dir.EAST;
        ptb = Dir.WEST;
      } else {
        pta = Dir.WEST;
        ptb = Dir.EAST;
      }
    } else {
      // 横方向 → 縦方向に変更
      if (ptA.y < ptB.y) {
        pta = Dir.SOUTH;
        ptb = Dir.NORTH;
      } else {
        pta = Dir.NORTH;
        ptb = Dir.SOUTH;
      }
    }
    grid[ptA.x][ptA.y] = pta;
    grid[ptB.x][ptB.y] = ptb;
  }
  
  // Python: _move
  Point move(Point pt) {
    if (pt == null) return null;
    Dir d = grid[pt.x][pt.y];
    if (d != Dir.NOWHERE) {
      int nx = pt.x + dx(d);
      int ny = pt.y + dy(d);
      if (inBounds(nx, ny)) {
        return new Point(nx, ny);
      }
    }
    return null;
  }
  
  // Python: _set_loop
  boolean setLoop(Point start, Point stop) {
    currLoop.clear();
    // inLoop リセット
    for (int i = 0; i < gw; i++) {
      for (int j = 0; j < gh; j++) {
        inLoop[i][j] = false;
      }
    }
    
    Point point = start;
    int maxLen = gw * gh;
    while (point != null &&
           currLoop.size() <= maxLen &&
           !point.equals(stop) &&
           grid[point.x][point.y] != Dir.NOWHERE) {
      point = move(point);
      if (point != null) {
        currLoop.add(point);
        inLoop[point.x][point.y] = true;
      }
    }
    return (point != null && point.equals(stop));
  }
  
  // Python: _split_grid
  Pair splitGrid() {
    ArrayList<Pair> candidates = new ArrayList<Pair>();
    
    for (int x = 0; x < gw; x++) {
      for (int y = 0; y < gh; y++) {
        Point pt = new Point(x, y);
        Dir dx = grid[x][y];
        if (dx == Dir.NORTH) {
          int cx = x + 1;
          int cy = y - 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.SOUTH) {
            candidates.add(new Pair(pt, new Point(cx, cy)));
          }
        } else if (dx == Dir.SOUTH) {
          int cx = x + 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.NORTH) {
            candidates.add(new Pair(pt, new Point(cx, cy)));
          }
        } else if (dx == Dir.EAST) {
          int cx = x + 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.WEST) {
            candidates.add(new Pair(pt, new Point(cx, cy)));
          }
        } else if (dx == Dir.WEST) {
          int cx = x - 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.EAST) {
            candidates.add(new Pair(pt, new Point(cx, cy)));
          }
        }
      }
    }
    
    if (candidates.size() > 0) {
      int idx = (int)random(candidates.size());
      Pair chosen = candidates.get(idx);
      Point start = chosen.a;
      Point end = chosen.b;
      if (setLoop(start, end)) {
        return chosen;
      } else if (!setLoop(end, start)) {
        println("Cannot split. Loop failed.");
        return null;
      } else {
        return new Pair(end, start);
      }
    }
    return null;
  }
  
  // Python: _mend_grid
  Pair mendGrid(Pair sp) {
    ArrayList<Pair> candidates = new ArrayList<Pair>();
    
    for (int x = 0; x < gw; x++) {
      for (int y = 0; y < gh; y++) {
        Point pt = new Point(x, y);
        Dir dx = grid[x][y];
        boolean lx = inLoop[x][y];
        
        if (dx == Dir.NORTH) {
          int cx = x + 1;
          int cy = y - 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.SOUTH) {
            boolean rx = inLoop[cx][cy];
            if (rx != lx) {
              candidates.add(new Pair(pt, new Point(cx, cy)));
            }
          }
        } else if (dx == Dir.SOUTH) {
          int cx = x + 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.NORTH) {
            boolean rx = inLoop[cx][cy];
            if (rx != lx) {
              candidates.add(new Pair(pt, new Point(cx, cy)));
            }
          }
        } else if (dx == Dir.EAST) {
          int cx = x + 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.WEST) {
            boolean rx = inLoop[cx][cy];
            if (rx != lx) {
              candidates.add(new Pair(pt, new Point(cx, cy)));
            }
          }
        } else if (dx == Dir.WEST) {
          int cx = x - 1;
          int cy = y + 1;
          if (inBounds(cx, cy) && grid[cx][cy] == Dir.EAST) {
            boolean rx = inLoop[cx][cy];
            if (rx != lx) {
              candidates.add(new Pair(pt, new Point(cx, cy)));
            }
          }
        }
      }
    }
    
    // sp と同じペアを candidates から除外
    if (sp != null) {
      for (int i = candidates.size() - 1; i >= 0; i--) {
        Pair p = candidates.get(i);
        boolean same1 = p.a.equals(sp.a) && p.b.equals(sp.b);
        boolean same2 = p.a.equals(sp.b) && p.b.equals(sp.a);
        if (same1 || same2) {
          candidates.remove(i);
        }
      }
    }
    
    if (candidates.size() > 0) {
      int idx = (int)random(candidates.size());
      return candidates.get(idx);
    } else {
      return sp;
    }
  }
  
  // Python: _zig_zag
  Dir zigZag(int x, int y) {
    boolean even = (y % 2 == 0);
    if ((x == 0 && even) || (x == gw - 1 && !even)) {
      return Dir.NORTH;
    }
    return even ? Dir.WEST : Dir.EAST;
  }
  
  // Python: print_path
  void printPath() {
    String resultStr = "";
    for (int y = 0; y < gh; y++) {
      // 1行目：縦線
      for (int x = 0; x < gw; x++) {
        if ((grid[x][y] == Dir.NORTH) ||
            (y > 0 && grid[x][y - 1] == Dir.SOUTH)) {
          resultStr += " |";
        } else {
          resultStr += "  ";
        }
      }
      resultStr += " \n";
      // 2行目：横線 + ノード
      for (int x = 0; x < gw; x++) {
        if ((grid[x][y] == Dir.WEST) ||
            (x > 0 && grid[x - 1][y] == Dir.EAST)) {
          resultStr += "-O";
        } else {
          resultStr += " O";
        }
      }
      resultStr += " \n";
    }
    println(resultStr);
  }
  
  // 画面への描画
  void drawPath(float cellSize, float nodeSize) {
    stroke(255);
    strokeWeight(2);
    noFill();
    
    // エッジ（方向）を描画
    for (int x = 0; x < gw; x++) {
      for (int y = 0; y < gh; y++) {
        Dir d = grid[x][y];
        if (d != Dir.NOWHERE) {
          float cx = x * cellSize;
          float cy = y * cellSize;
          int nx = x + dx(d);
          int ny = y + dy(d);
          if (inBounds(nx, ny)) {
            float nxp = nx * cellSize;
            float nyp = ny * cellSize;
            line(cx, cy, nxp, nyp);
          }
        }
      }
    }
    
    // ノード描画
    noStroke();
    fill(0, 200, 255);
    for (int x = 0; x < gw; x++) {
      for (int y = 0; y < gh; y++) {
        float cx = x * cellSize;
        float cy = y * cellSize;
        ellipse(cx, cy, nodeSize * 0.2, nodeSize * 0.2);
      }
    }
    
    // start を強調
    fill(255, 50, 120);
    ellipse(start.x * cellSize, start.y * cellSize, nodeSize * 0.35, nodeSize * 0.35);
  }
  
  // ユーティリティ
  
  boolean inBounds(int x, int y) {
    return (0 <= x && x < gw && 0 <= y && y < gh);
  }
  
  int dx(Dir d) {
    switch(d) {
    case NORTH: return 0;
    case SOUTH: return 0;
    case EAST:  return 1;
    case WEST:  return -1;
    default:    return 0;
    }
  }
  
  int dy(Dir d) {
    switch(d) {
    case NORTH: return -1;
    case SOUTH: return 1;
    case EAST:  return 0;
    case WEST:  return 0;
    default:    return 0;
    }
  }
}

original.py

# Source - https://stackoverflow.com/a
# Posted by Fabrice TIERCELIN, modified by community. See post 'Timeline' for change history
# Retrieved 2025-11-18, License - CC BY-SA 4.0

import random
import enum

class From(enum.Enum):
    NOWHERE = 1
    NORTH = 2
    EAST = 3
    SOUTH = 4
    WEST = 5

class Hamiltonian:

    def __init__(self, width: int, height: int, start: tuple = (0, 0)):
        self.arcs = {From.NORTH: (0, -1), From.SOUTH: (0, 1), From.EAST: (1, 0), From.WEST: (-1, 0)}
        self.width = width
        self.height = height
        self.start = start
        self.grid = {(i, j): self._zig_zag(i, j) for i in range(width) for j in range(height)}
        self.grid[start] = From.NOWHERE
        self.curr_loop = []

    def generate(self, count: int = 100):
        for i in range(count):
            sp = self._split_grid()
            self._modify_path(sp)
            tu = self._mend_grid(sp)
            self._modify_path(tu)

    def _modify_path(self, spl):
        pt_a, pt_b = spl
        pta, ptb = self.grid[pt_a], self.grid[pt_b]
        orientation = pta
        if orientation in [From.NORTH, From.SOUTH]:
            if pt_a[0] < pt_b[0]:
                pta, ptb = From.EAST, From.WEST
            else:
                pta, ptb = From.WEST, From.EAST
        else:
            if pt_a[1] < pt_b[1]:
                pta, ptb = From.SOUTH, From.NORTH
            else:
                pta, ptb = From.NORTH, From.SOUTH
        self.grid[pt_a] = pta
        self.grid[pt_b] = ptb

    def _move(self, pt) -> [tuple, None]:
        if pt in self.grid and self.grid[pt] != From.NOWHERE:
            (x, y), (dx, dy) = pt, self.arcs[self.grid[pt]]
            if (x + dx, y + dy) in self.grid:
                return x + dx, y + dy
        return None

    def _set_loop(self, start, stop):
        self.curr_loop = []
        point = start
        while point and len(self.curr_loop) <= len(self.grid) and point != stop and self.grid[point] != From.NOWHERE:
            point = self._move(point)
            self.curr_loop.append(point)
        return point == stop

    def _split_grid(self) -> tuple:
        candidates = []
        for pt, dx in self.grid.items():
            x, y = pt
            if dx == From.NORTH:
                cx = (x+1, y - 1)
                if cx in self.grid and self.grid[cx] == From.SOUTH:
                    candidates.append((pt, cx))
            elif dx == From.SOUTH:
                cx = (x+1, y + 1)
                if cx in self.grid and self.grid[cx] == From.NORTH:
                    candidates.append((pt, cx))
            elif dx == From.EAST:
                cx = (x + 1, y + 1)
                if cx in self.grid and self.grid[cx] == From.WEST:
                    candidates.append((pt, cx))
            elif dx == From.WEST:
                cx = (x - 1, y + 1)
                if cx in self.grid and self.grid[cx] == From.EAST:
                    candidates.append((pt, cx))
        if len(candidates) > 0:
            start, end = random.choice(candidates)
            if self._set_loop(start, end):
                return start, end
            elif not self._set_loop(end, start):
                raise Exception('Cannot split. Loop failed.')
            return end, start

    def _mend_grid(self, sp):
        candidates = []
        for pt, dx in self.grid.items():
            (x, y), lx = pt, pt in self.curr_loop
            if dx == From.NORTH:
                cx = (x+1, y - 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.SOUTH and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.SOUTH:
                cx = (x+1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.NORTH and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.EAST:
                cx = (x + 1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.WEST and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.WEST:
                cx = (x - 1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.EAST and rx != lx:
                    candidates.append((pt, cx))
        a, b = sp
        if (a, b) in candidates:
            candidates.remove((a, b))
        elif (b, a) in candidates:
            candidates.remove((b, a))
        if len(candidates) > 0:
            return random.choice(candidates)
        else:
            return sp

    def _zig_zag(self, x: int, y: int) -> From:
        even = y % 2 == 0
        if (x == 0 and even) or (x == self.width - 1 and not even):
            return From.NORTH
        return From.WEST if even else From.EAST

    def print_path(self):
        result_str = ''
        for y in range(self.height):
            for x in range(self.width):
                if (self.grid[x, y] == From.NORTH) or ((y > 0) and (self.grid[x, y - 1] == From.SOUTH)):
                    result_str = result_str + ' |'
                else:
                    result_str = result_str + '  '
            result_str = result_str + ' \n'
            for x in range(self.width):
                if (self.grid[x, y] == From.WEST) or ((x > 0) and (self.grid[x - 1, y] == From.EAST)):
                    result_str = result_str + '-O'
                else:
                    result_str = result_str + ' O'
            result_str = result_str + ' \n'
        print(result_str)


if __name__ == '__main__':
    h = Hamiltonian(5, 5)
    h.generate(500)
    h.print_path()