Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Presumably you mean one that doesn't already trivially violate the row, column and box constraints? –  MGwynne Aug 18 '11 at 17:36
4  
2 (Edit: Ah, @MGwynne beat me to the punch.) –  Willie Wong Aug 18 '11 at 17:39
5  
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
add comment

2 Answers

up vote 12 down vote accepted

5?

123|   |   
   |4  |  
___|___|4__
   |   |   
   |   |   
___|___|___
   |   |   
   |   |   
   |   |   
share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.