go-constraint-solver

A powerful and flexible Go library and CLI for solving Constraint Satisfaction Problems (CSP). This library provides efficient backtracking algorithms with intelligent heuristics for solving various constraint satisfaction problems including scheduling, puzzles (N-Queens, Sudoku), graph coloring, and research problems.

Features

• 🎯 Core CSP Solver: Efficient backtracking algorithm with constraint propagation
• 🧠 Smart Heuristics:
  • Minimum Remaining Values (MRV) for variable selection
  • Least Constraining Value (LCV) for value ordering
• 📊 Solution Explanation: Detailed explanations of how solutions were found
• 🔧 Flexible Constraints: Support for unary, binary, all-different, and custom function constraints
• 🎨 Built-in Examples: N-Queens, Sudoku, Map Coloring, and Meeting Scheduling
• 💻 CLI Tool: Command-line interface for quick problem solving
• ✅ Well-tested: Comprehensive test coverage

Installation

go get github.com/BaseMax/go-constraint-solver

Quick Start

Using the Library

package main

import (
    "fmt"
    "github.com/BaseMax/go-constraint-solver/csp"
)

func main() {
    // Create a new CSP
    problem := csp.NewCSP()
    
    // Add variables with their domains
    problem.AddVariable(csp.NewVariable("X", []interface{}{1, 2, 3}))
    problem.AddVariable(csp.NewVariable("Y", []interface{}{1, 2, 3}))
    problem.AddVariable(csp.NewVariable("Z", []interface{}{1, 2, 3}))
    
    // Add constraints: all variables must have different values
    problem.AddConstraint(csp.NewAllDifferentConstraint([]string{"X", "Y", "Z"}))
    
    // Solve with heuristics
    solution, err := problem.SolveWithHeuristics()
    if err != nil {
        fmt.Println("No solution found")
        return
    }
    
    // Print solution with explanation
    explainer := csp.NewSolutionExplainer(problem, solution, problem.GetStatistics())
    fmt.Println(explainer.Explain())
}

Using the CLI

# Build the CLI
go build -o csp-cli ./cmd/csp-cli

# Solve N-Queens problem (8x8 board)
./csp-cli --problem nqueens --size 8

# Solve 4-Queens problem
./csp-cli --problem nqueens --size 4

# Solve Map Coloring problem
./csp-cli --problem mapcoloring

# Solve Sudoku puzzle
./csp-cli --problem sudoku

# Solve Meeting Scheduling problem
./csp-cli --problem scheduling

# Find all solutions
./csp-cli --problem nqueens --size 4 --all

# Show help
./csp-cli --help

Examples

N-Queens Problem

package main

import (
    "fmt"
    "github.com/BaseMax/go-constraint-solver/csp"
    "github.com/BaseMax/go-constraint-solver/examples"
)

func main() {
    problem := examples.NQueens(8)
    solution, _ := problem.SolveWithHeuristics()
    
    explainer := csp.NewSolutionExplainer(problem, solution, problem.GetStatistics())
    fmt.Println(explainer.Explain())
}

Map Coloring

problem := examples.MapColoring()
solution, _ := problem.SolveWithHeuristics()

Custom Constraints

// Binary constraint: X < Y
problem.AddConstraint(csp.NewBinaryConstraint("X", "Y", 
    func(v1, v2 interface{}) bool {
        return v1.(int) < v2.(int)
    }, 
    "X < Y"))

// Function constraint: X + Y = 10
problem.AddConstraint(csp.NewFunctionConstraint(
    []string{"X", "Y"}, 
    func(a csp.Assignment) bool {
        return a["X"].(int) + a["Y"].(int) == 10
    }, 
    "X + Y = 10"))

API Reference

Core Types

• CSP: Main constraint satisfaction problem structure
• Variable: Represents a CSP variable with a domain
• Constraint: Interface for all constraint types
• Assignment: Map of variable names to assigned values

Constraint Types

• UnaryConstraint: Constraint on a single variable
• BinaryConstraint: Constraint between two variables
• AllDifferentConstraint: Ensures all variables have different values
• FunctionConstraint: Custom constraint with arbitrary predicate

Solver Methods

• Solve(): Basic backtracking search
• SolveWithHeuristics(): Backtracking with MRV and LCV heuristics
• SolveAll(): Find all possible solutions

Statistics

The solver tracks:

• Total assignments tried
• Number of backtracks performed
• Efficiency metrics

Performance

The solver uses intelligent heuristics to minimize search space:

• MRV (Minimum Remaining Values): Chooses the variable with the fewest legal values
• LCV (Least Constraining Value): Orders values to keep maximum flexibility for other variables

Example performance (4-Queens):

Total assignments tried: 7
Backtracks performed: 3
Efficiency: 57.14%

Testing

# Run all tests
go test ./...

# Run tests with coverage
go test ./... -cover

# Run specific package tests
go test ./csp -v
go test ./examples -v

Use Cases

This library is designed for:

• Scheduling Problems: Meeting scheduling, resource allocation, timetabling
• Puzzles: N-Queens, Sudoku, crosswords, logic puzzles
• Graph Problems: Graph coloring, map coloring
• Research: CSP algorithm experimentation and education
• Planning: Configuration problems, workflow planning

Contributing

Contributions are welcome! Please feel free to submit issues or pull requests.

License

MIT License - see LICENSE file for details.

Author

Max Base

Acknowledgments

This implementation is based on classical CSP solving techniques including backtracking search with constraint propagation and variable/value ordering heuristics.