Sudoku Solver PHP Part2

Sudoku Solver PHP Part2

Categorised in:

Last time we worked on alogrithm to solve Sudoko puzzles, see Sudoku Solver PHP Part 1. This worked for easy puzzles but when a more complex grid was entered the code could not solve it. A further algorithm is needed.

The way the algorithm worked was to assume every square (except those given starting numbers) could be any number from 1-9. It then went through the grid looking for starting numbers and checking the rows, columns and groups of these starting numbers to eliminate any duplicates. It repeated this process until no more could be found. The algorithm failed to solve a harder puzzle because duplicates in the row, column and group no longer existed. What we need is another rule to further reduce the grid.

The smaller (font) sized numbers are what is left after the algorithm has run, and we need to look for further rule sets to help us reduce this further. Take the middle top group. You can see the unreduced number set is 679, 69, 79, 34, 34 and 24. Of all these numbers, the number 2 is unique. Which means the cell with set “24” must in fact, be the “2”.

To further explain, in the example, the bottom-middle-group top-center-cell is the only cell in the group that can contain “1”. (The other options in the group are 4,6,8 & 9). If this cell is a 1, then in the group above, the cell that contains the possibles 1348 is now reduced to 348 since it is in the same column and therefore cannot be a “1”. That would mean the cell to the left of it that contains 134 would have a unique “1” and therefore that cell must be “1”.

So what we need to do is to include another algorithm to look for unique numbers in the rows, columns and groups, set these cells accordingly and then reduce the grid again. So the loop now becomes:

$changed = true;
$onemoretime = true;
$iterations = 0;
$uniresult = 0;
while( $changed || $onemoretime ) {
	if( !$changed && $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;
		}
	}
	
	// Now identify the unique cells.
	foreach( $grid as $key=>$value ) {
		if( strlen($value) > 1 ) {
			$changed = unique($key,$value);
			if( $changed ) $onemoretime=true;
			$uniterations++;
		}
	}
	$iterations++;
}

[Note the &amp&amp in the code above is a bug with the syntax parser and should of course be &&].

And the new function:

function unique( $cell, $value ) {
	global $grid, $row, $col, $group, $uniresult;
	$changed = false;
	// Go through all the check areas
	$checklist[] = $col;
	$checklist[] = $row;
	$checklist[] = $group;
	foreach( $checklist as $check ) {
		
		foreach( $check as $cd ) {
			if( in_array( $cell, $cd ) ) {
			// Get all the digits in the check area excluding the target
			
			$checkdigits = "";
			
			foreach( $cd as $c ) {
				if( $c != $cell ) $checkdigits .= $grid[$c];
				else $isincheck = true;
			}
			
				$tarnums = str_split( $value );
				$unique = true;
				// Go through each of the numbers in the target cell one by one
				foreach( $tarnums as $tn ) {
					if( !( stripos( $checkdigits, $tn ) === false ) ) $unique = false;
						else {
							$grid[$cell] = $tn;
							$changed = true;
							$uniresult++;
						}
				}

			}
		}
			
			
	}
	
	return $changed;
}

This works by calling the unique function on every cell that has a string length of greater than one. The function goes through each of the check arrays and if the target cell is in proceeds to check the other cells in the check. It concatenates all the other strings into one large string – $checkdigits, and then does a stripos on this with the target digits one at a time. If stripos returns false eg (!stripos returns true), then the value is unique.

So running this through the algorithm yields:

Bob’s your chuffing uncle. Now let’s try a hard.

$solve[] = "___48____";
$solve[] = "9__27_1_8";
$solve[] = "4_1_5__7_";
$solve[] = "56___2___";
$solve[] = "__7_1__6_";
$solve[] = "8___69___";
$solve[] = "_9__2_8__";
$solve[] = "_4____3__";
$solve[] = "2_3_____5";

Bingo! Now we’re on to something. Let’s try another hard one.

$solve[] = "__3_9_8_1";
$solve[] = "_____6_5_";
$solve[] = "__97_1___";
$solve[] = "13__4___8";
$solve[] = "2__1__46_";
$solve[] = "_9____7__";
$solve[] = "___3__6_5";
$solve[] = "____2_1__";
$solve[] = "34_9_____";

Well can’t win them all. Granted I’m no Sudoku expert but I can’t 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 solutions.

3 responses to “Sudoku Solver PHP Part2”

  1. […] 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 Sudoko Solver PHP Part 2. […]

  2. […] 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: […]

  3. […] 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. […]

Tagged with ,

Available Tags

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