Sliding Puzzle Programming Assignment Help

[jango2447]

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.

[wolle]

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.

[2kaud]

... 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.

[jango2447]

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:

#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;
}

[2kaud]

[When posting code, please use code tags so that the code is readable. Go Advanced, select the formatted code and click '#']

[jango2447]

Okay here is my code reformatted what should I add to it in order to make sure I meet the rules of this assignment?

// 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;
}

[salem_c]

> 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.

[2kaud]

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!