ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Search methods

For scripts to aid with computation or simulation in cellular automata.

Search methods

Postby 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.
If you're the person that uploaded to Sakagolue illegally, please PM me.
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2884
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Search methods

Postby calcyman » May 1st, 2018, 11:48 am

David Eppstein wrote a paper explaining how gfind works:

https://arxiv.org/abs/cs/0004003

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!
User avatar
calcyman
 
Posts: 2020
Joined: June 1st, 2009, 4:32 pm


Return to Scripts

Who is online

Users browsing this forum: No registered users and 1 guest