Sudoku Solver – 4th Session

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.

Click here to see the first post
Click here to see the second post
Click here to see the third post

I’ll post code snippets and then the full code at the bottom of this post.

To me, the logic in solving an “EASY” Sudoku is easy.

  1. Look at all possible values of a cell
  2. If there is only one possible value, that’s the answer
  3. Rinse and repeat until the whole puzzle is solved

Harder puzzles require more working out to eliminate possible values

  1. Look at all possible values of a cell
  2. If there is only one possible value, that’s the answer
  3. Rinse and repeat until no more cells can be solved
  4. Use more advanced methods to remove possible values from cell
  5. Repeat until whole puzzle is solved

In the array I’m going to build from the initial submit, only ‘solved’ values will be present.

As that cell has only one value, the length of that string will be 1. That’s how I’m going to determine a solved cell.

Initially an cell has a length of 0, it’s unsolved, I need to loop though each number, 1-9 to check if it appears in either that row, column or sub-grid. If the doesn’t exist in that check, add it as a possible value. If there is only 1 possible value, the cell is solved, otherwise, I’ll have a string for that cell where the length is >1, meaning unsolved.

Just thinking forward here, I can place an additional check if a cell is solved to remove that value from other cells in the column/row/sub-grid. That will reduce the number of loops going forward.

I can also reduce loops by building a second array of ‘solved cells’ so when stepping through checking cells, solve cells are skipped.

Now, coming back to the cell naming convention I set up.

[Column],[Row],[Cell],[Subgrid]

Logic

The next bit might sound strange, increasing row to check column and increasing column to check row, it it works.

  • Check a column – Set row number to 1 (aka second digit in four digit length), then add 100 to the CelliD
  • Check a row – Set column number to 1 (aka first digit in four digit length), then add 1000 to the CelliD
  • Check a sub-grid box —–

***** at this point I just realised I might be better to change the order the CelliD to being [Cell],[Row],[Column],[Subgrid] or even just identifying each cell as just a [Row],[Column] and have a separate array to hold the cell reference that appears in each Subgrid.

OK, no code this time.. rewrite required..

Sudoku Solver – 1st Session

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.

Read more