search

mikemcbride / vue-sudoku

Sudoku solver written in Javascript
https://sudoku.mcbrides.us
MIT License
5 stars 1 forks source link

Explore performance improvements #7

Closed mikemcbride closed 4 years ago

mikemcbride commented 4 years ago

Might be a fun exercise to see if there are opportunities for improving performance. When I built this initially I was only focused on making the algorithm work to solve any sudoku puzzle. There are probably places we could optimize solving logic and also JS performance.

One idea that might speed things up is to make a “detour” path. When you solve a cell, rather than moving on to the next cell you could set up an array of cells to check that have potentially been solved due to your new value. This might be something like:

Get every unsolved cell in the current column
Get every unsolved cell in the current row
Get every unsolved cell in the current square 

Are any of these now solvable given the newly solved cell?

This could potentially lead to multiple nested detours, so I’m not entirely sure how that would get implemented. Might be similar to snapshots, where we just tack on a list of coordinates to a “detour” array and then check that cell. When the array is empty, you continue iterating through.

I think this would be worth exploring. I’d like to take some benchmarks beforehand on a few extremely difficult puzzles to see whether or not this helps, and by how much.

The other thing to look at is making sure we are doing everything as efficiently as possible from a data model perspective. We do a lot of accessing items by array indices, since our grid is a two dimensional array. I would like to explore alternative data structures that might be more well suited to handle this.

mikemcbride commented 4 years ago

I am playing around with this concept of taking detours during a pass and the results so far are promising. I’m seeing total calculations required to solve a puzzle going down by about 30%.

mikemcbride commented 4 years ago

In regards to the 2 dimensional array structure, I did some research and it seems like this is the approach most people are taking. It makes it very easy to access items at any location and move around the grid. I don’t think refactoring anything there will yield good results.

I am going to explore some things around ditching a nested for loop and flattening the grid before making each pass. I think this would allow two things:

First it may yield better performance, and second it would allow me to add the detour cells onto the end of the array as I’m looping through it. I’m not sure if the second one will yield good results so it will take some tinkering.