Minha tentativa de afirmar esta questão , mas com um critério de solução mais objetivo.

Sua tarefa é criar um programa ou função que utilize uma grade resolvida do Sudoku Sno formato de sua escolha e tente gerar uma grade de problemas com o menor número possível de pistas que possua Ssua solução exclusiva. (Não importa qual método Sé a solução exclusiva, incluindo força bruta, desde que a solução seja comprovadamente única.)

Seu programa será pontuado executando-o em um conjunto de 100.000 grades de soluções encontradas neste arquivo (download de 7,82 MB) e adicionando o número de pistas em todas as 100.000 grades de problemas que sua solução produz.

As soluções Sudoku no arquivo de teste acima são expressas como uma sequência de 81 caracteres, da esquerda para a direita e de cima para baixo. O código necessário para transformar a entrada no arquivo de teste em uma solução utilizável não conta para a contagem de bytes da sua solução.

Como no meu desafio do Flood Paint , seu programa deve realmente produzir uma saída válida para todos os 100.000 quebra-cabeças serem considerados uma solução válida. O programa que fornece o menor número total de pistas para todos os 100.000 casos de teste é o vencedor, com um código mais curto interrompendo o empate.

Painel atual:

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

Remova as pistas que começam na última célula se um solucionador de força bruta encontrar apenas uma solução única.

Segunda tentativa: use a heurística para decidir em qual ordem remover as pistas, em vez de começar da última. Isso torna o código muito mais lento (20 minutos em vez de 2 para calcular o resultado). Eu poderia tornar o solucionador mais rápido, para experimentar diferentes heurísticas, mas por enquanto ele serve.

#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 sempre, aqui está uma solução de referência de último lugar:

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

A remoção da linha inferior de números provavelmente deixa o quebra-cabeça solucionável em todos os casos, pois cada coluna ainda possui 8 dos 9 números preenchidos e cada número na linha inferior é simplesmente o nono número restante da coluna.

Se algum concorrente sério conseguir legalmente ter uma pontuação pior que essa, ficarei surpreso.

Python 2 - 6.000.000 de pistas

Uma solução simples que usa os três métodos comuns para resolver esses quebra-cabeças:

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 função produz formatos de pista como este:

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

Isso sempre pode ser resolvido. As 4 partes 3x3 são resolvidas primeiro, depois as 8 colunas e depois as 9 linhas.

PHP - 2.580.210 pistas

Isso primeiro remove a última linha e coluna e o canto inferior direito de cada caixa. Em seguida, tenta limpar cada célula, executando o quadro através de um solucionador simples após cada alteração, para garantir que o quadro ainda seja inequivocamente solucionável.

Grande parte do código abaixo foi modificado a partir de uma das minhas respostas antigas . printBoardusa 0s para células vazias.

<?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;