Mínimamente inconsistente rompecabezas de Sudoku

Question

Un rompecabezas de sudoku es un parcialmente llenos $9\times 9$ cuadrícula con números de $1,\ldots,9$ de tal forma que cada columna, cada fila y cada uno de los nueve 3×3 sub-redes que componen la cuadrícula no se contienen dos del mismo número.

¿Cuál es el número mínimo de entradas que se necesita para producir un incoherente de puzzle, es decir, un rompecabezas que no puede ser completado a uno donde hay una solución?

EDIT: Ahora que hay un ejemplo donde 5 es alcanzado, se puede mostrar que este es el menos posible, es decir, que no trivial de puzzle con 4 entradas puede ser completado a una solución?

Answer 1

5?

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

Answer 2

Dudo que habrá un fácil-a-lea la explicación de la no-incompletability parcial de sudoku con un máximo de 4 celdas no vacías. Hice el intento de formar una prueba de la 3 celda no vacía caso (que es mucho más fácil), y se divide en un gran número de casos ya. Así que, yo en su lugar optó por una solución computacional. Mi código de C++ es la siguiente (es un sencillo algoritmo de retroceso).

Ya tenemos exactamente 4 símbolos, la distribución de los símbolos en las bandas es {2,1,1}, {2,2,0}, {3,1,0} o {4,0,0}. Por lo tanto, podemos asumir que:

• Las dos últimas filas están vacíos,
• Existe otra celda no vacía en las cuatro primeras filas,
• La celda superior izquierda contiene 1.

Si estos no ocurren en un ejemplo particular, se puede permutar las filas/columnas/símbolos de modo que, mientras que la preservación de la sukoku propiedades. Luego de completar este caso, entonces la inversa de la permutación en el completado de sudoku para obtener la conclusión de que el particular ejemplo en la pregunta. Hay condiciones más estrictas que se podría suponer, que podría reducir el espacio de búsqueda (pero no necesario).

El código encontrado ningún ejemplo en el que un parcial de sudoku con 4 celdas no vacías se incompleteable: en cada caso, la conclusión fue construido.

#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;
            }
          }
        }
      }
    }
  }
}

Este problema se refiere a la Evans Conjetura en cuadrados latinos, que establece que cualquier $n \times n$ parcial de cuadrado latino, que consta de $n-1$ no choque lleno de células, puede ser completado a un cuadrado latino. Este resultado fue posteriormente demostrada por:

B. Smetaniuk, Una nueva Construcción de Cuadrados latinos. I. Una Prueba de la Evans Conjetura. Ars Combinatoria (11) de 1981, pp 155-172.