sudoku-master
v0.0.3
Published
A utility that analyzes a Sudoku grid and gives hints on how to solve it.
Downloads
7
Readme
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
- [x] Parses a string representation of a grid into the program.
- [x] Serializes a grid from the program into a string representation.
- [x] Determines whether the digits in a grid are valid according to the constraints of the game.
- [x] Fills every empty cells with their candidates.
- [x] Solves a grid using a backtracking algorithm:
- [x] Indicates the cells that can be solved:
- [x] Full House
- [x] Last Digit
- [x] Naked Single
- [x] Hidden Single
- [ ] Indicates the candidates that can be eliminated:
- [ ] Intersections:
- [x] Locked Candidates (Pointing and Claiming)
- [x] Locked Pair and Locked Triple
- [ ] Almost Locked Candidates
- [x] Subsets:
- [x] Naked Subset (Pair, Triple and Quadruple)
- [x] Hidden Subset (Pair, Triple and Quadruple)
- [ ] Fish:
- [x] 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.
- [ ] Intersections:
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.
- 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; }
- 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 };
- 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).
- 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 aswitch
, repeating an action inside afor
or awhile
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 withmap
, usefilter
to reject some of the elements, applyreduce
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);
- 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
- 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:
TypeScript
is used to avoid making typing errors.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.ramda
is a library that allows to evaluate data without the use of statements or mutations, in a pure functional approach. Theremeda
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.