Quadratic Diffusor Design Calculator

This Python application generates matrices for quadratic diffusor design where no two adjacent cells (horizontally or vertically) have the same value. Unlike Latin squares, values can repeat in rows and columns as long as they are not adjacent to each other. This creates more efficient diffusor patterns with fewer levels needed.

Features

• Generate diffusor matrices with minimum levels needed
• Automatic level optimization: Starts with your specified minimum and finds the smallest number that works
• Efficient adjacent constraint solving using backtracking with random restarts
• Built-in validation to ensure no adjacent conflicts
• Detailed analysis of generated matrices
• Command-line interface for easy integration
• Reproducible results with seed support

Installation

1. Make sure you have Python 3.6+ installed
2. Create and activate a virtual environment:

   python3 -m venv venv
   ./venv/bin/activate  # On macOS/Linux
   # or venv\Scripts\activate  # On Windows

3. Install dependencies:

   ./venv/bin/pip install -r requirements.txt

Usage

Basic Usage

Generate a 4x4 matrix, trying 3+ levels until one works:

./venv/bin/python quadratic_diffusor.py 4 3

Generate an 8x8 matrix, trying 3+ levels:

./venv/bin/python quadratic_diffusor.py 8 3

Generate a 32x32 matrix, trying 4+ levels:

./venv/bin/python quadratic_diffusor.py 32 4

Advanced Options

Limit the maximum levels to try:

./venv/bin/python quadratic_diffusor.py 6 3 --max-levels 5

Get detailed analysis of the result:

./venv/bin/python quadratic_diffusor.py 6 3 --analyze

Use a specific random seed for reproducible results:

./venv/bin/python quadratic_diffusor.py 6 3 --seed 42

Run validation tests:

./venv/bin/python quadratic_diffusor.py --validate

View help:

./venv/bin/python quadratic_diffusor.py --help

Example Output

Finding minimum levels needed for 4x4 matrix...
  Trying with 3 levels... ✓ SUCCESS (0.00s)

Quadratic Diffusor Matrix
=========================
 1  2  1  2
 3  1  3  1
 2  3  2  3
 1  2  1  2

✓ Matrix validation: PASSED
  - No adjacent cells have the same value

Solution found using 3 levels!

How It Works

The application uses a constraint satisfaction approach:

1. Adjacent Constraint: No two horizontally or vertically adjacent cells can have the same value
2. Backtracking Algorithm: Systematically tries different value assignments
3. Random Restarts: If stuck, restarts with a different random order
4. Level Optimization: Automatically finds the minimum number of levels needed
5. Validation: Verifies that no adjacent conflicts exist

Mathematical Background

This solves a graph coloring problem where:

• Each cell in the matrix is a vertex
• Adjacent cells (horizontally/vertically) are connected by edges
• We need to color vertices so no adjacent vertices have the same color
• The goal is to minimize the number of colors (levels) needed

Key advantages over Latin squares:

• Fewer levels needed: Most matrices need only 3-4 levels regardless of size
• More freedom: Values can repeat in rows/columns if not adjacent
• Better for manufacturing: Fewer different depth levels to cut
• Optimal efficiency: Uses the theoretical minimum for grid graphs

Typical Level Requirements

Based on testing, here are typical minimum levels needed:

• 3x3 matrix: 2 levels
• 4x4 matrix: 3 levels
• 5x5+ matrices: Usually 3 levels
• Large matrices (8x8, 16x16, 32x32): Typically 3-4 levels

This is much more efficient than Latin squares which require N levels for an N×N matrix!

Error Handling

• If no solution is found with the specified level range, an error is reported
• Invalid inputs (negative numbers, zero) are caught and reported
• The algorithm will automatically try higher levels until a solution is found (up to the maximum)

Contributing

Feel free to extend this application with additional features such as:

• Export to CAD/manufacturing formats
• Visualization of the diffusor pattern
• Non-square matrices
• Different constraint patterns (diagonal constraints, etc.)
• Performance optimizations for very large matrices