# Minimally inconsistent Sudoku puzzle

A sudoku puzzle is a partially filled $9\times 9$ grid with numbers $1,\ldots,9$ such that each column, each row, and each of the nine 3×3 sub-grids that compose the grid does not contain two of the same number.

What is the minimal number of entries needed to produce an inconsistent puzzle, i.e., a puzzle that can not be completed to one where there is a solution?

EDIT: Now that there is an example where 5 is attained, can one show that this is the least possible, i.e., that any non-trivial puzzle with 4 entries can be completed to a solution?

-
Presumably you mean one that doesn't already trivially violate the row, column and box constraints? –  MGwynne Aug 18 '11 at 17:36
2 (Edit: Ah, @MGwynne beat me to the punch.) –  Willie Wong Aug 18 '11 at 17:39
I defined a sudoku puzzle as an arrangement where these constraint are not violated. So 2 is not the answer. –  Bonanza Aug 18 '11 at 17:44

5?

123|   |
|4  |
___|___|4__
|   |
|   |
___|___|___
|   |
|   |
|   |

-
5 probably is the minimum. If the four initial entries given are anything other than two repeating pairs, by renumbering, swaping "bands", and swapping rows/columns within the same band, we can find a solution of the form [123456789,456789123,789123456,234567891,...]. If the four numbers given are all contained in the same band, we can trivially complete the band, and a standard procedure can turn the completed band (with no further constraints) into a completed square. The remaining I am not sure how to get a standard procedure to do. –  Willie Wong Aug 18 '11 at 18:52
Re the two repeating pairs -- I think you can actually put 9 1's and 2 2's anywhere legal and the puzzle is still solvable. Can't prove it though, even for 2 2's! –  RoundTower Aug 18 '11 at 21:28

I doubt there will be an easy-to-read explanation of the non-incompletability of partial sudoku with at most 4 non-empty cells. I attempted to form a proof of the 3 non-empty cell case (which is much easier), and it split into a large number of cases already. So, I instead opted for a computational solution. My C++ code is below (it's a simple backtracking algorithm).

Since we have exactly 4 symbols, there distribution of symbols into bands is either {2,1,1}, {2,2,0}, {3,1,0} or {4,0,0}. Thus, we can assume:

• The last two rows are empty,
• There exists another non-empty cell in the first four rows,
• The top left cell contains 1.

If these don't occur in a particular example, you can permute the rows/columns/symbols so that it does, while preserving the sukoku properties. Then we complete this case, then reverse the permutation on the completed sudoku to obtain a completion of the particular example in question. There's stricter conditions we could assume that would reduce the search space (but they weren't required).

The code found no examples in which a partial sudoku with 4 non-empty cells was incompleteable: in every case, a completion was constructed.

#include <stdio.h>
#include <stdlib.h>

int predetermined_cells[9][9];
int test_matrix[9][9];

void print_current_matrix() {
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
printf("%d ",test_matrix[i][j]);
}
printf("\n");
}
printf("\n");
}

/* checks for clashes of the entry test_matrix[i][j] */
int check_for_clashes(int i, int j) {
for(int k=0;k<9;k++) {
if(k!=i && test_matrix[k][j]==test_matrix[i][j]) { return 1; }
/* same symbols in same column */
if(k!=j && test_matrix[i][k]==test_matrix[i][j]) { return 1; }
/* same symbols in same row */
}

int p=i/3,q=j/3;
p=3*p;
q=3*q;
for(int k=0;k<3;k++) { for(int l=0;l<3;l++) {
if(p+k!=i || q+l!=j) {
if(test_matrix[p+k][q+l]==test_matrix[i][j]) { return 1; } /* block clashes */
}
} }

return 0;
}

int recursion(int pos) {
if(pos==81) {
//print_current_matrix();
return 1;
}

int i=pos/9,j=pos%9;
if(predetermined_cells[i][j]!=0) {
return recursion(pos+1);
}
else {
for(int k=1;k<=9;k++) {
test_matrix[i][j]=k;
if(!check_for_clashes(i,j)) {
if(recursion(pos+1)) { return 1; }
}
}
}
test_matrix[i][j]=0;
return 0;
}

void update_predetermined_cells() {
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
test_matrix[i][j]=predetermined_cells[i][j];
}
}
}

void main() {
predetermined_cells[0][0]=1;

for(int posA=1;posA<36;posA++) {
printf("%d out of 35\n",posA);
for(int posB=posA+1;posB<63;posB++) {
for(int posC=posB+1;posC<63;posC++) {
for(int symA=1;symA<=9;symA++) {
for(int symB=1;symB<=9;symB++) {
for(int symC=1;symC<=9;symC++) {
int rowA=posA/9,colA=posA%9,rowB=posB/9,colB=posB%9,rowC=posC/9,colC=posC%9;
predetermined_cells[rowA][colA]=symA;
predetermined_cells[rowB][colB]=symB;
predetermined_cells[rowC][colC]=symC;
update_predetermined_cells();
if(!check_for_clashes(rowA,colA) && !check_for_clashes(rowB,colB) && !check_for_clashes(rowC,colC)) {
if(!recursion(0)) {
printf("[%d,%d,%d], [%d,%d,%d], [%d,%d,%d] %d\n",rowA,colA,symA,rowB,colB,symB,rowC,colC,symC);
}
}
predetermined_cells[rowA][colA]=0;
predetermined_cells[rowB][colB]=0;
predetermined_cells[rowC][colC]=0;
}
}
}
}
}
}
}


This problem relates to the Evans Conjecture in Latin squares, which states that any $n \times n$ partial Latin square, consisting of $n-1$ non-clashing filled cells, can be completed to a Latin square. This result was subsequently proved by:

B. Smetaniuk, A new Construction on Latin Squares. I. A Proof of the Evans Conjecture. Ars Combinatoria (11) 1981, pp. 155-172.

-