In this article, I use Tree Graphs as Support to the Top-Down Analyze method.
Contents
- Introduction
- Background
- yEd The Diagram Editor
- Stepwise Refinement, Structured Programming, Top-Down Analyze Methods
- Translation of typical structures to a tree
- A Practical Case : The NQueens Puzzle
- Incremental analyze
- Translation to Code
- Points of Interest
- Links
- History
Introduction
I am using Tree Graphs as helper with the Top-Down analyze method. Because the sheet of paper is never large enough. Here is how I do it.
Background
yEd The Diagram Editor
yEd is a freeware Graph Editor made by yWorks. yWorks is a company working around a library allowing easy integration of Graphs in tier applications.
yEd exists in two flavors, a Java app or a Live version on your browser.
The main reason I use yEd is the neat feature of Auto-Layout. Every time I make a change in tree, 1 click and the tree is rebuilt according to settings.
Stepwise Refinement, Structured Programming, Top-Down Analyze Methods
Three names for more or less a similar paradigm and the same result: a guideline to translate algorithms to structured programs, and also to help define the algorithm itself.
- Stepwise Refinement is a general purpose not aimed at programming
- Structured Programming by Edsger W. Dijkstra and overs
- Top-Down Analyze Method by Nicklaus Wirth
I am not sticking to one of those methods, but using a mix of the three.
Translation of Typical Structures to a Tree
A programmatic flowchart sticks to a translation of source code into a 2D graph, the problem is that it is of no help to define an algorithm.
With those analyze methods, we start at the level of general idea and then stepwise refinement is done, the tree helps to visualize the algorithm solution at different levels.
The general principle is to start from a single complex problem and to split into a few simpler problems and refine until each small problem is simple enough, so that you can code it without further explanation.
| Elements | Figures |
Bloc
Rectangle |  |
Condition
Diamond |  |
Loop
Rectangle with Round Edges |  |
| Patterns | Tree Translation |
Sequence
Seq A
Seq B |  |
Selection
if Cond A is true
Seq A
end if |  |
Selection
if Cond A is true
Seq A
else
Default Seq
end if |  |
Selection
if Cond A is true
Seq A
else if Cond B is true
Seq B
else
Default Seq
end if |  |
repetition
while Cond A is true
Seq A
end while |  |
repetition
do
Seq A
while Cond A is true |  |
repetition
do
Seq A
until Cond A is true |  |
Feel free to use any shape and pattern to fit your needs, but you will need to explain those if you share the trees.
| Patterns | Tree Translation |
| For Next |  |
Start
while End condition
Seq A
Step
end while |  |
Counter= Start
while Counter <= End
Seq A
Counter= Counter+ Step
end while |  |
You stop going into details when you have enough to translate to code.
A Practical Case: The NQueens Puzzle
The goal is to place 8 Queens on a board of same size. Same problem can be solved with different board sizes.
Solving by hand. Just the great lines of the method.
- If board is filled, it is a solution.
- For a new row, search first possible queen position. And go to the next row.
- For existing queen, search next possible position. And go to the next row.
- When there is no more possible position on row, go back to previous row and move the queen.
The name of the method is backtracking.
Incremental Analyze
I will use a backtracking version of the solving algorithm. Basically, the solving algorithm looks for all solutions, I will stop it after the first solution is found.
| Comments | Tree Translation |
N Queens Solver
Need Size of board
Need to store position of each queen
Position of Queens is the result |  |
I choose a non recursive backtracking algorithm. It is a large loop with two parts inside, a loop forward, and the backsticking part.
| Pattern | Tree Translation |
While Search non Finished
Go Forward
Go Backtrack
End While |  |
| Comments | Tree Translation |
Need to keep track of actual Row
if column is on board then try it, else backtrack |  |
To go forward
if position is free,
next Row and column 0,
else next column To go backward
Prev Row
Next column |  |
And now, just have to check if a given cell if free or locked.
| Comments | Tree Translation |
Position is free if
no queen locks the cell
on vertical or diagonals |  |
| And finally |  |
Translation to Code
#include <iostream>
using namespace std;
const int BSize = 8;
int QPos[BSize + 1];
int IsFree(int Row) {
for (int Index = 1; Index < Row; Index++) {
if (QPos[Row] == QPos[Index])
return 0;
if (QPos[Row] == QPos[Index] + (Row - Index))
return 0;
return 0;
}
return 1;
}
int NQ_Solver() {
int Row = 1;
QPos[Row] = 0;
while (Row > 0) {
if (QPos[Row] < BSize) {
if (IsFree(Row)) {
if (Row < BSize) {
Row++;
QPos[Row] = 0;
} else {
return 1;
}
} else {
QPos[Row]++;
}
} else {
Row--;
QPos[Row]++;
}
}
return 0;
}
int main() {
cout << "NQueens Solver" << endl;
if (NQ_Solver()) {
for (int Index = 1; Index <= BSize; Index++) {
cout << " " << QPos[Index] + 1;
}
cout << endl;
for (int Index = 0; Index < BSize; Index++) {
for (int Col = 0; Col < BSize; Col++) {
if (QPos[Col + 1] == Index) {
cout << " *";
} else {
cout << " .";
}
}
cout << endl;
}
cout << endl;
}
cout << "fini" << endl;
return 0;
}
NQueens.cpp in TopDown.zip.
Result
NQueens Solver
1 5 8 6 3 7 2 4
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
. . . . . * . .
. . * . . . . .
fini
Points of Interest
When creating an algorithm, building a tree graph helps me a lot to visualize the idea, but the operation is tedious as the tree shape changes with every addition.
The main interest over flowcharts is that we don't have to stick to programming language syntax, instead this approach organizes a high level description of the algorithm.
The auto-layout feature of yEd eases the tree creation process.
Links
- yED
- Methods
- Edsger_W._Dijkstra
- Nicklaus Wirth
- 8 Queens Puzzle
History
- 11th September, 2022: First draft
- 22nd July, 2023: First publishing
