The solution of combinatorial problems using Boolean equations: New challenges for teaching

It will be shown that many finite combinatorial problems can be solved by using Boolean equations. Therefore, it is necessary to teach how to transform the different problems into this area in a correct way. We demonstrate the required modeling steps in the first part using very different interesting examples. It is no longer necessary to develop different solution methods for different tasks; Boolean equations can uniquely be used. Ternary vectors and ternary arrays are powerful data structures that help to extenuate the complexity. Naturally, problems of a reasonable size cannot be solved by hand, therefore existing software systems must be used. The application of such a software system can require a huge amount of details. We show how a simplified environment of the software supports the teaching process because the key issues can be explored on a reasonable level of abstraction. Both the XBOOLEMonitor and a SAT-solver will be used. It must be learned how to use these systems, i.e., the structure and the working of the systems must be well understood. It can, however, be that the complexity of the problem is beyond the size of the existing systems. Then we have the last level that requires an excellent knowledge of Mathematics and excellent programming skills. We take as an example the rectangle-free coloring of grids using four colors. The solution of these last problems of the highest level show that only the unified efforts of Mathematics and Computer Science can solve the problems of the highest complexity. It is possible to solve problems that could not be solved before in a constructive way. You do not only know whether solutions exist or not, it is possible to build a very large number of solutions or even all the solutions. Therefore, the education of Mathematicians, Computer Scientists and Engineers must take this necessary cooperation into consideration. To be a specialist in one of these areas is not enough!