PHPhulp.nl
35k+ leden Over PHPhulp Offerte opdracht Contact
Scripts

Sudoku generator

Door Bart Waarom verplicht -10-01-2007 00:00 -9.634 views

Dit script genereert een sudoku. Script is op sommige delen een beetje een rommeltje (tis al laat). Script is soms ook wat traag, omdat de sudoku eigenlijk 'brute force' gemaakt wordt. Ook komen er vaak dubbele sudoku's voor. Daarnaast is het script ook nog behoorlijk server intensief ;-)... Ondanks dat vond ik het toch wel waard om te posten, zodat andere gebruikers hem misschien kunnen verbeteren oid...

Download alle bestanden als ZIP
sudoku-generator
[code]<?php 
session_start(); 
error_reporting(E_ALL);

$time_start = microtime_float();

// No cacheing headers
header('Expires: 0'); // Date in the past
header('Cache-Control: private, post-check=0, pre-check=0, max-age=0', false);
header('Pragma: no-cache'); // HTTP/1.0
header('Content-Type: text/html');

// Timing
function microtime_float()
{
   list($usec, $sec) = explode(" ", microtime());
   return ((float)$usec + (float)$sec);
}

// Seeds mt_rand() and rand()
function doseed()
{
	if(!defined('SEEDED'))
	{
		$seed = (double) microtime() * 1000000;
		mt_srand($seed);
		srand($seed);

		define('SEEDED', true);
	}
}

// Check if $post isset, numeric, and is 1 char long
function ischeck($post)
{
	if(!isset($_POST[$post])) return false;
	elseif(!is_numeric($_POST[$post])) return false;
	elseif(strlen($_POST[$post]) != 1) return false;
	else return true;
}

// Parses the input array($arr) and shows it as the sudoku
function showsudoku($arr)
{
	$res = '';
	$allok = true;

	// Top - Bottom
	for($tb = 0; $tb < 9; $tb++)
	{
		$res .= '<tr>'."\n";
		
		// Left - right
		for($lr = 0; $lr < 9; $lr++) 
		{
			$res .= '<td style="'.(($tb == 3 || $tb == 6) ? 'border-top: 1px solid black;' : '').(($tb == 2 || $tb == 5) ? ' border-bottom: 1px solid black;' : '').(($lr == 2 || $lr == 5) ? ' border-right: 1px solid black;' : '').(($lr == 3 || $lr == 6) ? ' border-left: 1px solid black;' : '').'">';

			if(isset($_SESSION['sudoku']['hidden'][$tb][$lr]))
			{
				if(ischeck('res_'.$tb.'_'.$lr.''))
				{
					if($_POST['res_'.$tb.'_'.$lr.''] == intval($arr[$tb][$lr]))
					{
						$res .= '<input type="hidden" name="res_'.$tb.'_'.$lr.'" value="'.$_POST['res_'.$tb.'_'.$lr.''].'" /><span class="inp_ok">'.$_POST['res_'.$tb.'_'.$lr.''].'</span>';
					}
					else
					{
						$res .= '<input type="text" name="res_'.$tb.'_'.$lr.'" value="'.$_POST['res_'.$tb.'_'.$lr.''].'" maxlength="1" class="inp" style="color: #FF0000;" />';
						$allok = false;
					}
				}
				else
				{
					$res .= '<input type="text" name="res_'.$tb.'_'.$lr.'" maxlength="1" class="inp" />';
					$allok = false;
				}
			}
			else
			{
				$res .= $arr[$tb][$lr]; 
			}

			$res .= '</td>'."\n";
		}

		$res .= '</tr>'."\n";
	}
	
	if(!isset($_SESSION['sudoku']['solved']) || $_SESSION['sudoku']['solved'] == false) $_SESSION['sudoku']['attempts']++;
	if($allok == true && (!isset($_SESSION['sudoku']['solved']) || $_SESSION['sudoku']['solved'] == false))
	{ 
		$_SESSION['sudoku']['solved'] = true;
		$_SESSION['sudoku']['endtime'] = time();
	}

	return($res);
}

// Generates a number based on the input
function gennr($forbid)
{
	doseed();

	$randlist = array(1, 2, 3, 4, 5, 6, 7, 8, 9);

	if(mt_rand(0, 1) == 1) shuffle($randlist);
	if(mt_rand(0, 1) == 1) shuffle($randlist);

	$randlist = array_diff($randlist, $forbid);
	
	if(mt_rand(0, 2) == 1) shuffle($randlist);
		
	$temprand = array_rand($randlist);
	if(!isset($randlist[$temprand])) { return false; }
	else { $rand = $randlist[$temprand]; }

	return($rand);
}

// Generates the 3 x 3 box
function genbox($r, $tb, $lr)
{
	$return = array();

	// Row 1
	if($tb == 0 || $tb == 3 || $tb == 7) 
	{ 
		if($lr == 0 || $lr == 3 || $lr == 7)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr+1)]; 
			@$return[] = $r[($tb+1)][($lr+2)]; 
			
			@$return[] = $r[($tb+2)][$lr]; 
			@$return[] = $r[($tb+2)][($lr+1)]; 
			@$return[] = $r[($tb+2)][($lr+2)]; 
		}
		elseif($lr == 1 || $lr == 4 || $lr == 8)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr-1)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr+1)]; 
			@$return[] = $r[($tb+1)][($lr-1)]; 
			
			@$return[] = $r[($tb+2)][$lr]; 
			@$return[] = $r[($tb+2)][($lr+1)]; 
			@$return[] = $r[($tb+2)][($lr-1)];
		}
		elseif($lr == 2 || $lr == 5 || $lr == 9)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr-1)]; 
			@$return[] = $r[($tb+1)][($lr-2)]; 
			
			@$return[] = $r[($tb+2)][$lr]; 
			@$return[] = $r[($tb+2)][($lr-1)]; 
			@$return[] = $r[($tb+2)][($lr-2)];
		}
	}
	
	elseif($tb == 1 || $tb == 4 || $tb == 8) 
	{ 
		if($lr == 0 || $lr == 3 || $lr == 7)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr+1)]; 
			@$return[] = $r[($tb+1)][($lr+2)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr+1)]; 
			@$return[] = $r[($tb-1)][($lr+2)]; 
		}
		elseif($lr == 1 || $lr == 4 || $lr == 8)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr-1)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr+1)]; 
			@$return[] = $r[($tb+1)][($lr-1)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr+1)]; 
			@$return[] = $r[($tb-1)][($lr-1)];
		}
		elseif($lr == 2 || $lr == 5 || $lr == 9)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb+1)][$lr]; 
			@$return[] = $r[($tb+1)][($lr-1)]; 
			@$return[] = $r[($tb+1)][($lr-2)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr-1)]; 
			@$return[] = $r[($tb-1)][($lr-2)];
		}
	}

	elseif($tb == 2 || $tb == 5 || $tb == 9) 
	{ 
		if($lr == 0 || $lr == 3 || $lr == 7)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr+1)]; 
			@$return[] = $r[($tb-1)][($lr+2)]; 
			
			@$return[] = $r[($tb-2)][$lr]; 
			@$return[] = $r[($tb-2)][($lr+1)]; 
			@$return[] = $r[($tb-2)][($lr+2)]; 
		}
		elseif($lr == 1 || $lr == 4 || $lr == 8)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr-1)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr+1)]; 
			@$return[] = $r[($tb-1)][($lr-1)]; 
			
			@$return[] = $r[($tb-2)][$lr]; 
			@$return[] = $r[($tb-2)][($lr+1)]; 
			@$return[] = $r[($tb-2)][($lr-1)];
		}
		elseif($lr == 2 || $lr == 5 || $lr == 9)
		{
			@$return[] = $r[$tb][($lr+1)]; 
			@$return[] = $r[$tb][($lr+2)]; 
			
			@$return[] = $r[($tb-1)][$lr]; 
			@$return[] = $r[($tb-1)][($lr-1)]; 
			@$return[] = $r[($tb-1)][($lr-2)]; 
			
			@$return[] = $r[($tb-2)][$lr]; 
			@$return[] = $r[($tb-2)][($lr-1)]; 
			@$return[] = $r[($tb-2)][($lr-2)];
		}
	}
		
	return($return);
}

// Generates a sudoku
function gensudoku()
{
	global $sudoku_attempts;

	// Defines
	$_SESSION['sudoku'] = array();
	$_SESSION['sudoku']['numbers'] = array();
	$_SESSION['sudoku']['hidden'] = array();
	$_SESSION['sudoku']['attempts'] = 0;
	$_SESSION['sudoku']['hash'] = '';
	$_SESSION['sudoku']['starttime'] = 0;
	$_SESSION['sudoku']['endtime'] = 0;
	$_SESSION['sudoku']['solved'] = false;

	$r = array();
	$h = array();
	$temparr = array();

	$res = '';
	$empt = 0;

	// Seed
	doseed();
		
	// Top - Bottom
	for($tb = 0; $tb < 9; $tb++)
	{
		$r[$tb] = array();
		$h[$tb] = array();

		$empt = 0;
		
		// Left - right
		for($lr = 0; $lr < 9; $lr++) 
		{
			$temparr_v = array();
			$temparr_b = array();

			// For vertical numbers
			for($i = 0; $i < 9; $i++) { if(isset($r[$i][$lr])) $temparr_v[] = $r[$i][$lr]; }

			// For the 3x3 box
			$temparr_b = genbox($r, $tb, $lr);
			
			// Fetch a number
			$tdnr = gennr(array_merge($r[$tb], $temparr_v, $temparr_b));
			if($tdnr === false) 
			{ 
				// Failed generating
				$sudoku_attempts++;

				return gensudoku();
				exit(); 
			}

			// Is this one empty?
			if($empt < mt_rand(1, 6) && mt_rand(0, 2) == 1)
			{
				$empt++;
				$r[$tb][$lr] = $tdnr;
				$h[$tb][$lr] = true;
			}
			else
			{
				$r[$tb][$lr] = $tdnr;
			}
		}
	}
	
	$_SESSION['sudoku']['numbers'] = $r;
	$_SESSION['sudoku']['hidden'] = $h;
	$_SESSION['sudoku']['hash'] = md5(serialize($_SESSION['sudoku']['numbers']));
	$_SESSION['sudoku']['starttime'] = time();
	echo "\n\n".'<!-- GENERATED :: '.serialize($r).'-->'."\n\n";

	return(showsudoku($r));
}

// Do we want a new game?
if(isset($_GET['do']) && $_GET['do'] == 'new') { unset($_SESSION['sudoku']); header("Location: ".basename($_SERVER['PHP_SELF'])); exit(); }
?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html>
<head>
<title>Sudoku generator</title>
<style type="text/css">
<!-- 
body				{ background-color: #C8C8C8; margin: 5px; color: #000000; } 
body, table, tr, td, fieldset, legend, input	{ font-size: 16px; font-family: verdana, sans-serif; } 
table.sudoku		{ background-color: #FFFFFF; padding: 0px; margin: 0px; width: 100%; } 
table.sudoku td		{ height: 30px; width: 30px; text-align: center; border: 1px dotted #000066; }
fieldset			{ width: 330px; border: 2px dotted #000066; margin: 0px; padding: 15px; }
legend				{ font-size: 24px; font-weight: bold; letter-spacing: 4px; background-color: #FFCC00; padding: 2px 6px; border: 2px solid #000066; }
.submit				{ font-weight: bold; width: 80%; }
.inp				{ width: 80%; font-weight: bold; text-align: center; border: 1px solid #000066; font-size: 18px; }
.inp_ok				{ color: #339900; font-weight: bold; font-size: 20px; }
div					{ display: block; }
.small				{ font-size: 11px; }
-->
</style>
</head>
<body>
<br />
<center>

<fieldset>
<legend>Sudoku</legend>

<form method="post" action="<?php echo $_SERVER['PHP_SELF']; ?>">
<input type="hidden" name="posted" value="1" />
<table class="sudoku">
<?php
// Starting a new game, or are we continueing one?
if(isset($_SESSION['sudoku']['numbers']) && isset($_SESSION['sudoku']['hash']) && $_SESSION['sudoku']['hash'] == md5(serialize($_SESSION['sudoku']['numbers'])))
{
	$show = showsudoku($_SESSION['sudoku']['numbers']);

	if(isset($_SESSION['sudoku']['solved']) && $_SESSION['sudoku']['solved'] == true)
	{
		echo $show;

		$time = ($_SESSION['sudoku']['endtime'] - $_SESSION['sudoku']['starttime']);
		echo '<tr><td colspan="9"><br /><b>Succes!</b><br /><br /><div style="text-align: left; width: 100%;">Gefeliciteerd, u heeft de sudoku opgelost!<br /><br /><b>Resultaten: </b><br /><ul><li><b>'.$_SESSION['sudoku']['attempts'].'</b> poging(en)</li><li><b>'.date("i", $time).'</b> minuten en <b>'.date("s", $time).'</b> seconden</li></ul></div></td></tr>';
		$sudoku = false;
	}
	else
	{
		echo $show;
		$sudoku = true;
	}
}
else
{
	$sudoku_attempts = 1;
	$sudoku = gensudoku();

	echo $sudoku;
}
?>
</table><br />
<?php 
// Aantal pogingen laten zien voor het genereren van de sudoku
if(isset($sudoku_attempts) && is_numeric($sudoku_attempts) && $sudoku !== false) { echo '<span class="small">Sudoku gegenereerd na '.$sudoku_attempts.' pogingen.</span><br /><br />'; }
elseif(isset($_SESSION['sudoku']['attempts']) && is_numeric($_SESSION['sudoku']['attempts']) && $sudoku !== false) { echo '<span class="small">Aantal pogingen: '.$_SESSION['sudoku']['attempts'].'</span><br /><br />'; }

// 'Controleren' knop alleen laten zien als er een sudoku is gemaakt
if(isset($sudoku) && $sudoku !== false) { echo '<input type="submit" value="Controleren" class="submit" /><br /><br />'; }
?>
<a href="<?php echo $_SERVER['PHP_SELF']; ?>?do=new">Nieuwe Sudoku</a>
</form>
</fieldset><br />
<span class="small"><?php $time_end = microtime_float(); $time = $time_end - $time_start; echo 'Sudoku gegenereerd in '.round($time, 6).' seconden.'; ?><br />Copyright: M-D / Bart</span>

</center>

</body>
</html>[/code]

Reacties

0
Nog geen reacties.