Skip to content

Instantly share code, notes, and snippets.

@coopermayne

coopermayne/generate_puzzle_json.py

Created January 28, 2026 03:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save coopermayne/bab15c1e02f3265587b31e3f59d16759 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save coopermayne/bab15c1e02f3265587b31e3f59d16759 to your computer and use it in GitHub Desktop.
Download ZIP
Two Not Touch Puzzle Generator - JSON Output
Raw
generate_puzzle_json.py
#!/usr/bin/env python3
"""
Two Not Touch Puzzle Generator - JSON Output
Generates a puzzle and outputs JSON with: puzzle, solution, steps
Usage:
python generate_puzzle_json.py # Output to stdout
python generate_puzzle_json.py > puzzle.json # Save to file
"""
import json
import random
import sys
from typing import List, Tuple, Optional, Set
from collections import deque
from itertools import combinations
# ============================================================================
# Constants
# ============================================================================
GRID_SIZE = 10
STARS_PER_UNIT = 2
NUM_REGIONS = 10
# ============================================================================
# Core Helpers
# ============================================================================
def get_neighbors(r: int, c: int, include_diagonal: bool = True) -> List[Tuple[int, int]]:
"""Get all neighboring cells."""
neighbors = []
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
if dr == 0 and dc == 0:
continue
if not include_diagonal and abs(dr) + abs(dc) == 2:
continue
nr, nc = r + dr, c + dc
if 0 <= nr < GRID_SIZE and 0 <= nc < GRID_SIZE:
neighbors.append((nr, nc))
return neighbors
def is_valid_star_placement(stars: Set[Tuple[int, int]], r: int, c: int) -> bool:
"""Check if placing a star at (r, c) is valid given existing stars."""
for sr, sc in stars:
if abs(sr - r) <= 1 and abs(sc - c) <= 1:
return False
return True
# ============================================================================
# Region Generation
# ============================================================================
def generate_random_regions() -> List[List[int]]:
"""Generate random connected regions using a seed-and-grow approach."""
regions = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
region_cells = [[] for _ in range(NUM_REGIONS)]
# Place initial seeds spread across the grid
seeds = []
positions = [(r, c) for r in range(GRID_SIZE) for c in range(GRID_SIZE)]
random.shuffle(positions)
for r, c in positions:
if len(seeds) >= NUM_REGIONS:
break
too_close = False
for sr, sc in seeds:
if abs(sr - r) + abs(sc - c) < 2:
too_close = True
break
if not too_close:
seeds.append((r, c))
while len(seeds) < NUM_REGIONS:
r, c = random.randint(0, GRID_SIZE-1), random.randint(0, GRID_SIZE-1)
if (r, c) not in seeds:
seeds.append((r, c))
for i, (r, c) in enumerate(seeds):
regions[r][c] = i
region_cells[i].append((r, c))
target_sizes = [5, 6, 8, 9, 10, 10, 11, 12, 14, 15]
random.shuffle(target_sizes)
for _ in range(GRID_SIZE * GRID_SIZE * 2):
unassigned = sum(1 for r in range(GRID_SIZE) for c in range(GRID_SIZE) if regions[r][c] == -1)
if unassigned == 0:
break
order = list(range(NUM_REGIONS))
random.shuffle(order)
grew = False
for region_id in order:
if len(region_cells[region_id]) >= target_sizes[region_id]:
continue
frontier = []
for r, c in region_cells[region_id]:
for nr, nc in get_neighbors(r, c, include_diagonal=False):
if regions[nr][nc] == -1:
frontier.append((nr, nc))
if frontier:
nr, nc = random.choice(list(set(frontier)))
regions[nr][nc] = region_id
region_cells[region_id].append((nr, nc))
grew = True
if not grew:
for region_id in order:
frontier = []
for r, c in region_cells[region_id]:
for nr, nc in get_neighbors(r, c, include_diagonal=False):
if regions[nr][nc] == -1:
frontier.append((nr, nc))
if frontier:
nr, nc = random.choice(list(set(frontier)))
regions[nr][nc] = region_id
region_cells[region_id].append((nr, nc))
grew = True
break
if not grew:
for r in range(GRID_SIZE):
for c in range(GRID_SIZE):
if regions[r][c] == -1:
for nr, nc in get_neighbors(r, c, include_diagonal=False):
if regions[nr][nc] != -1:
rid = regions[nr][nc]
regions[r][c] = rid
region_cells[rid].append((r, c))
grew = True
break
if grew:
break
if grew:
break
return regions
def is_region_connected(regions: List[List[int]], region_id: int) -> bool:
"""Check if a region is connected (using orthogonal adjacency)."""
cells = [(r, c) for r in range(GRID_SIZE) for c in range(GRID_SIZE)
if regions[r][c] == region_id]
if not cells:
return False
visited = {cells[0]}
queue = deque([cells[0]])
cells_set = set(cells)
while queue:
r, c = queue.popleft()
for nr, nc in get_neighbors(r, c, include_diagonal=False):
if (nr, nc) in cells_set and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc))
return len(visited) == len(cells)
def all_regions_connected(regions: List[List[int]]) -> bool:
"""Check if all regions are connected."""
return all(is_region_connected(regions, i) for i in range(NUM_REGIONS))
# ============================================================================
# Solution Finding & Validation
# ============================================================================
def count_solutions(regions: List[List[int]], max_count: int = 2) -> int:
"""Count solutions using backtracking with pruning."""
solution_count = [0]
def solve(row: int, stars: Set[Tuple[int, int]], col_counts: List[int],
region_counts: List[int]) -> None:
if solution_count[0] >= max_count:
return
if row == GRID_SIZE:
solution_count[0] += 1
return
row_stars = sum(1 for (r, c) in stars if r == row)
if row_stars == STARS_PER_UNIT:
solve(row + 1, stars, col_counts, region_counts)
return
needed = STARS_PER_UNIT - row_stars
valid_cols = []
for col in range(GRID_SIZE):
if (row, col) in stars:
continue
if col_counts[col] >= STARS_PER_UNIT:
continue
region_id = regions[row][col]
if region_counts[region_id] >= STARS_PER_UNIT:
continue
if not is_valid_star_placement(stars, row, col):
continue
valid_cols.append(col)
if len(valid_cols) < needed:
return
for combo in combinations(valid_cols, needed):
valid = True
for i in range(len(combo)):
for j in range(i + 1, len(combo)):
if abs(combo[i] - combo[j]) <= 1:
valid = False
break
if not valid:
break
if not valid:
continue
combo_region_counts = {}
for col in combo:
rid = regions[row][col]
combo_region_counts[rid] = combo_region_counts.get(rid, 0) + 1
region_valid = True
for rid, count in combo_region_counts.items():
if region_counts[rid] + count > STARS_PER_UNIT:
region_valid = False
break
if not region_valid:
continue
new_stars = stars.copy()
new_col_counts = col_counts.copy()
new_region_counts = region_counts.copy()
for col in combo:
new_stars.add((row, col))
new_col_counts[col] += 1
new_region_counts[regions[row][col]] += 1
solve(row + 1, new_stars, new_col_counts, new_region_counts)
if solution_count[0] >= max_count:
return
solve(0, set(), [0] * GRID_SIZE, [0] * GRID_SIZE)
return solution_count[0]
def solve_puzzle(regions: List[List[int]]) -> Optional[List[List[int]]]:
"""Solve a puzzle and return the solution grid, or None if unsolvable."""
result = [None]
def solve(row: int, solution: List[List[int]], stars: Set[Tuple[int, int]],
col_counts: List[int], region_counts: List[int]) -> bool:
if row == GRID_SIZE:
result[0] = [r[:] for r in solution]
return True
row_stars = sum(1 for (r, c) in stars if r == row)
if row_stars == STARS_PER_UNIT:
return solve(row + 1, solution, stars, col_counts, region_counts)
needed = STARS_PER_UNIT - row_stars
valid_cols = []
for col in range(GRID_SIZE):
if (row, col) in stars:
continue
if col_counts[col] >= STARS_PER_UNIT:
continue
region_id = regions[row][col]
if region_counts[region_id] >= STARS_PER_UNIT:
continue
if not is_valid_star_placement(stars, row, col):
continue
valid_cols.append(col)
if len(valid_cols) < needed:
return False
for combo in combinations(valid_cols, needed):
valid = True
for i in range(len(combo)):
for j in range(i + 1, len(combo)):
if abs(combo[i] - combo[j]) <= 1:
valid = False
break
if not valid:
break
if not valid:
continue
combo_region_counts = {}
for col in combo:
rid = regions[row][col]
combo_region_counts[rid] = combo_region_counts.get(rid, 0) + 1
region_valid = True
for rid, count in combo_region_counts.items():
if region_counts[rid] + count > STARS_PER_UNIT:
region_valid = False
break
if not region_valid:
continue
new_stars = stars.copy()
new_col_counts = col_counts.copy()
new_region_counts = region_counts.copy()
for col in combo:
solution[row][col] = 1
new_stars.add((row, col))
new_col_counts[col] += 1
new_region_counts[regions[row][col]] += 1
if solve(row + 1, solution, new_stars, new_col_counts, new_region_counts):
return True
for col in combo:
solution[row][col] = 0
return False
solution = [[0] * GRID_SIZE for _ in range(GRID_SIZE)]
if solve(0, solution, set(), [0] * GRID_SIZE, [0] * GRID_SIZE):
return result[0]
return None
# ============================================================================
# Logic Solver with Step Tracking
# ============================================================================
def solve_with_logic(regions: List[List[int]], track_steps: bool = False) -> Tuple[Optional[List[List[int]]], bool, List[str]]:
"""Attempt to solve puzzle using only logical deduction (no guessing)."""
state = [[0] * GRID_SIZE for _ in range(GRID_SIZE)]
steps = []
region_cells_map = {}
for r in range(GRID_SIZE):
for c in range(GRID_SIZE):
rid = regions[r][c]
if rid not in region_cells_map:
region_cells_map[rid] = []
region_cells_map[rid].append((r, c))
def cell_name(r: int, c: int) -> str:
return f"row {r+1}, column {chr(65+c)}"
def describe_region(region_id: int) -> str:
cells = region_cells_map[region_id]
size = len(cells)
min_r = min(r for r, c in cells)
max_r = max(r for r, c in cells)
min_c = min(c for r, c in cells)
max_c = max(c for r, c in cells)
center_r = (min_r + max_r) / 2
center_c = (min_c + max_c) / 2
if center_r < 3:
vert = "top"
elif center_r > 6:
vert = "bottom"
else:
vert = "middle"
if center_c < 3:
horiz = "left"
elif center_c > 6:
horiz = "right"
else:
horiz = "center"
if vert == "middle" and horiz == "center":
position = "center"
elif vert == "middle":
position = horiz + " side"
elif horiz == "center":
position = vert
else:
position = vert + "-" + horiz
height = max_r - min_r + 1
width = max_c - min_c + 1
if size == 2:
shape = "2-cell"
elif size == 3:
if height == 1:
shape = "3-cell horizontal"
elif width == 1:
shape = "3-cell vertical"
else:
shape = "L-shaped"
elif size == 4:
if height == 2 and width == 2:
shape = "2x2 square"
elif height == 1 or width == 1:
shape = "4-cell line"
else:
shape = "4-cell"
elif size <= 6:
shape = f"small {size}-cell"
else:
shape = f"{size}-cell"
return f"the {shape} region in the {position}"
def get_unknown_cells(cells: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
return [(r, c) for r, c in cells if state[r][c] == 0]
def get_star_count(cells: List[Tuple[int, int]]) -> int:
return sum(1 for r, c in cells if state[r][c] == 1)
def get_row_cells(row: int) -> List[Tuple[int, int]]:
return [(row, c) for c in range(GRID_SIZE)]
def get_col_cells(col: int) -> List[Tuple[int, int]]:
return [(r, col) for r in range(GRID_SIZE)]
def get_region_cells(region_id: int) -> List[Tuple[int, int]]:
return region_cells_map[region_id]
def eliminate(r: int, c: int, reason: str = "") -> bool:
if state[r][c] == 0:
state[r][c] = -1
return True
return False
def place_star(r: int, c: int, reason: str = "") -> bool:
if state[r][c] == 0:
state[r][c] = 1
for nr, nc in get_neighbors(r, c, include_diagonal=True):
eliminate(nr, nc)
return True
return False
def is_adjacent(r1: int, c1: int, r2: int, c2: int) -> bool:
return abs(r1 - r2) <= 1 and abs(c1 - c2) <= 1 and (r1, c1) != (r2, c2)
def add_step(msg: str, priority: str = "low"):
if track_steps:
steps.append((priority, msg))
def get_condensed_steps() -> List[str]:
condensed = []
i = 0
while i < len(steps):
priority, msg = steps[i]
if priority == "high":
condensed.append(msg)
i += 1
continue
if "3 cells in a" in msg and "line" in msg:
region_desc = msg.split(",")[0] if "," in msg else msg.split(".")[0]
count = 1
j = i + 1
while j < len(steps):
_, next_msg = steps[j]
if "3 cells in a" in next_msg and region_desc.split()[1:4] == next_msg.split()[1:4]:
count += 1
j += 1
else:
break
if count > 1:
region_part = msg.split(",")[0].replace("In ", "")
condensed.append(f"In {region_part}, eliminate the middle cells of any 3-in-a-line patterns ({count} cells eliminated).")
i = j
continue
if "touches every other" in msg or "wouldn't be enough" in msg:
condensed.append(msg)
i += 1
return condensed
def apply_rules() -> bool:
progress = False
all_groups = []
for row in range(GRID_SIZE):
all_groups.append(('row', row, get_row_cells(row)))
for col in range(GRID_SIZE):
all_groups.append(('col', col, get_col_cells(col)))
for region_id in range(NUM_REGIONS):
all_groups.append(('region', region_id, get_region_cells(region_id)))
for group_type, group_id, cells in all_groups:
unknown = get_unknown_cells(cells)
stars = get_star_count(cells)
needed = STARS_PER_UNIT - stars
if group_type == 'row':
group_name = f"row {group_id+1}"
elif group_type == 'col':
group_name = f"column {chr(65+group_id)}"
else:
group_name = describe_region(group_id)
if needed <= 0:
if unknown:
add_step(f"Since {group_name} already has 2 stars, we can eliminate the remaining open cells in it.", "medium")
for r, c in unknown:
if eliminate(r, c):
progress = True
continue
if len(unknown) == needed:
can_place = True
for i, (r1, c1) in enumerate(unknown):
for r2, c2 in unknown[i+1:]:
if is_adjacent(r1, c1, r2, c2):
can_place = False
break
if can_place:
if needed == 2:
add_step(f"Look at {group_name}. There are only 2 open cells left, and we need 2 stars. Since they don't touch each other, both must be stars!", "high")
else:
add_step(f"In {group_name}, there's only 1 open cell left and we still need a star. Place a star there.", "high")
for r, c in unknown:
if place_star(r, c):
progress = True
continue
for r, c in unknown:
if state[r][c] != 0:
continue
others = [cell for cell in unknown if cell != (r, c)]
if others and all(is_adjacent(r, c, rr, cc) for rr, cc in others):
if group_type == 'region':
add_step(f"In {group_name}, notice the cell at {cell_name(r,c)} touches every other open cell. If we put a star there, there'd be no room for the second star. Eliminate it.", "medium")
else:
add_step(f"The cell at {cell_name(r,c)} in {group_name} is adjacent to all other open cells there. Eliminate it.", "low")
if eliminate(r, c):
progress = True
for r, c in unknown:
if state[r][c] != 0:
continue
remaining = [cell for cell in unknown
if cell != (r, c) and not is_adjacent(r, c, cell[0], cell[1])]
if len(remaining) < needed - 1:
add_step(f"If we placed a star at {cell_name(r,c)} in {group_name}, there wouldn't be enough non-touching cells left for the remaining star(s). Eliminate it.", "medium")
if eliminate(r, c):
progress = True
for group_type, group_id, cells in all_groups:
unknown = get_unknown_cells(cells)
stars = get_star_count(cells)
needed = STARS_PER_UNIT - stars
if group_type == 'row':
group_name = f"row {group_id+1}"
elif group_type == 'col':
group_name = f"column {chr(65+group_id)}"
else:
group_name = describe_region(group_id)
if needed == 1 and len(unknown) == 2:
(r1, c1), (r2, c2) = unknown
if abs(r1 - r2) + abs(c1 - c2) == 1:
eliminated_any = False
for r in range(GRID_SIZE):
for c in range(GRID_SIZE):
if state[r][c] == 0 and (r, c) != (r1, c1) and (r, c) != (r2, c2):
if is_adjacent(r, c, r1, c1) and is_adjacent(r, c, r2, c2):
if not eliminated_any:
add_step(f"In {group_name}, the last star must go in one of two adjacent cells. Any cell touching both of them can be eliminated.", "medium")
eliminated_any = True
if eliminate(r, c):
progress = True
for region_id in range(NUM_REGIONS):
region_name = describe_region(region_id)
cells = get_region_cells(region_id)
unknown = get_unknown_cells(cells)
for r, c in unknown:
if state[r][c] != 0:
continue
if (r, c-1) in unknown and (r, c+1) in unknown:
add_step(f"In {region_name}, there are 3 cells in a horizontal line. The middle cell at {cell_name(r,c)} can't be a star - it would touch both neighbors, leaving no room for the second star. Eliminate it.", "low")
if eliminate(r, c):
progress = True
elif (r-1, c) in unknown and (r+1, c) in unknown:
add_step(f"In {region_name}, there are 3 cells in a vertical line. The middle cell can't be a star for the same reason. Eliminate it.", "low")
if eliminate(r, c):
progress = True
return progress
max_iterations = GRID_SIZE * GRID_SIZE * 4
for _ in range(max_iterations):
if not apply_rules():
break
total_stars = sum(1 for r in range(GRID_SIZE) for c in range(GRID_SIZE) if state[r][c] == 1)
solved = (total_stars == GRID_SIZE * STARS_PER_UNIT)
solution = [[max(0, state[r][c]) for c in range(GRID_SIZE)] for r in range(GRID_SIZE)]
final_steps = get_condensed_steps() if track_steps else []
return solution, solved, final_steps
def get_solving_steps(regions: List[List[int]]) -> List[str]:
"""Get human-readable steps for solving the puzzle."""
_, _, steps = solve_with_logic(regions, track_steps=True)
return steps
def has_logical_start(regions: List[List[int]]) -> bool:
"""Check if puzzle has at least one logical starting move."""
region_cells = {}
for r in range(GRID_SIZE):
for c in range(GRID_SIZE):
rid = regions[r][c]
if rid not in region_cells:
region_cells[rid] = []
region_cells[rid].append((r, c))
for rid, cells in region_cells.items():
if len(cells) == 2:
(r1, c1), (r2, c2) = cells
if abs(r1 - r2) > 1 or abs(c1 - c2) > 1:
return True
if len(cells) == 3:
cells_sorted = sorted(cells)
if (cells_sorted[0][0] == cells_sorted[1][0] == cells_sorted[2][0] and
cells_sorted[2][1] - cells_sorted[0][1] == 2):
return True
if (cells_sorted[0][1] == cells_sorted[1][1] == cells_sorted[2][1] and
cells_sorted[2][0] - cells_sorted[0][0] == 2):
return True
for r, c in cells:
others = [(rr, cc) for rr, cc in cells if (rr, cc) != (r, c)]
if all(abs(r - rr) <= 1 and abs(c - cc) <= 1 for rr, cc in others):
return True
if len(cells) == 4:
rows = [r for r, c in cells]
cols = [c for r, c in cells]
if max(rows) - min(rows) == 1 and max(cols) - min(cols) == 1:
return True
if len(cells) <= 5:
return True
return False
# ============================================================================
# Main Puzzle Generator
# ============================================================================
def generate_puzzle() -> Tuple[List[List[int]], List[List[int]]]:
"""Generate a complete Two Not Touch puzzle."""
max_attempts = 2000
for attempt in range(max_attempts):
regions = generate_random_regions()
if not all_regions_connected(regions):
continue
num_solutions = count_solutions(regions, max_count=2)
if num_solutions != 1:
continue
if not has_logical_start(regions):
continue
solution = solve_puzzle(regions)
if solution:
return regions, solution
raise RuntimeError("Failed to generate puzzle after maximum attempts")
def create_puzzle() -> dict:
"""
Generate a Two Not Touch puzzle and return as a dictionary.
Returns:
dict with keys:
- 'puzzle': 2D list (10x10) where each cell contains region ID (0-9)
- 'solution': 2D list (10x10) where 1 = star, 0 = empty
- 'steps': List of human-readable solving steps
"""
regions, solution = generate_puzzle()
steps = get_solving_steps(regions)
return {
'puzzle': regions,
'solution': solution,
'steps': steps
}
# ============================================================================
# Main Entry Point
# ============================================================================
if __name__ == "__main__":
puzzle_data = create_puzzle()
print(json.dumps(puzzle_data, indent=2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment