mikemcbride / vue-sudoku

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

Optimize backtracking and guesses #10

Closed mikemcbride closed 4 years ago

mikemcbride commented 4 years ago

Closes #9

The approach outlined in #9 turned out to mostly result in significant performance improvements, which is not surprising. On rare occasions some puzzles end up taking significantly longer than they did using the previous approach, but this is likely due to situations where a particular incorrect guess early on leads you far down a path that results in nothing. That is the nature of this type of puzzle. In the majority of puzzles, this new approach is orders of magnitude faster. I tested with about a dozen puzzles of extremely high difficulty and 10/12 were much faster using this technique. Screenshots below of one of the puzzles showing the improvements:

Puzzle

image

Using old logic

image

Using new logic

image

You can see that this new logic typically results in significantly fewer calculations and much lower completion times.

vercel[bot] commented 4 years ago

This pull request is being automatically deployed with ZEIT Now (learn more). To see the status of your deployment, click below or on the icon next to each commit.

🔍 Inspect: https://zeit.co/mcbridem/vue-sudoku/8okcf6nig ✅ Preview: https://vue-sudoku-git-find-optimal-cell.mcbridem.now.sh