Rewriting a program without using goto statements

Question

I had to program a similar problem using goto statements. Now we are asked to rewrite our code without using goto statement. I don't know how to begin doing this program. I paste in the previous program code using the goto.

// Eight Queens problem using one dimesional array and goto statement

#include "stdafx.h"
#include <iostream>
using namespace std;


int main()
{
    int q[8];
    q[0] = 0;
    int c = 0;
    int count = 0;

NC: //cout  << "Next column\n" << "Column = " << c << endl;
    c++;
    if (c == 8) goto print;
    q[c] = -1;

NR: //cout << "Next row\n" << "Row = " << q[c] << "\nColumn = " << c << endl;
    q[c]++;
    if (q[c] == 8) goto backtrack; 
    for(int i = 0; i < c; i++){
        if(q[i] == q[c] || abs(q[c] - q[i]) == (c - i))
            goto NR;
    }
    goto NC;

backtrack:
    //cout << "Backtrack" << endl;
    //cout <<"Column = " << c << endl;
    c--;
    if(c == -1) return 0;
    goto NR;

print:
    //cout << "print" << endl;
    ++count;
    cout << count << endl;
    for(int i = 0; i <= 7; i++){
            cout << q[i];
    }
    cout << endl;
    goto backtrack;


    return 0;
}

This program is a hint the professor posted for the class to use.

 #include <iostream>
    #include<cstdlib>
    #include <cmath>
    using namespace std;

    bool ok(int q[], int col){
    if the configuration is “bad” return false;
    else
    return true;
    }

    void backtrack(int &col){
    col--;
    if(col==-1) exit(1);
    }

    void print(int q[]){
    static int count =0;
    print the array q
    }

    int main(){
    int q[8]; q[0]=0;
    int c=1;
    // from_backtrack keeps track if we need to reset the row to the
    // top of the current colum or not.

    bool from_backtrack=false;
    // The outer loop keeps looking for solutions
    // The program terminates from function backtrack
    // when we are forced to backtack into column -1
    while(1){
    while(c<8){ //this loop goes across columns
    // if we just returned from backtrack, use current value of row
    // otherwise get ready to start at the top of this column
    if(!from_backtrack) // we did not just return from backtrack
    Code goes here
    from_backtrack=false;
    while(q[c]<8){ // place queen in this column
    q[c]++;
    // if row=8, there is no valid square in this column
    // so backtrack and continue the loop in the previous column
    Code goes here
    //if this position is ok, place the queen
    // and move on (break) to the next column,
    // otherwise keep looking in this column
    Code goes here
    }
    c++; // placed ok, move to the next column
    }
    // one complete solution found, print it.
    print(q); // board completed, print it out
    backtrack(c);
    from_backtrack=true;
    }
    }

And this is an attempted I've made to completed the program

// NoGoto.cpp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;



bool attack(int q[], int col){
    if(q[i] == q[c] || abs(q[c] - q[i]) == (c - i)) return false;
    else
        return true;
} // Attack

void backtrack(int & col){
    col--;
    if(col == -1) exit(1);
} // Backtrack

void print(int q[]){
    static int count = 0;
    ++count;
    cout << count << endl;
    for(int i = 0; i < 8; i++)
        cout << q[i];
    cout << endl;
}
int main()
{
    int q[8];
    q[0] = 0;
    int c = 1;

    bool from_backtrack = false;

    while(1){
        while(c < 8){ // this loops across columns

            if(!from_backtrack)
                attack(q[c],c)

            from_backtrack = false;

            while(q[c] < 8){ // place queen in this column
                q[c]++;

    return 0;
}

"I'm having problem writing the code. How [can I] call each function to make it correctly find the solutions?"

Answer 1

First, just look at the control flow by stripping everything else and adding explicit gotos for execution that reaches a label by straight-line execution.

NC: if (…) goto print;
    goto NR;

NR: if (…) goto backtrack;
    if (…) goto NR;
    goto NC;

backtrack:
    if (…) return;
    goto NR;

print:
    goto backtrack;

Now, take the unconditional gotos and try to move the blocks so they represent straight-line execution.

NR: if (…) goto backtrack;
    if (…) goto NR;
    goto NC;

NC: if (…) goto print;
    goto NR;

print:
    goto backtrack;

backtrack:
    if (…) return;
    goto NR;

Now eliminate the straight-line gotos

NR: if (…) goto backtrack;
    if (…) goto NR;

NC: if (…) goto print;
    goto NR;

print:

backtrack:
    if (…) return;
    goto NR;

Note that a label with all backward-going gotos is a loop:

for (;;) {
NR: if (…) goto backtrack;
    if (…) continue;

NC: if (…) goto print;
    continue;

print:

backtrack:
    if (…) return;
}

Hmm, we can reverse the sense of the NC: if() and eliminate the goto print. And the goto backtrack just jumps over some statements, which is equivalent to another reversed if.

for (;;) {
NR: if (! …) {
        if (…) continue;
NC:     if (! …) continue;
print:
    }
backtrack:
    if (…) return;
}

The loop has no condition, but backtrack: … if(…) return; just exits it, so move that block and the condition into the loop.

for (;…; /* backtrack */ …) {
NR: if (! …) {
        if (…) continue;
NC:     if (! …) continue;
print:
    }
}

Looking pretty good, no more gotos and no "suspicious" structure! However, NC is supposed to be the entry point.

This is where blind, mechanistic, compiler-ish transformations fail. I see three alternatives:

1. Introduce variables to force execution there for the first loop iteration. This is uglier than goto, in my opinion.
2. Disguise a goto NC; as a switch(0) and call label NC: as case 0:. The teacher will probably not accept this compromise.
3. Copy the blocks from NC to the end of the loop and paste above the beginning of the loop. You can then factor them out into functions. Actually, this is a blind, mechanistic transformation. Hooray. I'll also represent NR and backtrack as functions for uniformity.

.

NC();
if (…) {
    print();
}

while ( backtrack(), … ) { // <- note comma operator
    NR();
    if (! …) {
        if (…) continue;
        NC();
        if (! …) continue;
        print();
    }
}

There is probably a more elegant solution that involves looking at the contents of the code, but this takes less thinking.