Minesweeper in PHP

Whilst my Sudoku solver is up to a basic level, I just need to implement so more logic to reduce possible values, I started to think about the game Minesweeper.  I’ve played it since it was in the Microsoft Entertainment Pack 1, which was installed in to Windows 3.

Minesweeper is another grid based game, the player has to find all the mines which are hidden.  The basic game is an 8×8 grid with 10 mines. The first reveal is never a mine, but will show either a blank grid or a number. If it’s a number, it means in the 8 surrounding cells, there are that many mines. If it’s blank, all the blocks around will be revealed until a number is shown, indicating there is a mine in a surrounding cell.  If you think a cell is a mine, you can mark so it can’t be clicked.

The game is over when the number of remaining cells are the same as the number of mines, whether they are marked or not.

I actually started to think about this while I was trying to work out better ways to handle the logic in the Sudoku solver.  I was thinking, how are the minesweeper grids generated. I read one site where it say when the grid is presented, on the first click, if it’s a mine, the mine is moved to another cell and the grid is recalculated. I started to think the other way around. Generate the grid AFTER the first click, eliminating that cell as a possible mine.  So it would be a case of creating an array with all the cell references, remove the click cell, randomise the remaining references and then trimming the array to the number of bombs.  So that’s where I started.

I started coding and was able to quickly generate the grid, values and the numbers to indicate the number of mines surrounding a cell.  I did have to think of a better way to identify the numbers on the grid, mainly because of the function to reveal blank cells could go out of the region by using a 2 digit identification number.  So the grid numbers are identified by 4 digits, starting from 1010.  This method might not have been the best, but it worked for me.

I had a rough idea how I wanted to handle what happens when a blank cell is clicked, but that’s what took me the most time. Given that the surrounding cells have to be checked, then those have to be checked as well if they are blank.

The code is commented and I’ve tried using variable names that make things obvious. I’ve still used the similar classes as Sudoku. An input handler and a grid generator.  It’s a basic interface, but the core game mechanics are there.

When you run it, you get to choose difficulty or specify a custom sized grid:

Then when you start the game, you are submitting values from a form over and over again.

Until the game is lost

Or won

Below is the code. I’ve tried to factor as best I could without going too far.  Let me know if you have any suggestions.

index.php

input_handler.php

grid_gen.php

 

Sudoku Solver v1

So 4 ‘sessions’ and I hit a snag. I then spend the next week working on code which solves most (non extremely difficult) puzzles.

And then I put the code aside.

A few things I learn’t along the way..

  1. It’s great to have a goal, but instead of stepping up to the plate and going for broke, plan a little.
  2. Remember to break it down in to multiple steps and then break those down even more.
  3. By following 2, it’s easier to go back and fix small parts of the code as opposed to rewriting the entirety.

In saying that, I still didn’t fully apply these lessons learned when completing version 1. I just realised them more after I had completed it.

What I’ve got now is code which will allow you to enter a puzzle, then using a few ‘solving’ selections, will start to fill out the form.

If you have read any content from the last 4 posts, especially the ending of the last one, you will see I was questioning the naming scheme of the cells.

I decided to simplify it to [row][column].

The only reason I was thinking of using a ‘subgrid’ in the naming scheme was to generate arrays which had the cells located in a respective ‘subgrid’. In the final version of the code, I hard coded the values in to the array. I applied the thought method of WORM (Write Once, Read Many).  I had issues with where the arrays were being generated because that information was read from more than one function.

The solving method.

Stepping through the puzzle:

  1. Work out all possible values for each cell.  Mark submitted values as solved.
  2. Start at 11 (first cell) and step through each cell, using the check conditions below. Repeat from 11 until either puzzle is solved or no cells after solved in a pass.

What I’m checking in each cell

  1. If only 1 possible value, set as solved value.
  2. If any value is unique in row.
  3. If any value is unique in column.
  4. If any value is unique in subgrid.

After each step I perform a clean up of possible values but removing the value from all cells in the row, column and subgrid.

Applying that logic, most puzzles can be solved.

Solving harder puzzles is where I’m at at the moment. Another step needs to be added when the puzzle isn’t solved and after passing the puzzle, 0 values are solved.

I’ve played a number of puzzles in a Sudoku app I have on my phone and I’ve documented, the best way I can describe it is ‘Worded Logic’ for what I need to check. So far I have this:

  1. Applying to each Row and Column – If 1-3 possible values are ONLY in one row/column of a subgrid, remove values from respective row/column in other subgrids.
  2. Where multiple cells in a row/column/subgrid have same possible numbers, and the count of those possible numbers = the number cells they appear in, remove possible numbers from other cells in that row/column/subgrid

There are additional checks which I need to work out how to word up, but I’ve been able to solve all but one (manually), using the steps above.

Presentation

Currently, as I mentioned above, the solver is just generating a grid to display values/current state of the puzzle, and a basic output ‘Solving [cell] – [how it was solved]’.

Going forward, I’m going to have a ‘solve this’ button, and then an ‘analyse’ which will only solve one number at a time, which a check box to do one full pass.

After starting my solver, I did find one online which does the same thing, but to me, it’s more about working through to the solution.. even if there is already one available..

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 moreSudoku Solver – 1st Session