Rompecabezas de Sudoku mínimamente inconsistente

5?

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

Dudo que haya una explicación fácil de leer de la no incompletabilidad del sudoku parcial con un máximo de 4 celdas no vacías. Intenté formar una prueba del caso de 3 celdas no vacías (que es mucho más fácil), y ya se dividió en una gran cantidad de casos. Entonces, opté por una solución computacional. Mi código C ++ está debajo (es un algoritmo de retroceso simple).

Dado que tenemos exactamente 4 símbolos, la distribución de símbolos en bandas es {2,1,1}, {2,2,0}, {3,1,0} o {4,0,0}. Así, podemos suponer:

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

Si esto no ocurre en un ejemplo particular, puede permutar las filas/columnas/símbolos para que así sea, conservando las propiedades de sukoku. Luego completamos este caso, luego invertimos la permutación en el sudoku completo para obtener una finalización del ejemplo particular en cuestión. Hay condiciones más estrictas que podríamos suponer que reducirían el espacio de búsqueda (pero no eran necesarias).

El código no encontró ejemplos en los que un sudoku parcial con 4 celdas no vacías fuera incompleto: en todos los casos, se construyó un completo.

#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 relaciona con la conjetura de Evans en cuadrados latinos, que establece que cualquier$n \times n$cuadrado latino parcial, formado por$n-1$las celdas llenas que no chocan, se pueden completar en un cuadrado latino. Este resultado fue probado posteriormente por:

B. Smetaniuk, Una nueva construcción sobre cuadrados latinos. I. Una prueba de la conjetura de Evans. Ars Combinatoria (11) 1981, pp. 155-172.