Guided: Build a Sudoku Solver in TypeScript

Sudoku is a fascinating game of skill and concentration enjoyed by people all around the world. Anyone who has solved a Sudoku puzzle knows the satisfying and rewarding feeling obtained when solving one of these simple yet ingenious puzzles.

In this lab you will build an automated Sudoku solver which can produce the solution to easy-level puzzles nearly instantaneously. Throughout, you'll learn about efficient data processing, Typescript interfaces, and you might become a better Sudoku player as well!

Before you begin parsing the files containing Sudoku data, it can be helpful both to understanding the problem, and to building a maintainable and scalable code base, to define types.

In TypeScript, type definitions provide the IDE (integrated development enviornment) and compiler with information on how variables you define should interact with one another.

Each square of a Sudoku board can have a value of 1-9, or currently have no value. For squares that do not yet have a value, 0 is typically used. While we could represent the type of the value as a number or a string, neither is very precise, as both numbers and strings can have any number of possible values, but a Sudoku value can only have one of ten. A Sudoku puzzle contains 81 squares, arranged in a 9x9 grid. You'll start by creating a type for a sudoku square.

Each square has the following properties:

1. A possible definite value, which is set when we are sure we know what the square contains. It's a SudokuValue.
2. A map of possible values, which is a Object where each key can be a SodukuValue, and each value either true or false
3. An X coordinate
4. A Y coordinate

The X/Y coordinate may seem like just a number, but since it can only really be an integer between 0-8, you can create a custom type for that as well. Great work!

You may now optionally create Type Defintions for

1. SudokuPuzzle, which is simply an array of SudokuSquares
2. SudokuUnit, which refers to a row or column, and is also an array of SudokuSquares.

If you do not wish to create these additional types, use the any when we refer to them later on in this code lab.

Real-world programming tasks often require loading data and parsing it correctly. This makes sense, as data is often considered an organization's most important asset. Therefore, you'll next implement a function which can load a text file from any specified location in the project directory.

Now that our Sudoku data is formatted as an array of Sudoku Squares, we can solve any simple puzzle.

A SudokuUnit is one group of 9 SudokuSquares which can contain each number from 1-9 exactly once. In other words, each row, each column, and some 9x9 squares are Sudoku Units. In total, there are 27.

We now have all the information we need to solve any Easy difficulty Sudoku puzzle.

We know that within a given unit, the numbers 1-9 can only each appear once.

Therefore, we can solve a Sudoku Puzzle iteratively with the following algorithm:

• For a given unit,
  • Note all the definiteValues that are in this unit
  • All these values may be removed from the possibleValues of each square in the unit
  • If a square has only one possibleValue, that value may be set as the square's definite value.

Squares can hold information about interactions with different Sudoku Units, as the possibleValues properties persists between iterations.

You can now use your algorithm to solve any Easy Sudoku Puzzle.

Of course, using a computer algorithm to process data is much faster and more efficient than doing it yourself.

This concept is at the heart of "processing data at scale."

The puzzles directory contains three puzzles -

1.txt
2.txt
3.txt

For the final task, you'll create a method that solves all three. Congratulations on completing this lab!

In this lab, you learned the following things:

• Writing TypeScript applications
• Creating TypeScript type definitions, including union types
• Loading text files with the fs module
• Algorithms for solving Sudoku puzzles

In summary, the programmatic nature of solving Sudoku puzzles make it easy and rewarding to solve these puzzles using computer code. Doing so also gives you a better understanding of the processes that go on in your own brain while solving these callenging puzzles.