Sofa Problem

A fun solver for the Moving Sofa Problem - a math puzzle that asks: "What is the largest area of a sofa that can fit around a right-angled corner in a corridor of unit width?"

How It Works

The solver uses a ray-casting approach to find the maximum sofa area:

1. Path Generation: Creates candidate paths through an L-shaped corridor using various curve strategies (Bezier, circular arc, spline, etc.)
2. Ray Casting: For each position along the path, casts rays from the sofa center to determine the constraints imposed by corridor walls
3. Area Computation: Calculates the sofa area as the intersection of all constraints using polar coordinate integration
4. Optimization: Iteratively explores the parameter space to find paths that yield larger sofa areas

Installation

pip install -e .

Usage

Usage

python -m sofa                                    # Interactive route selection
python -m sofa --route arc --iterations 1000     # Specific route
python -m sofa --route spline --dashboard        # With live visualization
python -m sofa --route asymmetric --infinite     # Run indefinitely

Command Line Options

Option	Short	Description	Default
--route	-r	Route generation strategy	Interactive
--num-points	-np	Path discretization points	300
--num-rays	-nr	Number of rays to cast	2400
--iterations	-n	Maximum iterations	100
--infinite	-inf	Run indefinitely	False
--target-area	-t	Stop when area reached	2.2195
--parallel	-p	Number of workers	1
--dashboard	-d	Show live visualization	False
--output	-o	Save animation to file	Auto
--quiet	-q	Suppress progress output	False
--verbose	-v	Verbose output	False

Route Strategies

Route	Description	Best For
original	Simple symmetric Bezier curve	Baseline comparisons
asymmetric	Varied segment lengths	Exploration diversity
unpredictable	Highly randomized chaotic paths	Broad search space
arc	Clean circular arc through corner	Mathematical elegance
spline	Smooth Catmull-Rom spline	C1 continuous paths
clothoid	Euler spiral (smooth curvature)	Highway-design smooth

Project Structure

sofa/
├── sofa/                    # Main package
│   ├── __init__.py         # Package exports
│   ├── __main__.py         # CLI entry point
│   ├── config.py           # Configuration and data classes
│   ├── core/               # Core solver algorithms
│   │   ├── solver.py       # Main optimization loop
│   │   ├── raycaster.py    # Ray-casting constraint engine
│   │   └── geometry.py     # Geometric utilities
│   ├── routes/             # Path generation strategies
│   │   ├── base.py         # Abstract base class + registry
│   │   ├── original.py     # Symmetric Bezier curves
│   │   ├── asymmetric.py   # Varied segment lengths
│   │   ├── unpredictable.py # Chaotic paths
│   │   ├── arc.py          # Circular arc paths
│   │   ├── spline.py       # Catmull-Rom splines
│   │   └── clothoid.py     # Euler spiral
│   └── visualization/      # Output generation
│       ├── dashboard.py    # Live 2x2 grid visualization
│       └── animation.py    # MP4/GIF animation rendering
├── media/                  # Output directory for animations
├── requirements.txt        # Dependencies
└── README.md              # This file

The Algorithm

Ray Casting

For each position (x, y, θ) along the path:

1. Cast num_rays rays from the sofa center (default: 2400 rays spanning 180°)
2. Find the first intersection with corridor walls for each ray
3. Track min_distance (from inner boundary) and max_distance (from outer boundary)
4. The sofa boundary in each direction is constrained to [min, max]

Sofa Area

The sofa is the intersection of all constraint intervals from all path positions:

Sofa = ∩ {(r, θ) : r_min(t, θ) ≤ r ≤ r_max(t, θ)} for all t along path

Area is computed using polar wedge integration:

Area = Σ 0.5 × (r_max² - r_min²) × Δθ