Assume you have a sudoku solver that will find the first 100 solutions (at most) of a puzzle. What is the minimum number of blank spots needed to hit this 100 solution limit?

Elaborate.

Edit: Nevermind, a combination of my unfamiliarity with Sudoku and the fact that I had barely rolled out of bed at the time confused me.

There's no need for smittens to elaborate, I think. I understand the problem, but do not know how to solve it (yet).

Bad smittens. No graph theory and combinatorics in the morning.

I posted yesterday afternoon...

Interesting problem... I'll think harder about it after I've eaten.

1000

...wow. He got it.

[DELETED BY WHISTLER] - no giving out how you got the answer

Heh, Lecter. You know, that xkcd is actually accurate?

Hooray for déformation professionnelle.

So, I'm not convinced that there's an analytic solution to this problem... And any experimental solution will likely require an exponential-time search through the decision trees...

Yeah, I was thinking the same thing. I can't prove it, but I'm confident enough to stop banging my head against it.

I haven't entirely given up though, heh.

You might be right... this isn't a real question or a homework question or anything. For my class we had to program sudoku solvers which find the number of solutions in a puzzle. But it's also supposed to cap at 100 solutions and just return. As I was blanking out puzzles to make sure that cap worked, I wondered exactly how many blanks it would take, so here is the post.

And this kind of stuff isn't my strong point, but it seems like there would be an analytical solution? Because..
- Different patterns of filled in numbers make the board easier (IE more solutions) and harder, so there must be a way to figure out the easiest layout given some number of filled in spots
- Adding blanks seems like it would have a consistently mathematical change on the number of solutions, assuming a logically constant pattern among the filled in numbers

So if you could figure those out, you could get an answer?

Adding blanks seems like it would have a consistently mathematical change on the number of solutions, assuming a logically constant pattern among the filled in numbers

No, not necessarily. Due to the rules of sudoku, the effect of adding an additional blank is modified by every single other space on the board.

As far as we can tell, you'd have to re-analyze the board every time.

But it seems like if the rest of the board is filled out in a certain pattern, you could know what making a certain spot blank would do?

Yes, you could, by re-analyzing the board for each new possible combination.

That doesn't get us any closer to a remotely fast method of solving the original problem.

Maybe look for patterns? They found patterns in prime distribution. There might be patterns in sudoku solutions. I do not mean to directly relate one to the other with this post.

So, my understanding is that it's an open problem what the minimum number of givens to have a single unique solution is. Your problem seems like it is harder than that...