Search methods

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

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
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!
(Check gen 2)

User avatar
calcyman
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:

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!

Post Reply