Sudoku Solver PHP Part 3

Sudoku Solver PHP Part 3

Categorised in:

Last time we developed the algorithms to eliminate duplicates from the grid and then search for values where one number is unique in the group, row or col. This worked for a variety of puzzles but we came a cropper on the last one, namely:

You can see in this puzzle that the algorithm has done its work but there are no obvious means of seeing any further rules to solve this. The only way is to suck it and see. So we need to be able to edit the grid, and although I had to do this before coming up with the rest of the code, I’ll do this in reverse order. The first thing that we need to do is to be able to check the grid for errors. If we change one of the numbers and it won’t lead to a correct grid the algorithm won’t care. So we need to include an error check routine after each pass of the algorithm.

function errorcheck() {
	global $grid, $row, $col, $group;
	$error = false;
	for( $i=0; $i<9; $i++ ) {
		$check = "";
		foreach( $row[$i] as $r ) {
			if( strlen( $grid[$r] ) == 1 ) $check.=$grid[$r];
		}
		if( dupecheck( $check ) ) $error = true;
		var_dump( $check );
		
		$check = "";
		foreach( $col[$i] as $r ) {
			if( strlen( $grid[$r] ) == 1 ) $check.=$grid[$r];
		}
		if( dupecheck( $check ) ) $error = true;
		
		$check = "";
		foreach( $group[$i] as $r ) {
			if( strlen( $grid[$r] ) == 1 ) $check.=$grid[$r];
		}
		if( dupecheck( $check ) ) $error = true;
		
	}
	
	return $error;
}

function dupecheck( $text ) {
	$dupe = false;
	for( $i=1; $i<=9; $i++ ) {
		if( substr_count( $text, $i ) >1 ) $dupe = true;
	}
	return $dupe;
}

The function errorcheck goes through every row, column and group, concatenates all the digits and sends them to the function dupecheck. This checks the string against the numbers 1-9 and counts the numbers of each using the substr_count function. If the count is over one, the grid is in error.

So let’s change the top left square, which can be 4,5 or 6 to “5” and run the algortihm again:

Looks like it’s still valid. Now let’s change cell 4 (either 2 or 4) to “2”:

Although the grid is solved, the error check has picked up errors. You can see the problems with the 8’s. Let’s start again, but this time change digit 1 to “4” not “5”.

Awesome, solved!

So that’s it. I guess we could do some automagic routine to do the suck it and see, but that would be kind of complex and would then take some of the fun away. As promised I said I’d show and explain the full code and I’ll do that next.

One response to “Sudoku Solver PHP Part 3”

  1. […] see a method of solving this without a suck it and see approach. So that’ll be the quest for Part 3 – to add in code to let us edit the grid and check other […]

Tagged with ,

Available Tags

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