7
$\begingroup$

When checking if a 9x9 Sudoku solution is valid in the absence of an answer key it may not be necessary to check every row, column and 3x3 box.

What is the minimum number of items (rows, columns, or boxes) you must check if the only information you get from a check is whether that specific item is valid?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ This should be an interesting game theory question. Mathematics of Sudoku $\endgroup$
    – Raystafarian
    Commented Feb 4, 2016 at 18:40
  • $\begingroup$ I believe the minimum will depend on the question. for some questions, lesser number of numbers were necessary, for some questions you mightn ned lots of extra numbers to solve it. $\endgroup$
    – Oray
    Commented Feb 4, 2016 at 19:17
  • $\begingroup$ @Oray I am not trying to solve it. I want to know if a solution is correct as quickly as possible (or something like that). $\endgroup$
    – StrongBad
    Commented Feb 4, 2016 at 19:20
  • 2
    $\begingroup$ @StrongBad if checking that a solution is correct, you need to check each box once, that is a total of 81. This can be cut down a bit if you already knew what the initial numbers were. Lets say x numbers were given then you need to check 81-x boxes. Take a scenario where you don't check one of the squares, how can you say for sure that the one you skipped has the correct number? You cannot. Hence you need to check every square once. $\endgroup$
    – stackErr
    Commented Feb 4, 2016 at 19:24
  • 2
    $\begingroup$ There are several solutions already on SO: stackoverflow.com/questions/5484629/… And MO: mathoverflow.net/questions/129143/… $\endgroup$
    – stackErr
    Commented Feb 4, 2016 at 19:35

2 Answers 2

Reset to default
4
$\begingroup$

Welp, you need to check almost all rows and columns. Proof by counterexample:

Let X be a correct solution. Switch the topleft square with its right neighbour. All rows and boxes still check out but two columns do not. Same for rows if you switch two vertically aligned squares. So you can skip at most one row/column.

The only thing you can skip, after having checked all 9 of one item(say rows), is that you only need to check 8 of the other 2 items(columns and boxes), as it's already clear that there are 9 of each number. Alternatively, after fully checking rows and columns, you can skip boxes 1, 5 and 9(or 3 other boxes so that they do not align)(because there are 3 of the number in the 3 rows/columns it uses, and the other 2 boxes in those rows/columns are checked).

EDIT: That's a mighty useful link, mathoverflow has thought this through a lot. Paraphrasing the pages of text found there:

When you have checked the columns and rows, you can skip some boxes. Having checked the top 3 rows and boxes 1 and 2, you don't need to check box 3. Likewise you don't need to check box 6 if you have 4 and 5, and the bottom boxes are proven correct by having checked the columns and the first six boxes. The last row is proven correct by the bottom 3 boxes and the two rows above it. So you can skip 1 row and 5 boxes for 21 checks total.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What exactly do you mean by almost everything? Can you show that you can't select which ones you check to lessen the amount of work you have to do? $\endgroup$
    – Deusovi ♦
    Commented Feb 25, 2016 at 14:38
  • $\begingroup$ You answer suggests 23 checks (9+8+6) while this question at MO.SE seems to suggests that it can be done in at most 21 checks. That said, I have no idea what is being checked in those answers and I can implement your answer and save 4 checks. $\endgroup$
    – StrongBad
    Commented Feb 25, 2016 at 14:58
0
$\begingroup$

this was made obsolete by a subsequent edit

Conjecture: Given a unique solution to a Sudoku puzzle, one must check all squares that are not given in order to confirm its correctness

Proof:

Suppose that only one square on a board does not match the solution. Let us check all other squares that were not "given" (i.e. printed into the puzzle when given to you to solve). All of them will be correct. However, the puzzle is incorrect.

Understand that this refers to the minimum number needed to prove the puzzle is correct. This doesn't consider the minimum number to confirm it is wrong (i.e. 1). I'm assuming the asker isn't referring to that (trivial) value.

Going in response to the edit, here is a partial answer. This a pretty tricky puzzle to nail down an algorithm for that is most efficient. Therefore, I will work by proving more conjectures.

If a row/column is inconsistent then there exists another row/column/block that is inconsistent.

Proof: I'm still thinking about how to phrase it. I need to think about it a while.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Without an answer key you cannot check a square, you can only check rows, columns and 3x3 boxes. I am interested in the case where there is no answer key. $\endgroup$
    – StrongBad
    Commented May 23, 2017 at 21:58
  • $\begingroup$ @StrongBad where is it stated that I am not given an answer key? $\endgroup$
    – user64742
    Commented May 23, 2017 at 22:40
  • 1
    $\begingroup$ I think the framing of the question in terms of checking rows, columns, and 3x3 boxes would be a little strange if there was an answer key. I will edit the question to be clearer. $\endgroup$
    – StrongBad
    Commented May 23, 2017 at 22:46
  • $\begingroup$ @StrongBad that makes more sense now. $\endgroup$
    – user64742
    Commented May 23, 2017 at 22:48

Your Answer

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

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