A Loop Compression Algorithm for Slitherlink Puzzle

Key Points

• To develop an efficient algorithm that solves slitherlink puzzles with exponential time complexity in polynomial time.
• Designed a loop compression algorithm with O(c) complexity.
• Formed the largest rectangular loop connecting outermost points as the initial condition.
• Gradually compressed the loop inward based on adjacent clue cells to satisfy the required line patterns.
• Conducted benchmarking on 18 different datasets to validate effectiveness.
• Successfully solved all benchmark puzzles quickly and accurately.
• Demonstrated a significant reduction in time complexity compared to traditional methods.

Abstract