The Importance of Good Design
How do we go about writing a program for this problem?
To start with, let us investigate the problem deeper. We will try to dig-deeper into finding what is it that we do when we solve the puzzle ourselves. We will try to represent that information in a systematic, step-by-step fashion. Once we know the absolute step-by-step process of solving this problem, we will convert it into a functional program.
In this tutorial, we will consider the examples of the 4x4 puzzle (i.e. the 15-puzzle)
We will try to build up the problem step-by-step, very systematically – without wasting any thought in any non-useful way.
We will learn how to represent the problem well.
We will learn how to ask the right questions.
We will learn how to take small steps and build-over these small steps to take bigger steps.
Representing the problem
Board: The simple way to represent the 15-puzzle board is by a 4x4 matrix.
Coordinates: The coordinates can be represented as a 2-member structure (or its equivalent in the given programming language) to represent x- and y- coordinate of a tile/hole in the puzzle.
We will consider that the bottom-left corner has the coordinates (0, 0).
Hole Position: Since the position of the hole is common to the entire puzzle, we can store the HolePosition as a global variable.
A sample representation of the puzzle as a 4x4 matrix. We can consider the bottom-left corner as the position (0, 0).
Hence, the top-left corner is position (3 ,0).
The problem-statement becomes: Move the tile numbered ‘1’ from its initial position to the position (3, 0).
Next Step
The next question to ask is: What is basic “fundamental operation” in this puzzle? While playing the puzzle in the real-world, what is the most “fundamental operation” that we do?