Mein Versuch, diese Frage zu stellen , aber mit einem objektiveren Lösungskriterium.

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu erstellen, die ein gelöstes Sudoku-Raster Sim Format Ihrer Wahl verwendet und versucht, mit möglichst wenigen Hinweisen ein Problemraster zu generieren, Sdessen Lösung eindeutig ist. (Es spielt keine Rolle, nach welcher Methode Sdie eindeutige Lösung, einschließlich Brute Force, vorliegt, solange die Lösung nachweislich eindeutig ist.)

Ihr Programm wird bewertet, indem Sie es durch einen Satz von 100.000 Lösungsrastern in dieser Datei (7,82 MB Download) laufen lassen und die Anzahl der Hinweise in allen 100.000 Problemrastern addieren, die Ihre Lösung erzeugt.

Die Sudoku-Lösungen in der obigen Testdatei werden als 81-stellige Zeichenfolge von links nach rechts und von oben nach unten ausgedrückt. Der Code, der erforderlich ist, um die Eingabe in der Testdatei in eine verwendbare Lösung umzuwandeln, wird nicht für die Byteanzahl Ihrer Lösung berücksichtigt.

Wie bei meiner Flood Paint- Herausforderung muss Ihr Programm tatsächlich eine gültige Ausgabe für alle 100.000 Puzzlespiele liefern, um als gültige Lösung zu gelten. Das Programm, das die wenigsten Gesamthinweise für alle 100.000 Testfälle ausgibt, ist der Gewinner, wobei ein kürzerer Code ein Unentschieden löst.

Aktueller Anzeiger:

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 Hinweise

Entfernen Sie Hinweise ab der letzten Zelle, wenn ein Brute-Force-Löser nur eine eindeutige Lösung findet.

Zweiter Versuch: Verwenden Sie die Heuristik, um zu entscheiden, in welcher Reihenfolge Hinweise entfernt werden sollen, anstatt vom letzten zu beginnen. Dadurch wird der Code viel langsamer ausgeführt (20 Minuten anstelle von 2 Minuten, um das Ergebnis zu berechnen). Ich könnte den Löser schneller machen, um mit verschiedenen Heuristiken zu experimentieren, aber im Moment reicht es.

#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 Hinweise

Wie üblich ist hier eine Referenzlösung für den letzten Platz:

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

Wenn Sie die untere Zahlenreihe entfernen, bleibt das Rätsel nachweislich in allen Fällen lösbar, da in jeder Spalte immer noch 8 von 9 Zahlen gefüllt sind und jede Zahl in der unteren Reihe einfach die neunte Zahl in der Spalte ist.

Wenn es ein ernsthafter Anwärter schafft, legal schlechter als dieser zu punkten, werde ich erstaunt sein.

Python 2 - 6.000.000 Hinweise

Eine einfache Lösung, die die 3 häufigsten Methoden zum Lösen dieser Rätsel verwendet:

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

Diese Funktion erzeugt Hinweisformate wie dieses:

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

Dies kann immer gelöst werden. Die 4 3x3 Teile werden zuerst gelöst, dann die 8 Spalten, dann die 9 Zeilen.

PHP - 2.580.210 Hinweise

Dadurch werden zuerst die letzte Zeile und Spalte sowie die rechte untere Ecke aller Kästchen entfernt. Anschließend wird versucht, jede Zelle zu löschen und die Karte nach jeder Änderung einem einfachen Solver zu unterziehen, um sicherzustellen, dass die Karte immer noch eindeutig lösbar ist.

Ein Großteil des folgenden Codes wurde von einer meiner alten Antworten geändert . printBoardverwendet 0s für leere Zellen.

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