Thread: recursion inside for() not working as expected

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    87

    recursion inside for() not working as expected

    i am trying to make a recursive function that will go through the numbers 1-9 and if one of them works will then go on to the next space in the array. something is going wrong so that when solve() calls itself, if it fails it does not continue with the for loop, but instead calls itself again.
    Code:
    void solve()
    {
        if(finished) return;
        // iterate through the numbers, after hitting 9 return (go back a step)
        puzzle[x][y]++;
        for(;puzzle[x][y] <= 9;puzzle[x][y]++)
        {
            array_out();
            if(test())
            {
                x++;
                if(x < 9)
                {
                    solve();
                    continue;
                }
                else
                {
                    x = 0;
                    y++;
                    if(y<9)
                        solve();
                    else finished = true;
                    continue;
                }
            }
        }
        puzzle[x][y] = 0;
        return;
    }

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    This looks to be very badly designed.
    Post your whole program.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    87
    Code:
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    int puzzle[9][9];
    int x = 0;
    int y = 0;
    bool finished = 0;
    
    int get_box(int a);
    bool test();
    bool test_box();
    bool test_column();
    bool test_row();
    void solve();
    void array_out();
    
    
    int main()
    {
    
        cout << "this program will solve sudoku puzzles.\n enter with spaces between the numbers and no commas.\n a 0 is used for a blank space." << endl;
        for(int i = 0; i < 9;i++)
            for(int b=0; b < 9; b++)
                hints[i][b]=0;
        for(int i = 0; i < 9;i++)
            for(int b=0; b < 9; b++)
                puzzle[i][b] = hints[i][b];
        solve();
        array_out();
        return 0;
    }
    
    void array_out()
    {
        system("cls");
        for(int i = 0; i < 9;i++)
        {
            cout << endl;
            for(int b=0; b < 9; b++)
                cout << puzzle[i][b] << " ";
        }
    }
    
    bool test()
    {
        if(test_column())
            if(test_row())
                if(test_box())
                    return true;
        return false;
    }
    
    bool test_column()
    {
        bool unique = 1;
        for(int i=0; i < 9; i++)
            if(puzzle[x][i] == puzzle[x][y])
                if(i!=y)
                    unique = 0;
        return unique;
    }
    
    bool test_row()
    {
        bool unique = 1;
        for(int i=0; i < 9; i++)
            if(puzzle[i][y] == puzzle[x][y])
                if(i!=x)
                    unique = 0;
        return unique;
    }
    
    bool test_box()
    {
        int box_y = 3*get_box(y);
        int box_x = 3*get_box(x);
        bool unique = 1;
        for(int i = 0; i < 3; i++)
            for(int b = 0; b < 3; b++)
                if(puzzle[box_x+i][box_y+b] == puzzle[x][y])
                    if(box_x+i!= x)
                        if(box_y+b!=y)
                            unique = false;
        return unique;
    
    }
    
    int get_box(int a)
    {
        return (a/3);
    }
    
    void solve()
    {
        if(finished) return;
        puzzle[x][y]++;
        for(;puzzle[x][y] <= 9;puzzle[x][y]++)
        {
            array_out();
            if(test())
            {
                x++;
                if(x < 9)
                {
                    solve();
                    continue;
                }
                else
                {
                    x = 0;
                    y++;
                    if(y<9)
                        solve();
                    else finished = true;
                    continue;
                }
            }
        }
        puzzle[x][y] = 0;
        return;
    }
    im not asking for all the errors in this code, i just need to know whats wrong with sovle()

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I finally got enough time to look through your code. The essential problem is that since x and y are global values they can't backtrack the way you want them to. I.e., once you've set, say, location 1,3 to 6, you can never backtrack to that location in order to try a different number.

    You need to pass x and y into solve as parameters so that stack pops can backtrack them properly for you. I would normally mention a few other things you should probably fix, but since you don't want much help I'll leave you to it.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    They neither backtrack nor pop.
    The only thing is that local variables are just that--local. They are destroyed when they go out of scope. But the thing is that you can have the same name for variables in different scopes (functions).
    However, as you are using global variables, its value persists between functions because you aren't assigning to local variables.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. && not working as expected
    By TonyBalony in forum C Programming
    Replies: 4
    Last Post: 12-14-2011, 12:30 PM
  2. Multithreading not working as expected
    By shiroaisu in forum Windows Programming
    Replies: 5
    Last Post: 06-18-2011, 02:34 AM
  3. Program not working as expected
    By perrrson in forum C Programming
    Replies: 3
    Last Post: 10-02-2010, 01:49 PM
  4. Pipes not working as expected
    By Shadow_Fiend in forum C Programming
    Replies: 1
    Last Post: 05-16-2010, 05:55 AM
  5. cin.get(); doesn't seem to be working as expected
    By Diablo84 in forum C++ Programming
    Replies: 5
    Last Post: 03-30-2005, 07:00 PM