Sudoku-Master

Sudoku-Master is a program that can solve Sudoku grids using human and logical techniques. It is written in TypeScript so that it can be easily integrated in other applications as a library, either on the server side with Node.js or on the client side using web browsers or native applications (Electron, React Native or any other framework powered by JavaScript). It is designed to comply with the functional programming principles, in order to avoid mutating data or cause any side-effects.

Features

• Parses a string representation of a grid into the program.
• Serializes a grid from the program into a string representation.
• Determines whether the digits in a grid are valid according to the constraints of the game.
• Fills every empty cells with their candidates.
• Solves a grid using a backtracking algorithm:
  • Depth-first search algorithm.
• Indicates the cells that can be solved:
  • Full House
  • Last Digit
  • Naked Single
  • Hidden Single
• Indicates the candidates that can be eliminated:
  • Intersections:
    • Locked Candidates (Pointing and Claiming)
    • Locked Pair and Locked Triple
    • Almost Locked Candidates
  • Subsets:
    • Naked Subset (Pair, Triple and Quadruple)
    • Hidden Subset (Pair, Triple and Quadruple)
  • Fish:
    • Basic Fish (X-Wing, Swordfish and Jellyfish)
    • Finned Fish
    • Sashimi Fish
    • etc.
  • Coloring
  • Chains and Loops
  • Wings (XY-Wing, XYZ-Wing, WXYZ-Wing and W-Wing)
  • etc.

Functional programming

This program is used as a sandbox to try functional programming (FP) in TypeScript.

What is it?

FP is a programming paradigm in which the flow of the program is passed into pure functions instead of relying on objects like in object-oriented programming (OOP, which is a paradigm opposed to FP). The main motivation is to make the code easier to understand, more predictable, and well tested. In order to satisfy these goals, FP defines some concepts to eliminate any possible side effects.

How does it work?

FP relies on several concepts that aim to enforce building a software by describing what to do, using a structure and elements that expresses the logic of a computation, instead of how to do it with algorithms detailing explicitly every step. It is said to be declarative because it abstracts the flow control (how things are done) to focus on the data flow.

1. The first and probably most important elements are the pure functions. A pure function returns always the same result for the data that was pased to it as arguments, it doesn't rely on data outside of its scope and it doesn't change the state of any variable or mutable references (objects and arrays). These properties make it really to use unit testing with these functions, and ensure the caller that it will always get the right result no matter what happend before and the current state of the program.

   // This is an impure function:
   let size = 0;
   function incrementSize(inc) {
     size += inc;
   }
   // This is the proper way to do it with a pure function:
   function add(x, y) {
     return x + y;
   }

2. Speaking of state, it is important for the program to avoid changing the value of its variables and for its data to be immutable (their state cannot be modified after being created). To ensure that, every variable must be declared as constant and all the mutable data (objects and arrays for instance) need to be readonly. Moreover, the state must stay in its local context and never be shared to other parts of the program.

   // This variable is not constant and can change unexpectedly
   let size: number = 0;
   // This is a constant so we know that it will keep the same state
   const size: number = 0;
   // The data in this array and object can easily be modified when it is passed into a function
   const primeNumbers: number[] = [2, 3, 5, 7, 11];
   const options: { isMutable: boolean } = { isMutable: true };
   // With TypeScript it is possible to ensure that their data never change
   const primeNumbers: readonly number[] = [2, 3, 5, 7, 11];
   const options: { readonly isMutable: boolean } = { isMutable: false };

3. The compiler must reject every possible false positive errors. In JavaScript, this is done with the use of a typing mechanism like TypeScript (which is used in this project).
4. Another difference of FP is the use of expressions instead of statements. A statement is an element in the program that is executed and that does not return a result (e.g. assigning a value to a variable, checking a condition with an if or a switch, repeating an action inside a for or a while loop); whereas an expression is an element that is evaluated to determine a value that it must return to the caller (using only constants, functions and operators). Therefore, in FP, we need to use specific functions to replace statements (e.g. we can loop through an array with map, use filter to reject some of the elements, apply reduce to aggregate some results, etc.).

   // These are example of statemens:
   const evenNumbersDoubled = [];
   for (let i = 0; i < 10; i++) {
     // Loop
     let result = i;
     if (i % 2 === 0) {
       // Condition
       result = result * 2; // Variable assignement
       evenNumbers.push(result); // Data mutation
     }
   }
   // Instead we must use expressions:
   const evenNumbersDoubled = Array(10)
     .keys()
     .filter((i) => i % 2 === 0)
     .map((i) => i * 2);

5. Function composition is a mechanism that combines several simple general functions into a more specialized complicated one.

   // Composition of functions (evaluates functions from right to left in the argument list)
   function compose(f1, f2) {
     return function (x) {
       return f1(f2(x));
     };
   }
   // Describe simple general functions
   function divideBy2(x) {
     return x / 2;
   }
   function isEven(x) {
     return x % 2 === 0;
   }
   // Compose a specific function
   const isDivisionEven = compose(
     isEven, // This is executed last
     divideBy2, // This is executed first
   );
   isDivisionEven(4); // Equivalent to isEven(divideBy2(4)) => divideBy2(4) = 2 => isEven(2) => true
   // => true
   isDivisionEven(10); // Equivalent to isEven(divideBy2(10)) => divideBy2(10) = 5 => isEven(5) => false
   // => false

6. Other rules apply for FP, like currying or monads, but the one listed above are the most important to begin with.

In this project we ensure to comply with these rules as much as possible with the use of some external libraries:

1. TypeScript is used to avoid making typing errors.
2. eslint-plugin-functional is a set of rules that analyzes the code in order to detect violations of FP principles, these rules can be categorized like this: no mutation, no object-orientation, no statements, no exceptions and require currying.
3. ramda is a library that allows to evaluate data without the use of statements or mutations, in a pure functional approach. The remeda library is quite similar but with a focus on performance through lazy evaluation (that is not supported by ramda yet).

Why bothering with this?

FP is difficult to learn for a beginner as the declarative approach is quite the opposite from what we learn with imperative programs (like in OOP). Moreover, FP does not make a program more performant, it is probably the opposite as it is better to use standard (imperative) mechanisms in order to optimise every step of the program. Also, the constraints of FP also makes it often harder to describe the logic using a chain of general expressions rather than simply detailing each step with straightforward statements.

So why using FP for this project?

FP is growing in popularity as we can see with the usage of the Redux library that allows to manage the state of web applications in a FP style (without doing mutations). Its goals are to behave consistently and to be easy to test. In fact, a lot of softwares are using some of the FP principles to avoid some flaws encountered with other approaches:

• Difficulty to spot an error when it is caused by an unpredictable side effect, that can sometime be hidden deeper in the control flow.
• Using data that is shared among several parts of the systems, all of which being able to modify it in parallel.
• The increasing use of mocks, stubs, spies, dummies and other isolation mechanisms in unit frameworks for systems that are too dependent on the state of other parts of the program.
• etc.

This project is using FP in order to avoid these errors but most importantly it is a sandbox to evaluate the feasbility of building a software with complex pattern-recognition logics with all of these constraints, and to understand the advantages and limitations.

License

MIT