Número de sudokus con ninguna progresión aritmética consecutiva de longitud 3 en cualquier fila o columna.

Question

¿Cuántos de esos Sudokus existen? Cualquier referencia a documentos, libros, artículos o cualquier información sobre el problema será muy apreciada.

He probado varios motores de búsqueda, estudiante y no, con ningún resultado. Tal vez es una terminología para ellos que desconozco.

EDIT1 Título actualizado. Sin AP de cualquier fila o columna.

EDIT2 Título actualizado. AP consecutivo.

Answer 1

Por la manera de abordar este problema desde una perspectiva computacional aquí sigue un programa que produzca estos sudokus en la esperanza de que el lector pueda beneficiarse de las placas que se utilizan y tal vez inventar un más compacto/algoritmo eficiente. Lo que se utiliza aquí es retroceso en su forma más básica. Hemos barrido de la junta de fila por fila, colocando compatible valores que no contradice ninguna de las restricciones (filas/columnas/cuadros). En la máquina donde se ha probado soluciones son producidos casi al instante. Para más detalles sobre el método que recomienda la upvoted trabajo por MJD en este MSE enlace. Aquí están los primeros sudokus sin progresión aritmética de longitud tres:

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
5 3 2 6 9 1 7 4 8
6 8 7 5 4 2 9 3 1
9 4 1 7 3 8 5 6 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
5 3 2 6 9 1 7 4 8
9 4 1 7 3 8 5 6 2
6 8 7 5 4 2 9 3 1

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
6 8 7 5 4 2 9 3 1
9 4 1 7 3 8 5 6 2
5 3 2 6 9 1 7 4 8

Algunas soluciones adicionales son

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
7 4 2 6 1 8 9 3 5
6 3 5 9 4 2 7 1 8
9 8 1 5 3 7 4 6 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 4 1 5 3 2 7 6 8
7 3 5 6 4 8 9 1 2
6 8 2 9 1 7 4 3 5

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 8 1 5 3 7 4 6 2
6 3 5 9 4 2 7 1 8
7 4 2 6 1 8 9 3 5

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 8 1 5 3 7 4 6 2
6 4 5 9 1 2 7 3 8
7 3 2 6 4 8 9 1 5

El código Perl para esto fue como sigue:

#! /usr/bin/perl -w
#

sub búsqueda {
 my ($bordo, $regiones, $sofar) = @_;

 if($sofar == 9*9){
 para(mi $fila = 0; $fila < 9; $fila++){
 para(mi $col = 0; $col < 9; $col++){
 print "" si $col > 0;
 print $tabla->[$fila][$col];
}
 print "\n";
}
 print "\n";

de retorno;
}

 mi $col = $sofar % 9; my $fila = ($sofar-$col) / 9;

 para(mi $val = 1; $val <= 9; $val++){
 $tabla->[$fila][$col] = $val;

 mi $admitir = 1;
 foreach my $región (@$regiones){
 mi %visto; mi $vacía = 0;

 foreach my $ranura (@$región){
 mi $ent = $tabla->[$ranura->[0]][$ranura->[1]];

 if($ent == -1){
$vacía++;
}
else{
 $visto{$ent} = 1;
}
}

 si(escalares(teclas(%visto))+$vacía != 9){
 $admitir = undef;
último;
}
}

if($row>=2){
 mi @ap = (
$tabla->[$fila-2][$col],
$tabla->[$fila-1][$col],
$tabla->[$fila][$col]);
 if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
 $admitir = undef;
}
}

if($col>=2){
 mi @ap = (
$tabla->[$fila][$col-2],
$tabla->[$fila][$col-1],
$tabla->[$fila][$col]);
 if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
 $admitir = undef;
}
}


 búsqueda($bordo, $regiones, $sofar+1) 
 si se define($admitir);

 $tabla->[$fila][$col] = -1;
}
}

 PRINCIPAL: {
 mi $regiones = [];

 para(mi $line = 0; $line < 9; $line++){
 mi $region = [ 
 mapa {
 [$linea, $_]
 } (0..8) ];
 push @$regiones, $región;

 $region = [ 
 mapa {
 [$_, $line]
 } (0..8) ];
 push @$regiones, $región;
}

 para(mi $fila = 0; $fila < 3; $fila++){
 para(mi $col = 0; $col < 3; $col++){
 mi $region = [];

 para(mi $x = 0; $x < 3; $x++){
 para(mi $ $ y = 0; $y < 3; $ $ y++){
 push @$de la región,
 [$fila*3+$x, $col*3+$y];
}
}

 push @$regiones, $región;
}
}

 mi $board =
 [ map { [ (-1) x 9 ] } (0) x 9 ];

 búsqueda($bordo, $regiones, 0);
}

Una secuencia de más en el espacio de la solución, se lee como sigue:

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 5 4 1 6 9 8
9 6 1 7 3 8 5 4 2
5 4 8 6 9 2 7 1 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 5 9 1 6 4 8
9 6 8 7 4 2 5 1 3
5 4 1 6 3 8 7 9 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 6 9 1 5 4 8
9 6 8 5 4 2 7 1 3
5 4 1 7 3 8 6 9 2

Anexo Sat Nov 15 10:40:01 CET 2014. Por la forma de responder al reto aquí es un optimizado pero simple versión de la anterior que produjo 2600 soluciones en un minuto de tiempo de cálculo, no está mal para un lenguaje interpretado y diez veces más rápido que la primera versión. Sospecho que si esto se traduce en C, el rendimiento sería muy llamativo.

#! /usr/bin/perl -w
#

sub búsqueda {
 my ($bordo, $incidente, $sofar) = @_;

 if($sofar == 9*9){
 para(mi $fila = 0; $fila < 9; $fila++){
 para(mi $col = 0; $col < 9; $col++){
 print "" si $col > 0;
 print $tabla->[$fila][$col];
}
 print "\n";
}
 print "\n";

de retorno;
}

 mi $col = $sofar % 9; my $fila = ($sofar-$col) / 9;

 para(mi $val = 1; $val <= 9; $val++){
 mi $clave = "$fila-$col";
 $tabla->[$fila][$col] = $val;

 mi $admitir = 1;
 foreach my $región (@{ $incidente->{$key} }){
 foreach my $ranura (@$región){
 if($ranura->[0] != $fila || $ranura->[1] != $col){
 mi $ent = $tabla->[$ranura->[0]][$ranura->[1]];

 if($ent == $val){
 $admitir = undef;
último;
}
}
}

 de última si no se define($admitir);
}

if($row>=2){
 mi @ap = (
$tabla->[$fila-2][$col],
$tabla->[$fila-1][$col],
$tabla->[$fila][$col]);
 if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
 $admitir = undef;
}
}

if($col>=2){
 mi @ap = (
$tabla->[$fila][$col-2],
$tabla->[$fila][$col-1],
$tabla->[$fila][$col]);
 if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
 $admitir = undef;
}
}


 búsqueda($bordo, $incidente, $sofar+1) 
 si se define($admitir);

 $tabla->[$fila][$col] = -1;
}
}

 PRINCIPAL: {
 mi $regiones = [];

 para(mi $line = 0; $line < 9; $line++){
 mi $region = [ 
 mapa {
 [$linea, $_]
 } (0..8) ];
 push @$regiones, $región;

 $region = [ 
 mapa {
 [$_, $line]
 } (0..8) ];
 push @$regiones, $región;
}

 para(mi $fila = 0; $fila < 3; $fila++){
 para(mi $col = 0; $col < 3; $col++){
 mi $region = [];

 para(mi $x = 0; $x < 3; $x++){
 para(mi $ $ y = 0; $y < 3; $ $ y++){
 push @$de la región,
 [$fila*3+$x, $col*3+$y];
}
}

 push @$regiones, $región;
}
}

 mi $incidente = {};
 foreach my $región (@$regiones){
 foreach my $ranura (@$región){
 mi $clave = join('-', @$ranura);
 push @{ $incidente->{$key} }, $región;
}
}


 mi $board = [ map { [ (-1) x 9 ] } (0) x 9 ];

 búsqueda($bordo, $incidente, 0);
}

Answer 2

El siguiente programa en C produce 165K diferentes soluciones durante un minuto a ejecutar. Esta es una traducción literal del código Perl y algunos C cuestiones de estilo, siendo probablemente como no soy un experto en C coder. Compilado con GCC 4.8.3.

#include <stdio.h>

typedef struct {
 int fila, col;
} ranura;

typedef ranura de la región[9];

typedef struct {
 la región de las regiones[27];
 región *incidencia[9][9][3];
} boardinf;

typedef int boardvals[9][9];

void buscar(boardvals *bvptr, boardinf *binfptr, int hasta la fecha)
{
 int fila, col;

 si(sofar == 9*9){
 for(fila=0; fila<9; fila++){
 for(col=0; col<9; col++){
 si(col>0) printf(" ");
 printf("%d", (*bvptr)[fila][col]);
}
printf("\n");
}
printf("\n");

de retorno;
}

 col = sofar % 9; fila = (sofar-col) / 9;

 int val;
 para(val = 1; val <= 9; val++){
 (*bvptr)[fila][col] = val;

 int admitir = 1, regx;
 para(regx=0; regx<3; regx++){
 región *reg = binfptr->incidencia[fila][col][regx];

 int sx;
 para(sx=0; sx<9; sx++){
 ranura *s = (*reg)+sx;

 si(s->fila != fila || s->col != col){
 si((*bvptr)[s->fila][s->col] == val){
 admitir = 0;
break;
}
}
}

 si(!admitir) break;
}

si(row>=2){
 int ap[3] = {
(*bvptr)[fila-2][col],
(*bvptr)[fila-1][col],
 (*bvptr)[fila][col] };

 si(ap[2]-ap[1] == ap[1]-ap[0]){
 admitir = 0;
}
}

si(col>=2){
 int ap[3] = {
(*bvptr)[fila][col-2],
(*bvptr)[fila][col-1],
 (*bvptr)[fila][col] };

 si(ap[2]-ap[1] == ap[1]-ap[0]){
 admitir = 0;
}
}

 si(admitir) búsqueda(bvptr, binfptr, hasta la fecha+1);

 (*bvptr)[fila][col] = -1;
}
}


int main(int argc, char **argv)
{
 boardinf binf;
 int row, col, regx = 0;

 for(fila=0; fila<9; fila++){
 for(col=0; col<9; col++){
 binf.regiones[regx][col].fila = fila;
 binf.regiones[regx][col].col = col;

 binf.incidencia[fila][col][0] = binf.regiones+regx;
}

regx++;
}

 for(col=0; col<9; col++){
 for(fila=0; fila<9; fila++){
 binf.regiones[regx][fila].fila = fila;
 binf.regiones[regx][fila].col = col;

 binf.incidencia[fila][col][1] = binf.regiones+regx;
}

regx++;
}

 int x, y;
 para(y=0; y<3; y++){
 for(x=0; x<3; x++){
 int idx = 0;

 for(fila=0; fila<3; fila++){
 for(col=0; col<3; col++){
 binf.regiones[regx][idx].fila = 3*y+fila;
 binf.regiones[regx][idx].col = 3*x+col;

 binf.incidencia[3*y+fila][3*x+col][2] =
binf.regiones+regx;

idx++;
}
}

regx++;
}
}

 boardvals bv;
 for(fila=0; fila<9; fila++){
 for(col=0; col<9; col++){
 bv[fila][col] = -1;
}
}

 búsqueda(&bv, y binf, 0);
}

Aquí están algunas de las soluciones que se calcula.

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
7 8 2 6 9 5 4 1 3
4 6 1 7 3 8 5 9 2
9 3 5 4 1 2 7 6 8

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
7 8 5 6 9 2 4 1 3
4 6 1 7 3 8 5 9 2
9 3 2 4 1 5 7 6 8

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
9 6 2 7 3 5 4 1 8
4 3 5 6 1 7 8 9 2
7 8 1 4 9 2 5 6 3

Los siguientes tres soluciones son notables para la actividad de intercambio de haber llegado a la cuarta fila.

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 2 5 4 8 7 9 1
4 9 7 2 3 1 6 8 5
5 1 8 9 6 7 2 4 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 7 5 4 8 2 9 1
4 1 2 9 3 7 6 8 5
5 9 8 2 6 1 7 4 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 8 5 4 7 2 9 1
4 9 7 2 3 1 6 8 5
5 1 2 9 6 8 7 4 3