Talking about Sudoku game, Game development and Php.
This is an old project for a class held in 2005.
At that time, Sodoku game was very popular in Italy, and I saw quite a lot of Flash games based upon it.
If you don’t know what is a Sudoku, Wikipedia says is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.
The script consists in a set of functions that emulate the “human way” to solve a Sudoku game, with trials and errors, using backtracking.
The only thing you need to know is how I represent the Sudoku table inside the script.
It’s an array (line 193) with 81 values representing positions from 0
to 80
. The value at n-th
position is the one you will find on the table at row floor(n/9)
and column n%9
.
A value from 1
to 9
represents a know number of a Sudoku table, while a zero
represents an unknown one.
For this reason, an array filled only with zeros like the one in the script will generate a new, full Sudoku.
This is the script:
";
for($x=0;$x<=8;$x++){
$html .= "";
for($y=0;$y<=8;$y++){
$html.= "".$sudoku[$x*9+$y]." ";
}
$html .= " ";
}
$html .= "";
return $html;
}
function is_correct_row($row,$sudoku){
for($x=0;$x<=8;$x++){
$row_temp[$x] = $sudoku[$row*9+$x];
}
return count(array_diff(array(1,2,3,4,5,6,7,8,9),$row_temp)) == 0;
}
function is_correct_col($col,$sudoku){
for($x=0;$x<=8;$x++){
$col_temp[$x] = $sudoku[$col+$x*9];
}
return count(array_diff(array(1,2,3,4,5,6,7,8,9),$col_temp)) == 0;
}
function is_correct_block($block,$sudoku){
for($x=0;$x<=8;$x++){
$block_temp[$x] = $sudoku[floor($block/3)*27+$x%3+9*floor($x/3)+3*($block%3)];
}
return count(array_diff(array(1,2,3,4,5,6,7,8,9),$block_temp)) == 0;
}
function is_solved_sudoku($sudoku){
for($x=0;$x<=8;$x++){
if(!is_correct_block($x,$sudoku) or !is_correct_row($x,$sudoku) or !is_correct_col($x,$sudoku)){
return false;
break;
}
}
return true;
}
function determine_possible_values($cell,$sudoku){
$possible = array();
for($x=1;$x<=9;$x++){
if(is_possible_number($cell,$x,$sudoku)){
array_unshift($possible,$x);
}
}
return $possible;
}
function determine_random_possible_value($possible,$cell){
return $possible[$cell][rand(0,count($possible[$cell])-1)];
}
function scan_sudoku_for_unique($sudoku){
for($x=0;$x<=80;$x++){
if($sudoku[$x] == 0){
$possible[$x] = determine_possible_values($x,$sudoku);
if(count($possible[$x])==0){
return(false);
break;
}
}
}
return($possible);
}
function remove_attempt($attempt_array,$number){
$new_array = array();
for($x=0;$x";
for($x=0;$x<=8;$x++){
$html .= "";
for($y=0;$y<=8;$y++){
$values = "";
for($z=0;$z<=count($possible[$x*9+$y]);$z++){
$values .= $possible[$x*9+$y][$z];
}
$html.= "$values ";
}
$html .= " ";
}
$html .= "";
return $html;
}
function next_random($possible){
$max = 9;
for($x=0;$x<=80;$x++){
if ((count($possible[$x])<=$max) and (count($possible[$x])>0)){
$max = count($possible[$x]);
$min_choices = $x;
}
}
return $min_choices;
}
function solve($sudoku){
$start = microtime();
$saved = array();
$saved_sud = array();
while(!is_solved_sudoku($sudoku)){
$x+=1;
$next_move = scan_sudoku_for_unique($sudoku);
if($next_move == false){
$next_move = array_pop($saved);
$sudoku = array_pop($saved_sud);
}
$what_to_try = next_random($next_move);
$attempt = determine_random_possible_value($next_move,$what_to_try);
if(count($next_move[$what_to_try])>1){
$next_move[$what_to_try] = remove_attempt($next_move[$what_to_try],$attempt);
array_push($saved,$next_move);
array_push($saved_sud,$sudoku);
}
$sudoku[$what_to_try] = $attempt;
}
$end = microtime();
$ms_start = explode(" ",$start);
$ms_end = explode(" ",$end);
$total_time = round(($ms_end[1] - $ms_start[1] + $ms_end[0] - $ms_start[0]),2);
echo "completed in $x steps in $total_time seconds";
echo print_sudoku($sudoku);
}
$sudoku = array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
solve($sudoku);
?>
And this is an example of a new sudoku generated with the script:
Refresh the iframe to create another one.
This script too is quite easy to port in AS3, if you convert it I’ll post it on the blog.
I should have an old AS2 conversion too somewhere in my hard disks…
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.