Backtracking Algorithms & The Sudoku Game

Backtracking Algorithms & The Sudoku Game

If you just want to play the Sudoku game, it’s available here: sudoku.ivaylopavlov.com

I was wondering what game to make next using ReactJS to solidify my knowledge with the framework.
The choice was between a Minesweeper clone or a Sudoku game. The reason I narrowed it down to these two games, was because of their playing grid generation properties. If you’ve never played Sudoku, the rules are: You have a 9×9 grid, filled with numbers between 1-9 and each number in each each row, column and subgrid of 3×3 is unique. Some boxes are empty and you need to fill them in correctly. With Minesweeper, you again get a random size grid, you have the mines and the boxes with digits telling you how many mines are around the box with a digit. Mathematically, both are pretty pretty similar. I went with Sudoku, as it would be faster to code. Generating and solving either of the two games at runtime is an example use of a Backtracking Algorithm.

What is a Backtracking Algorithm?

It’s a general algorithm that is intended to solve a constrained problem by creating a solution step iteratively and backtracks (takes a step back), the moment a solution is not feasible, after the last iteration backs it into a corner. The full definition is here.

So how do we structure the Sudoku game, as a backtracking algorithm problem? 
1) The grid size 9×9, tell us there is a finite amount of possibilities.
2) The requirement for unique number by box, row & column is the constraint.
3) Our iteration logic is with each placed number, less possibilities remain for the rest of the boxes in the grid.

Algorithmic Complexity & Logic

What is the Big-O notation for a game like Sudoku?. It’s O(n^m), where n is the count of possible value – 9, and m is the number of empty boxes. Therefore, a completely empty grid would be 981. To give a perspective of how huge. This is 932 = 3,433,683,820,292,512,484,657,849,089,281. Now imagine 981, which is a 1.9662705047555291361807590852691e+77. That’s pushing the floating point 77 digits. So the short story, it’s enourmous. Who knew a newspaper puzzle would be an intersting algorithmic problem for computer science.

What we observe from a simple filled out game is that the numbers in the boxes 1,5 and 9 don’t have any overlap vertically or horizontally. So we can fill in these boxes in any way without any reprecussions forward. So we reduced the issue now to 954. However, as each box is filled, the complexity reduces exponentially as well. So this 9 is a not correct outside of BigO notation terms. The actual total grid possibilities are 9! × 722 × 27 ×27,704,267,971. The last problem to mention before explaining the algorithm is the sudoku difficulty. It’s very difficult to measure and it’s not just based on the number of empty cells provided. We are going to ignore it for now.

The Solution Logic is as follows:
1) Fill in Boxes 1,5,9 in with the digits 1-9 in any random order.
2) Scan the entire grid and check for all possible values for each cell.
3) If there is a cell with only 1 possible value, fill it in.
4) If there is no such cell, pick the one with least possible values and pick one of the numbers at random.
5) If a cell is reached where there are no possible numbers to satisfy the uniqueness constraint, delete the last populated value and try the other possible number, go to the next cell.
6) If it still doesn’t work, go back 2 cells back.
7) Repeat until you have a complete grid.

As you can imagine this process is expensive, so many of the Sudoku games in the app store have the grid ready and just hide numbers, rather than calculate at runtime. They do this because of the requirement of difficulty, as with this you cannot have a difficulty gurantee of the output grid.

The Game Interface

Used the Peg Solitaire Language Design I came up with, to speed up development. What I re-learned, if you wish, is the tought balancing act between Mobile & Desktop view. Doing both equally well is tremenedously difficult. An example, in the game on mobile, I wanted the keypad to pop up, not the full keyboard. Then I wanted the grid to be positioned in such a way, that when clicking on a text field, doesn’t zoom in the web page on iOS and Android, etc. These tiny details can eat so much of your time. Yet, make for a better experience overall. Rendering the grid was the core of the entire game, which was simple & straightforward:

ReactJS and TypeScript

My first ReactJS project was with ES6, my first Angular Project was TypeScript, so I decided to not try VueJS, but combine TypeScript and ReactJS. I found this actually an impediment, rather than facilitation when coding. Because you need to iterate. For example, I want to pass a new property to a newly created component, I immediately get an error I need to edit the interface for the component, otherwise I cannot proceed, when you are unsure of which design works best, this back-and-forth becomes really consuming. It’s like editing in C++, the CPP definition, the Header file and the Interface Header for the Google Mock tests. Unless you have 100% ironed out design at the start, it becomes very annoying. Then there are the “const” and “let” rules. You create a variable, but not sure if you’ll modify it later yet, without making it const, you can’t compile. Then you edit and have to go back to make it “let”. In ES6, you just add the propTypes in an object in the end. Looking back on my opinion on propTypes when I built the Peg Solitaire Game, I was unfair. Definitely, it still feels like it will be better in a definition-like file, but the strictness of a TypeScript compiler for a language like JavaScript that’s meant for fast iteration can become an annoyance. I can imagine it paying off in maintaing a much larger project. Also, setting up a workable tsconfig.json file is another time sink. You are better off copying one from a popular project on GitHub, than do your own trial-and-error settings.

NPM & Vulnerabilities

What I discovered is also the pain of NPM package updates. There are vulnerabilities in a package, use npm audit fix to fix it. However, some of them contain breaking changes, so once you do it, your compilation fails and you go down a different path. It took me 2 weeks to build the entire Sudoku game and on the day of doing the build, it already had 1 package with 1 vulnerability I needed to update, thankfully backwards compatible. This is plain ridiculous, from maintainability stand point. I’ve learned that quite a few of the very popular frameworks – like Material UI and ReactJS, Angular as well, go through the route of breaking changes frequently. I don’t have time to re-write my Tetris game every year, just to fix a bug here and there and keep it secure. This is just a symptom of a much deeper problem with the Node Package Manager, but that’s for a different post.

Bonus: Cheeky JavaScript Discoveries

How do you deep copy an array when array.slice() doesn’t work?

Shortest way to compare if two arrays are identical?

Cleverest way to check if all values in an array are unique?

One thought on “Backtracking Algorithms & The Sudoku Game

  1. Nice article Ivo. I like the idea of filling in box 1, 5, 9 randomly first because they are independent of each other.

Leave a Reply