Logic Life Search: Difference between revisions
might as well link |
rewrite inline external links in a more explicit way; consistent formatting for bulleted lists |
||
| Line 7: | Line 7: | ||
|platform = Unix; platform-independent | |platform = Unix; platform-independent | ||
}} | }} | ||
'''Logic Life Search''' (abbreviated as '''LLS''') is a program to search for patterns in [[Conway's Game of Life]] and other [[cellular automaton|cellular automata]] by use of a | '''Logic Life Search''' (abbreviated as '''LLS''') is a program to search for patterns in [[Conway's Game of Life]] and other [[cellular automaton|cellular automata]] by use of a SAT solver, written in Python. LLS is similar to [[lifesrc]], [[WinLifeSearch]] and [[JavaLifeSearch]], but offers more flexibility than these. The difference in underlying search methods means that LLS may sometimes be slower than lifesrc to find the same solution, but in many cases with the right optimization it can also be very much faster. | ||
==Mechanism== | ==Mechanism== | ||
LLS works by converting pattern searches to boolean satisfiability (SAT) problems, then employing an external SAT solver (e.g. MiniSAT, Lingeling or Glucose) to solve the SAT problem, and converting the solution to [[RLE]] format. Although SAT solving is | LLS works by converting pattern searches to boolean satisfiability (SAT) problems, then employing an external SAT solver (e.g. MiniSAT, Lingeling or Glucose) to solve the SAT problem, and converting the solution to [[RLE]] format. Although SAT solving is NP-complete, many practical problems can be solved swiftly by SAT solver tools, making this a viable approach to [[Life]] pattern searching. | ||
== | ==See also== | ||
* [[Tutorials/LLS]] — for information on how to install, configure, and use LLS. | * [[Tutorials/LLS]] — for information on how to install, configure, and use LLS. | ||
==External links== | ==External links== | ||
* [https://gitlab.com/OscarCunningham/logic-life-search Logic Life Search] on GitLab | * [https://gitlab.com/OscarCunningham/logic-life-search Logic Life Search] on GitLab | ||
{{LinkForumThread|f=9|t=3247|title=Logic Life Search}} | * {{LinkForumThread|f=9|t=3247|title=Logic Life Search}} | ||
* {{LinkWikipedia|Boolean_satisfiability_problem#Algorithms_for_solving_SAT|name=Algorithms for solving SAT}} | |||
* {{LinkWikipedia|NP-completeness|name=NP-completeness}} | |||
Revision as of 12:03, 6 June 2022
| Logic Life Search | ||
| ||
| Homepage | Click here | |
|---|---|---|
| Purpose | Search for patterns | |
| Created by | Oscar Cunningham | |
| Platform | Unix; platform-independent | |
Logic Life Search (abbreviated as LLS) is a program to search for patterns in Conway's Game of Life and other cellular automata by use of a SAT solver, written in Python. LLS is similar to lifesrc, WinLifeSearch and JavaLifeSearch, but offers more flexibility than these. The difference in underlying search methods means that LLS may sometimes be slower than lifesrc to find the same solution, but in many cases with the right optimization it can also be very much faster.
Mechanism
LLS works by converting pattern searches to boolean satisfiability (SAT) problems, then employing an external SAT solver (e.g. MiniSAT, Lingeling or Glucose) to solve the SAT problem, and converting the solution to RLE format. Although SAT solving is NP-complete, many practical problems can be solved swiftly by SAT solver tools, making this a viable approach to Life pattern searching.
See also
- Tutorials/LLS — for information on how to install, configure, and use LLS.
External links
- Logic Life Search on GitLab
- Logic Life Search (discussion thread) at the ConwayLife.com forums
- Algorithms for solving SAT at Wikipedia
- NP-completeness at Wikipedia