TopDown Analyze Method with Tree Graphs as Support

• Download source code - 30.6 KB

Contents

1. Introduction
2. Background
   1. yEd The Diagram Editor
   2. Stepwise Refinement, Structured Programming, Top-Down Analyze Methods
3. Translation of typical structures to a tree
4. A Practical Case : The NQueens Puzzle
   1. Incremental analyze
   2. Translation to Code
5. Points of Interest
6. Links
7. 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.

• yWorks - The Diagramming Experts[^]
• yEd - Graph Editor[^]

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

• Eight queens puzzle - Wikipedia[^]

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

// NQueens Solver
#include <iostream>
using namespace std;

// Persistant Initialisation
const int BSize = 8;
int QPos[BSize + 1];

int IsFree(int Row) {
	for (int Index = 1; Index < Row; Index++) {
		// Check column
		if (QPos[Row] == QPos[Index])
			return 0;
		// Check diag /
		if (QPos[Row] == QPos[Index] + (Row - Index))
			return 0;
		// Check diag \
		if (QPos[Row] == QPos[Index] - (Row - Index))
			return 0;
	}
	return 1;
}

int NQ_Solver() {
	// Local Initialisation
	int Row = 1;
	QPos[Row] = 0;
	// BackTracking Search
	while (Row > 0) {
		if (QPos[Row] < BSize) {
			// Go Forward
			if (IsFree(Row)) {
				// Ok, Solution or Next Row
				if (Row < BSize) {
					Row++;
					QPos[Row] = 0;
				} else {
					//	Solution found, Abort
					return 1;
				}
			} else {
				// Next Column
				QPos[Row]++;
			}
		} else {
			// Go Backward
			Row--;
			QPos[Row]++;
		}
	}
	return 0;
}

int main() {
	cout << "NQueens Solver" << endl;
// Call Solver
	if (NQ_Solver()) {
		// Result
		for (int Index = 1; Index <= BSize; Index++) {
			cout << " " << QPos[Index] + 1;
		}
		cout << endl;
		// Board Solution
		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
  • yWorks - The Diagramming Experts[^]
  • yEd - Graph Editor[^]
• Methods
  • Program Development by Stepwise Refinement[^]
  • https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
  • https://en.wikipedia.org/wiki/Structured_programming[^]
• Edsger_W._Dijkstra
  • https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
  • https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]
  • Structured Programming.pdf[^]
• Nicklaus Wirth
  • Niklaus Wirth - Wikipedia[^]
• 8 Queens Puzzle
  • Eight queens puzzle - Wikipedia[^]
  • Backtracking - Wikipedia[^]
  • Introduction to Backtracking - Data Structure and Algorithm Tutorials - GeeksforGeeks[^]

History

• 11^th September, 2022: First draft
• 22^nd July, 2023: First publishing