Search to prove the nonexistence of a 4-states minimal time solution to the Firing Squad Synchronization Problem.

fssp.lua

-- Computer search to prove the nonexistence of minimal time solutions
-- to the FSSP with 4-(non-boundary)states.
-- States *,g,s,f,h... are represented by 0,1,2,3,4... respectively.
-- Hosted at: https://gist.github.com/Average-user/4241ca84777ae6ed38326710d8b47da4

function initial_squad(n)
   local squad = {}
   squad[1],squad[2],squad[n+2] = "0","1","0"
   for i = 3,n+1 do squad[i] = "2" end
   return squad
end

function run(n,rule)
   local xs, ys = initial_squad(n), initial_squad(n)
   for j = 1,2*n-2 do
      local fired,nfired = false,false
      for i = 2,n+1 do
         local st = xs[i-1]..xs[i]..xs[i+1]
         local nv = rule[st]
         if not nv        then return false,st
         elseif nv == "3" then fired = true
         elseif nv ~= "3" then nfired = true
         end
         ys[i] = nv
      end
      if fired and nfired then         return false,nil
      elseif fired and j == 2*n-2 then return true,nil
      elseif fired then                return false,nil
      end
      for i = 2,n+1 do xs[i] = ys[i] end
   end
   return false,nil
end

function try_to_k(rule,k,start)
   for n = start,k do
      local solves,undef = run(n,rule)
      if not solves then
         return solves,undef,n
      end
   end
   return true, nil, nil
end

TOT,POS = 0,0

function find(N,rule,k,start)
   local solves, undef, n = try_to_k(rule,k,start)
   TOT = TOT+1
   if undef then
      for i=1,N do
         rule[undef] = tostring(i)
         find(N,rule,k,n)
         rule[undef] = nil
      end
   elseif solves then
      POS = POS+1
   end
end

find(arg[1],{["022"]="2", ["222"]="2", ["220"]="2"},arg[2],2)
print(TOT,POS)

The FSSP is a well known problem in combinatorics/automata theory.

A first search to prove the nonexistence of minimal time solutions with four states was done first by R.Balzer in his paper An 8-state minimal time solution to the firing squad synchronization problem in 1967. Later, in 1994, P. Sanders reported that the search done by Balzer was incomplete and gave a description of another search in his paper Massively parallel search for transition-tables of polyautomata. I was unable to find the source code, so I made my own search. It reaffirms the result, and also the fact reported by Sanders that there are minimal time solutions that work for n up to 8, but not 9.

To run use

luajit fssp.lua n k

Which will output two numbers. The first indicates the amount of partial transition rules analyzed. The second the amount of ones that actually solve the problem in minimal time for squads of length no more than k.

So, to obtain the result wanted is enough to check squads up to 9:

$ time luajit search.lua 4 9
241176313	0

real	9m55,358s

Which means that of the 241176313 nodes tried in the search 0 solve the FSSP in minimal time for all n in {2..9}. With 8 we
still have solutions (as reported by Sanders):

$ time luajit search.lua 4 8
241176245	27

real	9m48,725s

(runs were executed with LuaJIT 2.0.5).

States of boundary,general,soldier, firing, (and possible more) are represented by 0,1,2,3, ... respectively. Should be noted
that with four-state solution, we mean a solution with four-states not counting the boundary state 0.