Sudoku (数独), which means “single number” in Japanese, is a well-known and popular game that was invented in 1986, 2004, or 1892 depending upon how one thinks of it. It can be played on paper, or electronically. Classic Sudoku uses a grid consisting of 9 subgrids containing 9 cells each. This is considered “rank 3” because if we denote the rank as variable “n” then the numbers used to fill the grid in are 1, 2, 3,…,n2 or for rank 3, the numbers in the set {1,2,3,4,5,6,7,8,9}. To solve a puzzle, all cells must fulfill the “one-rule,” meaning that in any given row, column, or subgrid, each of the symbols in the set is only repeated once. In order to explore some of the mathematical aspects of the game, which I suspected was some sort of matrix, I looked over The Math Behind Sudoku: Introduction to Sudoku. As it turns out, the only math that applies is “Group Theory,” since no algebra, calculus, or even arithmetic, is needed to solve a puzzle. In fact, it is possible to substitute numbers with any set of symbols and still play the game as before.
I was first introduced to the game last year, and played it with pencil and paper. I found out that pen was not a good idea and bought a few big fat erasers. At first I started with mostly intuitive logical inference (always complying with the “one-rule”), and did a bit of guessing and back-tracking, but this quickly grew tedious, especially on physical paper. With anything harder than “easy” puzzles, I started using “pencil marking,” one of the first strategies than can be used. This was more effective, but still rather tedious, again, especially with pencil & paper. I won’t go into more elaborate strategies that are usually needed to solve medium & up puzzles; suffice it to say that I began to wish I could do pencil marking electronically. There are many sites / applications that provide this. When I thought about it, I realized a computer is well-suited to tracking one-rule candidates in a neighborhood (row, column, and subgrid) automatically, and I wanted to write my own application to do this. My current version does, and also enables the user to override the generated marks either additively, or subtractively. I arrived at the current version in stages.
At first I only wanted to generate the grid in HTML. The use of the <table> element is generally discouraged as a layout mechanism in modern webpages, but if there ever was an idiomatic use-case for them, it seems to be matrices and spreadsheets. Instead of churning out static HTML, I had Vanilla Javascript generate the table. Next I needed some data. I considered scraping it off of the myriad of online games, or even trying to OCR the PDFs that were available for printing. I was pleased to find this generator on github: SudokuGen: A fast sudoku puzzle generator.. It provides both puzzle and solution in 4 difficulty levels, and is quite fast, enough to generate on the fly in the front-end. Considering the topic of “rank,” I remembered there are puzzles of rank 2 (mostly for kids), and 4 (kinda crazy, takes hours, and won’t display well on phones, etc,..). In lieu of procuring full generators for these ranks, I found a little bit of puzzle & solution here and here.
Now it was time to develop the user interface and underlying logic. I worked on some projects last year in VueJS Options API, and appreciated the built-in decoupling of components, event handling, reusability, and reactivity. In some ways the design pattern seems to be object-oriented. This time I wanted to try the Composition API since it is considered more powerful, especially for Single-File Applications (SFAs). A further discussion of differences between the 2 API styles is here. My implementation breaks the game down into the following components and views:
- App: the main page which also contains a Help text dialog
- GameView: the next major component in the hierarchy which contains everything else
- Keypad: a set of stylized buttons which replace any keyboard in Mobile
- Controls: a form with fields for loading new puzzles, and in non-mobile, toggling game states which is provided by Keypad in mobile (more on these states later)
- GridCell: this component has the most instances, handles input on cells, and displays givens, guesses, and pencil-marks. Since my app supports keyboard shortcuts in non-mobile, it also listens for key events, such as <esc>, <enter>, and arrow keys.
Aside from the VueJS components, there is a Vanilla-JS module which defines how the data for each GridCell is managed and stored:
export class CellData
{
row; // row,col provided as 1-indexed, but arrays here are 0-indexed
col;
#subgrid_index; // like cells, indexed row-major top2bottom, left2right
grid_size; // used to initialize Marks array?
#rank // used to calc subgrid_index
result; // given, "guessed", or empty
answer; // correct answer (solution), not important if is_given
is_given; // indicates a "read-only" state for result
marks; // CellData only initializes this, otherwise interface to it is "pass-thru"
static getSubInd( ind, rank)
{
// returns 0-based index
return Math.floor( ( ind - 1) / rank);
}
constructor( { row, col, is_given, rank, answer, result=-1})
{
this.row = row;
this.col = col;
this.is_given = is_given;
this.#rank = rank;
this.grid_size = rank * rank;
// 1-indexed, like row, col in range(1,grid_size)
this.#subgrid_index = CellData.getSubInd( row, rank)
* rank + 1
+ CellData.getSubInd( col, rank);
this.answer = answer;
this.result = result; // `-1` indicates `empty` value
this.marks = new Marks();
}
updateResult( result)
{
if( this.is_given)
return false;
this.result = result;
return true;
}
}
I may transition much of the Javascript code to Typescript since it seems to be the direction many projects are going these days, and I appreciate its type-hints and many other Object-Oriented features.
Solve Singles
After implementing “Auto Marks” level, “one-rule,” which generates pencil marks based on remaining candidates for all cells, I found that especially with easy puzzles, one or more cells would only have one pencil mark available. Rather than go through and set each cell to that mark manually, I added the ability to accomplish this with all cells where it applies in one shot by clicking an icon. Sometimes this will set off a cascade where more cells will have single candidates repeatedly until in some cases, the puzzle “solves itself” after a few clicks. With anything above about “medium” difficulty, this won’t happen, and the user will still need to employ other strategies, such as naked and hidden pairs, triples, etc,.. to solve the puzzle.
