gurddy 0.1.5

Gurddy Python package.

Gurddy

Gurddy is a lightweight Python package designed to model and solve Constraint Satisfaction Problems (CSP) and Linear Programming (LP) problems with ease. Built for researchers, engineers, and optimization enthusiasts, Gurddy provides a unified interface to define variables, constraints, and objectives—then leverages powerful solvers under the hood to deliver optimal or feasible solutions.

Quick Start

import gurddy

# Solve 4-Queens problem
model = gurddy.Model("4-Queens", "CSP")

# Create variables (one per row, value = column)
queens = [model.addVar(f"q{i}", domain=[0,1,2,3]) for i in range(4)]

# All queens in different columns
model.addConstraint(gurddy.AllDifferentConstraint(queens))

# No two queens on same diagonal
for i in range(4):
    for j in range(i + 1, 4):
        row_diff = j - i
        diagonal_constraint = lambda c1, c2, rd=row_diff: abs(c1 - c2) != rd
        model.addConstraint(gurddy.FunctionConstraint(diagonal_constraint, (queens[i], queens[j])))

# Solve and print solution
solution = model.solve()
if solution:
    for row in range(4):
        line = ['Q' if solution[f'q{row}'] == col else '.' for col in range(4)]
        print(' '.join(line))

Output:

. Q . .
. . . Q  
Q . . .
. . Q .

Features

• 🧩 CSP Support: Define discrete variables, domains, and logical constraints.
• 📈 LP Support: Formulate linear objectives and inequality/equality constraints.
• 🔌 Extensible Solver Backend: Integrates with industry-standard solvers (e.g., Gurobi, CBC, or GLPK via compatible interfaces).
• 📦 Simple API: Intuitive syntax for rapid prototyping and experimentation.
• 🧪 Type-Hinted & Tested: Robust codebase with unit tests and clear documentation.

CSP Examples

🧩 Classic Puzzles

Sudoku Solver (optimized_csp.py)

• Complete 9×9 Sudoku puzzle solver
• Demonstrates AllDifferent constraints
• Shows mask-based optimizations for small integer domains
• Run: python examples/optimized_csp.py

N-Queens Problem (n_queens.py)

• Place N queens on N×N chessboard without conflicts
• Demonstrates custom function constraints for diagonal checks
• Supports any board size (4×4, 8×8, etc.)
• Run: python examples/n_queens.py

Logic Puzzles (logic_puzzles.py)

• Einstein's famous Zebra puzzle (5 houses, 5 attributes)
• Simple logic puzzles for learning
• Complex constraint modeling techniques
• Run: python examples/logic_puzzles.py

🎨 Graph Problems

Graph Coloring (graph_coloring.py)

• Color graph vertices with minimum colors
• Includes sample graphs: Triangle, Square, Petersen, Wheel
• Finds chromatic number automatically
• Run: python examples/graph_coloring.py

Map Coloring (map_coloring.py)

• Color geographical maps (Australia, USA, Europe)
• Demonstrates the Four Color Theorem
• Real-world adjacency relationships
• Run: python examples/map_coloring.py

📅 Scheduling Problems

Multi-Type Scheduling (scheduling.py)

• Course Scheduling: University course timetabling
• Meeting Scheduling: Conference room allocation
• Resource Scheduling: Task-resource-time assignment
• Complex temporal and resource constraints
• Run: python examples/scheduling.py

LP Examples

Basic Linear Programming (optimized_lp.py)

• Simple LP problem demonstration
• Shows PuLP integration
• Run: python examples/optimized_lp.py

Quick Start Guide

Running All Examples

# Navigate to examples directory
cd examples

# Run CSP examples
python n_queens.py
python graph_coloring.py
python map_coloring.py
python scheduling.py
python logic_puzzles.py
python optimized_csp.py

# Run LP examples
python optimized_lp.py

Example Output Preview

N-Queens (8×8 board)

8-Queens Solution:
+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+
...
Queen positions: (0,0), (1,4), (2,7), (3,5), (4,2), (5,6), (6,1), (7,3)

Graph Coloring

Triangle: Complete graph K3 (triangle)
Trying with 3 colors...
Chromatic number: 3
Vertex 0: Red
Vertex 1: Blue  
Vertex 2: Green

Zebra Puzzle

House 1:
  Color       : Yellow
  Nationality : Norwegian
  Drink       : Water
  Pet         : Fox
  Cigarette   : Kools

ANSWERS:
Who owns the zebra? Japanese (House 5)
Who drinks water? Norwegian (House 1)

Problem Categories

🔢 Combinatorial Puzzles

• Sudoku, N-Queens, Logic puzzles
• Key Techniques: AllDifferent constraints, custom functions
• Files: optimized_csp.py, n_queens.py, logic_puzzles.py

🌐 Graph Theory Problems

• Graph coloring, map coloring
• Key Techniques: Binary constraints, chromatic number finding
• Files: graph_coloring.py, map_coloring.py

⏰ Scheduling & Assignment

• Course scheduling, resource allocation
• Key Techniques: Time-resource encoding, complex constraints
• Files: scheduling.py

📊 Optimization Problems

• Linear programming, mixed-integer programming
• Key Techniques: Objective optimization, constraint relaxation
• Files: optimized_lp.py

Learning Path

🟢 Beginner (Start Here)

1. optimized_csp.py - Learn basic CSP concepts with Sudoku
2. n_queens.py - Understand custom constraints
3. graph_coloring.py - Explore graph problems

🟡 Intermediate

4. map_coloring.py - Real-world constraint modeling
5. scheduling.py - Multi-constraint problems
6. optimized_lp.py - Introduction to LP

Customization Tips

Adding New Constraints

# Custom constraint function
def my_constraint(val1, val2):
    return val1 + val2 <= 10

# Add to model
model.addConstraint(FunctionConstraint(my_constraint, (var1, var2)))

Performance Tuning

# For small integer domains (1-32), force mask optimization
solver = CSPSolver(model)
solver.force_mask = True
solution = solver.solve()

Domain Specification

# Different domain types
model.addVar('binary_var', domain=[0, 1])           # Binary
model.addVar('small_int', domain=[1,2,3,4,5])       # Small integers  
model.addVar('large_range', domain=list(range(100))) # Large range

---

Installation (PyPI)

Install the package from PyPI:

pip install gurddy

For LP/MIP examples you also need PuLP (the LP backend used by the built-in LPSolver):

pip install pulp

If you publish optional extras you may use something like pip install gurddy[lp] if configured; otherwise install pulp separately as shown above.

Usage — Core concepts

After installing from PyPI you can import the public API from the gurddy package. The library exposes a small Model/Variable/Constraint API used by both CSP and LP solvers.

• Model: container for variables, constraints, and objective. Use Model(...) and then addVar, addConstraint, setObjective or call solve() which will dispatch to the appropriate solver based on problem_type.
• Variable: create with Model.addVar(name, low_bound=None, up_bound=None, cat='Continuous', domain=None); for CSP use domain (tuple of ints), for LP use numeric bounds and category ('Continuous', 'Integer', 'Binary').
• Expression: arithmetic expressions are created implicitly by operations on Variable objects or explicitly via Expression(variable_or_value).
• Constraint types: LinearConstraint, AllDifferentConstraint, FunctionConstraint.

Usage — CSP Examples

Gurddy can solve a wide variety of Constraint Satisfaction Problems. Here are some examples:

Simple CSP Example

from gurddy.model import Model
from gurddy.constraint import AllDifferentConstraint

# Build CSP model
model = Model('simple_csp', problem_type='CSP')
# Add discrete variables with domains (1..9)
model.addVar('A1', domain=[1,2,3,4,5,6,7,8,9])
model.addVar('A2', domain=[1,2,3,4,5,6,7,8,9])

# Add AllDifferent constraint across a group
model.addConstraint(AllDifferentConstraint([model.variables['A1'], model.variables['A2']]))

# Solve (uses internal CSPSolver)
solution = model.solve()
print(solution)  # dict of variable name -> assigned int, or None if unsatisfiable

N-Queens Problem

from gurddy.model import Model
from gurddy.constraint import AllDifferentConstraint, FunctionConstraint

def solve_n_queens(n=8):
    model = Model(f"{n}-Queens", "CSP")
    
    # Variables: one for each row, value represents column position
    queens = {}
    for row in range(n):
        var_name = f"queen_row_{row}"
        queens[var_name] = model.addVar(var_name, domain=list(range(n)))
    
    # All queens in different columns
    model.addConstraint(AllDifferentConstraint(list(queens.values())))
    
    # No two queens on same diagonal
    def not_on_same_diagonal(col1, col2, row_diff):
        return abs(col1 - col2) != row_diff
    
    queen_vars = list(queens.values())
    for i in range(n):
        for j in range(i + 1, n):
            row_diff = j - i
            constraint_func = lambda c1, c2, rd=row_diff: not_on_same_diagonal(c1, c2, rd)
            model.addConstraint(FunctionConstraint(constraint_func, (queen_vars[i], queen_vars[j])))
    
    return model.solve()

# Solve 8-Queens
solution = solve_n_queens(8)

Graph Coloring

def solve_graph_coloring(edges, num_vertices, max_colors=4):
    model = Model("GraphColoring", "CSP")
    
    # Variables: one for each vertex
    vertices = {}
    for v in range(num_vertices):
        vertices[f"vertex_{v}"] = model.addVar(f"vertex_{v}", domain=list(range(max_colors)))
    
    # Adjacent vertices must have different colors
    def different_colors(color1, color2):
        return color1 != color2
    
    for v1, v2 in edges:
        var1 = vertices[f"vertex_{v1}"]
        var2 = vertices[f"vertex_{v2}"]
        model.addConstraint(FunctionConstraint(different_colors, (var1, var2)))
    
    return model.solve()

# Example: Color a triangle graph
edges = [(0, 1), (1, 2), (2, 0)]
solution = solve_graph_coloring(edges, 3, 3)

CSP Problem Types Supported

Gurddy's CSP solver can handle a wide variety of constraint satisfaction problems:

Constraint Types

• AllDifferentConstraint: Global constraint ensuring all variables take distinct values
• FunctionConstraint: Custom binary constraints defined by Python functions
• LinearConstraint: Equality and inequality constraints (var == value, var <= value, etc.)

Problem Categories

• Combinatorial Puzzles: Sudoku, N-Queens, Logic puzzles
• Graph Problems: Graph coloring, map coloring
• Scheduling: Resource allocation, time slot assignment
• Assignment Problems: Matching, allocation with constraints

Performance Optimizations

• Mask-based AC-3: Optimized arc consistency for small integer domains (1-32)
• AllDifferent Propagation: Uses maximum matching algorithms for global constraints
• Smart Variable Ordering: Minimum Remaining Values (MRV) heuristic
• Value Ordering: Least Constraining Value (LCV) heuristic
• Automatic Optimization: CSPSolver automatically detects when to use mask optimizations

Advanced Features

• Backtracking with Inference: AC-3 constraint propagation during search
• Multiple Constraint Types: Mix different constraint types in the same problem
• Extensible: Easy to add custom constraint types and heuristics

Usage — LP / MIP (example)

The LP solver wraps PuLP. A basic LP/MIP example:

from gurddy.model import Model

# Build an LP model
m = Model('demo', problem_type='LP')
# addVar(name, low_bound=None, up_bound=None, cat='Continuous')
x = m.addVar('x', low_bound=0, cat='Continuous')
y = m.addVar('y', low_bound=0, cat='Integer')

# Objective: maximize 3*x + 5*y
m.setObjective(x * 3 + y * 5, sense='Maximize')

# Add linear constraints (using Expression objects implicitly via Variable operations)
m.addConstraint((x * 2 + y * 1) <= 10)

# Solve (uses LPSolver which wraps PuLP)
sol = m.solve()
print(sol)  # dict var name -> numeric value or None

Examples Gallery

Gurddy comes with comprehensive examples demonstrating various problem types:

CSP Examples

• examples/optimized_csp.py - Complete Sudoku solver with optimizations
• examples/n_queens.py - N-Queens problem for any board size
• examples/graph_coloring.py - Graph coloring with various test graphs
• examples/map_coloring.py - Map coloring (Australia, USA, Europe)
• examples/scheduling.py - Course and meeting scheduling problems
• examples/logic_puzzles.py - Logic puzzles including Einstein's Zebra puzzle

LP Examples

• examples/optimized_lp.py - LP relaxation vs MIP, timings, sensitivity analysis

Running Examples

# CSP Examples
python examples/n_queens.py           # N-Queens problem
python examples/graph_coloring.py     # Graph coloring
python examples/map_coloring.py       # Map coloring
python examples/scheduling.py         # Scheduling problems
python examples/logic_puzzles.py      # Logic puzzles
python examples/optimized_csp.py      # Sudoku solver

# LP Examples  
python examples/optimized_lp.py       # Production planning
python examples/advanced_lp.py        # Advanced LP techniques

Problem-Specific Examples

Sudoku Solver

# Complete 9x9 Sudoku with given clues
model = Model("Sudoku", "CSP")

# Create 81 variables for 9x9 grid
vars_dict = {}
for row in range(1, 10):
    for col in range(1, 10):
        var_name = f"cell_{row}_{col}"
        vars_dict[var_name] = model.addVar(var_name, domain=[1,2,3,4,5,6,7,8,9])

# Add AllDifferent constraints for rows, columns, and 3x3 boxes
# ... (see examples/optimized_csp.py for complete implementation)

Einstein's Zebra Puzzle

# The famous logic puzzle with 5 houses, 5 attributes each
# Who owns the zebra and who drinks water?
model = Model("ZebraPuzzle", "CSP")

# Variables for colors, nationalities, drinks, pets, cigarettes
# Each assigned to houses 0-4
# ... (see examples/logic_puzzles.py for complete implementation)

Course Scheduling

# Schedule university courses avoiding conflicts
model = Model("CourseScheduling", "CSP")

courses = ['Math101', 'Physics101', 'Chemistry101', 'Biology101', 'English101']
time_slots = list(range(20))  # 5 days × 4 slots

# Variables and constraints for scheduling
# ... (see examples/scheduling.py for complete implementation)

Developer Notes

• CSP Optimizations: The CSP solver includes precomputed support masks, mask-based AC-3, and AllDifferent matching propagation for enhanced performance on small integer domains.
• LP Backend: Uses PuLP by default. Can be extended to support other solvers (ORTOOLS, Gurobi) by modifying src/gurddy/solver/lp_solver.py.
• Extensibility: Easy to add new constraint types by inheriting from the Constraint base class.
• Memory Efficiency: Mask-based operations reduce memory usage for problems with small domains.

Running tests

Run unit tests with pytest:

python -m pytest

Contributing

PRs welcome. If you add a new solver backend, please include configuration and a small example demonstrating usage.

API Reference (concise)

This section lists the most commonly used classes and functions with signatures and short descriptions.

Model

---

• Model(name: str = "Model", problem_type: str = "LP")

  • Container for variables, constraints, objective and solver selection.
  • Attributes: variables: Dict[str, Variable], constraints: List[Constraint], objective: Optional[Expression], sense: str

• addVar(name: str, low_bound: Optional[float] = None, up_bound: Optional[float] = None, cat: str = 'Continuous', domain: Optional[list] = None) -> Variable

  • Create and register a Variable. For CSP use domain (list/tuple of ints). For LP use numeric bounds and cat.

• addVars(names: List[str], **kwargs) -> Dict[str, Variable]

  • Convenience to create multiple variables with the same kwargs.

• addConstraint(constraint: Constraint, name: Optional[str] = None) -> None

  • Register a Constraint object (LinearConstraint, AllDifferentConstraint, FunctionConstraint).

• setObjective(expr: Expression, sense: str = "Maximize") -> None

  • Set the objective expression and sense for LP problems.

• solve() -> Optional[Dict[str, Union[int, float]]]

  • Dispatch to the appropriate solver (CSPSolver or LPSolver) and return a mapping from variable name to value, or None if unsatisfiable/no optimal found.

Variable

---

• Variable(name: str, low_bound: Optional[float] = None, up_bound: Optional[float] = None, cat: str = 'Continuous', domain: Optional[list] = None)
  • Represents a decision variable. For CSP set domain (discrete values). For LP set numeric bounds and cat in {'Continuous','Integer','Binary'}.
  • Supports arithmetic operator overloads to build Expression objects (e.g., x * 3 + y).

Expression

---

• Expression(term: Union[Variable, int, float, Expression])
  • Arithmetic expression type used to build linear objectives and constraints.
  • Operators: +, -, *, / with scalars; comparisons (==, <=, >=, <, >) produce LinearConstraint instances.

Constraint types

---

• LinearConstraint(expr: Expression, sense: str)

  • General linear constraint wrapper (sense in {'<=','>=','==', '!='}).

• AllDifferentConstraint(vars: List[Variable])

  • Global constraint enforcing all variables in the list take pairwise distinct values (used primarily for CSPs).

• FunctionConstraint(func: Callable[[int,int], bool], vars: Tuple[Variable, ...])

  • Custom binary (or n-ary) constraint defined by a Python callable.

Solvers

---

• class CSPSolver

  • CSPSolver(model: Model)
  • Attributes: mask_threshold: int (domain size under which mask optimization is used), force_mask: bool
  • Methods: solve() -> Optional[Dict[str, int]] (returns assignment mapping or None)

• class LPSolver

  • LPSolver(model: Model)
  • Methods: solve() -> Optional[Dict[str, float]] (returns variable values mapping or None). Uses PuLP by default; requires pulp installed.

Notes

• The API intentionally keeps model construction separate from solver execution. Use Model.solve() for convenience or instantiate solver classes directly for advanced control (e.g., change CSPSolver.force_mask).
• For more examples see examples/optimized_csp.py, examples/optimized_lp.py.