Sudoku creator/solver with PHP

December 9, 2008 by Emanuele Feronato
Filed under Game design, Php | 20 Comments

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:

<?php
 
function return_row($cell){
	return floor($cell/9);
}
 
function return_col($cell){
	return $cell % 9;
}
 
function return_block($cell){
	return floor(return_row($cell)/3)*3+floor(return_col($cell)/3);
}
 
function is_possible_row($number,$row,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){		
		if($sudoku[$row*9+$x] == $number){
			$possible = false;
		}		
	}
	return $possible;
}
 
function is_possible_col($number,$col,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){
		if($sudoku[$col+9*$x] == $number){
			$possible = false;
		}
	}
	return $possible;
}
 
function is_possible_block($number,$block,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){
		if($sudoku[floor($block/3)*27+$x%3+9*floor($x/3)+3*($block%3)] == $number){
			$possible = false;
		}
	}
	return $possible;
}
 
function is_possible_number($cell,$number,$sudoku){
	$row = return_row($cell);
	$col = return_col($cell);
	$block = return_block($cell);
	return is_possible_row($number,$row,$sudoku) and is_possible_col($number,$col,$sudoku) and is_possible_block($number,$block,$sudoku);
}	
 
function print_sudoku($sudoku){
	$html = "<table bgcolor = \"#000000\" cellspacing = \"1\" cellpadding = \"2\">";
	for($x=0;$x<=8;$x++){
		$html .= "<tr bgcolor = \"white\" align = \"center\">";
		for($y=0;$y<=8;$y++){
			$html.= "<td width = \"20\" height = \"20\">".$sudoku[$x*9+$y]."</td>";
		}
		$html .= "</tr>";
	}
	$html .= "</table>";
	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<count($attempt_array);$x++){
		if($attempt_array[$x] != $number){
			array_unshift($new_array,$attempt_array[$x]);
		}
	}
	return $new_array;
}
 
 
function print_possible($possible){
	$html = "<table bgcolor = \"#ff0000\" cellspacing = \"1\" cellpadding = \"2\">";
	for($x=0;$x<=8;$x++){
		$html .= "<tr bgcolor = \"yellow\" align = \"center\">";
		for($y=0;$y<=8;$y++){
			$values = "";
			for($z=0;$z<=count($possible[$x*9+$y]);$z++){
				$values .= $possible[$x*9+$y][$z];
			}
			$html.= "<td width = \"20\" height = \"20\">$values</td>";
		}
		$html .= "</tr>";
	}
	$html .= "</table>";
	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…

Rate this post: 1 Star

(10 votes, average: 4.80 out of 5)

Loading ...

Share on Facebook
Be my fan on Facebook - exclusive content

20 Responses

Joel Parkey says:

December 9, 2008 at 5:32 pm

I started to write a version of this in C# last week!

Reply
Nathan says:

December 9, 2008 at 11:42 pm

Cool. How would you make the 3×3 squares darker?

Reply
lamfan says:

December 10, 2008 at 12:26 pm

really good! I love it!

Reply
Colin Diam says:

December 13, 2008 at 11:05 pm

Can u please post the as2 version emanuele!!??!!

Reply
Creare un risolutore di sudoku con php : sastgroup.com says:

December 17, 2008 at 11:39 pm

[...] web: http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ Share and Enjoy: These icons link to social bookmarking sites where readers can share and [...]

Reply
Risolvere sudoku con php | Web2Eg says:

December 18, 2008 at 2:17 pm

[...] web: http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ Segnala [...]

Reply
Kevin Hoyt says:

December 18, 2008 at 9:44 pm

I got most of the way through an AS3 port, but got hung up on the data type of “next_move” in the solve() method. What’s that supposed to be?

The scan_sudoku_for_unique seems to either return a boolean, or an array. Yet the next line in the solve() method checks it for a boolean. The line after that attempts to pop a value off what is initially an empty array and return that value into next_move. The subsequent “if” appears to treat next_move as an array.

I’m not a PHP pro, so I’m likely missing something here, but if you could shed a little light on the data type/expectations for next_move, I’d really appreciate it.

Thanks,
Kevin

Reply
Creare un risolutore di sudoku con php says:

December 19, 2008 at 2:13 am

[...] Sito web: http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ [...]

Reply
Emanuele Feronato says:

December 19, 2008 at 10:48 am

next_move determines if I can make another “move” (placing another number or not).

If I can’t place a number, I have to backtrack the sudoku

Reply
A strange way AS3 manages arrays : Emanuele Feronato says:

December 26, 2008 at 11:35 pm

[...] I was porting my Sudoku creator/solver with PHP in AS3 when I found this strange [...]

Reply
Sudoku creator/solver with AS3 : Emanuele Feronato says:

December 27, 2008 at 3:09 pm

[...] At the beginning of this month I published the Sudoku creator/solver with PHP. [...]

Reply
Richard Howarth says:

January 2, 2009 at 5:31 pm

Thanks for this simple and easy to understand technique.

It ported fairly easily to the KiXtart scripting language with a few changes where the interpreter does not have the wealth of built-ins of PHP.

I’ve posted the ported script (with some additional code to create the starting grid) in the KiXtart community board here: http://www.kixtart.org/forums/ubbthreads.php?ubb=showflat&Number=191555

It’s a bit slow in KiXtart (it takes about 23 seconds to complete an empty grid), but watching the guesses is quite soothing.

Reply
johnli says:

January 5, 2009 at 12:02 pm

i have finished the as3 version!

Reply
Rodrigo says:

March 31, 2009 at 10:32 pm

can you post the initial state of the game?
please?

Reply
Subhajit says:

April 1, 2009 at 4:01 am

It’s really nice!!!!!!!!!!

Reply
Phil says:

May 27, 2009 at 9:42 pm

I’ve written a similar one using PHP – however it doenst really generate puzzels, only solves them. Its avaliable at http://www.idontplaydarts.com/code/sudoku-solver/

I use a similar method except my code is more OOP

Reply
Torvall says:

June 6, 2009 at 5:46 am

where is it matlab solucion from sudoku????

Reply
kr.roland says:

August 25, 2009 at 12:51 pm

Hy!

Thx!
perfect source code!

Reply
Ertyno says:

August 31, 2009 at 4:00 pm

No Sudoku X solver?

Reply
nicolasd says:

May 28, 2010 at 11:53 am

hi, i’m trying your code just for a test because i ve ceded one too, but i ve a non stop loop and nothing works, i dont know what isnt working but u call a variable x on solve method without declare it first, and i think the problem is due to that.
if you have a correction of your code which is working can you send me by mail.
i can also show you mine if needed

Reply