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.

## Friday, June 11, 2010

Subscribe to:
Post Comments (Atom)

500 Server Error :(

ReplyDeleteLooks to be http://groups.google.com/group/google-appengine-downtime-notify/browse_thread/thread/ad8e0dd4a86a87cd

ReplyDeleteYes, i can

ReplyDeleteNice challenge :) It would be great to see more thoughts on inventing good test data, it can be more challenging than solving the problem itself... I'm waiting for KillInefficientMaxFlow, KillHeuristicKnapsack, and a dozen more KillBacktracks!

ReplyDeleteHi,

ReplyDeleteI am having problems with one problem and wonder if you can give me some help. Thanks in advance! :)

https://www.spoj.pl/problems/SHOOTING/

Sorry, this is out of topic

ReplyDeleteI don't understand the reason for details in Large dataset info for Google code jam 2010 world final

problem F

Isn't was enough to say:

Large dataset

4 ≤ N, M ≤ 100

Hey Petr, Can u tell me how to improve mathematics for programming.

ReplyDeleteIt's been a while since this contest started. Is it time for an editorial? ;-)

ReplyDeleteGreat idea! Done: http://petr-mitrichev.blogspot.ru/2012/11/results-of-kill-backtracking-contest.html

ReplyDeleteHi Petr, I need some help with the problem C of ACM Regional Latin America 2009 named Code Lock.I Have some ideas but I really need a good solution

ReplyDelete