# The Existence of Total False Sudoku

Is it possible to construct a valid 9x9 puzzle of Total False Sudoku?

Total False Sudoku is a regular Sudoku puzzle where all given clue numbers are wrong. A valid puzzle is a puzzle that has only a single solution.

• Can the clue numbers even be "wrong" regarding Sudoku rules (e.g. have twice the same number in one square), or do they at least need to be "possibly" right? That will change the answer significantly I think... – Torsten Link Aug 11 '20 at 9:15
• Are there any rules for what the wrong numbers can be (like 1 more or 1 less) or can they be anything except the actual number – Beastly Gerbil Aug 11 '20 at 9:16
• Not an answer, because I've no time to make the reasoning solid enough. Anyway: rot13(N erthyne fhqbxh pyhr ehyrf bhg 8 ahzoref va n fvatyr fdhner. N pyhr gung vf whfg "jebat" jvgu ab bgure vasbezngvba ehyrf bhg 1 ahzore, be 8 gvzrf yrff. Fvapr vg gnxrf ng yrnfg 17 erthyne pyhrf gb qrsvar n havdhr fbyhgvba, vg fgnaqf gb ernfba gung ng yrnfg $16*8+1=129$ snyfr pyhrf jbhyq or arrqrq. Gurer'f bayl ebbz sbe 81.) – Bass Aug 11 '20 at 12:23
• @Bass the counting isn't quite true. For example, to start, I can see a way of writing down 13 wrong clues to guarantee two correct clues but admittedly it's difficult to roll that all the way back from 129 as you say. – hexomino Aug 11 '20 at 15:17
• A Total False Sudoku would be equivalent to a 'pencil-mark Sudoku' or 'Sukaku' with at most one candidate eliminated from every cell, or 8*81=648 candidates. Over the period from 2006 to 2019, the record for most candidates in a known Sukaku with a unique solution was pushed from 633 to 637. So while by no means a proof, I would be very surprised if this were possible. – Zomulgustar Aug 12 '20 at 5:47

## 4 Answers

(Very) partial answer (just a bit too long for a comment):

If a valid total false sudoku exists, it needs to have at least 36 clues.

Proof:

Assume a valid total false sudoku is given. For $$1\leq i,j \leq 9$$ let $$s_{i,j}$$ be the contents of the cell in the $$i$$-th row and $$j$$-th column of the solved sudoku. Also let $$c_{i,j}$$ be the corresponding clue (or $$0$$, if no clue exists). The condition of the clues means that $$s_{i,j}\neq c_{i,j}$$ for all $$i,j$$.

Let $$1\leq k, l\leq 9$$ with $$k\neq l$$. If there aren't $$i,j$$ such that either $$s_{i,j}=k$$ and $$c_{i,j}=l$$ or $$s_{i,j}=l$$ and $$c_{i,j}=k$$, then we can "swap" the digits $$k$$ and $$l$$ to get a new different solution $$s'$$ - swapping two digits doesn't invalidate the sudoku grid, and because of the assumption there still won't be $$i,j$$ with $$s'_{i,j}=c_{i,j}$$, so the clues are still satisfied. This is a contradiction to the assumption that the puzzle was valid, as there are now two distinct solutions.

This means that for every unordered pair $$k\neq l$$ of digits there has to be at least one clue where $$c_{i,j}$$ corresponds to one of the digits, while $$s_{i,j}$$ corresponds to the other. As there are $$\frac{9\cdot 8}{2}=36$$ such pairs, there are at least that many clues.

Unfortunately, I don't see any good way to go from here. While there are other sudoku "automorphisms" (such as swapping two rows from the same band) one could consider, I don't see any immediate nice way to combine those with the digit swapping. Also, considering arbitrary permutations on the digits (instead of just swapping two) doesn't seem to gain anything.

I offer no proof, but some evidence:

A Total False Sudoku is a special case of what is otherwise known as Pencilmark Sudoku or Sukaku. In Pencilmark Sudoku all the standard constraints apply, but the clues are given as candidate eliminations instead of positive assertions for the values of given cells. A Total False Sudoku is essentially a Pencilmark Sudoku with the additional restriction that no cell has more than 1 elimination: the cells with 1 elimination in the Pencilmark formulation are the cells with clues whose values are wrong in the Total False formulation.

I don't know whether it's possible to construct a Total False Sudoku, but my hunch is that it's not. Such a puzzle obviously has no more than 81 clues, and therefore has no more than 81 eliminations when expressed as a Pencilmark Sudoku. Unlike for vanilla Sudoku, there is not yet a proven bound for the minimum number of clues (eliminations) required to constrain a Pencilmark Sudoku to a single solution. However, I believe that 86 is the lowest number of clues for any Pencilmark Sudoku known today (see below for an example of an 87). The space of low-clue Pencilmark Sudoku has not been searched as intensively as the space of low-clue vanilla Sudoku, so it would not be surprising if 85 or even 84 clue puzzles exist. But 81 seems unlikely. And it seems still more unlikely that such a low-clue puzzle could satisfy the additional Total False constraint of one elimination per cell.

An 87-clue Pencilmark Sudoku:

+=====+=====+=====+=====+=====+=====+=====+=====+=====+
| 1.. | 123 | 123 | 123 | 123 | 123 | 123 | 123 | ..3 |
| ..6 | 4.6 | .56 | 456 | 45. | 456 | 456 | .5. | ... |
| 789 | 789 | 789 | 789 | 789 | 789 | 789 | .89 | ..9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 123 | 123 | 123 | 123 | 123 | 123 | 123 | 123 | .23 |
| 456 | 456 | .56 | 456 | 45. | 45. | 45. | 45. | 45. |
| 789 | 789 | 789 | 7.9 | 789 | 789 | .89 | ..9 | ..9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 123 | 123 | 123 | 123 | .23 | 123 | 123 | 123 | 123 |
| ..6 | 4.6 | .56 | 456 | 456 | 456 | .5. | 456 | .56 |
| 789 | 789 | 789 | 789 | 78. | 789 | .89 | .89 | .89 |
+=====+=====+=====+=====+=====+=====+=====+=====+=====+
| 123 | 123 | 123 | 123 | 123 | 123 | 123 | 123 | 123 |
| 456 | 456 | 456 | 456 | 456 | 456 | 456 | 456 | 456 |
| 789 | 789 | 7.9 | 7.9 | 789 | 789 | 7.9 | ..9 | 7.9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 123 | 123 | .23 | 123 | 123 | 123 | 123 | 123 | .23 |
| 456 | 456 | 456 | 456 | 456 | 456 | 456 | 456 | 456 |
| 789 | 789 | 789 | 789 | 789 | 789 | 7.9 | ..9 | 7.9 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1.3 | 1.3 | 1.3 | 1.3 | 123 | 1.3 | 123 | 123 | ..3 |
| ... | 456 | .56 | ..6 | 456 | ... | 456 | 456 | ..6 |
| 789 | 789 | 789 | 789 | 789 | 789 | 789 | 789 | 7.9 |
+=====+=====+=====+=====+=====+=====+=====+=====+=====+
| 123 | 123 | 123 | 123 | 123 | 123 | 123 | 1.3 | 123 |
| 4.6 | 456 | 456 | 456 | 456 | 456 | .56 | 456 | 456 |
| 789 | 789 | 789 | 789 | 789 | 789 | 789 | .89 | 789 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 123 | 123 | .23 | 1.3 | .23 | 123 | 123 | 123 | 123 |
| 456 | 456 | .56 | 456 | 45. | 456 | 456 | 456 | 456 |
| 789 | 789 | 789 | 789 | 789 | 789 | 789 | .89 | 789 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 123 | 123 | 123 | 123 | 123 | 123 | 123 | 123 | 123 |
| 456 | 456 | 456 | 456 | 45. | 456 | 456 | 456 | 456 |
| 789 | 789 | 789 | 789 | 789 | 789 | 789 | .89 | ..9 |
+=====+=====+=====+=====+=====+=====+=====+=====+=====+

• How should one read this pencil mark suduko? Every box contains hints, which numbers are not allowed in the corresponding tile of the sudoku? and 87 correspond to what? the dots ? – daw Aug 12 '20 at 11:35
• Correct. The board is just as if you had decorated each cell of a regular Sudoku: the digits represent candidates that might fill the cell and the dots represent candidates that have been ruled out (i.e. the "clues" of pencilmark Sudoku). If there were no more than one dot per cell and the puzzle was still constrained to a single solution, then we would have a Total False Sudoku. – 53x15 Aug 12 '20 at 15:33

It's possible to do an Total False Irregular Sudoku: Use the grid from

Your Task Is to Create the World's Hardest Irregular Sudoku!

and replace each digit with that digit in every other cell in the column.

• Ah, actually the question asks for a standard Sudoku grid, but yes your answer is correct if we use an irregular version. – athin Nov 24 '20 at 13:45

I don't have a lot of calculations, but here is my answer.

It is impossible to have a Total False Sudoku

My reasoning:

In order for a sudoku clue to be wrong, there must be a solution to the board that can be reached by replacing wrong clues with right clues. If we remove all the wrong clues from a board one-by-one, we will eventually be left with a singular clue. It is impossible for a singular clue to be wrong, since a singular clue can fit a large number of valid sudoku boards. Therefore, any board with any number of clues greater than one is guaranteed to have a singe clue that is correct.

Update based on comment feedback:

In order for a sudoku puzzle to fit the parameters of a Total Wrong Sudoku, it must have only one valid solution. Let's assume we have a board with a number of clues that all differ from the intended solution to the puzzle. Using my previous logic, it is possible to select any one number from the set of clues and change it to another number which in turn has a large number of solutions. Because every single clue is wrong, we can change those clues to fit any number of these possible solutions. Therefore, a sudoku that is made entirely out of wrong clues cannot have a singular unique solution, since any individual wrong clue can be used to form at least one unique and valid solution.

• There’s a uniqueness aspect that’s missing from this answer, I think — any one clue by itself generates a sudoku solution but not a unique one. it’s the combination of clues (in this case, incorrect), which may possibly combine to form a valid AND unique solution. – El-Guest Aug 11 '20 at 16:59
• ah, okay, i understand what you're saying. i'll look into my answer some more – Bewilderer Aug 11 '20 at 17:01
• "Total False Sudoku" does not mean "a puzzle where there is one way to fill the grid so at least one number is wrong", but "a puzzle where there is one way to fill the grid so that every number is wrong". It doesn't matter that you can change a clue and keep it wrong: that's not what the question is asking. [...] – Deusovi Aug 11 '20 at 21:29
• [...] In other words, we're looking for a puzzle (a partially-filled 9x9 grid) and a solution (a full 9x9 grid) so that:  The solution satisfies the usual Sudoku rules.  In the puzzle, every single digit is different from the solution.  There is no other solution that satisfies both of the other two rules. // You showed that we can always find another puzzle that satisfies the other rules, but that's not what's being asked. – Deusovi Aug 11 '20 at 21:31