2
$\begingroup$

I'm working a program that should generate bad ass sudoku puzzles. Recently I noticed there's a thing called "logical sudoku", which means it can be logical-deducted all the way to solution. The problem is - I can't really tell if I added all possible deductions in my code.

enter image description here

This is an example of what I'v come up with so far (after all deductions I could think of). My question is - is this the edge? Or maybe I can add some more deductions to my code? Can you find another number here without guessing?

Here's a link to this state from my online program.

$\endgroup$

2 Answers 2

4
$\begingroup$

suduko689

If r6c7 is a 6, then r3c7 is an 8. Also r6c3 is 9 (the only 9 left on row) r5c2 is 5, r7c2 is 9, and r7c7 is cancelled. Therefore r6c7 us a 9, and the puzzle can be solved.

$\endgroup$
3
  • 1
    $\begingroup$ That's a correct distinction - but I'm not really sure it's a deduction... Feels more like guessing to me. Isn't it guessing? Like, how did you get there? you started writing down numbers to see if you get cancelled. No? $\endgroup$
    – Shl
    Commented Apr 15, 2020 at 20:12
  • $\begingroup$ We've just had a Sudoku question about BUG's (puzzling.stackexchange.com/questions/97090/…) , which are chains of bivalued cells. This puzzle has a lot of them, so I figured if a BUG isn't going to crash, it must force a contradiction. I started with 3 in the top-left, but this solved it, so there must be a problem with choosing 9. This eventually forces the error above, and I managed to simplify it to it's minimal form. Once a pattern has been spotted, a computer can do the machine-like searching bit. $\endgroup$
    – JMP
    Commented Apr 15, 2020 at 20:24
  • $\begingroup$ Nice find. Although I do feel like the answer is missing a conclusion though, like <rot13>Guhf, e6p7 zhfg or n 9 vafgrnq. Naq gur Fhqbxh pna or fbyirq sebz gurer.</rot13> Btw, is there a name for this technique. I've made this answer once showing 13 Sudoku techniques, but I feel like this one is another technique that could be added to the list (as is that BUG+1 approach you used earlier, although I feel like that one is a bit too situational imo). $\endgroup$ Commented Apr 15, 2020 at 20:58
2
$\begingroup$

From the standpoint of propositional logic if a Sudoku has a unique solution then that solution (and every step leading up to it) can always be reached by a logical deduction.

Put another way, for each of the 729 cell-value candidates there always exists a deductive proof that the candidate is or is not part of the solution, where the proof depends only on the standard exactly-one constraints that define Sudoku, the initial givens for the puzzle, and the single inference rule of propositional resolution. This is just a consequence of the soundness and completeness of resolution as an inference procedure in propositional logic.

That being said, even though there always exists a way to make deductive progress on a puzzle, this doesn't mean that the corresponding resolution proof is short or tree-structured or easy to find, which are some of the things people are really getting at when discussing logical methods for solving Sudoku.

With the exception of techniques based on uniqueness assumptions (which are never necessary in the framework above) all of the logical techniques that humans use in puzzle solving correspond to searches for restricted classes of resolution proofs. You could say roughly that the restricted classes we look for are those that are simple or easy to recognize or describe. But this isn't always true. It might be more accurate to say that we look for those that can be discovered with (small) bounded working memory (so you can keep things in your head without a pencil and eraser). But really there is no principled distinction between the restricted classes we associate with logical methods and the encompassing set of all resolution proofs that arise from propositional logic.

So to your question: Can you add more deductions to your code? Certainly yes. Have you added all deductions that human solvers would count as not involving guessing? This is not a well defined goal.

$\endgroup$
2
  • $\begingroup$ As I mentioned, my goal is to generate sudoku that can be deducted by humans without guessing. I want to add as much human logic as possible so it would be as harder as possible to solve. I think I did my best. Unless someone can show me another insight on the shared sudoku's state, without "guessing". (My definition of guessing is trial and error) $\endgroup$
    – Shl
    Commented Apr 16, 2020 at 20:24
  • 1
    $\begingroup$ If your goal is to incorporate as many human solving techniques as you can into your puzzle generator/rater then you may want to look for inspiration to existing tools like Hodoku or Sudoku Explainer. $\endgroup$
    – 53x15
    Commented Apr 17, 2020 at 2:35

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