4
$\begingroup$

I want to build a specific puzzle box. The physical side I have down, but I'm struggling with ensuring that there's only one valid solution.

The box consists of 9 freely rotating bands, inscribed with a random looking set of digits 1-9. The exact number of digits on each ring is about 30, but I can tweak the design to vary this slightly if it helps. A window allows a 9x9 grid of digits (so 9 adjacent digits from each ring) in a classic sudoku grid.

My problem is how to generate the digits on the rings such that there is exactly one valid sudoku grid that can be formed by rotating them.

If necessary I can brute force it, but that will take hours or days to run; does anybody have a better solution?

Thanks in advance

Improve this question
$\endgroup$
2
  • $\begingroup$ Assuming you're talking about code to check it. This question is probably better suited to Stack Overflow, here is a similar question [stackoverflow.com/questions/1697334/… $\endgroup$
    – Jon.G
    May 18, 2018 at 12:13
  • $\begingroup$ Are you talking about this cube? $\endgroup$
    – Ian MacDonald
    May 18, 2018 at 12:54

1 Answer 1

Reset to default
2
$\begingroup$

Brute force away, it's much faster than you think.

Here are some back-of-the-envelope numbers:

First of all, given a band of 30 digits, there aren't going to be very many ways to choose a spot where all 9 digits are unique. But let's assume there are 30.

Adding a second such strip, and checking the sudoku squares constraint, the first digit will fit with 6/9 probability, the next one with 5/8, and the third with 4/7, so you have about one in four chance of matching the first square. Out of the 30 possible second strip positions, this leaves about 8, out of which there is a slim chance that any one will satisfy the squares constraints. Let's say that one always will. (EDIT: turns out there is exactly a 1 in 30 chance of a random valid sudoku row satisfying the square constraint with another random valid sudoku row, so our estimate was way too accurate for this kind of calculation.)

So, after the second band, we have performed about 900 checks, and we have about 30 candidates left

Checking the square constraint for the third band then, it is pretty much guaranteed that no position will fit. Since each square has its three numbers dictated by the square constraint, there are exactly 216 possible rows among the 362880 (nine factorial) valid sudoku rows, and the probability of a random one fitting is therefore 1 in 1680. So the third band isn't really going to fit unless the bands are designed with that property in mind, but for argument's sake, let's say we find one such combination for each candidate anyway.

After the third band, we have performed about 1800 checks, and we are left with 30 plausible configurations, since we were extremely generous.

From then on, each digit will also have to be different from the three digits on the earlier bands, so the probability of finding a valid position for the next band is going to fall even faster. This means that adding more bands to the mix doesn't add exponentially many new positions to check, instead the number of plausible candidates will start to decrease after each additional band, no matter how generous we are.

From these numbers, it would seem that a brute force check should be easily doable in an hour or less; given enough caffeine, it should be possible even manually.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If I understand correctly, you describe how to check if the given puzzle configuration has a unique solution. I'd actually expect that checking that is a matter of seconds, not hours (however, I didn't implement it, so I may be wrong). The much more complicated problem is to generate a valid puzzle configuration, which is what the OP was actually asking. $\endgroup$
    – Sleafar
    May 18, 2018 at 16:52
  • $\begingroup$ @Sleafar, armed with a tool for checking (in seconds) whether a particular puzzle has a unique solution, the (not really all that complicated) generation method goes like this: Pick a sudoku, any sudoku. Add noise around the edges. Check if the resulting puzzle still has a unique solution. It almost certainly does. (See above for details). Done. $\endgroup$
    – Bass
    May 18, 2018 at 17:08
  • $\begingroup$ You might be right, but if each strip has only 1 position where no digit is repeated (which would be the probable case for random numbers), then the whole puzzle becomes pretty trivial. $\endgroup$
    – Sleafar
    May 18, 2018 at 17:21
  • $\begingroup$ Sorry if I sound terse (the toddlers have decided their favourite pastime is trying to annoy me), but shouldn't the difficulty level of the puzzle (read: selecting which particular noise to use) be for the puzzle designer to decide? $\endgroup$
    – Bass
    May 18, 2018 at 17:46
  • $\begingroup$ Given the search space is waaaaay smaller than I thought, I can easily enough rig my generator to give 'nearly right' answers to make the whole problem difficult. Thanks, @Bass $\endgroup$
    – Funcan
    May 23, 2018 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.