Futoshiki Puzzle Solver

# Futoshiki Puzzle Solver using Evolutionary Programming ## Overview This project implements an **Evolutionary Programming** approach to solve **Futoshiki puzzles**, a Japanese logic-based combinatorial number puzzle. The solver uses genetic algorithms and advanced techniques like island models to tackle the complex constraint satisfaction problem that Futoshiki presents. This project was developed for the course `30592 -Topics in Computational Modelling - From Information Theory to Evolutionary Models`, Bocconi University. ## Table of Contents - [Futoshiki Puzzle Solver using Evolutionary Programming](#futoshiki-puzzle-solver-using-evolutionary-programming) - [Overview](#overview) - [Table of Contents](#table-of-contents) - [About Futoshiki](#about-futoshiki) - [Rules:](#rules) - [Project Features](#project-features) - [Core Implementation](#core-implementation) - [Evolutionary Algorithms](#evolutionary-algorithms) - [Optimization Features](#optimization-features) - [Files Structure](#files-structure) - [Key Components](#key-components) - [1. Puzzle Representation](#1-puzzle-representation) - [2. Solution Candidates](#2-solution-candidates) - [3. Genetic Algorithm](#3-genetic-algorithm) - [4. Island Model](#4-island-model) - [Performance Results](#performance-results) - [4×4 Puzzles](#44-puzzles) - [5×5 and 6×6 Puzzles](#55-and-66-puzzles) - [Key Findings](#key-findings) - [Usage](#usage) - [Example Usage](#example-usage) - [Dependencies](#dependencies) - [Future Work](#future-work) ## About Futoshiki **Futoshiki** (不等式, meaning "inequality" in Japanese), also known as "Unequal", is a logic puzzle similar to Sudoku but with inequality constraints between adjacent cells. ### Rules: 1. The puzzle is played on an N × N square grid (commonly 4×4, 5×5, or 6×6) 2. Some cells contain predefined numbers that cannot be changed 3. Fill each cell with a number from 1 to N 4. Each number must appear exactly once in every row 5. Each number must appear exactly once in every column 6. Some cells are separated by inequality signs (< or >) that indicate relative ordering between adjacent cells 7. Any placed numbers must satisfy all given inequality constraints 8. The puzzle has a unique solution that respects all constraints ## Project Features ### Core Implementation - **FutoshikiPuzzle Class**: Represents and handles puzzle instances with constraints - **Individual Class**: Represents candidate solutions in the genetic algorithm - **Fitness Evaluation**: Counts constraint violations (row, column, and inequality) - **Genetic Operators**: Crossover and mutation for solution evolution ### Evolutionary Algorithms 1. **Standard Genetic Algorithm** - Population-based evolutionary approach - Elitism strategy (preserves top 10% of individuals) - Roulette wheel selection for parent selection - Crossover and mutation operators 2. **Island Model Genetic Algorithm** - Multiple isolated populations (islands) - Independent evolution with periodic migration - Ring topology for migration between islands - Enhanced diversity and escape from local optima ### Optimization Features - **Grid Search**: Systematic hyperparameter optimization - **Performance Analysis**: Fitness tracking and visualization - **Multiple Puzzle Sizes**: Support for 4×4, 5×5, and 6×6 grids ## Files Structure ``` ├── project.ipynb # Main Jupyter notebook with complete implementation ├── project_Straccialini.html # HTML export of the notebook └── README.md # This file ``` ## Key Components ### 1. Puzzle Representation ```python class FutoshikiPuzzle: def __init__(self, size, initial_grid, constraints): # Initialize puzzle with size, grid, and inequality constraints ``` ### 2. Solution Candidates ```python class Individual: def __init__(self, puzzle): # Represents a candidate solution with fitness evaluation # Implements crossover and mutation operators ``` ### 3. Genetic Algorithm ```python def genetic_algorithm(puzzle, population_size=100, generations=1000, mutation_rate=0.1, verbose=False): # Standard GA implementation with elitism and roulette wheel selection ``` ### 4. Island Model ```python def island_model_genetic_algorithm(puzzle, islands=5, pop_per_island=50, generations=200, migration_interval=20, mutation_rate=0.1, verbose=False): # Advanced GA with multiple populations and migration ``` ## Performance Results ### 4×4 Puzzles - Standard GA: Excellent performance with proper hyperparameter tuning - Optimal parameters found through grid search - Consistent solution finding within reasonable generations ### 5×5 and 6×6 Puzzles - Standard GA: Struggles with local optima, limited success - Island Model: Significantly improved performance - Successfully solves complex puzzles where standard GA fails ### Key Findings 1. **Population size matters**: Larger populations maintain better genetic diversity 2. **Mutation rate balance**: 0.1-0.2 provides optimal exploration vs. exploitation 3. **Island model superiority**: Outperforms standard GA on larger, more complex puzzles 4. **Genetic diversity**: Critical for escaping local optima in constraint satisfaction problems ## Usage 1. **Open the Jupyter notebook**: `project.ipynb` 2. **Run the cells sequentially** to see the implementation and results 3. **Modify puzzle instances** or parameters to experiment with different configurations 4. **Use the provided test puzzles** or create your own following the format ### Example Usage ```python # Define a 4x4 puzzle test_puzzle = FutoshikiPuzzle( size=4, initial_grid=[[2, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 4]], constraints=[((0,0), (1,0)), ((1,1), (1,2)), ...] ) # Solve with standard GA solution, generation, fitness_history = genetic_algorithm( test_puzzle, population_size=1000, generations=1000, mutation_rate=0.1 ) # Solve with island model solution, generation, fitness_history = island_model_genetic_algorithm( test_puzzle, islands=5, pop_per_island=200, generations=500 ) ``` ## Dependencies - Python 3.x - matplotlib (for visualization) - random (for stochastic operations) - copy (for deep copying) ## Future Work Potential enhancements include: - **Constraint-aware mutation**: Operators that directly address violated constraints - **Advanced crossover strategies**: Preserving valid row/column permutations - **Island model optimization**: Fine-tuning topology, migration strategies, and parameters - **Hybrid approaches**: Combining with local search or constraint propagation - **Parallel implementation**: Leveraging multi-core processing for island populations --- *For detailed implementation, results, and analysis, please refer to the complete Jupyter notebook `project.ipynb`.*