Counting Candy Crush configurations

Abstract

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