dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: Sliding Puzzle Programming Assignment Help

  1. #1
    Join Date
    Nov 2019
    Posts
    6

    Sliding Puzzle Programming Assignment Help

    Hello, I am a bit new to C++ programming and was wondering if anyone knew how to go about this program as I am stuck on where to start with this problem. Any help would be appreciated.


    Assignment Instructions:

    The Rules
    Each 8-puzzle has tiles labeled 1-8 and one empty space denoted by a 0.
    The commands given signify where you should attempt to move the empty space in relation to its current position.
    The only moves you are allowed to make are swapping the empty space with an adjacent tile to it.
    If asked to make an impossible swap (ie. move the blank tile out of the grid bounds), don't terminate the program, simply ignore that command.
    The Assignment
    For this assignment, we are asking you to take an 8-puzzle and follow a sequence of movement commands UP, DOWN, LEFT, and RIGHT. At the end of the sequence, you should check whether the puzzle has been solved.

    Input
    As input you will be given some initial board state in the form of a sequence of numbers where 0 corresponds to the "blank" tile. The example below would be the form of the "initial state" example above. After that will be a sequence of commands "UP", "DOWN", "LEFT", and "RIGHT" represented by characters on a single line separated by spaces. (The example command sequence below has no connection to the example graphic)

    1 8 2 0 4 3 7 6 5
    D R R R U L

    Your Task
    After storing the initial board state, you will perform the commands given (so long as they are allowed, as specified in the rules section). Run through all the commands, then check whether the puzzle is solved correctly.

    Output
    Your output should be Solution is good! if the puzzle is in solved order as specified above, and Wrong solution! if the puzzle is not in the "goal state" specified above.

  2. #2
    Join Date
    Feb 2017
    Posts
    483

    Re: Sliding Puzzle Programming Assignment Help

    Quote Originally Posted by jango2447 View Post
    Hello, I am a bit new to C++ programming and was wondering if anyone knew how to go about this program as I am stuck on where to start with this problem. Any help would be appreciated.
    The command names "UP", "DOWN", "LEFT", and "RIGHT" suggest the board is 2-dimensional. Is that so?

    What is a solution? Is it maybe the sequence 1 2 3 4 5 6 7 8 with the 0 at an arbitrary position?

    Do you need to read the input from somewhere or are you allowed to hard-code it in an internal data structure?

    The first step when writing a program is to specify the problem properly.
    Last edited by wolle; November 15th, 2019 at 03:25 AM.

  3. #3
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,921

    Re: Sliding Puzzle Programming Assignment Help

    ... and then to do it manually using paper and pencil/pen and see what steps are required to be undertaken. These steps then become part of the algorithm which when followed manually produces the required result. Then when the algorithm is complete, this is then converted into a program design (including input, output etc) from which the code is then written, tested & debugged until the program performs as expected.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.4.0)

  4. #4
    Join Date
    Nov 2019
    Posts
    6

    How would I fix this code to meet the assignment instructions?

    Okay so I started coding this slding puzzle assignment and was just wondering how I would fix my code in order to meet the rules of this assignment:

    Each 8-puzzle has tiles labeled 1-8 and one empty space denoted by a 0.
    The commands given signify where you should attempt to move the empty space in relation to its current position.
    The only moves you are allowed to make are swapping the empty space with an adjacent tile to it.
    If asked to make an impossible swap (ie. move the blank tile out of the grid bounds), don't terminate the program, simply ignore that command.
    The Assignment
    For this assignment, we are asking you to take an 8-puzzle and follow a sequence of movement commands UP, DOWN, LEFT, and RIGHT. At the end of the sequence, you should check whether the puzzle has been solved.

    Input
    As input you will be given some initial board state in the form of a sequence of numbers where 0 corresponds to the "blank" tile. The example below would be the form of the "initial state" example above. After that will be a sequence of commands "UP", "DOWN", "LEFT", and "RIGHT" represented by characters on a single line separated by spaces. (The example command sequence below has no connection to the example graphic)

    1 8 2 0 4 3 7 6 5
    D R R R U L
    Your Task
    After storing the initial board state, you will perform the commands given (so long as they are allowed, as specified in the rules section). Run through all the commands, then check whether the puzzle is solved correctly.

    Output
    Your output should be Solution is good! if the puzzle is in solved order as specified above, and Wrong solution! if the puzzle is not in the "goal state" specified above.



    Here is the code I have so far:

    Code:
    #include <time.h>
    #include <stdlib.h>
    #include <vector>
    #include <string>
    #include <iostream>
    
    class p15 {
    public :
        void play() {
            bool p = true;
            std::string a;
    
            while( p ) {
                createBrd();
                while( !isDone() ) {
                    drawBrd();
                    getMove();
                }
              
                drawBrd();
                std::cout << "\n\nCongratulations!\nPlay again (Y/N)?";
                std::cin >> a;
                if( a != "Y" && a != "y" ) 
                   break;
           }
        }
        
    private:
        void createBrd() {
            int i = 1;
            std::vector<int> v;
    
            for( ; i < 16; i++ ) {
                brd[i - 1] = i;
            }
    
            brd[15] = 0;
            x = y = 3;
            for( i = 0; i < 1000; i++ ) {
                getCandidates( v );
                move( v[rand() % v.size()] );
                v.clear();
            }
        }
    
        void move( int d ) {
            int t = x + y * 4;
    
            switch( d ) {
                case 1: y--; break;
                case 2: x++; break;
                case 4: y++; break;
                case 8: x--;
            }
    
            brd[t] = brd[x + y * 4];
            brd[x + y * 4] = 0;
        }
    
        void getCandidates( std::vector<int>& v ) {
            if( x < 3 ) v.push_back( 2 ); 
    
            if( x > 0 ) v.push_back( 8 );
    
            if( y < 3 ) v.push_back( 4 );
    
            if( y > 0 ) v.push_back( 1 );
        }
    
        void drawBrd() {
            int r; 
    
            std::cout << "\n\n";
            for( int y = 0; y < 4; y++ ) {
                std::cout << "+----+----+----+----+\n";
                for( int x = 0; x < 4; x++ ) {
                    r = brd[x + y * 4];
                    std::cout << "| ";
                    if( r < 10 ) std::cout << " ";
    
                    if( !r )
                        std::cout << "  ";
                    else 
                         std::cout << r << " ";
                }
                std::cout << "|\n";
            }
            std::cout << "+----+----+----+----+\n";
        }
    
        void getMove() {
            std::vector<int> v;
    
            getCandidates( v );
    
            std::vector<int> p;
    
            getTiles( p, v );
    
            unsigned int i;
    
            while( true ) {
                std::cout << "\nPossible moves: ";
                for( i = 0; i < p.size(); i++ ) std::cout << p[i] << " ";
    
                int z;
    
                std::cin >> z;
                
                for( i = 0; i < p.size(); i++ )
                    if( z == p[i] ) {
                         move( v[i] ); 
                         return;
                    }
            }
        }
    
        void getTiles( std::vector<int>& p, std::vector<int>& v ) {
            for( unsigned int t = 0; t < v.size(); t++ ) {
                int xx = x, yy = y;
    
                switch( v[t] ) {
                    case 1: yy--; break;
                    case 2: xx++; break;
                    case 4: yy++; break;
                    case 8: xx--;
                }
    
                p.push_back( brd[xx + yy * 4] );
            }
        }
    
        bool isDone() {
            for( int i = 0; i < 15; i++ ) {
                if( brd[i] != i + 1 )
                      return false;
            }
            return true;
        }
    
        int brd[16], x, y;
    };
    
    int main(int argc, char* argv[])
    {
        srand( ( unsigned )time( 0 ) );
    
        p15 p;
    
        p.play();
        return 0;
    }
    Last edited by 2kaud; November 16th, 2019 at 06:01 AM. Reason: Added code tags and merged threads

  5. #5
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,921

    Re: Sliding Puzzle Programming Assignment Help

    [When posting code, please use code tags so that the code is readable. Go Advanced, select the formatted code and click '#']
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.4.0)

  6. #6
    Join Date
    Nov 2019
    Posts
    6

    Re: Sliding Puzzle Programming Assignment Help

    Okay here is my code reformatted what should I add to it in order to make sure I meet the rules of this assignment?
    Code:
    // C++ program to check if a given instance of 8 puzzle is solvable or not
    #include <iostream>
    using namespace std;
    
    // A utility function to count inversions in given array 'arr[]'
    int getInvCount(int arr[])
    {
        int inv_count = 0;
        for (int i = 0; i < 9 - 1; i++)
            for (int j = i+1; j < 9; j++)
                 // Value 0 is used for empty space
                 if (arr[j] && arr[i] &&  arr[i] > arr[j])
                      inv_count++;
        return inv_count;
    }
    
    // This function returns true if given 8 puzzle is solvable.
    bool isSolvable(int puzzle[3][3])
    {
        // Count inversions in given 8 puzzle
        int invCount = getInvCount((int *)puzzle);
    
        // return true if inversion count is even.
        return (invCount%2 == 0);
    }
    
    /* Driver progra to test above functions */
    int main(int argv, int** args)
    {
    
      int puzzle[3][3] =  {{1, 8, 2},
                          {0, 4, 3},  // Value 0 is used for empty space
                          {7, 6, 5}};
      isSolvable(puzzle)? cout << "Solution is good!":
                          cout << "Wrong Solution!";
      return 0;
    }

  7. #7
    Join Date
    Nov 2018
    Posts
    23

    Re: Sliding Puzzle Programming Assignment Help

    > Here is the code I have so far:
    From 2017 apparently.
    https://2ch.hk/b/arch/2017-01-30/res/145545422.html

    > Okay here is my code reformatted
    You're not very good at this are you.
    https://www.geeksforgeeks.org/check-...zzle-solvable/

    > int main(int argv, int** args)
    Just for the LOL's.

  8. #8
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,921

    Re: Sliding Puzzle Programming Assignment Help

    here is my code reformatted
    But it's not your code - is it.

    Passing off other peoples code as your own is called 'cheating' and is not condoned on these forums.

    PS It's not even good code!
    Last edited by 2kaud; November 16th, 2019 at 07:13 AM. Reason: PS
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.4.0)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)