CODEWITHSUNDEEP
c#.netalgorithmwinforms
CodyK
CodyK

Reputation: 3657

15 Puzzle Shuffle Method Issues

I am making a 15 puzzle game in C# that allows the user to enter a custom row and column value up to a maximum of a 10 x 10 puzzle. Because of this I am having problems with the shuffle method. I want to make it so the puzzle is always solvable. By first creating a winning puzzle then shuffling the empty space. The problem is it is too inefficient to call every click event each time. I need a way to invoke the click event of a button adjacent to the empty space but not diagonal. I also use an invisible static button for the empty spot. The PuzzlePiece class inherits from Button. I am not too sure how to do this. I would appreciate any help.

Thanks

here is what I have:

private void shuffleBoard()
    {
        //5 is just for test purposes
        for (int i = 0; i < 5; i++)
        {
            foreach (Control item in this.Controls)
            {
                if (item is PuzzlePiece)
                {
                    ((PuzzlePiece)item).PerformClick();
                }
            }
        }
    }

 void PuzzlePiece_Click(object sender, EventArgs e)
    {
        PuzzlePiece piece = (PuzzlePiece)sender;

        if (piece.Right == puzzleForm.emptyPiece.Left && piece.Top == puzzleForm.emptyPiece.Top)
        {
            movePiece(piece);
        }
        else if (piece.Left == puzzleForm.emptyPiece.Right && piece.Top == puzzleForm.emptyPiece.Top)
        {
            movePiece(piece);
        }
        else if (piece.Top == puzzleForm.emptyPiece.Bottom && piece.Left == puzzleForm.emptyPiece.Left)
        {
            movePiece(piece);
        }
        else if (piece.Bottom == puzzleForm.emptyPiece.Top && piece.Left == puzzleForm.emptyPiece.Left)
        {
            movePiece(piece);
        }
    }

Upvotes: 0

Views: 2408

Answers (2)

RBarryYoung
RBarryYoung

Reputation: 56725

For 15-puzzles (and similar sliding-tile games), any arrangement of tiles is solvable If and only If it has an even parity.

Therefore, you should be able to just lay the tiles out randomly. If the parity is even then its solvable as is. If the parity is odd, then just swap two adjacent tiles to reverse the parity and then it's solvable.

See here for details on how to measure the parity: http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability

Since the Wikipedia article has been changed so that it is no longer clear how to calculate the parity of a Fifteen-puzzle arrangement, I will explian below:

For any arrangement of tiles, you calculate the inversion by:

  1. Counting all of the "Inversions". An inversion is anytime in the sequence from the upper right-hand corner, across each row, down to the lower left-hand corner that a numbered tile is lower than the tile that came before it. The first tile never counts as inverted (because it has no tile before it, so it cannot be lower than that tile), and you do not count the empty space.

  2. Add to that the Row Number of the blank space minus 1.

This total is the Count of an arrangement. If the Count is even then the arrangement has even (or 0) parity. If the Count is odd then it has odd (or 1) parity.

Compare the parity of the starting arrangement to the parity of the target arrangement. If they are the same, then the puzzle is solvable, otherwise it is not solvable. Since the standard target arrangement (space, 1-15 in order) has 0 inversions and the row number of the space is 1, then we get a Count of 0 + (1 - 1) or 0, which is even so the parity of the target is 0. Thus any starting arrangement that is also 0 is solvable.

Upvotes: 11

Enigmativity
Enigmativity

Reputation: 117055

If I were you I would separate out your model from your UI.

Create a class called Puzzle. This class will hold the state of puzzle and perform all operations on the state.

It's likely that you might implement MoveLeft, MoveRight, MoveUp & MoveDown methods. To shuffle your board you could just perform a (fairly long) series of moves by calling these four methods randomly.

Your Puzzle class would need to expose enough state for the UI to render itself.

Doing it this way you can simplify your code and make unit testing much simpler.

Upvotes: 2

Related Questions