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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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…

Tweet
## Comments 36

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

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

really good! I love it!

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

Pingback: Creare un risolutore di sudoku con php : sastgroup.com

Pingback: Risolvere sudoku con php | Web2Eg

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

Pingback: Creare un risolutore di sudoku con php

Author

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

Pingback: A strange way AS3 manages arrays : Emanuele Feronato

Pingback: Sudoku creator/solver with AS3 : Emanuele Feronato

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.

i have finished the as3 version!

can you post the initial state of the game?

please?

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

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

where is it matlab solucion from sudoku????

Hy!

Thx!

perfect source code!

No Sudoku X solver?

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

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

who can send me the sududu(php)

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

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!

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.

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.

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;

}

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?

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

Author

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

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

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…

The code do not start. There are endless unknown offset errors.

Can yo tell me az explanation, PLEASE!

it’s work fine if :

1) Add two @ near count($possible in function “next_random”

function next_random($possible)

{ $max = 9;

for($x=0;$x<=80;$x++)

{ if ((@count($possible[$x])0))

{

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

function solve($sudoku)

{ $x=0;

$start = microtime();

$saved = array();

$saved_sud = array();

while(!is_solved_sudoku($sudoku))

{ $x+=1;

it’s nicer if you add in “print_sudoku” some colors

function print_sudoku($sudoku)

{ $color = array(‘pink’,’gold’);

$html = “”;

for($x=0;$x<=8;$x++)

{ $html .= "”;

for($y=0;$y<=8;$y++)

{ $bgcol = floor($y/3)%2;

$bgcol = floor($x/3)%2 ? !$bgcol : $bgcol ;

$html.= "”.$sudoku[$x*9+$y].””;

}

$html .= “”;

}

$html .= “”;

return $html;

}

Pingback: sudoku formula explanation - DL-UAT

Pingback: finding formula from table | Question and Answer