I'm trying to practice algorithm questions and I'm currently attempting a sudoku solver, please bare in mind that it isn't currently finished! I haven't added backtracking when there is more than one option that the cell could be, but my issue currently is that my if statement to check if there is only one possible answer the cell could be is failing, as the semi filled sudoku its returning is wrong.
Also feel free to give me tips on how to speed things up etc.
function sudoku(array $puzzle): array
{
// Return the solved puzzle as a 9 × 9 grid
$data = [];
for ($i = 0; $i < 8; $i ) {
for ($a = 0; $a < 8; $a ) {
if ($puzzle[$i][$a] == 0) {
$horizontal_missing = getHorizontalNumbers($puzzle[$i]);
$vertical_missing = getVerticalNumbers($puzzle, $a);
$square_missing = getSquareNumbers($puzzle, $i, $a);
$intersect = array_intersect($horizontal_missing,$vertical_missing,$square_missing);
if (count($intersect) == 1) {
sort($intersect);
$puzzle[$i][$a] = $intersect[0];
$i = 0;
$a = 0;
}
}
}
}
return $puzzle;
}
function getSquareNumbers($p, $row, $col)
{
$sectors = [1 => [0, 2], 2 => [3, 5], 3 => [6, 8]];
$across = getSector($sectors, $row);
$down = getSector($sectors, $col);
switch (($across * $down)) {
case 1:
$row = [
$p[0][0], $p[0][1], $p[0][2],
$p[1][0], $p[1][1], $p[1][2],
$p[2][0], $p[2][1], $p[2][2]
];
break;
case 2:
$row = [
$p[0][3], $p[0][4], $p[0][5],
$p[1][3], $p[1][4], $p[1][5],
$p[2][3], $p[2][4], $p[2][5]
];
break;
case 3:
$row = [
$p[0][6], $p[0][7], $p[0][8],
$p[1][6], $p[1][7], $p[1][8],
$p[2][6], $p[2][7], $p[2][8]
];
break;
case 4:
$row = [
$p[3][0], $p[3][1], $p[3][2],
$p[4][0], $p[4][1], $p[4][2],
$p[5][0], $p[5][1], $p[5][2]
];
break;
case 5:
$row = [
$p[3][3], $p[3][4], $p[3][5],
$p[4][3], $p[4][4], $p[4][5],
$p[5][3], $p[5][4], $p[5][5]
];
break;
case 6:
$row = [
$p[3][6], $p[3][7], $p[3][8],
$p[4][6], $p[4][7], $p[4][8],
$p[5][6], $p[5][7], $p[5][8]
];
break;
case 7:
$row = [
$p[6][0], $p[6][1], $p[6][2],
$p[7][0], $p[7][1], $p[7][2],
$p[8][0], $p[8][1], $p[8][2]
];
break;
case 8:
$row = [
$p[6][3], $p[6][4], $p[6][5],
$p[7][3], $p[7][4], $p[7][5],
$p[8][3], $p[8][4], $p[8][5]
];
break;
case 9:
$row = [
$p[6][6], $p[6][7], $p[6][8],
$p[7][6], $p[7][7], $p[7][8],
$p[8][6], $p[8][7], $p[8][8]
];
break;
}
return getHorizontalNumbers($row);
}
function getSector($sectors, $num)
{
if (($sectors[1][0] <= $num) && ($num <= $sectors[1][1])) {
return 1;
} else if (($sectors[2][0] <= $num) && ($num <= $sectors[2][1])) {
return 2;
} else if (($sectors[3][0] <= $num) && ($num <= $sectors[3][1])) {
return 3;
}
}
function getHorizontalNumbers($row)
{
$missing = [];
for ($i = 1; $i <= 9; $i ) {
if (!in_array($i, $row)) {
$missing[] = $i;
}
}
return $missing;
}
function getVerticalNumbers($puzzle, $col)
{
$row = [
$puzzle[0][$col],
$puzzle[1][$col],
$puzzle[2][$col],
$puzzle[3][$col],
$puzzle[4][$col],
$puzzle[5][$col],
$puzzle[6][$col],
$puzzle[7][$col],
$puzzle[8][$col]
];
return getHorizontalNumbers($row);
}
$data = sudoku([
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]);
$string = '';
$count = 0;
foreach($data as $key => $row){
foreach($row as $cell){
$count ;
if ($count == 9){
$string.= $cell.", \n";
$count = 0;
} else {
$string.= $cell.", ";
}
}
}
echo nl2br($string);
Surely if I'm only inputting numbers where there is only ONE common denominator between vertical line, horizontal line and the square there shouldn't be any errors in the SEMI filled Sudoku so far, yet there is? What am I missing? My brain can't compute lol.
CodePudding user response：
function test_sectors($puzzle=null) {
if (!$puzzle) {
$puzzle = [
[1,1,1, 2,2,2, 3,3,3],
[1,1,1, 2,2,2, 3,3,3],
[1,1,1, 2,2,2, 3,3,3],
[4,4,4, 5,5,5, 6,6,6],
[4,4,4, 5,5,5, 6,6,6],
[4,4,4, 5,5,5, 6,6,6],
[7,7,7, 8,8,8, 9,9,9],
[7,7,7, 8,8,8, 9,9,9],
[7,7,7, 8,8,8, 9,9,9]
];
}
for ($i=0; $i<9; $i ) {
for ($j=0; $j<9; $j ) {
$expected = $puzzle[$i][$j];
$sector = getSquareNumbers($puzzle, $i, $j);
if ($sector[0] == $expected) {
echo ".";
} else {
echo "F (got sector {$sector[0]} expected {$expected} at coord [{$i}][{$j}])\n";
};
}
}
}
test_sectors();
I did this function (I do not have a php at hand now) to test the behaviour of your getSquareNumbers function that seems odd to me. You can use it to see if the correct square is selected for every possible coordinate, you can automate it too (but it is up to you).
Edit: Rewritten a la unit test fashion!
CodePudding user response：
In getSquareNumbers you assume that $across * $down gives unique values, but that is not true:
For example 1*3 is 3, but also 3*1 is 1. Furthermore, there is no case where the product is 5, 7 or 8. So in many cases your code is looking at the wrong square area.
You can avoid a lot of code (duplication) by just using the modulo operator and slice the rows of the grid at given indices.
Secondly, you seem to swap the meaning of $down and $across. The first should be about rows and the second about columns, and the code does relates them differently.
Here is the suggested fix for that function:
function getSquareNumbers($p, $row, $col)
{
$down = $row - $row % 3; // This will be 0, 3 or 6
$across = $col - $col % 3; // This will be 0, 3 or 6
$row = [...array_slice($p[$down 0], $across, $across 3),
...array_slice($p[$down 1], $across, $across 3),
...array_slice($p[$down 2], $across, $across 3)];
return getHorizontalNumbers($row);
}
Now your grid will be filled more... still leaving some zeroes, but those zeroes really represent cells that cannot be solved as there is no value that can be put there without violating one of the rules. So this is where you need to implement backtracking to continue the process in an alternative direction.