Usaha saya menyatakan pertanyaan ini , tetapi dengan kriteria penyelesaian yang lebih objektif.

Tugas Anda adalah membangun program atau fungsi yang mengambil kisi-kisi Sudoku yang dipecahkan Sdalam format pilihan Anda dan berupaya menghasilkan kisi-kisi masalah dengan sesedikit mungkin petunjuk yang dimiliki Ssebagai solusi uniknya. (Tidak masalah metode apa yang Smerupakan solusi unik oleh, termasuk brute force, selama solusi tersebut terbukti unik.)

Program Anda akan dinilai dengan menjalankannya melalui sekumpulan 100.000 kisi solusi yang ditemukan dalam file ini (unduhan 7.82 MB), dan menambahkan jumlah petunjuk dalam semua 100.000 kisi masalah yang dihasilkan solusi Anda.

Solusi Sudoku dalam file tes di atas dinyatakan sebagai string 81 karakter, dari kiri ke kanan, kemudian dari atas ke bawah. Kode yang diperlukan untuk mengubah input dalam file uji menjadi solusi yang dapat digunakan tidak akan dihitung terhadap jumlah byte solusi Anda.

Seperti dalam tantangan Cat Banjir saya , program Anda harus benar-benar menghasilkan keluaran yang valid untuk semua 100.000 teka-teki yang akan dianggap sebagai solusi yang valid. Program yang menghasilkan petunjuk total paling sedikit untuk semua 100.000 kasus uji adalah pemenangnya, dengan kode yang lebih pendek memutus ikatan.

Papan skor saat ini:

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 petunjuk

Hapus petunjuk yang dimulai dari sel terakhir jika seorang brute force solver hanya menemukan satu solusi unik.

Percobaan kedua: gunakan heuristik untuk memutuskan untuk menghapus petunjuk bukannya mulai dari yang terakhir. Ini membuat kode berjalan lebih lambat (20 menit, bukan 2 untuk menghitung hasilnya). Saya bisa membuat pemecah lebih cepat, untuk bereksperimen dengan heuristik yang berbeda, tetapi untuk sekarang akan dilakukan.

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

Seperti biasa, berikut ini adalah solusi referensi tempat terakhir:

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

Menghapus baris paling bawah dari angka-angka dapat dibuktikan menyisakan teka-teki dalam semua kasus, karena setiap kolom masih memiliki 8 dari 9 angka yang terisi, dan setiap angka di baris bawah hanyalah angka kesembilan yang tersisa dalam kolom.

Jika ada pesaing serius yang berhasil mencetak skor lebih buruk dari yang satu ini, saya akan heran.

Python 2 - 6.000.000 petunjuk

Sebuah solusi sederhana yang menggunakan 3 metode umum untuk memecahkan teka-teki ini:

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

Fungsi ini menghasilkan format petunjuk seperti ini:

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

Ini selalu bisa diselesaikan. Bagian 4 3x3 diselesaikan terlebih dahulu, lalu 8 kolom, lalu 9 baris.

PHP - 2.580.210 petunjuk

Ini pertama menghapus baris dan kolom terakhir, dan sudut kanan bawah setiap kotak. Kemudian mencoba untuk membersihkan setiap sel, menjalankan papan melalui pemecah sederhana setelah setiap perubahan untuk memastikan papan masih dapat dipecahkan.

Banyak kode di bawah ini dimodifikasi dari salah satu jawaban lama saya . printBoardmenggunakan 0s untuk sel kosong.

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