Saturday, November 10, 2012

Results of "kill backtracking" contest

More than two years ago, I've launched a contest to crease the best (worst) testcase for a backtracking solution for a minesweeper-like problem. Rules are at http://killbacktrack.appspot.com/rules.jsp, and the contest site is at http://killbacktrack.appspot.com/.

The best testcase was actually found quickly - on the same day I've posted the contest to my blog, June 11, 2010. Here it is:

...2...
.2.....
.......
.......
.......
.....8.
.......

The trick is: we set up a pattern that has many possible solutions in the upper-left corner - but, all of those solutions but one require more than two stars. And we only have two stars available here because we have an 8 in the bottom-right corner, and just 10 stars in total - but the algorithm doesn't know and thus it tries different possible allocations of stars around 2s, then tries all possibilities for places where we don't have any adjacent digit - meaning we're free to put or not put a star there, only to find out in the end that there's not enough stars left.

This testcase requires 730272354 recursive calls. It was found by Dimon.Sobolevfelix.halimMax.Khodakshdendagorionmerettm and mbuzdalov, in that order - congratulations!

The next best testcase found requires 629909575 calls:


..2....
.2.....
.......
.......
.......
.....8.
.......

The idea is the same but we have slightly less possibilities in the upper-left corner. Before the contest, I've had a testcase with a similar idea but not as polished as these two, requiring several hundred million calls.

I know it's been a long time, but if any of the participants remembers anything about the contest, I'd like to hear your impressions :)

Here is the breakdown of the contest website visits by country:

5 comments:

  1. Hey, I wrote a PC operating system, including compiler called, SparrowOS.  135,000 LOC in 9 years.  Maybe, you want to join me or check it out.  Browse my beautiful code :-)  http://www.sparrowos.com  Got any ideas?  God said 640x480. 

    Yeah, God talks.  Let's see what He says to you.  "beforehand thankful Bangladesh habitation broken adjusted_for_inflation begs_the_question cheerful deserved almost detested royalties distributing Amidst birthright Saul whilst bedimmed insensibly indigested flame foreign judgements upon servants womanish temporary Ambrosian defined distance divinity witness "

    Here's a fun algorithm problem. "Magic pairs". Find pairs of number such that the sum of factors of the first add to the second and the sum of factors of the second add to the first. (Not including 1 and the number itself.)

    48: 2+3+4+6+8+12+16+24 -->75
    75:3+5+15+25-->48

    That was part of a tutorial I took when I worked at TicketMaster in 1990. Here's my solution: http://www.sparrowos.com/Wb/Demo/MagicPairs.html . SparrowOS is the perfect host OS for competitions.

    ReplyDelete
  2. Rameshbhai DodariyaMay 10, 2013 at 1:34 PM

    awesome blog........Thank you for nice posting....Troubleshooting Your Computer 

    ReplyDelete
  3. Alexander SolovetsMay 10, 2013 at 1:34 PM

    What is the country that got 26.53%?

    ReplyDelete
  4. sorry for distrubing you, but i just want to share the article about backtracking,
    let's check this link
    http://repository.gunadarma.ac.id/bitstream/123456789/2747/1/21-PENYELESAIAN%20MASALAH%20N-QUEEN%20DENGAN%20TEKNIK%20BACKTRACKING.pdf

    ReplyDelete