Friday, June 11, 2010

Can you kill backtracking?

Here's a problem that has appeared at a recent contest: We are given a 7 times 7 field where some of the cells have numbers between 0 and 8, inclusive, and all remaining cells have dots. We want to find such allocation of exactly 10 stars to the cells with dots, at most one star per cell, so that each cell with a number has exactly that number of stars in its 8 adjacent cells. Moreover, we will only consider such 7 times 7 fields where such allocation of 10 stars exists and is unique.

Can you create a testcase for this problem that will kill backtracking solutions? It seems pretty hard to do at such small field, but it is possible!

Here are the official rules of this challenge: http://killbacktrack.appspot.com/rules.jsp.
And here's the website where you can test your testcases, which also keeps a scoreboard: http://killbacktrack.appspot.com/.

I've got a pretty good testcase, but I don't want to reveal it yet :) Please tell if there's some problem or possible improvement to the website.