sudoku on php

kbrij · May 12, 2005

Has anyone attempted to write Sudoku (www.sudoku.com) puzzle using php ?

i am going to try it out, wont be an easy task.

bij.

drew_man · Dec 8, 2005

How are you coming along with your sudoku php generator? I have been looking all over the net for one.

rincewind456 · Dec 8, 2005

This might help, can't recommend it as I haven't used it, just something that came in the mail. Sudoku Class

kasab · Dec 9, 2005

I'm doing a solution for sudoku puzzles now, but need to find a way to refresh the database table once a solution is reached. I doubt that my site users can access PHPMyAdmin. May have to run a series of queries? Any suggestions?

suntra · Nov 17, 2006

Well here are some code of mine... Please note, variable and function names are in French and there are no comments, so enjoy !

First one, generate a Sudoku grid...

<?
 function microtime_float() {
	list($usec, $sec) = explode(" ", microtime());
	return ((float)$usec + (float)$sec);
 }
 $intDebut	= microtime_float();
 $intEssais	= 0;
 function Sudoku_Generer_Squelette($intLargeur, $intHauteur) {
	$GLOBALS['arrSudoku']		= array();
	$GLOBALS['arrLigne_Reference']	= array();
	$GLOBALS['arrLigne_Possibilites']	= array();
	$arrLigne	= array_fill(0, $intLargeur, 0);
	$GLOBALS['arrSudoku']	= array_fill(0, $intHauteur, $arrLigne);
	for($intL = 1; $intL <= $intLargeur; $intL++) {
		$GLOBALS['arrLigne_Reference'][]	= $intL;
	}
 }
 function Sudoku_Verifier_Possibilites($intHauteur, $intLargeur, $arrLigne) {
	for($intH = 0; $intH < $intHauteur; $intH++) {
		$intValeur		= $GLOBALS['arrSudoku'][$intH][$intLargeur];
		$intRecherche_Index	= array_search($intValeur, $arrLigne);
		if(!($intRecherche_Index === false)) {
			array_splice($arrLigne, $intRecherche_Index, 1);
		}
	}
	$intCarre_H	= floor($intHauteur / 3);
	$intCarre_L	= floor($intLargeur / 3);
	$intDebut_H	= $intCarre_H * 3;
	$intDebut_L	= $intCarre_L * 3;
	for($intH = $intDebut_H; $intH < ($intHauteur); $intH++) {
		for($intL = $intDebut_L; $intL < ($intDebut_L + 3); $intL++) {
			$intValeur		= $GLOBALS['arrSudoku'][$intH][$intL];
			$intRecherche_Index	= array_search($intValeur, $arrLigne);
			if(!($intRecherche_Index === false)) {
				array_splice($arrLigne, $intRecherche_Index, 1);
			}
		}
	}
	for($intL = $intDebut_L; $intL < $intLargeur; $intL++) {
		$intValeur		= $GLOBALS['arrSudoku'][$intHauteur][$intL];
		$intRecherche_Index	= array_search($intValeur, $arrLigne);
		if(!($intRecherche_Index === false)) {
			array_splice($arrLigne, $intRecherche_Index, 1);
		}

}
return $arrLigne;
 }
 function Sudoku_Retourner_Chiffre($intH, $intL, &$arrLigne) {
	$arrLigne1		= Sudoku_Verifier_Possibilites($intH, $intL, $arrLigne);
	if(count($arrLigne1)) {
		$intPossibilite_Index	= array_rand($arrLigne1, 1);
		$intPossibilite		= $arrLigne1[$intPossibilite_Index];
		$intPossibilite_Index	= array_search($intPossibilite, $arrLigne);
		array_splice(&$arrLigne, $intPossibilite_Index, 1);
		return $intPossibilite;
	} else {
		return false;
	}
 }
 function Sudoku_Remplir() {
	$intHauteur	= count($GLOBALS['arrSudoku']);
	$intLargeur	= count($GLOBALS['arrSudoku'][0]);
	for($intH = 0; $intH < $intHauteur; $intH++) {
		$arrLigne_Possibilites	= $GLOBALS['arrLigne_Reference'];
		for($intL = 0; $intL < $intLargeur; $intL++) {

		$intNb	= Sudoku_Retourner_Chiffre($intH, $intL, $arrLigne_Possibilites);
		if($intNb === false) {
			ob_clean();
			Sudoku_Amorcer();
			break 2;
		}
		$GLOBALS['arrSudoku'][$intH][$intL]	= $intNb;
	}
}
 }
 function Sudoku_Dessiner() {
	$intHauteur	= count($GLOBALS['arrSudoku']);
	$intLargeur	= count($GLOBALS['arrSudoku'][0]);
	echo '<table padding="0" cellspacing="0">';
	for($intH = 0; $intH < $intHauteur; $intH++) {
		echo '<tr>';
		for($intL = 0; $intL < $intLargeur; $intL++) {
			$strExtra	= '';
			if(!($intL % 3)) {
				$strExtra	.= 'border-left:solid 3px #000000;';
			}
			if(!($intH % 3)) {
				$strExtra	.= 'border-top:solid 3px #000000;';
			}
			if($intL == 8) {
				$strExtra	.= 'border-right:solid 3px #000000;';
			}
			if($intH == 8) {
				$strExtra	.= 'border-bottom:solid 3px #000000;';
			}
			echo '<td style="width:50px;height:50px;text-align:center;vertical-alignment:center;border:solid 1px #000000;' . $strExtra . '">';
			echo $GLOBALS['arrSudoku'][$intH][$intL];
			echo '</td>';
		}
		echo '</tr>';
	}
	echo '</table>';
 }
 function Sudoku_Amorcer() {
	$GLOBALS['intEssais']++;
	ob_start();
	Sudoku_Generer_Squelette(9, 9);
	Sudoku_Remplir();
	ob_flush();
 }
 Sudoku_Amorcer();
 Sudoku_Dessiner();
 $intFin	= microtime_float();
 printf('Temps requis : %s seconde%s<br />', ($intFin - $intDebut), ((($intFin - $intDebut) > 1) ? 's' : ''));
 printf('Essais requis : %s<br />', $intEssais);
?>

suntra · Nov 17, 2006

The second one resolves a grid...

You need to create a text file containing the grid you want to be solved...

It must look like this :

x4x5x2x1x
2x7xxx9x4
xx8xxx6xx
xx57x98xx
x2x8x6x9x
xx31x42xx
xx9xxx1xx
8x1xxx3x2
x7x3x1x6x

And you must specify its location with this function (you'll find this one in the last lines...) :
Sudoku_Importer('./sudoku.txt');«

<?
 set_time_limit(0);
 $arrGrille	= array();
 function Sudoku_Importer($strFichier) {
	global $arrGrille;
	if(file_exists($strFichier)) {
		$arrLignes		= file($strFichier);
		$intY			= 0;
		$arrCarre_Defaut	= array(
						1	=> true,
						2	=> true,
						3	=> true,
						4	=> true,
						5	=> true,
						6	=> true,
						7	=> true,
						8	=> true,
						9	=> true
					  );
		foreach($arrLignes as $strLigne) {
			$strLigne	= trim($strLigne);
			if(strlen($strLigne) < 1) {
				exit('Une ou plusieurs lignes sont de longueur incorrecte.');
			} else {
				$arrGrille[$intY]	= array();
				for($intX = 0; $intX < 9; $intX++) {
					$intCarre			= intval(substr($strLigne, $intX, 1));
					$arrGrille[$intY][$intX]	= (($intCarre > 0) ? $intCarre : $arrCarre_Defaut);
				}
			}
			$intY++;
		}
	} else {
		exit('Fichier non existant.');
	}
 }
 function Sudoku_Enlever_Chiffre_Carre($intChiffre, $intY, $intX) {
	global $arrGrille;
	$intY	= floor($intY / 3) * 3;
	$intX	= floor($intX / 3) * 3;
	for($intY1 = $intY; $intY1 < ($intY + 3); $intY1++) {
		for($intX1 = $intX; $intX1 < ($intX + 3); $intX1++) {
			if(is_array($arrGrille[$intY1][$intX1])) {
				unset($arrGrille[$intY1][$intX1][$intChiffre]);
			}
		}
	}
 }
 function Sudoku_Enlever_Chiffre_Horizontal($intChiffre, $intY) {
	global $arrGrille;
	for($intX = 0; $intX < 9; $intX++) {
		if(is_array($arrGrille[$intY][$intX])) {
			unset($arrGrille[$intY][$intX][$intChiffre]);
		}
	}
 }
 function Sudoku_Enlever_Chiffre_Vertical($intChiffre, $intX) {
	global $arrGrille;
	for($intY = 0; $intY < 9; $intY++) {
		if(is_array($arrGrille[$intY][$intX])) {
			unset($arrGrille[$intY][$intX][$intChiffre]);
		}
	}
 }
 function Sudoku_Verifier_Horizontal($intY) {
	global $arrGrille;
	$arrPossibilites	= array(
					1	=> array(0, 0),
					2	=> array(0, 0),
					3	=> array(0, 0),
					4	=> array(0, 0),
					5	=> array(0, 0),
					6	=> array(0, 0),
					7	=> array(0, 0),
					8	=> array(0, 0),
					9	=> array(0, 0),
				  );
	for($intX = 0; $intX < 9; $intX++) {
		if(is_int($arrGrille[$intY][$intX])) {
			unset($arrPossibilites[$arrGrille[$intY][$intX]]);
		} elseif(is_array($arrGrille[$intY][$intX])) {
			foreach(array_keys($arrGrille[$intY][$intX]) as $intChiffre) {
				if(isset($arrPossibilites[$intChiffre])) {
					$arrPossibilites[$intChiffre][0]++;
					$arrPossibilites[$intChiffre][1]	= $intX;
				}
			}
		}
	}
	foreach($arrPossibilites as $intChiffre => $arrTotal) {
		if($arrTotal[0] == 1) {
			$arrGrille[$intY][$arrTotal[1]] = $intChiffre;
		}
	}
 }
 function Sudoku_Verifier_Vertical($intX) {
	global $arrGrille;
	$arrPossibilites	= array(
					1	=> array(0, 0),
					2	=> array(0, 0),
					3	=> array(0, 0),
					4	=> array(0, 0),
					5	=> array(0, 0),
					6	=> array(0, 0),
					7	=> array(0, 0),
					8	=> array(0, 0),
					9	=> array(0, 0),
				  );
	for($intY = 0; $intY < 9; $intY++) {
		if(is_int($arrGrille[$intY][$intX])) {
			unset($arrPossibilites[$arrGrille[$intY][$intX]]);
		} elseif(is_array($arrGrille[$intY][$intX])) {
			foreach(array_keys($arrGrille[$intY][$intX]) as $intChiffre) {
				if(isset($arrPossibilites[$intChiffre])) {
					$arrPossibilites[$intChiffre][0]++;
					$arrPossibilites[$intChiffre][1]	= $intY;
				}
			}
		}
	}
	foreach($arrPossibilites as $intChiffre => $arrTotal) {
		if($arrTotal[0] == 1) {
			$arrGrille[$arrTotal[1]][$intX] = $intChiffre;
		}
	}
 }
 function Sudoku_Verifier_Unicite_Horizontal() {
	global $arrGrille;
	$arrUniques	= array();
	for($intY = 0; $intY < 9; $intY++) {
		for($intX = 0; $intX < 9; $intX++) {
			if(is_array($arrGrille[$intY][$intX]) && (count($arrGrille[$intY][$intX]) == 1)) {
				if(!isset($arrUniques[$arrGrille[$intY][$intX]])) {
					$arrUniques[$arrGrille[$intY][$intX]]	= 1;
				} else {
					return false;
					break 2;
				}
			} elseif(is_array($arrGrille[$intY][$intX]) && (count($arrGrille[$intY][$intX]) == 0)) {
				return false;
				break 2;
			} else if(!is_int($arrGrille[$intY][$intX])) {
			}
		}
	}
	return true;
 }
 function Sudoku_Verifier_Unicite_Vertical() {
	global $arrGrille;
	$arrUniques	= array();
	for($intX = 0; $intX < 9; $intX++) {
		for($intY = 0; $intY < 9; $intY++) {
			if(is_array($arrGrille[$intY][$intX]) && (count($arrGrille[$intY][$intX]) == 1)) {
				if(!isset($arrUniques[$arrGrille[$intY][$intX]])) {
					$arrUniques[$arrGrille[$intY][$intX]]	= 1;
				} else {
					return false;
					break 2;
				}
			} elseif(is_array($arrGrille[$intY][$intX]) && (count($arrGrille[$intY][$intX]) == 0)) {
				return false;
				break 2;
			}
		}
	}
	return true;
 }
$execs	= 0;
 function Sudoku_Resoudre_Logique() {
	$GLOBALS['execs']++;
	global $arrGrille;
	$arrCopie	= $arrGrille;
	$intArrays_Total	= 0;
	for($intY = 0; $intY < 9; $intY++) {
		for($intX = 0; $intX < 9; $intX++) {
			if(is_int($arrGrille[$intY][$intX])) {
				Sudoku_Enlever_Chiffre_Carre($arrGrille[$intY][$intX], $intY, $intX);
				Sudoku_Enlever_Chiffre_Horizontal($arrGrille[$intY][$intX], $intY);
				Sudoku_Enlever_Chiffre_Vertical($arrGrille[$intY][$intX], $intX);
			} elseif(is_array($arrGrille[$intY][$intX]) && (count($arrGrille[$intY][$intX]) == 1)) {
				$arrCles			= array_keys($arrGrille[$intY][$intX]);
				$intChiffre			= $arrCles[0];
				$arrGrille[$intY][$intX]	= $intChiffre;
			} elseif(is_array($arrGrille[$intY][$intX])) {
				$intArrays_Total++;
			}
			Sudoku_Verifier_Horizontal($intY);
			Sudoku_Verifier_Vertical($intX);
		}
	}
	if($arrCopie == $arrGrille) {
		return false;
	} elseif($intArrays_Total > 0) {
		return Sudoku_Resoudre_Logique();
	} else {
		return true;
	}
 }
 function Sudoku_Resoudre_Essai_Erreur() {
	global $arrGrille;
	$bolRetour	= false;
	$intMin		= 2;
	$intX0		= 0;
	$intY0		= 0;
	for($intY = 0; $intY < 9; $intY++) {
		for($intX = 0; $intX < 9; $intX++) {
			if(is_array($arrGrille[$intY][$intX])) {
				$intTotal	= count($arrGrille[$intY][$intX]);
				if($intTotal == 2) {
					$intMin	= 2;
					$intY0	= $intY;
					$intX0	= $intX;
					break 2;
				} elseif($intTotal < $intMin) {
					$intMin	= $intTotal;
					$intY0	= $intY;
					$intX0	= $intX;
				}
			}
		}
	}
	if(is_array($arrGrille[$intY0][$intX0]) && (count($arrGrille[$intY0][$intX0]) > 0)) {
		$arrCles	= array_keys($arrGrille[$intY0][$intX0]);
		$arrCopie	= $arrGrille;
		foreach($arrCles as $intChiffre) {
			$arrGrille			= $arrCopie;
			$arrGrille[$intY0][$intX0]	= $intChiffre;
			$bolLogique	= Sudoku_Resoudre_Logique();
			if(!$bolLogique) {
				$bolH	= Sudoku_Verifier_Unicite_Horizontal();
				$bolV	= Sudoku_Verifier_Unicite_Vertical();
				if($bolH && $bolV) {
					if(Sudoku_Resoudre_Essai_Erreur()) {
						$bolRetour	= true;
						break;
					} else {
						continue;
					}
				} else {
					continue;
				}
			} else {
				$bolRetour	= true;
				break;
			}
		}
	}
	return $bolRetour;
 }
 function Sudoku_Resoudre() {
	if(!Sudoku_Resoudre_Logique()) {
		if(Sudoku_Resoudre_Essai_Erreur()) {
			echo 'Résous par essai-erreur...<br>';
		} else {
			echo 'Impossible de le résoudre...<br>';
		}
	} else {
		echo 'Résous par logique...<br>';
	}
 }
 function Imprimer() {
	global $arrGrille;
 	echo '<table border="1">' . "\n";
 	for($intY = 0; $intY < 9; $intY++) {
		echo '	<tr>' . "\n";
		for($intX = 0; $intX < 9; $intX++) {
			echo '		<td style="width:50px;height:50px;text-align:center;vertical-align:center;">' . "\n";
			if(is_int($arrGrille[$intY][$intX])) {
				echo '<span style="font-size:20pt;font-weight:bold;">';
				echo $arrGrille[$intY][$intX];
				echo '</span>';
			} elseif(is_array($arrGrille[$intY][$intX])) {
				foreach(array_keys($arrGrille[$intY][$intX]) as $intChiffre) {
					echo $intChiffre . '&nbsp;';
				}
			} else {
				echo '?';
			}
			echo '		</td>' . "\n";
		}
		echo '	</tr>' . "\n";
	}
	 echo '</table>';
 }
 list($usec, $sec) = explode(" ", microtime());
 $td	= (float) $sec + (float) $usec;
 Sudoku_Importer('./sudoku.txt');
 echo '<table border="1">' . "\n";
 for($intY = 0; $intY < 9; $intY++) {
	echo '	<tr>' . "\n";
	for($intX = 0; $intX < 9; $intX++) {
		echo '		<td style="width:50px;height:50px;text-align:center;vertical-align:center;font-size:20pt;font-weight:bold;">' . "\n";
		echo '			' . ((is_int($arrGrille[$intY][$intX])) ? $arrGrille[$intY][$intX] : '&nbsp;');
		echo '		</td>' . "\n";
	}
	echo '	</tr>' . "\n";
 }
 echo '</table><br /><br />';
 Sudoku_Resoudre();
// Sudoku_Resoudre_Logique();
 echo $execs . ' loupes nécessaires...<br><br>';
 Imprimer();
 list($usec, $sec) = explode(" ", microtime());
 $te	= (float) $sec + (float) $usec;
 echo ($te - $td);
?>

suntra · Nov 17, 2006

*** Please note : these files are only made for 9x9 grids containing 9 3x3 squares...

Haven't spent enough time

sudoku on php

Kkbrij

Ddrew_man

Rrincewind456

Kkasab

Ssuntra

Ssuntra

Ssuntra