Search methods

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
Posts: 3199
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Search methods

Post by Saka » May 1st, 2018, 4:42 am

What are some methods of searching that programs such as zfind and gfind use? LLS is pretty obvious (SAT solver) but what about zfind, gfind, qfind, and WLS?

I ask because I'd like to try making my own search program, perhaps for LTL rules.

Code: Select all

x = 17, y = 10, rule = B3/S23
(Check gen 2)

User avatar
Posts: 2144
Joined: June 1st, 2009, 4:32 pm

Re: Search methods

Post by calcyman » May 1st, 2018, 11:48 am

David Eppstein wrote a paper explaining how gfind works:

WLS/JLS/lifesrc are similar to LLS, but using an ad hoc solver instead of a commercial SAT solver. Then zfind and ikpx are similar to gfind, but replacing the de Bruijn graph with a large lookup table and an incremental SAT solver, respectively. Finally, qfind is just a parallelised combination of breadth-first and depth-first searching, based on the zfind methodology.
What do you do with ill crystallographers? Take them to the mono-clinic!

Post Reply