Eli Bendersky's website Project Euler problem 68 is your typical puzzle - you have to fill in some numbers into a pattern according to certain rules (constraints). Kind-of like Sudoku, just simpler.
The approaches people have used to solve it are quite varied:
- By hand, using pencil and paper. It isn't a very hard puzzle, after all.
- Brute forcing the 10! permutations of 10 numbers, checking which permutation satisfies all the constraints and has the largest 16-digit string representation.
- Smarter brute forcing with some pruning of bad paths - this comes closer to AI approaches.
- Some people recognized that this can be easily solved by a constraint-satisfaction engine, found such an engine and used it to solve the problem (there's still a challenge here, and that's representing the problem in the language of the constraint satisfier).
- The most brilliant solution I saw was using SQL! The constraints were coded as a SQL
selectstatement - not the most efficient solution, but an original one!
Now, as I tend to do in many cases, I took the long and hard way here. I coded my own constraint satisfaction engine in Python - complete with constraint propagation, search pruning and some generic heuristics. For sample problems I represented map coloring, Sudoku, magic squares and N-queens problems. The solver works quite fine for all these problems, and when I represented the 5-gon problem for it, it was easy to find the solution quickly.
It was real fun coding the CSP solver (kinda like the time when I coded a simple SAT solver to solve Sudokus) - it was an educational experience. True, solving problem 68 took 6-7 hours instead of 20 minutes this way, but it was definitely worth it!
The code for the solver is available here. Drop me an email if you have any questions about it.