Stumped Need Help 15 Puzzle
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Stumped Need Help 15 Puzzle

  1. #1
    Join Date
    Mar 2013
    Posts
    3

    Stumped Need Help 15 Puzzle

    I've been trying to figure out how to implement a way to save this board state throughout a user's inputted path. At the end, I need the output to print out the board states (user's path) of how he or she got the puzzle solved. This puzzle is the 15 Puzzle; but we have it to change by the user's input on what size they want to play (3x3 to 5x5). I need help figuring out how to save the board state of each user input, then print those out in order from beginning to solved puzzle state. Subsequently, I would also need some help on transferring the board state to change with using a vector to store the size based on user input. Yes, this is college work; and I have turned this in last week late. I need help on figuring out how to fix last week's problems to proceed with this week's homework assignment, which is using a first search to solve the puzzle from the current board's state.

    calculations.h
    Code:
    /*Calculations set as a header to keep compiling simple and faster*/
    
    #ifndef calculations
    #define calculations
    
    int solved[5][5];
    
    void initialize(int board[][5], int);
    void slide(int board[][5],int move,int);
    bool isBoardSolved(int board[][5],int);
    
    /*Configure and Setup the 15-Puzzle Game*/
    void initialize(int board[][5], int amt)
    {
    	int i = 1;
    	for(int row = 0; row <= amt; row++)
    	{
    		for(int column = 0; column <= amt; column++)
    		{
    			board[row][column] = i;
    			solved[row][column] = i;
    			i++;
    		}
    		board[amt][amt] = 0;
    		solved[amt][amt] = 0;
    	}
    }
    
    /*Results of moving the blank space*/
    void slide(int board[][5],int move, int amt)
    {
    	int emptyRow;
    	int emptyCol;
    	bool legalMoves[4] = {1,1,1,1}; //array of possible moves, [0] = left, [1] = right, [2] = up, [3] = down. (1) represents a possible move to be accessible.
    	for(int rows = 0; rows <= amt; rows++)
    	{
    		for(int columns = 0; columns <= amt; columns++)
    		{
    			if(board[rows][columns] == 0) //Find location of empty space
    			{
    
    				emptyRow = rows;
    				emptyCol = columns;
    			}
    		}
    	}
    	if(emptyRow + 1 > amt) //Able to move up?
    		legalMoves[2] = false; //If false, set move flag to false
    	else if(emptyRow - 1 < 0) //Able to move down?
    		legalMoves[3] = false;
    
    	if(emptyCol - 1 < 0) //Able to move right?
    		legalMoves[1] = false; //If false, set move flag to false
    	else if(emptyCol + 1 > amt) //Able to move left?
    		legalMoves[0] = false;
    
    	switch(move) //Replace zero space with space to the left right up or down.
    	{
    	case 0:
    		if(legalMoves[move])
    		{
    			board[emptyRow][emptyCol] = board[emptyRow][emptyCol + 1];
    			board[emptyRow][emptyCol + 1] = 0;
    			emptyCol = emptyCol+1;
    		}
    		break;
    	case 1:
    		if(legalMoves[move])
    		{
    			board[emptyRow][emptyCol] = board[emptyRow][emptyCol - 1];
    			board[emptyRow][emptyCol- 1] = 0;
    			emptyCol = emptyCol-1;
    		}
    		break;
    	case 2:
    		if(legalMoves[move])
    		{
    			board[emptyRow][emptyCol] = board[emptyRow+1][emptyCol];
    			board[emptyRow+1][emptyCol] = 0;
    			emptyRow = emptyRow+1;
    		}
    		break;
    	case 3:
    		if(legalMoves[move])
    		{
    			board[emptyRow][emptyCol] = board[emptyRow-1][emptyCol];
    			board[emptyRow-1][emptyCol] = 0;
    			emptyRow = emptyRow-1;
    		}
    		break;
    	}
    
    }
    bool isBoardSolved(int board[][5], int amt)
    {
    	bool boardSolved = true;
    	int row = 0;
    	int col = 0;
    	while(boardSolved && row<=amt)
    	{
    		if(solved[row][col] == board[row][col]) //Compares to make sure if the puzzle is solved 
    												//and sets numbers to green if they are in the correct position
    		{
    			col++;
    			if(col == amt)
    			{
    				row++;
    				col = 0;
    			}
    		}
    		else //If there is any hinderance on solving the puzzle, break the loop by setting it to false
    			boardSolved = false;
    	}
    	return boardSolved;
    }
    
    #endif
    main.cpp
    Code:
    /*Advance AI for Game & Sim Dsgn w/L
      Professor:  Marty Geier
      By: Cody Bennett
      References:	1) http://xoax.net/cpp/crs/console/lessons/Lesson29/
    				2) http://www.cplusplus.com/forum/beginner/11636/
      This program is designed to have the user able to play the 15-Puzzle game. Although,
      the user is also able to make a choice from 3x3(9) and 5x5(25) puzzle as well. Once
      the puzzle is solved, the user has their amount of moves and time displayed.*/
    
    
    #include <iostream>
    #include <string>
    #include <conio.h>
    #include <stdio.h>
    #include <ctime>
    #include <vector>
    #include <array>
    #include <new>
    #include <calculations.h>
    #include <Windows.h>
    
    using namespace std;
    
    // To use the arrow keys instead of letters
    
    #define UP 72
    #define LEFT 75
    #define RIGHT 77
    #define DOWN 80
    
    vector< vector<int> > board;
    board matrix(m);
    
    void print(int board[][5], int);
    void initialize(int board[][5], int);
    void slide(int board[][5],int move,int);
    bool isBoardSolved(int board[][5],int);
    void scramble(int board[][5],int);
    void WaitKey(); 
    
    int main()
    {
    	int boardAmount = 0;
    	int moves = 0;
    	int shuffleCount = 0;
    	
    	do
    	{
    		system("CLS");
                    cout << endl << endl << endl << "\t\tEnter designated size for sliding puzzle. (3 to 5)";
    		cout << endl << endl << "\t\t\t\t\t";
    			cin >> boardAmount;
    		if(boardAmount <3 || boardAmount > 5)
    			cout << "\t\t\tSorry, this program is unable to allow playing with that size specified. Please, enter another size." << endl << endl;
    		Sleep(1300);
    	}while (boardAmount <3 || boardAmount > 5);
    
    	int gameBoard[5][5];
    	
    	char input;
    	string direction;
    	bool invalid = false;
    	boardAmount--; /* Use this method in order to keep from having to
    	                subtract 1 from the checking to make sure the blank space 
    				   doesn't go outside the boundaries of the board.*/
    	initialize(gameBoard,boardAmount); 
    	print(gameBoard,boardAmount);
    	cout << boolalpha;
    	cout<<"isBoardSolved(): "<<isBoardSolved(gameBoard,boardAmount)<<endl;
    	cout<<"How many times would you like to shuffle the board?" << endl;
    	cin >> shuffleCount;
    	cout<<"Press enter to continue to shuffle the board"<<endl;
    	WaitKey(); 
    	cout<<"Scrambling is commencing..."<<endl;
    	scramble(gameBoard, boardAmount); 
    	cout<<"Scrambling is completed, please press enter to continue"<<endl;
    	cin.get(); 
    	system("CLS");
    
    	print(gameBoard,boardAmount);
    	cout<<endl<<endl;
    	clock_t begin = clock ();
    	cout<<"Use arrow keys to move the blank in the desired direction" << endl;
    	cout<<"in order to move the tiles!"<<endl;
    	cout<<"Input: ";
    	while(!isBoardSolved(gameBoard, boardAmount)) 
    	{
    		input = _getch();
    		system("CLS");
    
    		switch(input)
    		{
    		case DOWN:
    			slide(gameBoard,2,boardAmount);
    			direction = "Up";
    			moves++;
    			break;
    		case RIGHT:
    			slide(gameBoard,0,boardAmount);
    			direction = "Left";
    			moves++;
    			break;
    		case UP:
    			slide(gameBoard,3,boardAmount);
    			direction = "Down";
    			moves++;
    			break;
    		case LEFT:
    			slide(gameBoard,1,boardAmount);
    			direction = "Right";
    			moves++;
    			break;
    		default:
    			invalid = true;
    
    		}
    		print(gameBoard,boardAmount);
    		cout<<endl<<endl;
    		cout<<"Use arrow keys to move the blank space in the direction that you want."<<endl;
    		if(invalid)
    			invalid = false;
    		else
    			cout<<"Last User Input: "<<direction;
    	}
    	cout << endl;
    	clock_t end = clock();
    	double elasped_secs = double(end - begin)/ CLOCKS_PER_SEC;
    	cout << "Congratulations!!! You've Won!" << endl;
    	cout << "RESULTS:" << endl;
    	cout << "Moves made: " << moves << endl;
    	cout << "Your time to solve the puzzle is: " << elasped_secs << " seconds" << endl;
    	cout << "Please any key to print your moves below:" << endl;
    	system ("PAUSE");
    
    }
    
    /* Print board and replace zero with a character 177 */
    void print(int board[][5], int amt)
    {
    	HANDLE hConsole;
    	hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    	for(int row = 0; row <= amt; row++)
    	{
    		for(int column = 0; column <= amt; column++)
    		{
    			if(board[row][column] == 0)
    			{
    				SetConsoleTextAttribute(hConsole, 7); //Default color
    				cout << "\xB1\xB1 ";
    			}
    			else
    			{
    				if(board[row][column] == solved[row][column]) //Change the numbers as they are crossed over their correct positions
    															  //They are compared to the solved solution
    					SetConsoleTextAttribute(hConsole, 10);
    				else
    					SetConsoleTextAttribute(hConsole, 12); //If the numbers are not in the right position, turn their color red
    				if (board[row][column]<10) // Print a 0 first if # < 10
    					cout<<"0";
    				cout<<board[row][column] << " ";
    			}
    		}
    		cout<<endl;
    	}
    	SetConsoleTextAttribute(hConsole, 7);
    }
    
    void scramble(int board[][5], int shuffleCount)
    {
    	time_t t;
        srand((unsigned) time(&t));
    	int move;
    	while(isBoardSolved(board,shuffleCount))// Shuffle the board based on the user input
    	{
    		for(int i = 0; i < 50;i++) //Shuffle the board with random tiles moved
    		{
    			move = rand() % 4;
    			slide(board,move,shuffleCount);
    		}
    	}
    }
    
    void WaitKey()
    {
    	while (_kbhit()) _getch(); // Empty the input buffer
    	_getch(); // Wait for a key
    	while (_kbhit()) _getch(); // Empty the input buffer (some keys sends two messages)
    }
    I would appreciate any quick responses. I've spent a long time trying to figure this out myself; but as the title states, I'm stumped.

  2. #2
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Stumped Need Help 15 Puzzle

    Quote Originally Posted by graphic2489 View Post
    I've been trying to figure out how to implement a way to save this board state throughout a user's inputted path. At the end, I need the output to print out the board states (user's path) of how he or she got the puzzle solved. This puzzle is the 15 Puzzle; but we have it to change by the user's input on what size they want to play (3x3 to 5x5). I need help figuring out how to save the board state of each user input, then print those out in order from beginning to solved puzzle state. Subsequently, I would also need some help on transferring the board state to change with using a vector to store the size based on user input. Yes, this is college work; and I have turned this in last week late. I need help on figuring out how to fix last week's problems to proceed with this week's homework assignment, which is using a first search to solve the puzzle from the current board's state.
    Before writing one line of C++ code, did you write out a plan on how to solve these issue? Unless there are bugs in your program you posted, what is it we're supposed to do with that code? First, it takes time to read it, then it takes time to run it. All of this and we have to comment on the shortcomings of the design you've chosen, etc.

    If you're trying to work out a solution by writing C++ code first and changing it so that it "works", that is the wrong approach. You have to have a plan first, and then code toward that plan. Then there would be no such thing as "being stumped", as the only thing that would be stopping you would be bugs in the program, or a wrong data structure being used, or similar problem.
    but we have it to change by the user's input on what size they want to play (3x3 to 5x5)
    Have you done that?
    I need help figuring out how to save the board state of each user input
    "Save the board state" meaning what exactly? Save the board so that when you run the program again, it remembers what was played?
    then print those out in order from beginning to solved puzzle state
    The obvious high-level answer is to come up with a structure that holds one "state", and then create a container of these structures. At the end, you now have a container of these states and you print them out.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 16th, 2013 at 12:12 PM.

  3. #3
    Join Date
    Mar 2013
    Posts
    3

    Re: Stumped Need Help 15 Puzzle

    We had a plan of execution. I had this worked out on how to do; but when I got to the last part of this assignment (the outputted results, when the puzzle is solved). I was stumped. The help that I need is how to implement a way on saving the board state, which is the matrix as it changes based on the user's input. From there, the user input's change the board state; and after each input, the board state is saved. Then when the puzzle is saved, the end would output the matrix as it changes due to the user's moves.

    For example,

    1 2 3
    4 5 6
    7 8

    You won!!!
    ...amount of moves
    ...time to solve puzzle
    ...system ("PAUSE");
    ...Press enter to view your moves made.
    ...output matrix as it changes due to user's input (up, down, right left) from beginning to end

    P.S. Yes, I know the design is inadequate to some; but I'm in college learning this. So with or without intention, I didn't like the mention of the response of shortcomings of my design. I know that it isn't the best way to go about doing this assignment; and so, I will polish my programming code with more experience.

  4. #4
    VictorN's Avatar
    VictorN is online now Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,006

    Re: Stumped Need Help 15 Puzzle

    Quote Originally Posted by graphic2489 View Post
    The help that I need is how to implement a way on saving the board state, which is the matrix as it changes based on the user's input. From there, the user input's change the board state; and after each input, the board state is saved.
    Then save the matrix dimension(s) first, then the matrix data (row by row), then all the other data. So what is the problem?
    Victor Nijegorodov

  5. #5
    Join Date
    Mar 2013
    Posts
    3

    Re: Stumped Need Help 15 Puzzle

    So, how would I save them? Would I save them in a multidimensional vector with the matrix stored in it as it is push_back when a user makes an input? Or am I just over complicating this?

  6. #6
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Stumped Need Help 15 Puzzle

    Quote Originally Posted by graphic2489 View Post
    So, how would I save them? Would I save them in a multidimensional vector with the matrix stored in it as it is push_back when a user makes an input? Or am I just over complicating this?
    The code you posted IMO reveals why you're having problems.

    Nowhere in your code do you use a struct or class to store related information. Instead you have arrays and vectors strewn about in the code where there is no cohesion or connection between the arrays, vectors, and the play of the game.

    A struct allows you to use a type, call it BoardGame, and inside this type you have a matrix, the number of rows, etc. Then you write a function that takes a BoardGame and writes the information to a file or to output. Then you're passing a BoardGame to all of those functions, and not discrete, individual arrays, vectors, or other information.
    Code:
    vector< vector<int> > board;
    board matrix(m);
    
    void print(int board[][5], int);
    void initialize(int board[][5], int);
    void slide(int board[][5],int move,int);
    bool isBoardSolved(int board[][5],int);
    void scramble(int board[][5],int);
    These all should be in one class or struct.
    Code:
    class BoardGame
    {
           std::vector< std::vector<int> > board;
        public:
           void print();
           void initialize();
           void slide();
           bool isBoardSolved();
           void scramble();
           void saveGame();
    };
    This is what would have been expected with such a program. One struct or class that encapsulates the entire game, and a function called saveGame() that saves a game. Look up what a struct is. That should help you in how to solve the problem.

    Secondly, why are you using arrays for one thing, and vector for another? Why not just use vector instead of getting involved with arrays?
    Code:
    int gameBoard[5][5];
    //...
    void print(int board[][5], int);
    Why aren't these vectors also? Then there is no need for the [5] or any other hard-coded value.
    Code:
    int matrixNumber;
    cout << "Enter game size ";
    cin >> matrixNumber;
    //...
    std::vector<std::vector<int> > gameBoard(matrixNumber, std::vector<int>(matrixNumber));
    Now gameBoard is 3x3, 5x5, or 10x10, or 1000x1000, all depending on the value of matrixNumber.
    I didn't like the mention of the response of shortcomings of my design
    What response would that be? I mentioned that you can't write any program without knowing what you're going to do first and have worked it out on paper. No programming is involved in the initial design stage, so it has nothing to do with programming skills or how much C++ you know or don't know.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 16th, 2013 at 03:45 PM.

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    1,990

    Re: Stumped Need Help 15 Puzzle

    Do you really want to save the board state when a user makes an input - or just save the users input? If you copy the initial state of the board (after the suffles) and then just save the user input char then you can recreate the board by replaying the saved input to the copy of the initial state.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center