Sudoku Solver PHP Part 1

Sudoku Solver PHP Part 1

Categorised in:

Was given a project for a solver for Sudoku. It’s a brain teaser, but, unless you get to the higher levels, it really is a method of just following some rules. So first things first, define the rules and then do some coding to solve the puzzle.

What is Sudoku?

It’s a game with 81 squares arranged into nine 3×3 blocks. Each row, column and 3×3 group must have each number from 1-9 present. That is, you can’t have more than one of each number. In the example below the highlighted row contains the numbers 1,4,3,9 & 2, the column, 7,2,4 & 9 and the group 1,3,9 & 2.

So based on this you can see that the for the top left square the row contains 1,2,5&7 so this value cannot be any of these. The column contains 2,5,7&8, and the group 2&4. This means that this square can only be one of the numbers 3,6 or 9.

Now, take the top square 4th along from the left. In its row are the numbers 2,7,5&1. In it’s column are 1,9,8 & 7. In it’s group are the numbers 1,2,3,4,5,7&9. Which means this square cannot contain the numbers 1,2,3,4,5,7,8 or 9, leaving 6 as the only possible.

Which now means the top left square, previously which could be 3,6,9 can now only be 3 or 9 as 6 is now in the row. So this is the basis of the algorithm that we’ll use to try and solve a puzzle. So let us create the grid in an array and assign the grid a string containing all the possible numbers that could be. In a blank grid, this means every square contains “123456789”. So we create an array of 81 elements all with the string content “123456789”. We’re using strings and not numbers as this is the basis of all the checks and manipulation we’ll need to do. In fact, you could do Sudoko with “abcdefghi” or any other unique 9 digit characters. This is most simply done using the array_fill function.

$grid = array_fill( 1, 81, "123456789");

The first row will be array elements 1-9, followed by 10-18 etc. The next thing we are going to do is to define an array of checks, that is the rows, columns and groups that we will traverse. This involves a little number manipulation:

// This bit is to define the check rows, columns and groups.	
	$groupone = array(1,2,3,10,11,12,19,20,21);
	for( $i=1; $i<=9; $i++ ) {
		unset( $thisrow, $thiscol, $thisgroup, $thisgroup2, $thisgroup3 );
		for( $j=1; $j<=9; $j++ ) {
			$thisrow[] = $j + ($i-1)*9;
			$thiscol[] = $i + ($j-1)*9;
		}
		$row[] = $thisrow;
		$col[] = $thiscol;
		if( $i==1 OR $i==4 OR $i==7 ) {
			foreach( $groupone as $go ) {
				$thisgroup[] = 9*($i-1) + $go;
				$thisgroup2[] = 9*($i-1) + $go+3;
				$thisgroup3[] = 9*($i-1) + $go+6;
			}
			$group[] = $thisgroup;
			$group[] = $thisgroup2;
			$group[] = $thisgroup3;
		}
	}

What this has done is give us 3 arrays each of 9×9 elements. For $col the first element will contain the numbers 1,10,19,28,37,46,55,64 & 73, eg they refer to the elements in the $grid array. Likewise the first $group is elements 1,2,3,10,11,12,19,20&21. For completion the first $row is the numbers 1-9 and $row[9] is 73-81.

Now we need to put some numbers in the grid to solve. We’ll use an array with each element holding 9 chars. We use a ‘_’ for not given. The first array element corresponds to the first row and so on.

// Now I'm going to put some numbers into the grid and attempt to reduce the grid
// Easy
$solve[] = "__2_78_1_";
$solve[] = "___1_4392";
$solve[] = "_4_923___";
$solve[] = "7_38____4";
$solve[] = "2947___8_";
$solve[] = "8___496__";
$solve[] = "____9_856";
$solve[] = "_79___2_1";
$solve[] = "586____3_";

And use this to put the fixed numbers in the grid array.

// Now override the grid array with the solve array.
$g = 1;
foreach( $solve as $s ) {
	for( $i=0; $i<9; $i++) {
		$j = substr($s,$i,1);
		if( $j != '_' ) $grid[$g] = $j;
		$g++;
	}
}

So now we need to traverse the grid array and reduce the options down. The idea is we will compare each cell that has a string of length of 1 (eg the set number) and then remove that number from the list of possibles in the matching row, column and group. We will need to do this several times. Instead of guessing an artibrary number of times we will look for when no more changes to the grid have occurred and then do it one more time.

This is the loop:

$changed = true;
$onemoretime = true;
$iterations = 0;
while( $changed || $onemoretime ) {
	if( !$changed &amp;&amp; $onemoretime ) $onemoretime=false;
	
	// Reduce the grid by eliminating impossibles
	foreach( $grid as $key=>$value ) {
		if( strlen($value) == 1 ) { // A found/given cell only has one char.
			$changed = reduce($key,$value);
			if( $changed ) $onemoretime=true;
		}
	}
	$iterations++;
}

And this is the function, note the !(stripos( $grid[$v], $value ) === false). You have to explicitly determine if it’s found or not as if the found element is at position zero, that’s what the function returns – which is treated as false in the if statement.

function reduce( $cell, $value ) {
	global $grid, $row, $col, $group;
	$changed = false;
	// Go through all the check areas
	$checklist[] = $col;
	$checklist[] = $row;
	$checklist[] = $group;
	foreach( $checklist as $check ) {
		foreach( $check as $c ) {
			// If the cell id is in the check row then check this row
			if( in_array( $cell, $c ) ) {
				foreach( $c as $k=>$v ) {
					// So if $value is found at one of the cells in this row then remove it from the rest
					// and its not the cell we're looking at (length must be more than 1)
					if( !(stripos( $grid[$v], $value ) === false) &amp;&amp; ( strlen( $grid[$v] ) >1 )) {
						$grid[$v] = str_ireplace( $value, '', $grid[$v] );
						$changed = true;
					}
				}
			}
		}
	}
	
	return $changed;
}

So, how does it work? In order to present it there is extra code (that’ll I show at the end of this series) to present the grid and style it, but I won’t include this for now. Running this programme yielded this result:

Yes, that’s right, solved first time. Now that was taken from a standard Suduko puzzle that was deemed “easy”, now let’s move up a level to medium. Replace the $solve array with the following:

// Medium
$solve[] = "_43851967";
$solve[] = "______234";
$solve[] = "976______";
$solve[] = "______796";
$solve[] = "7__2__1__";
$solve[] = "__1__6__3";
$solve[] = "32_5_____";
$solve[] = "_15_7____";
$solve[] = "____2351_";

This time it couldn’t complete the grid, so we will need to look at extra rules to clear these. This will be the subject of Sudoku Solver PHP Part 2.

One response to “Sudoku Solver PHP Part 1”

  1. […] time we worked on alogrithm to solve Sudoko puzzles, see Sudoko Solver PHP Part 1. This worked for easy puzzles but when a more complex grid was entered the code could not solve it. […]

Tagged with ,

Available Tags

api barcode ean13 finder foreach functions json oscommerce php programming sudoku themes webp wordpress