Sudoku Solver – 1st Session

by

This is just a stream of thought blog post as I’m coding a Sudoku solving program.  I’m a beginner coder, so the code won’t be the best, but I’m learning as I go.

 

It’s been a while since I’ve worked in PHP and to be truthful, in the past it’s been a lot of copy and paste.

Sudoku has always been a timewaster of mine and I’ve been thinking more and more about writing a solver.

I could write it in python or C++, one language I have no idea about (Python) and the other I’m just starting out.. very slowly.

So.. let me start my thought process.. hopefully it will end with a product that can solve a Sudoku puzzle.

  1. Initial idea/steps
  2. Create a form to input puzzle to solve
  3. Create a render of the puzzle
  4. Solve puzzle

Solve puzzle will be broken down in to a number of more steps. Whilst playing I’ve been trying to think of the logic I can apply to solve it.

Above the first step I’m going to address is the display, it should be added as maybe 1.1.

Sudoku is a 9×9 grid. The grid is divided up in to 9 sub-grids. Each box (when working) can have up to 9 possible values.

Yes, I’m going to create this in a table, could possibly be done in css, but for the moment, I’m starting with what I know.

What the HTML output should look like:

<table border="1">
  <tr>
    <td>
      <table border="1">
        <tr>
          <td>1</td>
          <td>2</td>
          <td>3</td>
        </tr>
        <tr>
          <td>4</td>
          <td>5</td>
          <td>6</td>
        </tr>
        <tr>
          <td>7</td>
          <td>8</td>
          <td>9</td>
        </tr>
      </table>
    </td>
... and so on..

php code to generate that:

<?php
//Opening Grid table
$grid = "<table border='2'>\n";
for($x = 1; $x <=9; $x++){
	// Start a row
	if ($x == 1 || $x == 4 || $x == 7){
	$grid .= "  <tr>\n";
	}
		//Build a cell
		$cell = "  <td>\n";
		$cell .= "    <table border='1'>\n";
		for($z = 1; $z <=9; $z++){
			if ($z == 1 || $z == 4 || $z == 7){
				$cell .= "      <tr>\n";
			}
			$cell .= "        <td>$z</td>\n";
			if ($z == 3 || $z == 6 || $z == 9){
				$cell .= "      </tr>\n";
			}
		}
		$cell .= "    </table>\n";
		$cell .= "  </td>\n";

	// Add Cell to grid
	$grid .= $cell;
	
	// End a row
	if ($x == 3 || $x == 6 || $x == 9){
		$grid .= "  </td>\n";
		$grid .= "  </tr>\n";
	}
}
// Closing Grid table
$grid .= "</table>\n";
//Display Grid
echo $grid;
?>

Output of the above code:

Cell references

In the code above, technically, I can produce a unique number in each cell.

I made the cell building part of the loop in to a function. This will just make my code cleaner, in the fact that a lot of logic won’t be in the middle of my script and because overtime, there will be 3 possible states of each cell:

  1. Input mode
  2. Possible values
  3. Solved value

Thinking back to the labelling of each cell above, each cell has a 2 number reference, the 1st being the 9 cell block, the second being the number of the cell IN the block.

The other way to refer to it would be columns and rows. I’m wondering if having multiple ‘index’ locations would make it easier to ‘solve’ with queries.

Using 3 digits, The top left corner cell would be 111. The top right would be 193. The bottom left would be 197.

It would mean rewriting the table building part of the code, but doing that now would be easier than latter.

Leave a Reply