19
$\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?

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

2 Answers 2

20
$\begingroup$

5?

123|   |   
   |4  |  
___|___|4__
   |   |   
   |   |   
___|___|___
   |   |   
   |   |   
   |   |   
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Aug 18, 2011 at 18:52
  • $\begingroup$ 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! $\endgroup$
    – RoundTower
    Commented Aug 18, 2011 at 21:28
11
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .