Programming Classic 15 Puzzle in Python

Question

I'm new to python and trying to implement a non-gui version of the classic 15 puzzle in python.

Currently I have code which randomly generates a list containing 4 other lists each containing a number from 1 to 16 (I'm using 16 as the blank space.)

This is one example of a list generated:

[['11', '14', '01', '16'], ['02', '13', '09', '06'], ['04', '05', '03', '07'], ['10', '15', '12', '08']]

My questions are:

1. What would be the best way to implement a function to switch the position of two tiles if and only if they are adjacent to each other?
2. Is my method of nested lists an optimal way of representing the puzzle board?
3. Is a functional or object-oriented approach better? I was thinking that each tile could be represented as an object with a move method.

This is what I have currently:

#!/usr/bin/env python3
import random


class game:
    def __init__(self, array):
        self.array = array
        print (array)

    def objects(self):
        self.objects = []
        for i in self.array:
            if len(str(i)) == 1:
                i = '0'+str(i)
                self.objects.append(i)
            else:
                i = str(i)
                self.objects.append(i)
        print (self.objects)

    def grid(self):
        self.grid = [[], [], [], []]
        for eachrow in range(4):
            print ("row number", eachrow)


     for eachobject in range(4):
            print ("this is a list of objects before popping:\n{0}".format(self.objects))
            k = random.randint(0, len(self.objects)-1)
            print (k)
            self.grid[eachrow].append(self.objects.pop(k))
            print (self.grid)


def main():
    array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
    test = game(array)
    test.objects()
    test.grid()

if __name__ == "__main__":
    main()

Answer 1

Split your big problem into many small problems, and it will be easier to reason about.

Are you wanting to implement a program where a human plays the game?

If you want to ask about adjacent tiles, I would suggest a useful method to implement would be one that, given a square, gives you a list off all its adjacent squares.

Maybe you might also want a method which tells you which tiles are currently available to be moved (/swapped).

Maybe also one which tells you how far a tile is away from its home.

A tiles_to_correct() method could use that to tell you how many tiles still need to be moved to their correct position (i.e aren't 0 away from their home). finished() might then return True when tiles_to_correct() returns 0.

Implementing all these will likely at the very least help you think about and move towards writing your finished program, even if they don't directly help.

A 2D list should be fine to represent the problem while getting a working program. I would just go with that before trying optimize for speed. I wouldn't use strings for the tiles though, I would use numbers, and probably 0-15. If you want to display the board to the player its easy enough to write output code which adds 1 to the number if you want 1-16 to be displayed.

Answer 2

Answering your third question:

Is a functional or object-oriented approach better? I was thinking that each tile could be represented as an object with a move method.

I think that you should consider each approach depending on what you want to achieve.

If you want a clear design, you may want to model the problem with objects representing the behaviour of each entity of your problem (Tile, Game, EmptyTile, etc). It might not be the best performing system, though, as you may create many indirections. But you also may gain in reusability, modularity, etc.

In the other hand, if you want to focus in data and algorithms working over them, you should use an imperative approach (with the functional spice of python). As said before, this may be also faster as it deletes many layers of indirections.

Based on the (few) things you said, I would go on the OOP direction.

Of course, you can use Object Oriented Programming and do terrible code. And you can use imperative and create slow programs. It's up to you to do things in the right way.