Petr's blog

Kill backtracking!
By Petr, 14 years ago, translation, In English
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.
  • Vote: I like it
  • +33
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are you the author?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Isn't there a solution for this test case ?
2343432
3353533
1121211
0000000
0000000
0000000
0000000


Like:
*******
0*0*0*0
0000000
0000000
0000000
0000000
0000000
( i've replaced dots with zeroes to make it look better )

I get the error message: "No solution"  :(
Maybe I've missed something.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    We want to find such allocation of exactly 10 stars to the cells with dots.
    Seems, that in your testcase there are no such cells.
    → Reply