Troubleshooting with Colt Python .357: PHP: sudoku solver

Sep 19, 2008
PHP: sudoku solver

This was also my assignment in college, allthough in Java, but I like it better in PHP. You can see this script live on http://www.kafol.net/sudoku.
<?php
set_time_limit(500);
?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1250" />
<title>Sudoku solver</title>
</head>

<body>
<h3>- jean caffou</h1>
<form id="form1" name="form1" method="post" action="">
  <label>
  <textarea name="grid" id="grid" cols="20" rows="12"><?
if(isset($_POST['grid'])) echo $_POST['grid']; else { ?>0 9 0  3 0 0  0 0 0
4 0 8  1 0 0  6 7 5
1 0 6  8 0 0  0 0 0

6 0 3  0 0 0  0 5 0
2 0 0  0 1 0  0 0 9
0 7 0  0 0 0  2 0 6

0 0 0  0 0 2  1 0 8
8 2 9  0 0 1  5 0 4
0 0 0  0 0 3  0 9 0<? } ?></textarea>
  </label>
  <label>  <br />
  Vnesi ?tevke od 1-9 v ?tevilsko mre?o. Kjer je mesto prazno, vnesi 0.<br />
  <input type="submit" name="button" id="button" value="Re?i" />
  </label>
</form>
<?php
  $grid=array(array());
 $solvable = false;
 //////////////////////////////////////////////////////////////////////
if(isset($_POST['grid'])) {
 
 $str=$_POST['grid'];
 $elements=split("[\n\r\t ]+",$str);
 //elements must containt 81 numeric values
 $x=0;
 $y=0;
 if(count($elements)!=81) { echo "<center><h1>Neveljavna matrika"; exit; }
 for($i=1;$i<=81;$i++) {
  $val=$elements[$i-1];
  $grid[$y][$x]=$val;
  if(!($val>=0&&$val<=9)) { echo "<center><h1>Neveljavna matrika"; exit; }
  $x++;
  if($x==9) {
   $x=0;
   $y++;
  }
  
 }
 $orig=$grid;
 if(solve(0,0)) disp();
 if(!$solvable) echo "<h1>Ni re?itev.";
}

 function solve($y,$x) {
  global $grid,$solvable;
  if($x==9) {
   $y++;
   $x=0;
   if($y==9) {
    $solvable=true;
    return true;
   }
  }
  
  if($grid[$y][$x]!=0) { //this position is already solved
   return solve($y,$x+1);
  }
   
  for($n=1;$n<=9;$n++) {
   if(ok($y,$x,$n)) {
    $grid[$y][$x]=$n;
    if(solve($y,$x+1)) {
     disp();
     $solvable=true;
    }
   }
  }
  
  $grid[$y][$x]=0;
  return false;
 }
 
 function ok($y,$x,$n) {
  global $grid;
  for($i=0;$i<9;$i++) { //row
   if($grid[$y][$i]==$n) return false;
   if($grid[$i][$x]==$n) return false;
  }
  $r=floor($y/3)*3;
  $c=floor($x/3)*3;
  for($a=$r;$a<$r+3;$a++)
   for($b=$c;$b<$c+3;$b++)
    if($grid[$a][$b]==$n) return false;
  
  return true;
 }
 
 function disp() {
  global $grid,$orig;
  echo "<p><table border=\"2\">";
  for($y=0;$y<9;$y++) {
   echo "<tr>";
   if(($y+1)%3==1&&$y>2) echo "<tr></tr>";
   for($x=0;$x<9;$x++) {
    $v=$grid[$y][$x];
    $s="";
    if($orig[$y][$x]!=$grid[$y][$x]) $s="<font color=red>";
    echo "<td><strong>$s $v </td>";
    if(($x+1)%3==0&&$x<8) echo "<td>  </td>";
   }
   echo "</tr>";
  }
  echo "</table></p><br>";
 }
?>
</body>
</html>
Sep 19, 2008

PHP: sudoku solver

No comments:
