I proved that all 21-bit pseudo still-lifes are synthesisable.
However, since all but 11 of them were solved with a depth-3 transfer.cpp search (and a vast majority at depth-1 with a strictly increasing population), I don't consider that the bulk of my syntheses are interesting enough to post. For any specific pseudo xs21 for which I don't provide a synthesis, it is easy to find one in a couple of minutes.
I will still describe my method, which took less than 12 hours of computing on a reasonnably fast laptop with 10 threads. I made a few mistakes about the optimal order of searches, which I try to correct here.
I did several transfer.cpp searches with restrictions on the cost of components ("-c minpop maxpop" parameter) and on the population difference ("-d mindiff maxdiff" parameter). Between each search, I could remove a substantial part of the unsolved xs21 list. No search took longer than two hours. For the six first searches, it is worth using "--best" (an experimental feature which accelerates the search when there are too many solutions).
1. cost between 1G and 2G, population difference at 1
2. cost at 3G, population difference at 1
3. cost between 1G and 3G, population difference at 2
4. cost between 1G and 3G, population difference at 3+
5. cost between 1G and 3G, population difference at 0
6. cost at 4G+, population difference at 1+ (after which ~1000 were remaining)
7. Full search (after which ~100 were remaining)
8. Depth-2 search (after which 19 were remaining)
9. Depth-3 search
I realise that transfer.cpp is not optimally designed for the first six searches, which could ideally be reduced to one, so that's something to improve in the future.
Note : it may seem very important at first sight to solve quickly all boat-bits, blocks additions, etc. It is actually not so relevant : there are 179011 pseudo xs21 but only 3224 strict xs16, so this can solve only a small fraction of the total. Perhaps I am overestimating this effect since 70000 easy xs21 were already solved.
Of the remaining 11, 8 could be synthesised with known techniques :
Code:
Select all
x = 723, y = 514, rule = B3/S23
238bo$239bo$237b3o19bo$233bo23b2o$234b2o22b2o$226bo6b2o29bobo$224bobo
37b2o$225b2o38bo2$262bo$170bo40bo48b2o$168bobo3bo36bobo47b2o76bo$169b
2o3bobo34b2o3bo52bo68bo$174b2o40bobo50bobo58bo7b3o$216b2o51b2o59bobo$
170bobo36b2o119b2o10bobo$170b2o38b2o130b2o$171bo37bo30bo87bo14bo$239bo
bo84bobo6b2o$240b2o85b2o4bo2bo$333b3o$172b2o70b2o$172b2o70b2o87b3o$
167bo71bo82b2o8bobobo$167b3o2b2o65b3o2b2o75bobo7bo4bo$170bo2bo68bo2bo
77bo6bo4bo$169bob2o68bob2o85b2o2bob3o$169bo71bo92bo3bo$168b2o70b2o91b
2o5$265b2o$265bobo$265bo4$260b3o$260bo$233bo27bo$233b2o$232bobo67$586b
o$587bo$521bo9bo53b3o$516bo3b2o9bobo2bobo$444bobo59bo9b2o2bobo8b2o3b2o
57bo$445b2o57bobo8bobo19bo55b2o$445bo59b2o87b2o2$50bobo52bo152bo191bob
o147bo$51b2o52bobo66bobo79bobo95bobo93b2o148bobo$51bo49bo3b2o54bo12b2o
81b2o3bo92b2o12bo75bobo3bo148b2o$59bo42bo59b2o11bo85bo93bo11b2o77b2o$
59bobo38b3o58b2o98b3o104b2o76bo145b2o$59b2o531b2o$170bo189bo$50bo53bo
4bo53b2o4bobo4bo74b2o6bo91b2o6bobo4b2o73b2o8b2o62b2o3b2o3b2o65b4o$49bo
bo9bo41bobo2bobo46b2o5b2o4bobo2bobo73bobobo2bobo90bobobo2bobo4b2o5b2o
67bobobo2bobobo62bobobo2bobobo64bo4bo$50b2o7bobo42b2o2b2o48b2o3bo7b2o
2b2o77b2o2b2o94b2o2b2o7bo3b2o71b2o2b2o68b2o2b2o67b2o2b2o$60b2o3bo91bo
215bo229b2o$50b2o2b2o8bo39b2o2b2o61b2o2b2o77b2o2b2o94b2o2b2o84b2o2b2o
68b2o2b2o67b2o2b2o6bobo$51bo3bo8b3o38bo3bo62bo3bo78bo3bo95bo3bo85bo3bo
69bo3bo68bo3bo6bo$51bobo51bobo64bobo80bobo97bobo87bobo71bobo14b2o54bob
o$50b2ob2o49b2ob2o62b2ob2o78b2ob2o95b2ob2o85b2ob2o69b2ob2o12b2o54b2ob
2o$537bo3$64b2o$63b2o$65bo29$587bo$588bo$522bo9bo53b3o$517bo3b2o9bobo
2bobo$445bobo59bo9b2o2bobo8b2o3b2o57bo$446b2o57bobo8bobo19bo55b2o$446b
o59b2o87b2o2$54bobo49bo152bo191bobo147bo$54b2o50bobo66bobo79bobo95bobo
93b2o148bobo$55bo46bo3b2o54bo12b2o81b2o3bo92b2o12bo75bobo3bo148b2o$47b
o55bo59b2o11bo85bo93bo11b2o77b2o$45bobo53b3o58b2o98b3o104b2o76bo145b2o
$46b2o545b2o$171bo189bo$56bo48bo4bo53b2o4bobo4bo74b2o6bo91b2o6bobo4b2o
73b2o8b2o62b2o3b2o3b2o65b4o$45bo9bobo46bobo2bobo46b2o5b2o4bobo2bobo73b
obobo2bobo90bobobo2bobo4b2o5b2o67bobobo2bobobo62bobobo2bobobo64bo4bo$
45bobo7b2o48b2o2b2o48b2o3bo7b2o2b2o77b2o2b2o94b2o2b2o7bo3b2o71b2o2b2o
68b2o2b2o67b2o2b2o$41bo3b2o111bo215bo229b2o$42bo8b2o2b2o48b2o2b2o61b2o
2b2o77b2o2b2o94b2o2b2o84b2o2b2o68b2o2b2o67b2o2b2o6bobo$40b3o8bo2bobo
48bo2bobo61bo2bobo77bo2bobo94bo2bobo84bo2bobo68bo2bobo67bo2bobo6bo$52b
obo51bobo64bobo80bobo97bobo87bobo71bobo14b2o54bobo$53bobo51bobo64bobo
80bobo97bobo87bobo71bobo12b2o56bobo$54bo53bo66bo82bo99bo89bo73bo15bo
56bo3$41b2o$42b2o$41bo29$589bo$590bo$524bo9bo53b3o$519bo3b2o9bobo2bobo
$447bobo59bo9b2o2bobo8b2o3b2o57bo$448b2o57bobo8bobo19bo55b2o$448bo59b
2o87b2o$6bo$2bo3bobo47bobo49bo152bo191bobo147bo$obo3b2o48b2o50bobo66bo
bo79bobo95bobo93b2o148bobo$b2o54bo46bo3b2o54bo12b2o81b2o3bo92b2o12bo
75bobo3bo148b2o105bo$49bo55bo59b2o11bo85bo93bo11b2o77b2o260bo$4bobo40b
obo53b3o58b2o98b3o104b2o76bo145b2o112b3o8bo$5b2o41b2o545b2o123bobo$5bo
167bo189bo356b2o$58bo48bo4bo53b2o4bobo4bo74b2o6bo91b2o6bobo4b2o73b2o8b
2o62b2o3b2o3b2o65b4o106b2o$47bo9bobo46bobo2bobo46b2o5b2o4bobo2bobo73bo
bobo2bobo90bobobo2bobo4b2o5b2o67bobobo2bobobo62bobobo2bobobo64bo4bo
104bo2bobo$47bobo7b2o48b2o2b2o48b2o3bo7b2o2b2o77b2o2b2o94b2o2b2o7bo3b
2o71b2o2b2o68b2o2b2o67b2o2b2o104b2o2b2o$3b2o38bo3b2o111bo215bo229b2o$
3bo2bobob2o32bo8b2o52b2o65b2o81b2o98b2o88b2o72b2o71b2o10bobo95b2o13bo$
5b2ob2obo30b3o8bo2bobob2o45bo2bobob2o58bo2bobob2o74bo2bobob2o91bo2bobo
b2o81bo2bobob2o65bo2bobob2o64bo2bobob2o3bo97bo2bobob2o6bobo$55b2ob2obo
47b2ob2obo60b2ob2obo76b2ob2obo93b2ob2obo83b2ob2obo67b2ob2obo9b2o55b2ob
2obo103b2ob2obo6b2o$538b2o$540bo$721bo$719b2o$43b2o675b2o$44b2o$43bo2$
718b3o$718bo$719bo30$589bo$590bo$524bo9bo53b3o$519bo3b2o9bobo2bobo$
447bobo59bo9b2o2bobo8b2o3b2o57bo$448b2o57bobo8bobo19bo55b2o$448bo59b2o
87b2o2$53bobo52bo152bo191bobo147bo$54b2o52bobo66bobo79bobo95bobo93b2o
148bobo$54bo49bo3b2o54bo12b2o81b2o3bo92b2o12bo75bobo3bo148b2o$62bo42bo
59b2o11bo85bo93bo11b2o77b2o$62bobo38b3o58b2o98b3o104b2o76bo145b2o$62b
2o531b2o$173bo189bo$53bo53bo4bo53b2o4bobo4bo74b2o6bo91b2o6bobo4b2o73b
2o8b2o62b2o3b2o3b2o65b4o$52bobo9bo41bobo2bobo46b2o5b2o4bobo2bobo73bobo
bo2bobo90bobobo2bobo4b2o5b2o67bobobo2bobobo62bobobo2bobobo64bo4bo$53b
2o7bobo42b2o2b2o48b2o3bo7b2o2b2o77b2o2b2o94b2o2b2o7bo3b2o71b2o2b2o68b
2o2b2o67b2o2b2o$63b2o3bo91bo215bo229b2o$53b2o2b2o8bo39b2o2b2o61b2o2b2o
77b2o2b2o94b2o2b2o84b2o2b2o68b2o2b2o67b2o2b2o6bobo$53bobo2bo8b3o37bobo
2bo61bobo2bo77bobo2bo94bobo2bo84bobo2bo68bobo2bo67bobo2bo6bo$55bobo51b
obo64bobo80bobo97bobo87bobo71bobo13b2o55bobo$54bobo51bobo64bobo80bobo
97bobo87bobo71bobo13b2o55bobo$55bo53bo66bo82bo99bo89bo73bo16bo55bo3$
67b2o$66b2o$68bo109$282bobo$283b2o$283bo78bo$363bo$292bo68b3o$215bo77b
o$22bo190bobo69bobo3b3o75bobo$20bobo191b2o70b2o8bobo70b2o$21b2o3bo259b
o9b2o72bo$16bo8bo65bo127bobo75bo$17bo7b3o3bobo55bobo63bo63b2o147bo58bo
131bo$15b3o13b2o57b2o3bo60bo57bobo3bo145bobo57bo68bo64bo$32bo61bo59b3o
58b2o150b2o57b3o59bobo3bo63b3o$94b3o118bo273b2o3b3o$164bo324bo$163bo
217b2o41b2o6b2o67b2o58b2o$90b2o66b2o3b3o54b2o63b2o4b2o81b2o4bobo40bobo
5bobo58b2o6bobo57bobo$88bo2bo65bo2bo54bo2bo2bo63bo3bo2bo81bo2bo3bo41bo
4bo3bo59bo2bobo3bo52b2obo3bo$88b3o66b3o55b6o65b6o83b6o43b8o61b3ob4o53b
ob5o$166b2o319b2o$22b2obo62b2obo65b2obo5bobo46b2obo67b2obo85b2obo47b2o
bo56bobo6b2obo56b2obo$21bob2obo60bob2obo63bob2obo4bo47bob2obo65bob2obo
83bob2obo45bob2obo57bo5bob2obo54bob2obo$20bo5bo8b2o49bo5bo62bo5bo51bo
5bo64bo5bo82bo5bo44bo5bo62bo5bo53bo5bo$21b5o9bobo49b5o64b5o53b5o66b5o
84b5o46b5o64b5o55b5o$23bo11bo53bo68bo57bo70bo88bo50bo68bo59bo42$282bob
o$283b2o$283bo78bo$363bo$292bo68b3o$215bo77bo$22bo190bobo69bobo3b3o75b
obo$20bobo191b2o70b2o8bobo70b2o$21b2o3bo259bo9b2o72bo$16bo8bo65bo127bo
bo75bo$17bo7b3o3bobo55bobo63bo63b2o147bo58bo131bo$15b3o13b2o57b2o3bo
60bo57bobo3bo145bobo57bo68bo64bo$32bo61bo59b3o58b2o150b2o57b3o59bobo3b
o63b3o$94b3o118bo273b2o3b3o$164bo324bo$163bo217b2o41b2o6b2o67b2o58b2o$
90b2o66b2o3b3o54b2o63b2o4b2o81b2o4bobo40bobo5bobo58b2o6bobo57bobo$88bo
2bo65bo2bo54bo2bo2bo63bo3bo2bo81bo2bo3bo41bo4bo3bo59bo2bobo3bo52b2obo
3bo$88b3o66b3o55b6o65b6o83b6o43b8o61b3ob4o53bob5o$166b2o319b2o$22b2obo
62b2obo65b2obo5bobo46b2obo67b2obo85b2obo47b2obo56bobo6b2obo56b2obo$21b
ob2obo60bob2obo63bob2obo4bo47bob2obo65bob2obo83bob2obo45bob2obo57bo5bo
b2obo54bob2obo$20bo5bo8b2o49bo5bo62bo5bo51bo5bo64bo5bo82bo5bo44bo5bo
62bo5bo53bo5bo$21b3obo9bobo49b3obo64b3obo53b3obo66b3obo84b3obo46b3obo
64b3obo55b3obo$23b2o10bo53b2o67b2o56b2o69b2o87b2o49b2o67b2o58b2o!
And 3 required a new component :
Code:
Select all
x = 199, y = 273, rule = B3/S23
182bobo$182b2o$183bo3$180bobo$180b2o$181bo3$169bo$170b2o$169b2o10bo$
181bobo$181b2o9$82bo9bo$83b2o7bobo$14bo11bo50bo4b2o8b2o69bo$12b5o9bobo
46b5o81b5o$11bo5bo8b2o46bo5bo79bo5bob2o$12bob2obo57bob2obo80bob2obob2o
$13b2obo59b2obo82b2obo$196bobo$76b3o83b3o15bo15b2o$76bo2bo82bo2bo14bob
o14bo$78b2o84b2o14b2o3$179b2o$23bo155bobo$6b3o13b2o155bo$8bo7b3o3bobo
166b2o$7bo8bo174bobo$12b2o3bo173bo$11bobo$13bo2$108b3o$108bo$109bo$
152b2o$153b2o14bo$152bo15b2o25bo$168bobo23b2o$156b2o21b3o12bobo$157b2o
20bo$156bo23bo44$182bobo$182b2o$183bo3$180bobo$180b2o$181bo3$169bo$
170b2o$169b2o10bo$181bobo$181b2o9$82bo9bo$83b2o7bobo$14b2o10bo50b2o3b
2o8b2o69b2o$12b3obo9bobo46b3obo81b3obo$11bo5bo8b2o46bo5bo79bo5bob2o$
12bob2obo57bob2obo80bob2obob2o$13b2obo59b2obo82b2obo$196bobo$76b3o83b
3o15bo15b2o$76bo2bo82bo2bo14bobo14bo$78b2o84b2o14b2o3$179b2o$23bo155bo
bo$6b3o13b2o155bo$8bo7b3o3bobo166b2o$7bo8bo174bobo$12b2o3bo173bo$11bob
o$13bo2$108b3o$108bo$109bo$152b2o$153b2o14bo$152bo15b2o25bo$168bobo23b
2o$156b2o21b3o12bobo$157b2o20bo$156bo23bo67$161bo$159bobo$160b2o9$192b
o$192bobo$192b2o$155bo$153bobo12bo$154b2o7bo3bo$164bo2b3o$162b3o5$14bo
$6bo6bo$7bo5b3o$5b3o$11bo162b2o$12bo159bo2bo$10b3o81b2o76b3o$92bo2bo$
92b3o75b3o$5bo164bo2bo$6bo83b3o79bobo$4b3o83bo2bo79bobo$12bo73bo5bobo
51bo22bo5bo$11bobo70bobo6bobo50b2o20bobo3b2obo12b3o$12bobo70b2o8bo49bo
bo21bobobo2b2o12bo$13bobo74bo3b2obo72b2ob2o16bo$bo13bo73bobobo2b2o$b2o
7bo3b2obo64b3o5b2ob2o$obo6bobobo2b2o66bo105b2o$10b2ob2o68bo105b2o$191b
o8$152b2o$153b2o$152bo!
