17
$\begingroup$

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?

  • 6
    I defined a sudoku puzzle as an arrangement where these constraint are not violated. So 2 is not the answer.2011-08-18

2 Answers 2

19

5?

123|   |       |4  |   ___|___|4__    |   |       |   |    ___|___|___    |   |       |   |       |   |    
  • 0
    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!2011-08-18
9

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  #include   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.