The Existence of Total False Sudoku

Question

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.

Answer 1

(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.

Answer 2

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 | 
+=====+=====+=====+=====+=====+=====+=====+=====+=====+

Answer 3

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.