Sudoku creator/solver with PHP

December 9, 2008 • Game design, Php by Emanuele Feronato • 32 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);
?>

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

<?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

(21 votes, average: 4.90 out of 5)

Loading ...

Be my fan on Facebook and follow me on Twitter! Exclusive content for my Facebook fans and Twitter followers

This post has 32 comments

Joel Parkey

on December 9, 2008 at 5:32 pm

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

on December 9, 2008 at 11:42 pm

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

on December 10, 2008 at 12:26 pm

really good! I love it!
Colin Diam

on December 13, 2008 at 11:05 pm

Can u please post the as2 version emanuele!!??!!
Creare un risolutore di sudoku con php : sastgroup.com

on 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 [...]
Risolvere sudoku con php | Web2Eg

on December 18, 2008 at 2:17 pm

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

on 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
Creare un risolutore di sudoku con php

on December 19, 2008 at 2:13 am

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

on 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
A strange way AS3 manages arrays : Emanuele Feronato

on December 26, 2008 at 11:35 pm

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

on December 27, 2008 at 3:09 pm

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

on 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.
johnli

on January 5, 2009 at 12:02 pm

i have finished the as3 version!
Rodrigo

on March 31, 2009 at 10:32 pm

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

on April 1, 2009 at 4:01 am

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

on 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
Torvall

on June 6, 2009 at 5:46 am

where is it matlab solucion from sudoku????
kr.roland

on August 25, 2009 at 12:51 pm

Hy!

Thx!
perfect source code!
Ertyno

on August 31, 2009 at 4:00 pm

No Sudoku X solver?
nicolasd

on 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
Jim Nelms

on December 3, 2010 at 10:00 am

Hi All,

I would be pleased to hear from a programmer to write the code for a new type of ‘Sudoku’ puzzle, if you are interested and prepared to sign a NDA please reply at the earlist, the successful candidate will be given shares in the company as a reward. Regards, Jim Nelms
diallo

on February 9, 2011 at 12:03 pm

who can send me the sududu(php)
gg

on February 21, 2011 at 5:10 pm

chewdoku is better: try http://twasack.tripod.com/index.htm
Rizta Husni Ananda

on April 8, 2011 at 4:12 pm

For this particular problem (Platinum Blonde from Wikipedia):
$sudoku = array(0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,0,3,0,0,2,3,0,0,4,0,0,0,0,1,8,0,0,0,0,5,0,6,0,0,7,0,8,0,0,0,0,0,0,0,9,0,0,0,0,0,8,5,0,0,0,0,0,9,0,0,0,4,0,5,0,0,4,7,0,0,0,6,0,0,0);
And its solution:
839465712
146782953
752391486
391824675
564173829
287659341
628537194
913248567
475916238

My PHP script ran for 6.64 secs in my system. And yours for about 3 times longer.
But still, your way of thinking is really interesting. Very much different than mine. I myself never use array push pop diff etc.
Besides, I already spent over 500 lines of code for the basic elimination, trial & error, backtracking function. But yours only took less than 200 LOC for everything.
Nice and neat. Good one dude!
Rizta Husni Ananda

on April 8, 2011 at 4:18 pm

Argh shoot…
Sorry my comment ruin your page. I didn’t know that it would be displayed like that. You can just delete it if you mind.
Btw, on line 157 there’s a bit warning. Some kind of undefined variable. Thank you.
David

on May 4, 2011 at 7:25 pm

Three bugs:

The initial array is busted, it is too short.

FIX:

$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,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0
);

In the function “solve”, initialize $x before the loop:

$x = 0;

while (!is_solved_sudoku($sudoku)) {
$x++;

And the big one, check if a key for the array is valid, before trying to access it:

function next_random($possible)
{
$max = 9;

for ($x = 0; $x <= 80; $x++) {
$keyExists = array_key_exists($x, $possible);

if ($keyExists) {
if ( (count($possible[$x]) 0) ) {
$max = count($possible[$x]);
$min_choices = $x;
}
}
}

return $min_choices;
}

Very nice code, works extremely fast.
David

on May 4, 2011 at 7:29 pm

Three bugs to fix.

1) The initial array is busted, it is too short.

FIX:

$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,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0
);

2) Initialize the variable $x before the loop within the function “solve”.

$x = 0;

while (!is_solved_sudoku($sudoku)) {
$x++;

3) Check if the array has the key available.

function next_random($possible)
{
$max = 9;

for ($x = 0; $x <= 80; $x++) {
$keyExists = array_key_exists($x, $possible);

if ($keyExists) {
if ( (count($possible[$x]) 0) ) {
$max = count($possible[$x]);
$min_choices = $x;
}
}
}

return $min_choices;
}
Max Kessler

on June 9, 2011 at 8:06 pm

I don’t see any copyright notice. Did you release this to the public domain? If not, then what are your terms with regard to derivative works?
Max Kessler

on June 11, 2011 at 7:28 am

To clarify, I don’t see a copyright notice in the *script*.
Emanuele Feronato

on June 11, 2011 at 9:15 am

Use as you want. If you are going to making money out of this, consider a small donation to triqui@libero.it
??????

on December 22, 2011 at 2:39 pm

Thank you for this tutorial and i’ll try to develope this code for a facebook application.
jay patil

on December 28, 2012 at 11:42 am

I wanna display a grid of numbers from 1-8..
I want each number to be unique in its row as well as in its column..
Can u help me based on ur sodoku algo…

italian geek and PROgrammer

This post has 32 comments

Nathan

lamfan

Colin Diam

Emanuele Feronato

Richard Howarth

johnli

Rodrigo

Subhajit

Torvall

Ertyno

nicolasd

Jim Nelms

gg

David

David

Emanuele Feronato

jay patil