Counting Candy Crush configurations

Abstract A k -stable c -coloured Candy Crush grid is a weak proper c -colouring of a particular type of k -uniform hypergraph. In this paper we introduce a fully polynomial randomised approximation scheme (FPRAS) which counts the number of k -stable c -coloured Candy Crush grids of a given size ( m , n ) for certain values of c and k . We implemented this algorithm on Matlab, and found that in a Candy Crush grid with 7 available colours there are approximately 4 . 3 × 1 0 61 3-stable colourings. (Note that, typical Candy Crush games are played with 6 colours and our FPRAS is not guaranteed to work in expected polynomial time with k = 3 and c = 6 .) We also discuss the applicability of this FPRAS to the problem of counting the number of weak c -colourings of other, more general hypergraphs.