search

flopp / alcazar-gen

SAT-based generator for Alcazar puzzles
MIT License
10 stars 2 forks source link

Improve Speed #2

Open XeroOl opened 3 weeks ago

XeroOl commented 3 weeks ago

I've come up with an alternate, efficient way to encode Alcazar into SAT that lets the solver run much faster. I imagine instead of 5x5 puzzles, it may be feasible to generate puzzles of size 20x20 or bigger.

However, efficient solving is only half the challenge of generating good puzzles, and I've not been able to figure out how to generate high quality puzzles. They usually end up very easy to solve via propagation.

If you're interested in playing around with puzzle generation algorithms, I'd be willing to port my efficient Alcazar SAT encoding to this codebase.

Would you be interested in a PR that improves the SAT speed?

flopp commented 3 weeks ago

Sure, why not. It will be interesting to see what's different in your approach.

I didn't think that anyone else was doing something like this ;)

XeroOl commented 3 weeks ago

My solution doesn't have any Path/Field logic in it at all, but it seems like its going to be a lot of work to take out the path/field stuff, so I'll just leave it in, and just pass the Clauses of both the approaches the SAT solver

XeroOl commented 3 weeks ago

I was running into more problems. You also do the walls differently too :)

XeroOl commented 3 weeks ago

Okay, so gluing them together seems to make it much slower