Write a program to generate all and only three-digit number from 000 to 999 the sum of whose digits is odd. So, for example, your program won’t print 000 or 246, but it would print 001 and 342.

How?

Use the backtracking method that we used for the 8 queens problem (and 8 numbers in a cross, and stable marriage, and missionaries …).

Integer array q[3] will represent the solutions (for example the number 11 will be represented in the array as:[0,1,1]. Use an ok() function to test for validity and use gotos to control the program flow as we did in class.

Here is an outline of the structure of the 8 queens program:

bool ok(   some parameters go here ){

Code goes here

}

int main(){

// declarations and initializations of array q, c , …etc. go here

nc: c++;

if(         )     goto print;

q[c]= ________________________

nr: q[c]++;

            if (                    ) goto backtrack;

// test if ok

            if( not ok() ) goto nr;

// passed all tests

goto nc;

backtrack:c--;

            if(c==-1)return 0;

            goto nr;

           

print:

    // print goes here

            goto backtrack;

}

1). Describe your algorithm for generating the required numbers using the data structure (array q) and the backtracking method that we first developed with the 8 queens problem.

Your description should generally follow the code outline above.