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.