Nuruomino Solver

Solver for the Nuruomino logic puzzle, built for the Artificial Intelligence course 2024/2025 (IST).

What is Nuruomino?

Nuruomino is a logic puzzle played on a grid divided into numbered regions. The goal is to place exactly one LITS tetromino (L, I, T, or S) into each region such that:

1. The tetromino cells within a region must all belong to that region.
2. No two tetrominoes of the same type can be orthogonally adjacent (touching side-by-side).
3. All placed tetromino cells must form a single orthogonally connected group across the whole board.
4. No 2×2 square of cells may be entirely filled by tetrominoes.

The four tetromino shapes (and all their rotations/reflections) are:

I: X    L: X    T: X    S:  X
   X       X       XX      XX
   X       X       X      X
   X       XX

How it works

The solver models Nuruomino as a search problem using the AIMA Python framework:

• State: the current board, tracking which regions have been filled and which tetrominoes have been placed.
• Actions: all valid tetromino placements for the next unfilled region (chosen by a most-constrained-first heuristic — the region with the fewest remaining possibilities).
• Constraints are enforced incrementally on each placement: same-type adjacency, 2×2 squares, and connectivity checks.
• Search algorithm: Depth-First Tree Search (with forward checking / constraint propagation to prune the search space).

Key files

File	Description
nuruomino.py	Main solver — board representation, constraint checking, and problem definition
search.py	AIMA search algorithms (DFS, BFS, A*, greedy, RBFS)
utils.py	AIMA utility functions used by search.py
public/	Test cases (input .txt + expected output .out)

Running the solver

Requirements: Python 3.8+ and NumPy.

pip install numpy

Run on a puzzle input file:

python nuruomino.py < public/test-01.txt

Input format

The board is read from stdin as a grid of integers where each integer identifies the region that cell belongs to:

1 1 2 2 3 3
1 2 2 2 3 3
1 3 3 2 3 5
3 3 3 3 3 5
4 4 4 3 3 5
4 3 3 3 3 5

Output format

The solver prints the solved board, replacing region numbers with the tetromino letter placed in each cell (cells that were not selected by any tetromino keep their region number):

L L S 2 3 3
L 2 S S 3 3
L 3 3 S 3 I
3 3 3 T 3 I
L L L T T I
L 3 3 T 3 I

Test cases

The public/ folder contains 13 test cases of varying difficulty, along with PNG visualisations for some of them.