search

cbarrick / puzzles.pl

Logic puzzles in Prolog
1 stars 0 forks source link

Nonogram solver is slow #1

Closed cbarrick closed 10 years ago

cbarrick commented 10 years ago

After 35+ cpu minutes, the 20x20 puzzle still hasn't yielded a solution on my machine.

See this site for other nonogram solvers, including one written in prolog. The solver written in D claims to be able to do 25x25 puzzles in under a second.

I'll try the other prolog solution (which uses automaton/3 from clpfd) and see how it's performance compares.

cbarrick commented 10 years ago

The other prolog solver is by Dr. Lars Buitinck and differs from my attempt in the 1-demensional case.

Given a list of clues and a row/column, my implementation generates each possible configuration, leaving choice points. Dr. Buitinck's solution creates an NFA that represents all configurations and applies that as a constraint on the row/column with clpfd.

Backtracking is much slower than clpfd when there is a unique solution.