Consider the following game (see also this question):One day a castle is attacked at sunrise (by surprise) by n soldiers.Each soldier carries a canon and a rifle. The castle has strength s.On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points).After all the soldiers have fired, the castle sends dpw defenders to battle them.In the ensuing days the castle and the soldiers battle it out following these rules:All the soldiers fire first. A soldier can fire his canon at thecastle or his rifle at one of the defenders (but not both and eachsoldier can only shoot once). One shot at a defender kills him. Oneshot at the castle decreases its strength by 1.Then each of the d defenders shoots at one soldier (and onlyone) killing him. If the castle still has strength points (i.e. s>0) it sends anew batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.Repeat 1 through 3 on each new day.If all soldiers are killed by the defenders, the castle wins.If there are zero defenders after the soldiers shoot and thecastle strength is zero, the soldiers win.The answer to this question gives the strategy the soldiers should follow to win in a minimum number of rounds.If $$n\leq s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n$$, the strategy that leads to a victory for the soldiers in the minimum number of rounds consists of the soldiers shooting only at the castle in the first and second days and destroying it, and from then on, the soldiers trade fire with the remaining defenders winning in a total of$2+\max(k,0)$ days, where$$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$If $dpw<n$, the soldiers can win in a minimum of $c+\max(k,0)$ days, where$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$and$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$In this case they shoot, in each round, at the defenders first then the castle for $c$ days which is the time it takes to destroy the castle.What is an algorithm to find systematically all the strategies that lead to a win by the soldiers not just the minimum day strategy?For example if $n=10, s=12, dpw=10$, there are 2 solutions in which the soldiers win:The first where the number of soldiers, defenders and castle strength goes like this (in 3 rounds)start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12  round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2round2:'soldiers': 8, 'defenders': 2, 'castle-strength': 0round3:'soldiers': 8, 'defenders': 0, 'castle-strength': 0and the second solution where it goes like this (4 rounds)start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 1round3:'soldiers': 6, 'defenders': 3, 'castle-strength': 0round4:'soldiers': 6, 'defenders': 0, 'castle-strength': 0(in the particular case where $dpw=n$, like in the example above, there is an infinite number of solutions as @rotia points out, where the 10 soldiers eliminate the 10 defenders in either the 3rd or 4th or 5th... round before destroying the castle)
Finding all soldier wins
algorithms;optimization;search algorithms;dynamic programming;backtracking