And in C++?
06/08/2020
The comparison between VBA, Phyton, PHP or C remained in a procedural style. And if we ventured into the object oriented ?
Go let's change paradigm, attention it's bestial:
Zoo, in Oriented Object !
We could transcribe the code in C quasi directly in C++. After all, the methods of the objects are written in a procedural language. But it would be without interest and contrary to the philosophy of the object oriented. In OO, the approach necessarily leaves the procedural to go in the conceptual...
How does an OO developer see a sudoku grid ? Like that :
That is to say in the form of 9 regions, themselves composed of 9 values ; an embryo of fractal structure. We then define two classes:
- a class for the regions,
- a class for the grid of a sudoku.
The Region class
An instance of the Region class contains some private attributes:
- a grid of 3x3 values between 0 and 9
- a position of a current cell whose coordinates in line, column are memorized by two integers l and c.
And some trivial methods (that is to say whose names should suffice to evoke their functions), with a few exceptions near:
- next() passes the current cell to the next position and returns a boolean "true" if we reach the last cell or "false" otherwise,
- tests(v) checks if the value v is suitable for the current position,
- add(v) affects the value v to the current position and passes it to the next cell,
- dup() creates a copy of an instance,
- val(l,c) returns the value of the private grid in line l and column c (independently of the current cell).
The Grid class
The Grid class is barely more complex.
Its constructor starts by drawing up the list of all possible regions:
______#0 ______#1 1 2 3 4 5 6 7 8 9 ______#2 1 2 3 4 5 6 7 9 8 ______#3 1 2 3 4 5 6 8 7 9 ... ______#362879 9 8 7 6 5 4 3 1 2 ______#362880 9 8 7 6 5 4 3 2 1
There are only 9! (plus one for the empty region, a negligible quantity for the OO developer) whose number is memorized in the public attribute nbRegions and each possible case in the Regions table of pointers on instances of the Region class. It's the private method listRegions() that is charged to inform the list of possible regions.
Moreover, the Grid class contains some attributes and private methods:
- a table of 3x3 regions chosen each among the 362,881 possible regions,
- a grid of 9x9 values between 0 and 9 that correspond to the choice of the 9 regions, updated thanks to the private method inGrid(),
- the constraints to respect for the sudoku searched,
- a position of a current cell whose coordinates in line, column are memorized by two integers l and c.
The public methods of the Grid class do what their name expresses, valid(r) being the equivalent of tests(v) of the Region class.
The beauty of an OO code
Once this preliminary work performed, the search for a solution for a sudoku is spectacularly concise and readable:
The hidden horrors
The flip side of the decor is much less.
A considerable work
Even by contenting ourselves with the encapsulation of the OO approach (we leave aside the notions of inheritance and polymorphism), the 113 lines of code of the solution in C are replaced by 365 lines distributed in 5 files (region.h, region.cpp, grille.h, grille.cpp and sudoku.cpp).
A lamentable result
The very latest versions of Python, PHP and C++ not being available on the server used for the performance tests of the previous article, we redo them on a freshly installed server (Centos 8 in this case):
- 3 s in Python3,
- 1 s in PHP 7,
- 0,04 s in C,
- 45 s in C++ !
By the way, the first solution found in C++ is different from those found in the other languages:
2 1 4 3 6 5 8 9 7 3 5 6 7 8 9 1 4 2 7 8 9 1 4 2 3 5 6 4 9 5 2 1 7 6 3 8 8 2 7 9 3 6 4 1 5 1 6 3 8 5 4 7 2 9 6 7 2 4 9 1 5 8 3 5 3 1 6 2 8 9 7 4 9 4 8 5 7 3 2 6 1
Here's a very beautiful example for the law of Less :-)
Conclusion
We should especially not throw the baby out with the bathwater: to conclude that the object oriented approach would be ineffective would be a grave error !
Because here, in the particular case of the resolution of a sudoku, it is inappropriate. It's a too simple problem.
For other more complex situations, the object oriented approach brings a salvific vision, as suggested by the simplicity of the main code of resolution of a sudoku in C++.
Without forgetting that the programs designed for these tests are certainly improvable.
(Sources of the code examples on request)