Moja próba sformułowania tego pytania , ale z bardziej obiektywnym kryterium rozwiązywania.

Twoim zadaniem jest zbudowanie programu lub funkcji, która przyjmuje rozwiązaną siatkę Sudoku Sw wybranym przez ciebie formacie i próbuje wygenerować problematyczną siatkę z jak najmniejszą liczbą wskazówek, która ma Sswoje unikalne rozwiązanie. (Nie ma znaczenia, jaką metodą Sjest unikalne rozwiązanie, w tym brutalna siła, o ile rozwiązanie jest możliwe do udowodnienia).

Twój program zostanie oceniony przez uruchomienie go przez zestaw 100 000 siatek rozwiązań znalezionych w tym pliku (7,82 MB do pobrania) i zsumowanie liczby wskazówek we wszystkich 100 000 siatkach problemowych tworzonych przez twoje rozwiązanie.

Rozwiązania Sudoku w powyższym pliku testowym są wyrażone jako ciąg znaków o długości 81 znaków, od lewej do prawej, a następnie od góry do dołu. Kod wymagany do przekształcenia danych wejściowych w pliku testowym w użyteczne rozwiązanie nie będzie wliczany do liczby bajtów rozwiązania.

Podobnie jak w moim wyzwaniu Flood Paint , twój program musi faktycznie wygenerować prawidłowy wynik dla wszystkich 100 000 zagadek, aby można go było uznać za prawidłowe rozwiązanie. Program, który generuje najmniejszą liczbę wskazówek dla wszystkich 100 000 przypadków testowych, jest zwycięzcą, z krótszym kodem przerywającym remis.

Aktualna tablica wyników:

1. 2 3610 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 wskazówek

Usuń wskazówki, zaczynając od ostatniej komórki, jeśli solute solver znajdzie tylko jedno unikalne rozwiązanie.

Druga próba: użyj heurystyki, aby zdecydować, w jakiej kolejności usunąć wskazówki zamiast zaczynać od ostatniej. Powoduje to, że kod działa znacznie wolniej (20 minut zamiast 2, aby obliczyć wynik). Mógłbym przyspieszyć solver, eksperymentować z różnymi heurystykami, ale na razie się uda.

#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 wskazówek

Jak zwykle, oto rozwiązanie referencyjne na ostatnim miejscu:

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

Usunięcie dolnego rzędu liczb z pewnością sprawi, że łamigłówka będzie możliwa do rozwiązania we wszystkich przypadkach, ponieważ w każdej kolumnie nadal jest wypełnionych 8 z 9 liczb, a każda liczba w dolnym rzędzie jest po prostu dziewiątą liczbą pozostałą w kolumnie.

Jeśli jakiemukolwiek poważnemu kandydatowi uda się zalegalizować gorzej niż ten, będę zaskoczony.

Python 2 - 6 000 000 wskazówek

Proste rozwiązanie, które wykorzystuje 3 popularne metody rozwiązywania tych zagadek:

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))

Ta funkcja generuje formaty wskazówek takie jak to:

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

To zawsze można rozwiązać. 4 części 3x3 są rozwiązywane najpierw, następnie 8 kolumn, a następnie 9 rzędów.

PHP - 2580 210 wskazówek

Ten pierwszy usuwa ostatni wiersz i kolumnę oraz prawy dolny róg każdego pola. Następnie próbuje wyczyścić każdą komórkę, po każdej zmianie przeprowadzając tablicę za pomocą prostego solwera, aby upewnić się, że tablica jest nadal jednoznacznie rozwiązalna.

Znaczna część poniższego kodu została zmodyfikowana na podstawie jednej z moich starych odpowiedzi . printBoardużywa zer dla pustych komórek.

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