Backtracking – we left the classroom!

Taking advantage of the giant chess that is in the patio of the ESI, today's class has consisted of carrying out three activities on the board with the aim of illustrating and consolidating some basic notions about backtracking, which is the subject that we have begun to study this week in the subject of Programming Methodology.

This problem-solving technique is often presented, both in class and in reference manuals, with some basic examples set out on a chessboard. The best known is the one that consists of placing 8 queens on the board without threatening each other. Another typical example is that of traversing the squares of the board with the movements of a knight without going through it twice. But there is also a very intuitive example for them, which is trying to find the way out of a maze, which can also be represented by a chessboard.

Since the technique of backtracking makes a search in the space of all possible states, the number of moves that must be made to generate this space of states on a chessboard, 8 × 8 squares, is enormous. Therefore, we have “divided” the 8×8-cell board into four simpler 4×4-cell boards, which also allows 4 problems to be presented simultaneously.

Thus, the students have been divided into 4 groups, each of which has worked on a quadrant and on a different version of each of the three problems. In addition, each group has been provided with a sheet, which they have been completing while solving the problem, in which questions about basic concepts related to the backtracking.

Throughout the process, the role of Professor Carmen Lacave has been to help each group trying to resolve the doubts that arose or correcting some misconceptions. And, above all, thank them for their good disposition despite the cold and the amount of rain that has fallen while carrying out the activities. I hope that tomorrow, at the time that the other group has, the patio thermostat will be better regulated 😉