Last active
November 7, 2018 13:29
-
-
Save tounsils/852134f667e39caf63b3de4f33109118 to your computer and use it in GitHub Desktop.
Sudoku for easy case
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* Created by PhpStorm. | |
* User: PC16 | |
* Date: 30/10/2018 | |
* Time: 11:59 | |
*/ | |
//var $grid; | |
Function get_unassigned_location($grid) | |
{ | |
for ($row = 0; $row < 9; $row++) { | |
for ($col = 0; $col < 9; $col++) { | |
//echo "grid [$row] [$col] = " . $grid[$row][$col] . " "; | |
if ($grid[$row][$col] == 0) { | |
return array($row, $col); | |
} | |
} | |
} | |
return array(9, 9); | |
} | |
Function used_in_row($grid, $row, $num) | |
{ | |
for ($col = 0; $col < 9; $col++){ | |
//echo $grid[$row][$col] . "($row, $num) <br>"; | |
if ($grid[$row][$col] == $num) { | |
return true; | |
} | |
} | |
return false; | |
} | |
Function used_in_col($grid, $col, $num) | |
{ | |
for ($row = 0; $row < 9; $row++) { | |
//echo "$col, $num <br>"; | |
if ($grid[$row][$col] == $num) { | |
return true; | |
} | |
} | |
return false; | |
} | |
Function used_in_box($grid, $box_start_row, $box_start_col, $num) | |
{ | |
for ($row = 0; $row < 3; $row++) { | |
for ($col = 0; $col < 3; $col++) | |
if ($grid[$row + $box_start_row][$col + $box_start_col] == $num) { | |
return true; | |
} | |
} | |
return false; | |
} | |
Function is_safe($grid, $row, $col, $num) | |
{ | |
// Check if 'num' is not already placed in current row, // current column and current 3x3 box | |
$res = ((!used_in_row($grid, $row, $num)) | |
&& (!used_in_col($grid, $col, $num)) | |
&& (!used_in_box($grid, $row - ($row % 3), $col - ($col % 3), $num))); | |
return $res; | |
} | |
Function solve_soduko($grid) | |
{ | |
// If the Soduko grid has been filled, we are done | |
//$grid = $soduko; | |
if (array(9, 9) == get_unassigned_location($grid)) {echo "<br>"; | |
displayArray($grid); | |
return true; } // | |
// Get an unassigned Soduko grid location | |
else { | |
$row = get_unassigned_location($grid)[0]; | |
$col = get_unassigned_location($grid)[1]; | |
} | |
// Consider digits 1 to 9 | |
for ($num = 1; $num <= 9; $num++) { | |
// If placing the current number in the current | |
// unassigned location is valid, go ahead | |
if (is_safe($grid, $row, $col, $num)) | |
{ | |
// Make tentative assignment | |
//echo "($row, $col, $num)[" . $grid[$row ][$col - 1] . "]"; | |
$grid[$row][$col] = $num; | |
// Do the same thing again recursively. If we go | |
// through all of the recursions, and in the end | |
// return true, then all of our number placements | |
// on the Soduko grid are valid and we have fully | |
// solved it | |
if (solve_soduko($grid)) {return true; } // | |
// As we were not able to validly go through all | |
// of the recursions, we must have an invalid number | |
// placement somewhere. Lets go back and try a | |
// different number for this particular unassigned location | |
else $grid[$row][$col] = 0;//echo "[$row][$col] I go back (cause $num)"; | |
} | |
} | |
// If we have gone through all possible numbers for the current unassigned | |
// location, then we probably assigned a bad number early. Lets backtrack | |
// and try a different number for the previous unassigned locations. | |
return false; | |
} | |
function displayArray($arr){ | |
$ii=3;echo " | "; | |
for ($i = 0; $i < 9; $i++){ | |
for ($j = 0; $j < 9; $j++){ | |
if($ii == 0) {echo " | "; $ii = 3;} | |
$ii--; echo $arr[$i][$j] . " "; | |
} | |
echo "<br>"; | |
} | |
} | |
$grid = array( | |
array(0, 0, 0, 0, 7, 6, 5, 0, 0), | |
array(0, 0, 9, 0, 0, 8, 0, 0, 1), | |
array(0, 4, 6, 0, 1, 5, 0, 0, 7), | |
array(3, 5, 0, 0, 9, 0, 6, 0, 0), | |
array(9, 0, 2, 7, 0, 4, 1, 0, 5), | |
array(0, 0, 7, 0, 6, 0, 0, 4, 9), | |
array(7, 0, 0, 8, 3, 0, 4, 9, 0), | |
array(6, 0, 0, 2, 0, 0, 8, 0, 0), | |
array(0, 0, 3, 6, 5, 0, 0, 0, 0), | |
); | |
/* | |
* Complex case | |
$grid = array( | |
array(0, 3, 4, 1, 0, 0, 0, 0, 0), | |
array(0, 8, 0, 0, 2, 0, 1, 0, 2), | |
array(0, 0, 1, 0, 1, 0, 0, 0, 0), | |
array(0, 5, 0, 4, 9, 0, 8, 0, 5), | |
array(0, 1, 0, 0, 0, 4, 0, 5, 0), | |
array(4, 0, 8, 2, 1, 0, 0, 0, 0), | |
array(0, 0, 0, 0, 1, 0, 4, 0, 0), | |
array(6, 0, 7, 0, 8, 0, 0, 3, 0), | |
array(0, 0, 0, 0, 0, 3, 7, 2, 0), | |
); | |
*/ | |
displayArray($grid); | |
solve_soduko($grid); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment