This was intended to to find max-density still lifes and later modded to find still lifes with a certain population.
Code: Select all
"""
OR-Tools still life searcher
By: NNlk05
Find still lifes in Conway's Game of Life
Versions:
1.0.0 (2026-7-17): Release
OR-Tools still life searcher - Find still lifes in Conway's Game of Life
Copyright (C) 2026 NNlk05
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
"""
import argparse
from ortools.sat.python import cp_model
from sys import exit, stderr
from platform import system
def get_python_exe() -> str:
current_system = system()
if current_system == "Linux":
return "python"
if current_system == 'Windows':
return 'py'
if current_system == 'Darwin':
return "python3"
return "python"
def print_error(message: str) -> None:
print(f"{message} Exiting.", file=stderr)
exit(1)
def parse_args() -> tuple[int, int, int | None, bool, bool]:
parser = argparse.ArgumentParser(
prog=get_python_exe() + " " + __file__,
description="""
OR-Tools still life searcher
By: NNlk05
Find still lifes in Conway's Game of Life
"""
)
parser.add_argument("x", type=int, help="Grid width")
parser.add_argument("y", type=int, help="Grid height")
parser.add_argument(
"cells",
nargs="?",
type=int,
default=None,
help="Optional: Target number of live cells (if not specified, maximizes population)"
)
parser.add_argument(
"-a", "--all",
action="store_true",
help="Print all solutions without prompting"
)
parser.add_argument(
"-y", "--yes",
action="store_true",
help="Print all solutions without prompting (alias for --all)"
)
parser.add_argument(
"-q", "--quiet",
action="store_true",
help="Skip the 'Population: x' message"
)
try:
args = parser.parse_args()
except SystemExit:
raise
if args.x <= 0 or args.y <= 0:
print_error("Grid dimensions must be positive integers!")
if args.cells is not None and args.cells <= 0:
print_error("Cell count must be a positive integer!")
all_solutions = args.all or args.yes
return args.x, args.y, args.cells, all_solutions, args.quiet
class Grid:
def __init__(self, x: int, y: int):
self.x: int = x
self.y: int = y
self.grid: list[list[int]] = [
[0 for _ in range(x)] for _ in range(y)
]
def __str__(self) -> str:
output: str = ""
for row in self.grid:
for cell in row:
if cell == 1:
output += "O"
elif cell == 0:
output += "."
else:
print_error("Invalid value in Grid!")
output += "\n"
return output
def pop(self) -> int:
pop: int = 0
for row in self.grid:
for cell in row:
if cell == 1:
pop += 1
elif cell == 0:
pass
else:
print_error("Invalid value in Grid!")
return pop
def is_still(self, x: int, y: int) -> bool:
if not (0 <= x < self.x and 0 <= y < self.y):
print_error(f"Coordinates ({x}, {y}) out of grid bounds!")
count: int = 0
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
if dx == 0 and dy == 0:
continue
nx: int = x + dx
ny: int = y + dy
if 0 <= nx < self.x and 0 <= ny < self.y:
if self.grid[ny][nx] == 1:
count += 1
current_state: int = self.grid[y][x]
if current_state == 1:
return count in (2, 3)
elif current_state == 0:
return count == 3
else:
print_error("Invalid value in Grid!")
return False
def main() -> None:
x, y, target_cells, all_solutions, quiet = parse_args()
padded_x: int = x + 2
padded_y: int = y + 2
model: cp_model.CpModel = cp_model.CpModel()
grid: Grid = Grid(x, y)
grid_vars: list[list[cp_model.IntVar]] = [
[model.NewIntVar(0, 1, f"cell_{i}_{j}") for j in range(padded_x)]
for i in range(padded_y)
]
for i in range(padded_y):
for j in range(padded_x):
if i == 0 or i == padded_y - 1 or j == 0 or j == padded_x - 1:
model.Add(grid_vars[i][j] == 0)
for i in range(padded_y):
for j in range(padded_x):
neighbors: list[cp_model.IntVar] = []
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
if di == 0 and dj == 0:
continue
ni: int = i + di
nj: int = j + dj
if 0 <= ni < padded_y and 0 <= nj < padded_x:
neighbors.append(grid_vars[ni][nj])
neighbor_sum: cp_model.IntVar = model.NewIntVar(0, 8, f"neighbors_{i}_{j}")
model.Add(neighbor_sum == sum(neighbors))
cell: cp_model.IntVar = grid_vars[i][j]
model.Add(neighbor_sum >= 2).OnlyEnforceIf(cell)
model.Add(neighbor_sum <= 3).OnlyEnforceIf(cell)
model.Add(neighbor_sum != 3).OnlyEnforceIf(cell.Not())
interior_sum = sum(
grid_vars[i][j]
for i in range(1, padded_y - 1)
for j in range(1, padded_x - 1)
)
if target_cells is not None:
model.Add(interior_sum == target_cells)
else:
model.Maximize(interior_sum)
solver: cp_model.CpSolver = cp_model.CpSolver()
status: cp_model.CpSolverStatus = solver.Solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
if target_cells is None:
optimal_pop = int(solver.ObjectiveValue())
model.Add(interior_sum == optimal_pop)
while True:
for i in range(y):
for j in range(x):
grid.grid[i][j] = int(solver.Value(grid_vars[i + 1][j + 1]))
print(grid)
if not quiet:
print(f"Population: {grid.pop()}")
if all_solutions:
forbid_clause = []
for i in range(1, padded_y - 1):
for j in range(1, padded_x - 1):
if solver.Value(grid_vars[i][j]) == 1:
forbid_clause.append(grid_vars[i][j].Not())
else:
forbid_clause.append(grid_vars[i][j])
model.AddBoolOr(forbid_clause)
status = solver.Solve(model)
if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
print("\nNo more unique solutions found.")
break
else:
ans = input("Another solution (Y/n)? ").strip().lower()
if ans != 'n':
break
forbid_clause = []
for i in range(1, padded_y - 1):
for j in range(1, padded_x - 1):
if solver.Value(grid_vars[i][j]) == 1:
forbid_clause.append(grid_vars[i][j].Not())
else:
forbid_clause.append(grid_vars[i][j])
model.AddBoolOr(forbid_clause)
status = solver.Solve(model)
if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
print("\nNo more unique solutions with the same population found.")
break
else:
print_error("No solution found!")
if __name__ == "__main__":
main()