Counting Candy Crush Configurations

• Published in 2019
• Added on 2021-01-06

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 with7 available colours there are approximately 4.3*10^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.

Links

• http://arxiv.org/abs/1908.09996v1
• http://arxiv.org/pdf/1908.09996v1

Other information

BibTeX entry

@article{CountingCandyCrushConfigurations,
	key = {CountingCandyCrushConfigurations},
	type = {article},
	title = {Counting Candy Crush Configurations},
	author = {Adam Hamilton and Giang T. Nguyen and Matthew Roughan},
	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 with7 available colours there are approximately 4.3*10^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.},
	comment = {},
	date_added = {2021-01-06},
	date_published = {2019-12-07},
	urls = {http://arxiv.org/abs/1908.09996v1,http://arxiv.org/pdf/1908.09996v1},
	collections = {combinatorics,games-to-play-with-friends},
	url = {http://arxiv.org/abs/1908.09996v1 http://arxiv.org/pdf/1908.09996v1},
	year = 2019,
	urldate = {2021-01-06},
	archivePrefix = {arXiv},
	eprint = {1908.09996},
	primaryClass = {math.CO}
}