Removal of gotos

Finally back at looking through code...I am trying to eliminate the gotos in the sudoku function below:


I have eliminated simple gotos before...

Code:

---

double sum = 0.0;
   
  int x = 1;
  repeat: sum += 1.0 / x++;

  if (x <= N)
    goto repeat;

  printf("The sum of the first %d reciprocals is %lf\n", N, sum);

Removal:

double sum = 0.0;
   
 int x = 1;
 do
 {
        sum += 1.0 / x;
        x++;
 } while (x <= N);
 printf("The sum of the first %d reciprocals is %lf\n", N, sum);

---

Now, I am trying to eliminate the 4 goto statments without using breaks or continues...

Code:

---

bool sudoku_solver(int sudoku[][9], int& diff_single, int& diff_line, int& diff_row, int& diff_block)
{
        bool empty_fields = true;
    bool operation_done;
    int counter;
        int empty_fields_counter;
        int sdk_to_solve [9][9];

        diff_single = 0;
        diff_line = 0;
        diff_row = 0;
        diff_block = 0;
       
        int sudoku_bool[9][9][10];

        for (int n = 0; n < 9; n++) {
                for (int m = 0; m < 9; m++) {
                        for (int p = 0; p < 10; p++) {
                                sudoku_bool[n][m][p] = true;
                        }
                }
        }
       
        for (int m = 0; m < 9; m++) {
                for (int n = 0; n < 9; n++) {
                        sdk_to_solve[m][n] = sudoku[m][n];
                }
        }
       
        //main solver
        while (empty_fields) {
                operation_done = false;
                //Scanning
                for (int n = 0; n < 9; n++) {
                        for (int m = 0; m < 9; m++) {
                                if (sdk_to_solve[m][n] != NULL) {
                                        for (int i = 0; i < 10; i++) {
                                                sudoku_bool[m][n][i] = false;
                                        }
                                        for (int i = 0; i < 9; i++) {
                                                sudoku_bool[m][i][sdk_to_solve[m][n]] = false;
                                                sudoku_bool[i][n][sdk_to_solve[m][n]] = false;
                                        }
                                        for (int k = 0; k < 3; k++) {
                                                for (int l = 0; l < 3; l++) {
                                                        sudoku_bool[(3 * (m / 3)) + l][(3 * (n / 3)) + k][sdk_to_solve[m][n]] = false;
                                                }
                                        }
                                }
                        }
                }
                //analyze scanned pattern
                //single field defined value?
                for (int m = 0; m < 9; m++) {
                        for (int n = 0; n < 9; n++) {
                                int counter = 0;
                                int last_true;
                                for (int num = 1; num < 10; num++) {
                                        if (sudoku_bool[m][n][num]) {
                                          counter++;
                                          last_true = num;
                                        }
                                }
                                if (counter == 1) {
                                        sdk_to_solve[m][n] = last_true;
                                        operation_done = true;
                                        diff_single++;
                                }
                        }
                }
               
                if (operation_done) {
                        goto field_counter;  //eliminate me!!!
                }
               
                //Column defined field?
                for (int num = 1; num < 10; num++) {
                        for (int m = 0; m < 9; m++) {
                                int counter = 0;
                                int last_field;
                                for (int n = 0; n < 9; n++) {
                                        if (sudoku_bool[m][n][num]) {
                                                counter++;
                                                last_field = n;
                                        }
                                }
                                if (counter == 1) {
                                        sdk_to_solve[m][last_field] = num;
                                        operation_done = true;
                                        diff_line++;
                                }
                        }
                }
                if (operation_done) {
                        goto field_counter;  //eliminate me
                }
               
                //Row defined field?
                for (int num = 1; num < 10; num++) {
                        for (int n = 0; n < 9; n++) {
                                int counter = 0;
                                int last_field;
                                for (int m = 0; m < 9; m++) {
                                        if (sudoku_bool[m][n][num]) {
                                                counter++;
                                                last_field = m;
                                        }
                                }
                                if (counter == 1) {
                                        sdk_to_solve[last_field][n] = num;
                                        operation_done = true;
                                        diff_row++;
                                }
                        }
                }
                if (operation_done) {
                        goto field_counter;  //eliminate me
                }
                //block defined field?
                for (int num = 1; num < 10; num++) {
                        for (int block_row = 0; block_row < 9; block_row += 3) {
                                for (int block_line = 0; block_line < 9; block_line += 3) {
                                        counter = 0;
                                        int last_line;
                                        int last_row;
                                        for (int inblock_row = 0; inblock_row < 3; inblock_row++) {
                                                for (int inblock_line = 0; inblock_line < 3; inblock_line++) {
                                                        if (sudoku_bool[block_row + inblock_row][block_line + inblock_line][num]) {
                                                                counter++;
                                                                last_row = block_row + inblock_row;
                                                                last_line = block_line + inblock_line;
                                                        }
                                                }
                                        }
                                        if (counter == 1) {
                                                sdk_to_solve[last_row][last_line] = num;
                                                operation_done = true;
                                                diff_block++;
                                        }
                                }
                        }
                }
                if (operation_done) {
                        goto field_counter;  //eliminate me
                }
               
                field_counter:
                empty_fields_counter = 0;
                for (int m = 0; m < 9; m++) {
                        for (int n = 0; n < 9; n++) {
                                if (sdk_to_solve[m][n] == NULL) {
                                        empty_fields_counter++;
                                }
                        }
                }
                if (empty_fields_counter == 0) {
                        empty_fields = false;
                }
                if (empty_fields_counter != 0 && !operation_done) {
                        return false;
                }
        }
        return true;
}

---

Any ideas or suggestions on how to do this...flags, what?

I'd probably start from breaking things into functions of their own.

E.g my own Sudoku solving loop looks like this:

Code:

---

bool SudokuGenerator::solve_()
{
    do {
        while (find_single_candidates_() || find_hidden_single_());

    } while (found_count < 81 && (
        find_locked_candidates_() ||
        find_naked_pair_() ||
        ... ));
    return found_count == 81;
}

---

Cross-posted

What's wrong with breaks & continues?

Quote:

---

Originally Posted by cpjust

What's wrong with breaks & continues?

---

nothing.

I use them all the time in my code. everyone says they're just "pretty wrappers for goto", but isn't that actually the BEST reason to use them? so you don't have to use goto. there often isn't a better way to leave a loop or bypass the remainder of the loop, and they fill that role quite nicely.

In this case they don't seem to be good, and the gotos can be replaced with nested ifs:

Code:

---

while some condition:
    do something
    if not done:
        do something
        if not done:
            do something
            ...
    work done at the end of the iteration

---

Simply mechanically avoiding the goto won't improve the code much (the gotos all go forward to the same place anyway). Breaking it into more manageable bits might do a lot (you'll also have more options to provide a goto-less structure).

Naturally the best way to be rid of gotos is to not put them in there in the first place!

I thoroughly agree with anon here. The first step to eliminate those gotos must be to break it down into sub-functions. Do that first!

Re the whole "not using break" thing: It is a ridiculous double-standard. Such people can't do without them in switch statements, but wont put them in loops, which makes no sense at all. It's making up rules of your own just to give yourself an excuse to not bother with structured programming, that you've made it too hard for yourself on purpose. If you wont use a break in a loop then I forbid you to use one in a switch statement.

A quote from the legendary Zahlman of Gamedev.net to ponder:

Quote:

---

There is no meaningful sense in which break and continue are "gotos" but the ends of for loops, ends of while loops, function calls and returns (explicit or implicit) are not.

---

By the same measure, if you've only introduced the need for `break' or `continue' because you've nested control structures you're essentially giving yourself an excuse not to rewrite the code.

Quote:

---

Such people can't do [...] no sense at all.

---

I don't use `break' or `continue' at all. Coding under that implication I produce better code.

I think the problem is making up rules for the sake of having rules. Their doesn't seem to be a need for a rationale behind them. (See not allowing templates in an embedded environment.)

Soma

Quote:

---

Originally Posted by phantomotap

I don't use `break' or `continue' at all. Coding under that implication I produce better code.

---

So you don't use switch statements?

O_o

What? What does that have to do with using `break' or `continue'? What do they have to do with `switch'? Are you making some indirect association? ('break' -> `goto' <- 'case acase:')

[Edit]

I've got it now. You asked that because of the common "rule" that every `case' block must end with a `break'. It is a stupid rule and has nothing to do with the standard.

[/Edit]

Whatever.

If the situation is best illustrated by a `switch' statement, I naturally use a `switch' statement, but you'll have to explain how that necessitates `break' or `continue'. I've managed without them for some time.

Actually, come to think on it, most of my code is "library level" where a `switch' statement wouldn't be allowed for mechanical reasons (For example, in template code where you'd have to use a different construct simple because the `case' labels must be integer like.) or design reasons. (The related values are not constant/literal expressions.) Considering that, I suppose it would be safe to say I don't use `switch' statements.

Soma

Quote:

---

Originally Posted by phantomotap

O_o

What? What does that have to do with using `break' or `continue'?

---

Switch's have cases which use "break." That's all he meant.

The main reason goto's are bad is because they produce spaghetti code. "break" and "continue" do not produce spaghetti code. They are quite uniform and generally not too hard to follow. Using a few here and there (such as for/while/if statements, switch case/break is perfectly fine) is fine (even using a small amount of goto's under certain circumstances has been argued, even though I've never encountered them).

Quote:

---

Switch's have cases which use "break." That's all he meant.

---

I don't know why he said it, but the association is too strong in the minds of most programmers. I blame the bogus "rule".

"`if' statements have cases which use "break"."

Hear? The association sounds silly. One doesn't necessitate the other. If you want to use `break' fine, but don't assume you need to because of a rule or because that's the way you first "see" it.

Quote:

---

The main reason goto's are bad is because they produce spaghetti code.

---

Except where they don't. I use `goto' (and its "big brothers": `setjmp'/`longjmp') in virtually every "library level" function in C. (I hate C.) I dare you to try your hand at solid and structured source cleaning up of a dozen resources in the face of a dozen exit points without using `goto' in C.

Quote:

---

"break" and "continue" do not produce spaghetti code.

---

Except where they do. If you care to search the Dev-C++ forum you'll find anecdotal "proof". A user had argued the same statement with me and Clifford, another regular. The source he posted as proof was a horrible mess of nesting and fake control structures solving the "N-Queen" problem. If you find it you'll find the companion source written by Clifford.

Source is written for people. (That's probably a quote.) Source is written by people. (Which is plainly obvious.) It is the programmers writing the source that are responsible for "spaghetti" code. Programming is great like that; you can write crap source in any language using any construct.

Soma

Certainty a determined programmer does not need goto to produce spaghetti code.

The thing about break and continue, is that often getting rid of them does not make the code any better. Often it just adds extra variables.

In any case, The OP's problem is simple. Instead of:

Code:

---

if (operation_done) {
    goto field_counter;  //eliminate me
}
code_segment();
field_counter:
general_code();

---

Do:

Code:

---

if(!operation_done)
{
    code_segment();
}
general_code();

---

Quote:

---

Originally Posted by phantomotap

Source is written for people. (That's probably a quote.)

---

If you do want a quote along those lines, Abelson and Sussman's "programs must be written for people to read, and only incidentally for machines to execute" might qualify.