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:

```";
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…

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers