ソーマキューブ soma cube 240解を解く

ChatGPTが5.2になり、過去に解けなかった問題がすんなり解けるようになりました。

よくある、3x3x3の積み木パズルの240解です。

自分の手元には頂き物のエド・インター賢人パズルがあります。
他にも、100均の木で作った木製の自作があったり、
工作画用紙で作った、40年物があったりします。

一般にはsoma cubeという呼称があり、賢人パズルとは若干異なります。

何が違うかといえば、キューブが１種類違います。
賢人パズルにはO(オー)ミノがあり、Left Armがない。
soma cubeはその逆。

一見すると、Right Arm / Left Arm はねじれのある複雑な形状で、療法存在するsoma cubeのほうが、難しそうなのであるが、賢人パズルは何通りの解があるのだろうか。

ここで、somaCubeの場合、240通りの解がわかっている。

まず、somaCubeの240解を数え上げるプログラムを完成させ、ピース定義を変更することによって賢人パズルの解を数え上げたところ、

159,178

という数字が出た。
２つあるのはRight Arm / Left Armをそれぞれ入れ替えた結果であるが、胸像反転は除外しているので、同じ数字になるはずなのだが、何かがおかしい。
この数字があってる保証はないが、240より小さいということは、パズル難易度は上がってるといえる。

というわけで、オリジナルのsoma cubeのほうが、解のパターンは多いという結果となった。

プログラム

Processing 4

解くプログラムsoma2025.pdeと、表示するプログラムsoma2025visualize.pdeに分けた。

解く方の318行目のコメントアウトを消せば、以下のような240個のファイルが出力される。

solution_000.txt

TTT
LTZ
LLL

ABB
PPZ
PVZ

AAB
PAB
VVZ

表示するプログラムの下にdataフォルダを作って、その出力されたファイルを入れて実行する。
操作は左右のカーソルキーで240通りを切り替えできる。

まずは240解を出力するプログラムから。

:soma2025.pde

// Soma Cube solver (3x3x3) - count solutions
// T piece is fixed on an edge (position + orientation fixed).
// Processing(Java) sketch.

import java.util.*;

final int N = 3;                 // cube size
final int CELLS = N*N*N;         // 27
final int FULL_MASK = (1 << CELLS) - 1;

// Piece order: [T fixed], then others
final String[] PIECE_NAMES = { "T", "L", "Z", "A", "B", "P", "V" };

// 書き出し用
int solIndex = 0;

// Each piece is defined as a set of unit-cube coordinates (x,y,z) in some base orientation.
// We'll generate all 24 rotations and dedupe.
static class P3 {
  int x, y, z;
  P3(int x, int y, int z) {
    this.x=x;
    this.y=y;
    this.z=z;
  }
}

static class Placement {
  int mask; // 27-bit occupancy
  Placement(int mask) {
    this.mask = mask;
  }
}

HashMap<String, ArrayList<Placement>> placementsByPiece = new HashMap<String, ArrayList<Placement>>();

long solutionCount = 0;

// ---- utilities ----
int idx(int x, int y, int z) {
  return x + N*y + N*N*z;
}

boolean inBounds(int x, int y, int z) {
  return (0 <= x && x < N) && (0 <= y && y < N) && (0 <= z && z < N);
}

// Generate 24 cube rotations as functions (x,y,z)->(x',y',z') with axes permutations & signs.
// We build them from rotation matrices with determinant +1.
static class Rot {
  // matrix rows: each row is one of +/- unit axis of original
  int[][] m = new int[3][3];
  Rot(int[][] mm) {
    for (int r=0; r<3; r++) for (int c=0; c<3; c++) m[r][c]=mm[r][c];
  }
  P3 apply(P3 p) {
    int nx = m[0][0]*p.x + m[0][1]*p.y + m[0][2]*p.z;
    int ny = m[1][0]*p.x + m[1][1]*p.y + m[1][2]*p.z;
    int nz = m[2][0]*p.x + m[2][1]*p.y + m[2][2]*p.z;
    return new P3(nx, ny, nz);
  }
}

ArrayList<Rot> allRots24() {
  ArrayList<Rot> rots = new ArrayList<Rot>();
  int[][] axes = {
    { 1, 0, 0}, {-1, 0, 0},
    { 0, 1, 0}, { 0, -1, 0},
    { 0, 0, 1}, { 0, 0, -1}
  };
  // choose xAxis and yAxis orthogonal, zAxis = xAxis cross yAxis
  for (int i=0; i<axes.length; i++) {
    for (int j=0; j<axes.length; j++) {
      int[] ax = axes[i];
      int[] ay = axes[j];
      // dot = 0
      if (ax[0]*ay[0] + ax[1]*ay[1] + ax[2]*ay[2] != 0) continue;
      int[] az = cross(ax, ay);
      // must be unit axis (one of +/- basis) and non-zero
      if (isZero(az)) continue;

      int[][] m = new int[3][3];
      // rows are the new axes in terms of old axes
      m[0] = ax.clone();
      m[1] = ay.clone();
      m[2] = az.clone();

      // determinant must be +1 (proper rotation)
      if (det3(m) != 1) continue;

      rots.add(new Rot(m));
    }
  }
  // should be 24
  return rots;
}

int[] cross(int[] a, int[] b) {
  return new int[]{
    a[1]*b[2] - a[2]*b[1],
    a[2]*b[0] - a[0]*b[2],
    a[0]*b[1] - a[1]*b[0]
  };
}

boolean isZero(int[] v) {
  return v[0]==0 && v[1]==0 && v[2]==0;
}

int det3(int[][] m) {
  int a=m[0][0], b=m[0][1], c=m[0][2];
  int d=m[1][0], e=m[1][1], f=m[1][2];
  int g=m[2][0], h=m[2][1], i=m[2][2];
  return a*(e*i - f*h) - b*(d*i - f*g) + c*(d*h - e*g);
}

// Normalize a set of points: translate so min x,y,z become 0.
ArrayList<P3> normalize(ArrayList<P3> pts) {
  int minx=999, miny=999, minz=999;
  for (P3 p : pts) {
    minx = min(minx, p.x);
    miny = min(miny, p.y);
    minz = min(minz, p.z);
  }
  ArrayList<P3> out = new ArrayList<P3>();
  for (P3 p : pts) out.add(new P3(p.x - minx, p.y - miny, p.z - minz));
  return out;
}

// Key for dedup: sorted coordinates "x,y,z;..."
String keyOf(ArrayList<P3> pts) {
  ArrayList<String> s = new ArrayList<String>();
  for (P3 p : pts) s.add(p.x + "," + p.y + "," + p.z);
  Collections.sort(s);
  StringBuilder sb = new StringBuilder();
  for (String t : s) {
    sb.append(t).append(";");
  }
  return sb.toString();
}

// Build all unique orientations for a piece (as normalized point lists)
ArrayList<ArrayList<P3>> orientations(ArrayList<P3> base, ArrayList<Rot> rots) {
  HashSet<String> seen = new HashSet<String>();
  ArrayList<ArrayList<P3>> out = new ArrayList<ArrayList<P3>>();

  for (Rot r : rots) {
    ArrayList<P3> pts = new ArrayList<P3>();
    for (P3 p : base) pts.add(r.apply(p));
    pts = normalize(pts);
    String k = keyOf(pts);
    if (seen.add(k)) {
      out.add(pts);
    }
  }
  return out;
}

// Generate all placements (bitmasks) for a piece within 3x3x3
ArrayList<Placement> genPlacements(ArrayList<ArrayList<P3>> orients) {
  ArrayList<Placement> out = new ArrayList<Placement>();

  for (ArrayList<P3> o : orients) {
    int maxx=0, maxy=0, maxz=0;
    for (P3 p : o) {
      maxx = max(maxx, p.x);
      maxy = max(maxy, p.y);
      maxz = max(maxz, p.z);
    }
    for (int tx=0; tx <= (N-1 - maxx); tx++) {
      for (int ty=0; ty <= (N-1 - maxy); ty++) {
        for (int tz=0; tz <= (N-1 - maxz); tz++) {
          int mask = 0;
          boolean ok = true;
          for (P3 p : o) {
            int x = p.x + tx;
            int y = p.y + ty;
            int z = p.z + tz;
            if (!inBounds(x, y, z)) {
              ok=false;
              break;
            }
            int bit = 1 << idx(x, y, z);
            if ((mask & bit) != 0) {
              ok=false;
              break;
            }
            mask |= bit;
          }
          if (ok) out.add(new Placement(mask));
        }
      }
    }
  }

  // dedupe masks (different orientations/translations can coincide for symmetric pieces)
  HashSet<Integer> uniq = new HashSet<Integer>();
  ArrayList<Placement> dedup = new ArrayList<Placement>();
  for (Placement p : out) {
    if (uniq.add(p.mask)) dedup.add(p);
  }
  return dedup;
}

// ---- piece definitions (standard Soma pieces) ----
// NOTE: These are the canonical Soma pieces:
// V is the only tricube; the others are tetracubes.
ArrayList<P3> piece_T() {
  // T tetracube: 3 in a row + one attached to middle (planar)
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {1, 1, 0}
    });
}
ArrayList<P3> piece_L() {
  // L tetracube: 3 in a row + one attached at one end (planar)
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {2, 1, 0}
    });
}
ArrayList<P3> piece_Z() {
  // Z tetracube (planar): zigzag
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {1, 1, 0}, {2, 1, 0}
    });
}
ArrayList<P3> piece_A() {
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {1, 1, 0}, {1, 1, 1}
    });
}
ArrayList<P3> piece_B() {
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 1, 1}
    });
}
ArrayList<P3> piece_P() {
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}
    });
}
ArrayList<P3> piece_V() {
  // V tricube: 3 cubes making a corner (2 legs)
  return pts(new int[][]{
    {0, 0, 0}, {1, 0, 0}, {0, 1, 0}
    });
}

ArrayList<P3> pts(int[][] a) {
  ArrayList<P3> out = new ArrayList<P3>();
  for (int[] v : a) out.add(new P3(v[0], v[1], v[2]));
  return out;
}

// ---- solver ----
String[] solveOrder = { "L", "Z", "A", "B", "P", "V" }; // T is fixed

void setup() {
  size(600, 200);
  println("Soma Cube solver (T fixed) starting...");

  ArrayList<Rot> rots = allRots24();
  println("rotations: " + rots.size()); // should be 24

  // generate placements for each movable piece
  buildPlacements("L", piece_L(), rots);
  buildPlacements("Z", piece_Z(), rots);
  buildPlacements("A", piece_A(), rots);
  buildPlacements("B", piece_B(), rots);
  buildPlacements("P", piece_P(), rots);
  buildPlacements("V", piece_V(), rots);

  // fixed T mask:
  int fixedT = maskOfFixedT();
  println("Fixed T mask bits: " + Integer.bitCount(fixedT));

  // backtracking
  int occ = fixedT;
  backtrack(occ, new HashMap<String, Integer>());

  println("DONE. Solutions (with this fixed T): " + solutionCount);
  noLoop();
}

void draw() {
  background(240);
  fill(20);
  textSize(14);
  text("out on Console of kai", 20, 40);
  text("Solutions (T fixed): " + solutionCount, 20, 70);
}

void buildPlacements(String name, ArrayList<P3> base, ArrayList<Rot> rots) {
  ArrayList<ArrayList<P3>> orients = orientations(base, rots);
  ArrayList<Placement> pl = genPlacements(orients);
  placementsByPiece.put(name, pl);
  println(name + " orientations=" + orients.size() + " placements=" + pl.size());
}

int maskOfFixedT() {
  // fixed as: (0,0,0)(1,0,0)(2,0,0)(1,1,0)
  int mask = 0;
  int[][] cells = {
    {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {1, 1, 0}
  };
  for (int[] c : cells) {
    mask |= (1 << idx(c[0], c[1], c[2]));
  }
  return mask;
}

void backtrack(int occ, HashMap<String, Integer> chosen) {
  if (chosen.size() == solveOrder.length) {
    if (occ == FULL_MASK) {
      // ---- 反転（鏡像）を同一視：xミラーした解と比較して代表だけ数える ----
      String key  = solutionKey(chosen);
      String mkey = solutionKeyMirroredX(chosen);
      if (key.compareTo(mkey) <= 0) {
        //saveSolution(chosen, solIndex++);
        solutionCount++;
      }
    }
    return;
  }

  // choose next piece with minimum remaining placements (simple heuristic)
  String bestPiece = null;
  ArrayList<Placement> bestList = null;
  int bestCount = 1<<30;

  for (String p : solveOrder) {
    if (chosen.containsKey(p)) continue;
    ArrayList<Placement> list = placementsByPiece.get(p);
    int cnt = 0;
    for (Placement pl : list) {
      if ((pl.mask & occ) == 0) cnt++;
    }
    if (cnt < bestCount) {
      bestCount = cnt;
      bestPiece = p;
      bestList = list;
      if (bestCount == 0) break;
    }
  }

  if (bestCount == 0) return;

  for (Placement pl : bestList) {
    if ((pl.mask & occ) != 0) continue;
    chosen.put(bestPiece, pl.mask);          // ★「1」じゃなく mask を入れる
    backtrack(occ | pl.mask, chosen);
    chosen.remove(bestPiece);
  }
}


String solutionKey(HashMap<String, Integer> chosen) {
  int fixedT = maskOfFixedT();
  StringBuilder sb = new StringBuilder();
  sb.append("T:").append(hex8(fixedT)).append("|");
  for (String p : solveOrder) {
    sb.append(p).append(":").append(hex8(chosen.get(p))).append("|");
  }
  return sb.toString();
}

String solutionKeyMirroredX(HashMap<String, Integer> chosen) {
  int fixedT = maskOfFixedT();
  StringBuilder sb = new StringBuilder();
  sb.append("T:").append(hex8(mirrorMaskX(fixedT))).append("|");
  for (String p : solveOrder) {
    sb.append(p).append(":").append(hex8(mirrorMaskX(chosen.get(p)))).append("|");
  }
  return sb.toString();
}

String hex8(int v) {
  return String.format("%08X", v);
}

// xミラー: (x,y,z) -> (N-1-x, y, z)
int mirrorMaskX(int mask) {
  int out = 0;
  for (int z=0; z<N; z++) {
    for (int y=0; y<N; y++) {
      for (int x=0; x<N; x++) {
        int b = 1 << idx(x, y, z);
        if ((mask & b) != 0) {
          int nx = (N-1) - x;
          out |= (1 << idx(nx, y, z));
        }
      }
    }
  }
  return out;
}


void saveSolution(HashMap<String,Integer> chosen, int id){
  char[] cube = new char[27];
  Arrays.fill(cube, '.');

  // T
  fillMask(cube, maskOfFixedT(), 'T');

  // others
  for(String p : solveOrder){
    fillMask(cube, chosen.get(p), p.charAt(0));
  }

  String[] lines = new String[11];//必要十分
  int idx = 0;

  for(int z=0; z<3; z++){
    for(int y=0; y<3; y++){
      String line = "";
      for(int x=0; x<3; x++){
        line += cube[x + 3*y + 9*z];
      }
      lines[idx++] = line;
    }
    if(z < 2){
      lines[idx++] = ""; // 層の区切り
    }
  }

  saveStrings("solution_" + nf(id,3) + ".txt", lines);
}

void fillMask(char[] cube, int mask, char c){
  for(int i=0;i<27;i++){
    if((mask & (1<<i)) != 0){
      cube[i] = c;
    }
  }
}

以下が表示するプログラム

soma2025visualize.pde

int solIndex = 0;
char[][][] cube = new char[3][3][3]; // cube[z][y][x]

void setup() {
  size(800, 800, P3D);
  perspective(PI/6, 1, 1, 2000);

  loadSolution(solIndex);
}

void draw() {
  background(255);
  lights();

  // camera / rotation
  translate(width/2, height/2, -400);
  rotateX(-PI/6);
  rotateY(PI/4);

  float s = 55; // voxel size

  for (int z = 0; z < 3; z++) {
    for (int y = 0; y < 3; y++) {
      for (int x = 0; x < 3; x++) {
        char c = cube[z][y][x];
        if (c == 0) continue;

        color col = pieceColor(c);
        if (col == -1) {
          // 未定義文字はスキップ
          continue;
        }

        pushMatrix();
        translate((x-1)*s-100, (y-1)*s, (z-1)*s-100);
        fill(col);
        stroke(col,64);
        box(s * 0.95);
        popMatrix();

        pushMatrix();
        translate((x-1)*s+100, (y-1)*s*4, (z-1)*s+100);
        fill(col);
        stroke(col,64);
        box(s * 0.95);
        popMatrix();
      }
    }
  }
 
}

// ---- fixed colors (no HashMap) ----
color pieceColor(char c) {
  switch (c) {
    case 'T': return color(128, 255, 255);  // cyan
    case 'L': return color(255, 255,   0);  // yellow
    case 'Z': return color(255,   0,   0);  // red
    case 'A': return color(255, 128, 255);  // magenta
    case 'B': return color( 64,   0,   0);  // brown
    case 'P': return color(  0, 128,   0);  // green
    case 'V': return color(128, 255, 128);  // light green
    default:  return -1;                    // undefined
  }
}

// ---- load one solution file into cube[z][y][x] ----
void loadSolution(int idx) {
  // clear
  for (int z = 0; z < 3; z++)
    for (int y = 0; y < 3; y++)
      for (int x = 0; x < 3; x++)
        cube[z][y][x] = 0;

    String filename = "solution_" + nf(idx, 3) + ".txt";
    String[] lines = loadStrings(filename);
    if (lines == null) {
    println("File not found: data/" + filename);
    return;
  }

  int z = 0;
  int y = 0;

  for (int i = 0; i < lines.length; i++) {
    String line = lines[i];

    // blank line -> next layer
    if (line == null || line.trim().isEmpty()) {
      z++;
      y = 0;
      if (z >= 3) break;
      continue;
    }

    // safety: strip CR (Windows)
    line = line.replace("\r", "");

    // expect 3 chars
    if (line.length() < 3) continue;

    for (int x = 0; x < 3; x++) {
      char c = line.charAt(x);
      if (c == ' ') continue; // just in case
      cube[z][y][x] = c;
    }
    y++;
    if (y >= 3) y = 3; // clamp
  }
}

void keyPressed() {
  if (keyCode == RIGHT) {
    solIndex = (solIndex + 1) % 240;
    loadSolution(solIndex);
  } else if (keyCode == LEFT) {
    solIndex = (solIndex + 239) % 240;
    loadSolution(solIndex);
  }
}