15 puzzle solver: Difference between revisions
→The Plan
Line 241:
=={{header|Fortran}}==
===The Plan===
There is a straightforward method for dealing with problems of this sort, the Red Tide. Imagine a maze and pouring red-dyed water into the "entry" - eventually, red water issues forth from the exit, or, back pressure will indicate that there is no such path. In other words, from the starting position find all possible positions that can be reached in one step, then from those positions, all possible positions that can be reached in one step from them, and so on. Eventually, either the stopping position will be reached, or, there will be no more new (still dry) positions to inspect. What is needed is some way of recording whether a position has been marked red or not, and an arrangement for identifying positions that are on the leading edge of the tide as it spreads. Keeping as well some sort of information identifying the path followed by each droplet, so that when a droplet spreads to the end position, its path from the source can be listed.
One could imagine an array FROM whose value for a given position identifies the position from which a step was taken to reach it. The value could be a number identifying that position or be a (sixteen element) list of the placement of the tiles. An index for FROM would span the values zero to fifteen, and there would be sixteen dimensions...
===The Code===
The source code started off as a mainline only, but then as facilities were added and service routines became helpful. This prompted the use of F90's MODULE facility so that the PARAMETER statement could be used to describe the shape of the board with this available to each routine without the need for passing the values as parameters or messing with COMMON storage, or repeating the PARAMETER statement in each routine. Otherwise, literal constants such as 4 would appear in various places. These appearances could now be documented by using the appropriate name such as <code>NR</code> and <code>NC</code> rather than just <code>4</code> and similar. However, inside FORMAT statements the use of <NR - 1> (and not <NC - 1>) rather than 3 will succeed only if the compiler accepts this usage, and not all do. More complex calculations involving the board size have not been attempted. The PARAMETER facility is useful only for simple calculations. Considerations such as a 4x4 board having 16 squares is easy, but the consequences of this count fitting into a four-bit binary field are not, thus the equivalences involving <code>BOARD, BORED and <BOAR</code> are not general for different board shapes, nor are the column headings adjustable. Similarly, subroutine UNPACK does not attempt to use a loop but employs explicit code.
| |||