Mi intento de plantear esta pregunta , pero con un criterio de resolución más objetivo.

Su tarea es construir un programa o función que tome una cuadrícula de Sudoku resuelta Sen el formato que elija e intente generar una cuadrícula de problemas con la menor cantidad de pistas posible que tenga Scomo solución única. (No importa qué método Ssea ​​la solución única, incluida la fuerza bruta, siempre que la solución sea demostrablemente única).

Su programa se puntuará ejecutándolo a través de un conjunto de 100,000 cuadrículas de solución que se encuentran en este archivo (7,82 MB de descarga) y sumando el número de pistas en las 100,000 cuadrículas problemáticas que produce su solución.

Las soluciones de Sudoku en el archivo de prueba anterior se expresan como una cadena de 81 caracteres, de izquierda a derecha, luego de arriba a abajo. El código requerido para convertir la entrada en el archivo de prueba en una solución utilizable no contará para el recuento de bytes de su solución.

Como en mi desafío Flood Paint , su programa debe producir una salida válida para que todos los 100,000 rompecabezas se consideren una solución válida. El programa que genera la menor cantidad de pistas totales para los 100,000 casos de prueba es el ganador, con un código más corto que rompe un empate.

Marcador actual:

1. 2,361,024 - nutki, C
2. 2,580,210 - es1024, PHP
3. 6,000,000 - CarpetPython, Python 2
4. 7,200,000 - Joe Z., Python

C - 2,361,024 2,509,949 pistas

Elimine las pistas a partir de la última celda si un solucionador de fuerza bruta encuentra solo una solución única.

Segundo intento: use la heurística para decidir en qué orden eliminar las pistas en lugar de comenzar desde el último. Esto hace que el código se ejecute mucho más lento (20 minutos en lugar de 2 para calcular el resultado). Podría hacer que el solucionador sea más rápido, experimentar con diferentes heurísticas, pero por ahora funcionará.

#include <stdio.h>
#include <string.h>
char ll[100];
short b[81];
char m[81];
char idx[81][24];
int s;
char lg[513];
void pri2() {
    int i;
    for(i=0;i<81;i++) putchar(lg[b[i]]);
    putchar('\n');
}
void solve(pos){
int i,p;
if (s > 1) return;
if (pos == 81) { s++; return; }
if (b[pos]) return solve(pos+1);
for (p=i=0;i<24;i++) p |= b[idx[pos][i]];
for (i = 0; i < 9; i++) if (!(p&(1<<i))) {
    b[pos] = 1 << i;
    solve(pos + 1);
}
b[pos] = 0;
}
int main() {
    int i,j,t;
    for(i=0;i<9;i++) lg[1<<i]='1'+i;
    lg[0] = '.';
    for(i=0;i<81;i++) {
    t = 0;
    for(j=0;j<9;j++) if(i/9*9 + j != i) idx[i][t++] = i/9*9 + j;
    for(j=0;j<9;j++) if(i%9 + j*9 != i) idx[i][t++] = i%9 + j*9;
    for(j=0;j<81;j++) if(j/27 == i/27 && i%9/3 == j%9/3 && i!=j) idx[i][t++] = j;
    }
    while(scanf("%s ",ll)>0) {
    memset(m, 0, sizeof(m));
    for(i=0;i<81;i++) b[i] = 1 << (ll[i]-'1');
    for(i=0;i<81;i++) {
    int j,k,l = 99;
    for(k=0;k<81;k++) if (m[k] <= l) l = m[k], j = k;
    m[j] = 24;
    t = b[j]; b[j] = 0;
    s = 0; solve(0);
    if (s > 1) b[j] = t;
    else for(k=0;k<24;k++) m[idx[j][k]]++;
    }
    pri2();
    }
    return 0;
}

Python - 7,200,000 pistas

Como de costumbre, aquí hay una solución de referencia de último lugar:

def f(x): return x[:72] + "." * 9

La eliminación de la fila inferior de números probablemente deja el rompecabezas solucionable en todos los casos, ya que cada columna todavía tiene 8 de 9 números llenos, y cada número en la fila inferior es simplemente el noveno número que queda en la columna.

Si algún contendiente serio logra anotar legalmente peor que este, me sorprenderé.

Python 2 - 6,000,000 pistas

Una solución simple que utiliza los 3 métodos comunes para resolver estos acertijos:

def f(x): 
    return ''.join('.' if i<9 or i%9==0 or (i+23)%27 in (0,3) else c 
        for i,c in enumerate(x))

Esta función produce formatos de pista como este:

.........
.dddddddd
.dddddddd
.ddd.dd.d
.dddddddd
.dddddddd
.ddd.dd.d
.dddddddd
.dddddddd

Esto siempre se puede resolver. Primero se resuelven las 4 partes de 3x3, luego las 8 columnas, luego las 9 filas.

PHP - 2,580,210 pistas

Esto primero elimina la última fila y columna, y la esquina inferior derecha de cada cuadro. Luego, trata de limpiar cada celda, ejecutando la placa a través de un solucionador simple después de cada cambio para garantizar que la placa aún pueda resolverse sin ambigüedades.

Gran parte del código a continuación fue modificado de una de mis respuestas anteriores . printBoardusa 0s para celdas vacías.

<?php
// checks each row/col/block and removes impossible candidates
function reduce($cand){
    do{
        $old = $cand;
        for($r = 0; $r < 9; ++$r){
        for($c = 0; $c < 9; ++$c){
            if(count($cand[$r][$c]) == 1){ // if filled in
                // remove values from row and col and block
                $remove = $cand[$r][$c];
                for($i = 0; $i < 9; ++$i){
                    $cand[$r][$i] = array_diff($cand[$r][$i],$remove);
                    $cand[$i][$c] = array_diff($cand[$i][$c],$remove);
                    $br = floor($r/3)*3+$i/3;
                    $bc = floor($c/3)*3+$i%3;
                    $cand[$br][$bc] = array_diff($cand[$br][$bc],$remove);
                }
                $cand[$r][$c] = $remove;
            }
        }}
    }while($old != $cand);
    return $cand;
}

// checks candidate list for completion
function done($cand){
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        if(count($cand[$r][$c]) != 1)
            return false;
    }}
    return true;
}

// board format: [[1,2,0,3,..],[..],..], $b[$row][$col]
function solve($board){
    $cand = [[],[],[],[],[],[],[],[],[]];
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        if($board[$r][$c]){ // if filled in
            $cand[$r][$c] = [$board[$r][$c]];
        }else{
            $cand[$r][$c] = range(1, 9);
        }
    }}
    $cand = reduce($cand);

    if(done($cand))  // goto not really necessary
        goto end;    // but it feels good to use it 
    else return false;

    end:
    // back to board format
    $b = [];
    for($r = 0; $r < 9; ++$r){
        $b[$r] = [];
        for($c = 0; $c < 9; ++$c){
            if(count($cand[$r][$c]) == 1)
                $b[$r][$c] = array_pop($cand[$r][$c]);
            else 
                $b[$r][$c] = 0;
        }
    }
    return $b;
}

function add_zeros($board, $ind){
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        $R = ($r + (int)($ind/9)) % 9;
        $C = ($c + (int)($ind%9)) % 9;
        if($board[$R][$C]){
            $tmp = $board[$R][$C];
            $board[$R][$C] = 0;
            if(!solve($board))
                $board[$R][$C] = $tmp;
        }   
    }}
    return $board;
}

function generate($board, $ind){
    // remove last row+col
    $board[8] = [0,0,0,0,0,0,0,0,0];
    foreach($board as &$j) $j[8] = 0;

    // remove bottom corner of each box
    $board[2][2] = $board[2][5] = $board[5][2] = $board[5][5] = 0;

    $board = add_zeros($board, $ind);

    return $board;    
}
function countClues($board){
    $str = implode(array_map('implode', $board));
    return 81 - substr_count($str, '0');
}

function generateBoard($board){
    return generate($board, 0);
}

function printBoard($board){
    for($i = 0; $i < 9; ++$i){
        echo implode(' ', $board[$i]) . PHP_EOL;
    }
    flush();
}
function readBoard($str){
    $tmp = str_split($str, 9);
    $board = [];
    for($i = 0; $i < 9; ++$i)
        $board[] = str_split($tmp[$i], 1);
    return $board;
}
// testing
$n = 0;
$f = fopen('ppcg_sudoku_testing.txt', 'r');
while(($l = fgets($f)) !== false){
    $board = readBoard(trim($l));
    $n += countClues(generateBoard($board));
}
echo $n;