お絵かきロジック（イラストロジック）

10x10ぐらいなら使えるソルバ

バックトラッキング（深さ優先探索）
ヒントから「可能な行パターン」を列挙

例えばヒントが [3,1] なら、
●●●○●○○○○○
○●●●○●○○○○
○○●●●○●○○○
…
など、条件を満たしうる配列を全て生成
ArrayList generateRowPatterns(int[] clue, int width)
buildRowPatterns(...) 再帰で全列挙

列チェックを早い段階で入れて、計算量を削減
20×20を超えてくると、組み合わせ爆発
ヒントが [1,1,1,1,1] などでは組み合わせ爆発

import java.util.*;  // ArrayList 用

// Picross / Nonogram 10x10
// EDIT mode: create puzzle by clicking cells
// PLAY mode: solve the puzzle

final int W = 10;
final int H = 10;
final int CELL = 30;

final int MARGIN_LEFT = 80;
final int MARGIN_TOP  = 80;

int[][] solution = new int[H][W];  // 0 empty, 1 filled  (author's pattern)
int[][] player   = new int[H][W];  // 0 blank, 1 filled, 2 X-mark

String mode = "EDIT";  // "EDIT" or "PLAY"
String message = "";

// ---- solver state ----
int solverSolutionCount = 0;
int[][] solverFirstSolution = new int[H][W];

void setup() {
  size(640, 480);
  textAlign(CENTER, CENTER);
  textSize(14);
}

void draw() {
  background(240);
  
  drawGrid();
  
  if (mode.equals("EDIT")) {
    drawSolutionCells();
  } else {
    drawPlayerCells();
  }
  
  drawRowClues();
  drawColClues();

  // Mode display
  fill(0);
  textAlign(LEFT, TOP);
  text("MODE: " + mode, 10, 10);

  // Message
  if (message.length() > 0) {
    fill(200, 0, 0);
    text(message, 10, 30);
  }

  // Help text
  textAlign(LEFT, TOP);
  fill(0);
  int ty = height - 80;
  text("EDIT: L-click design / P: Play / C: Clear / V: Validate puzzle", 10, ty);
  text("PLAY: L=Fill, R=X / S: Check answer / E: Edit mode", 10, ty + 20);
}

//==================== Grid ====================

void drawGrid() {
  stroke(0);
  noFill();
  rect(MARGIN_LEFT, MARGIN_TOP, W * CELL, H * CELL);
  
  for (int x = 0; x <= W; x++) {
    int sx = MARGIN_LEFT + x * CELL;
    line(sx, MARGIN_TOP, sx, MARGIN_TOP + H * CELL);
  }
  for (int y = 0; y <= H; y++) {
    int sy = MARGIN_TOP + y * CELL;
    line(MARGIN_LEFT, sy, MARGIN_LEFT + W * CELL, sy);
  }
}

void drawSolutionCells() {
  noStroke();
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      if (solution[y][x] == 1) {
        fill(50);
        rect(MARGIN_LEFT + x * CELL + 1, MARGIN_TOP + y * CELL + 1,
             CELL - 2, CELL - 2);
      }
    }
  }
}

void drawPlayerCells() {
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      int v = player[y][x];
      int cx = MARGIN_LEFT + x * CELL;
      int cy = MARGIN_TOP + y * CELL;
      
      if (v == 1) {
        fill(50);
        noStroke();
        rect(cx + 1, cy + 1, CELL - 2, CELL - 2);
      } else if (v == 2) {
        noFill();
        stroke(150, 0, 0);
        strokeWeight(2);
        line(cx + 4, cy + 4, cx + CELL - 4, cy + CELL - 4);
        line(cx + CELL - 4, cy + 4, cx + 4, cy + CELL - 4);
        strokeWeight(1);
      }
    }
  }
}

//==================== Clues ====================

int[] getRowClue(int row) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  int run = 0;
  for (int x = 0; x < W; x++) {
    if (solution[row][x] == 1) {
      run++;
    } else {
      if (run > 0) {
        list.add(run);
        run = 0;
      }
    }
  }
  if (run > 0) list.add(run);
  if (list.size() == 0) list.add(0);

  int[] r = new int[list.size()];
  for (int i = 0; i < list.size(); i++) r[i] = list.get(i);
  return r;
}

int[] getColClue(int col) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  int run = 0;
  for (int y = 0; y < H; y++) {
    if (solution[y][col] == 1) {
      run++;
    } else {
      if (run > 0) {
        list.add(run);
        run = 0;
      }
    }
  }
  if (run > 0) list.add( run );
  if (list.size() == 0) list.add(0);

  int[] r = new int[list.size()];
  for (int i = 0; i < list.size(); i++) r[i] = list.get(i);
  return r;
}

void drawRowClues() {
  textAlign(RIGHT, CENTER);
  fill(0);
  for (int y = 0; y < H; y++) {
    int[] clue = getRowClue(y);
    int baseX = MARGIN_LEFT - 10;
    int cy = MARGIN_TOP + y * CELL + CELL / 2;
    for (int i = 0; i < clue.length; i++) {
      int vx = baseX - i * 20;
      text(clue[clue.length - 1 - i], vx, cy);
    }
  }
}

void drawColClues() {
  textAlign(CENTER, BOTTOM);
  fill(0);
  for (int x = 0; x < W; x++) {
    int[] clue = getColClue(x);
    int baseY = MARGIN_TOP - 10;
    int cx = MARGIN_LEFT + x * CELL + CELL / 2;
    for (int i = 0; i < clue.length; i++) {
      int vy = baseY - i * 20;
      text(clue[clue.length - 1 - i], cx, vy);
    }
  }
}

//==================== Input ====================

void mousePressed() {
  if (mouseX < MARGIN_LEFT || mouseX >= MARGIN_LEFT + W * CELL) return;
  if (mouseY < MARGIN_TOP  || mouseY >= MARGIN_TOP + H * CELL) return;
  
  int gx = (mouseX - MARGIN_LEFT) / CELL;
  int gy = (mouseY - MARGIN_TOP)  / CELL;
  
  if (mode.equals("EDIT")) {
    // Toggle solution cell (0 <-> 1)
    if (mouseButton == LEFT) {
      solution[gy][gx] = 1 - solution[gy][gx];
    }
  } else {
    // PLAY mode
    if (mouseButton == LEFT) {
      // Toggle fill (0 <-> 1)
      player[gy][gx] = (player[gy][gx] == 1 ? 0 : 1);
    } else if (mouseButton == RIGHT) {
      // Toggle X (0 <-> 2)
      player[gy][gx] = (player[gy][gx] == 2 ? 0 : 2);
    }
  }
}

void keyPressed() {
  if (key == 'c' || key == 'C') {
    if (mode.equals("EDIT")) {
      clearSolution();
      message = "Solution cleared.";
    }
  }
  if (key == 'p' || key == 'P') {
    mode = "PLAY";
    clearPlayer();
    message = "PLAY mode.";
  }
  if (key == 'e' || key == 'E') {
    mode = "EDIT";
    message = "EDIT mode.";
  }
  if (key == 's' || key == 'S') {
    if (mode.equals("PLAY")) {
      if (checkSolvedByPlayer()) {
        message = "CLEAR!";
      } else {
        message = "Not solved yet.";
      }
    }
  }
  if (key == 'v' || key == 'V') {
    if (mode.equals("EDIT")) {
      validatePuzzleBySolver();
    }
  }
}

//==================== Helpers (play check) ====================

void clearSolution() {
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      solution[y][x] = 0;
    }
  }
}

void clearPlayer() {
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      player[y][x] = 0;
    }
  }
}

// check player's board vs author solution
boolean checkSolvedByPlayer() {
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      if (solution[y][x] == 1 && player[y][x] != 1) return false;
      if (solution[y][x] == 0 && player[y][x] == 1) return false;
    }
  }
  return true;
}

//==================== Solver part ====================

// called in EDIT mode: use clues from current solution[][]
void validatePuzzleBySolver() {
  // build clues (from current solution)
  int[][] rowClues = new int[H][];
  int[][] colClues = new int[W][];
  for (int y = 0; y < H; y++) rowClues[y] = getRowClue(y);
  for (int x = 0; x < W; x++) colClues[x] = getColClue(x);

  int[][] grid = new int[H][W]; // 0/1 grid for solver
  
  solverSolutionCount = 0;
  solveRow(0, rowClues, colClues, grid);

  if (solverSolutionCount == 0) {
    message = "No solution from clues.";
  } else if (solverSolutionCount == 1) {
    // compare first solution with author's pattern
    boolean same = true;
    for (int y = 0; y < H; y++) {
      for (int x = 0; x < W; x++) {
        if (solverFirstSolution[y][x] != solution[y][x]) {
          same = false;
          break;
        }
      }
      if (!same) break;
    }
    if (same) {
      message = "Exactly 1 solution (same as current).";
    } else {
      message = "Exactly 1 solution (different shape).";
    }
  } else {
    message = "Multiple solutions: " + solverSolutionCount;
  }
}

// backtracking over rows
void solveRow(int row, int[][] rowClues, int[][] colClues, int[][] grid) {
  if (solverSolutionCount > 2) return;  // we only care 0,1,2+ なので 3 以上は数えない

  if (row == H) {
    // all rows filled: check all columns exactly match clues
    for (int x = 0; x < W; x++) {
      if (!columnMatchesClue(grid, x, colClues[x])) return;
    }
    // valid full solution
    solverSolutionCount++;
    if (solverSolutionCount == 1) {
      // store first solution
      for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
          solverFirstSolution[y][x] = grid[y][x];
        }
      }
    }
    return;
  }

  int[] clue = rowClues[row];
  ArrayList<int[]> patterns = generateRowPatterns(clue, W);

  for (int[] pattern : patterns) {
    // put this pattern to grid[row][]
    for (int x = 0; x < W; x++) {
      grid[row][x] = pattern[x];
    }
    // check partial column consistency (rows 0..row)
    if (columnsPartiallyOK(grid, row, colClues)) {
      solveRow(row + 1, rowClues, colClues, grid);
    }
    if (solverSolutionCount > 2) return;
  }
}

// generate all row patterns of length width that match given clue
ArrayList<int[]> generateRowPatterns(int[] clue, int width) {
  ArrayList<int[]> res = new ArrayList<int[]>();

  // special case: clue = [0]
  if (clue.length == 1 && clue[0] == 0) {
    int[] row = new int[width];
    // all zeros
    res.add(row);
    return res;
  }

  int[] row = new int[width];
  buildRowPatterns(0, 0, clue, width, row, res);
  return res;
}

void buildRowPatterns(int pos, int clueIndex, int[] clue, int width,
                      int[] row, ArrayList<int[]> res) {
  if (clueIndex == clue.length) {
    // no more blocks: fill rest with 0
    for (int i = pos; i < width; i++) row[i] = 0;
    res.add(row.clone());
    return;
  }
  int len = clue[clueIndex];

  // minimum cells needed for remaining blocks including this one
  int remainingLen = 0;
  for (int i = clueIndex; i < clue.length; i++) remainingLen += clue[i];
  int blocksLeft = clue.length - clueIndex - 1;
  // for blocks after this, at least one 0 between them
  int minNeeded = remainingLen + blocksLeft;

  for (int start = pos; start <= width - minNeeded - len + remainingLen; start++) {
    // fill zeros up to start
    for (int i = pos; i < start; i++) row[i] = 0;
    // fill this block
    for (int i = start; i < start + len; i++) row[i] = 1;
    int nextPos = start + len + 1; // at least one 0 after block
    if (clueIndex == clue.length - 1) {
      nextPos = start + len; // last block: no forced space
    }
    buildRowPatterns(nextPos, clueIndex + 1, clue, width, row, res);
  }
}

// check column fully matches clue (for finished grid)
boolean columnMatchesClue(int[][] grid, int col, int[] clue) {
  ArrayList<Integer> runs = new ArrayList<Integer>();
  int run = 0;
  for (int y = 0; y < H; y++) {
    if (grid[y][col] == 1) {
      run++;
    } else {
      if (run > 0) {
        runs.add(run);
        run = 0;
      }
    }
  }
  if (run > 0) runs.add(run);
  if (runs.size() == 0) runs.add(0);

  if (runs.size() != clue.length) return false;
  for (int i = 0; i < clue.length; i++) {
    if (runs.get(i) != clue[i]) return false;
  }
  return true;
}

// partial check for columns up to row 'lastRow'
boolean columnsPartiallyOK(int[][] grid, int lastRow, int[][] colClues) {
  for (int x = 0; x < W; x++) {
    ArrayList<Integer> runs = new ArrayList<Integer>();
    int run = 0;
    for (int y = 0; y <= lastRow; y++) {
      if (grid[y][x] == 1) {
        run++;
      } else {
        if (run > 0) {
          runs.add(run);
          run = 0;
        }
      }
    }
    boolean lastIsOpen = false;
    if (run > 0) {
      runs.add(run);
      lastIsOpen = (grid[lastRow][x] == 1);
    }

    int[] clue = colClues[x];

    // too many runs already
    if (runs.size() > clue.length) return false;

    for (int i = 0; i < runs.size(); i++) {
      int r = runs.get(i);
      if (i < runs.size() - 1 || !lastIsOpen) {
        // completed run: must equal clue
        if (i >= clue.length) return false;
        if (r != clue[i]) return false;
      } else {
        // open run: must not exceed clue
        if (i >= clue.length) return false;
        if (r > clue[i]) return false;
      }
    }
  }
  return true;
}

イラストロジックの容量

「マリオのスーパーピクロス」では、なんと300問が用意されている。
問題を保存するフォーマットはどんなものが良いだろうか？

30x30サイズの下記画像で検証。

① 生データをビット列で表す場合（理想値）
1セル1bitなので、30x30 = 900 bit = 112.5 Byte
※サイズ決め打ちなので参考程度に

② 白黒のBMP
184 Byte
（ZIP圧縮した場合は 662 Byte）

③ 白黒のGIF
159 Byte
（これもいいかもしれない）

④ 白黒のPNG
284 Byte
（画像が小さすぎて、逆効果）

BMPファイルの中身

計184	BMPの内訳
14	BITMAPFILEHEADER
40	BITMAPINFOHEADER
8	Palette
122	画像データ

122 Byteの内容

1 bit / pixel
1行で30 bit
ただし、4 Byte境界の制限があるので、32 bit/行 = 4 Byte/行
30行あるので、4x30=120 Byte
余りの2 Byteはなんだろうか？
実害はないが、ファイル全体を8の倍数にするため？PhotoShopの仕様？