Quote:
Originally Posted by JoeP
If minimising yellows is a goal (maybe ...), would it be viable to try possible yellows in turn rather than always building them up, and only go to 2 yellows if no single one makes the solution unique?
It's only a little combinatorial explosion.
|
Yes, a recursive search would do the trick, and by keeping track of the 'lowest number of yellows for a solution found so far' and abandoning the recursion whenever the number of tried yellows reaches that count, most of the branches of the search tree would be pruned back fairly quickly. I think it's doable.
Of course, if you really want to minimize yellows, then by choosing a different set of green clues for the same solved grid, you could get the number of yellows down to zero. Sudoffle always provides 32 green clues, which it currently chooses entirely at random - it could keep trying to solve the puzzle, swapping the position of a chosen green until there's a unique solution.
I think it would always be able to do this with 32 greens: it's been shown that the maximum possible number of clues required to guarantee a unique solution is either 39 or 40 - but that's only by carefully choosing a solved grid, and then giving the worst possible set of clues for that grid.
I like the fact that (most) Sudoffle puzzles have some initial yellows - it's one of the things that sets it apart from most other Sudoku puzzles.