Sudoku creator/solver with 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:
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…
19 Responses to “Sudoku creator/solver with PHP”
Leave a Reply
Trackbacks
-
Creare un risolutore di sudoku con php : sastgroup.com on
December 17th, 2008 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 18th, 2008 2:17 pm
[...] web: http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ Segnala [...]
-
Creare un risolutore di sudoku con php on
December 19th, 2008 2:13 am
[...] Sito web: http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ [...]
-
A strange way AS3 manages arrays : Emanuele Feronato on
December 26th, 2008 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 27th, 2008 3:09 pm
[...] At the beginning of this month I published the Sudoku creator/solver with PHP. [...]
- Citrus Engine released for free for learning
- My epic fail with ClickBank
- Get up to $100,000 for your next Flash game with Mochi GAME Developer Fund
- Create a dynamic content animated footer ad for your site in just 9 jQuery lines – 17 lines version
- Sell sitelocked version of your Flash games and even .fla sources to Free Online Games
- Protect your work from ActionScript code theft with SWF Protector
- Create a dynamic content animated footer ad for your site in just 9 jQuery lines
- Understanding Box2D’s one-way platforms, aka CLOUDS
- Triqui MochiAds Arcade plugin for WordPress upgraded to 1.2
- Box2D Flash game creation tutorial – part 2
- Create a Lightbox effect only with CSS - no javascript needed
- Flash game creation tutorial - part 1
- Create a Flash Racing Game Tutorial
- Flash game creation tutorial - part 2
- Make a Flash game like Flash Element Tower Defense - Part 2
- Flash game creation tutorial - part 3
- Make a Flash game like Flash Element Tower Defense - Part 1
- Create a flash draw game like Line Rider or others - part 1
- Triqui MochiAds Arcade plugin for WordPress official page
- Create a flash artillery game - step 1
- Flash game creation tutorial – part 5.2 (4.88/5)
- Create a flash artillery game – step 1 (4.79/5)
- Create a Flash Racing Game Tutorial (4.76/5)
- Create a survival horror game in Flash tutorial – part 1 (4.74/5)
- Create a flash artillery game – step 2 (4.74/5)
- Creation of a Flash arcade site using WordPress – step 2 (4.73/5)
- Flash game creation tutorial – part 1 (4.71/5)
- Flash game creation tutorial – part 2 (4.71/5)
- Create a flash draw game like Line Rider or others – part 1 (4.69/5)
- Creation of a platform game with Flash – step 2 (4.68/5)

(9 votes, average: 4.78 out of 5)



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