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;