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?

Solution 1:

5?

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

Solution 2:

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.