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.

10 comments:

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

    ReplyDelete
  2. Nice 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!

    ReplyDelete
  3. Hi,

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

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

    ReplyDelete
  4. Sorry, this is out of topic

    I 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

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

    ReplyDelete
  6. Thomas Dybdahl AhleMay 10, 2013 at 1:34 PM

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

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

    ReplyDelete
  8. Hi 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