15Puzzle-Python/Class.py at master · HugoDs21/15Puzzle-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import copy


class Tabuleiro:
    def __init__(self, arg, parent=None, depth=0):
        self.estado = arg
        self._findx()
        self.filhos = []
        self.backtrack = parent
        self.profundidade = depth


    def __hash__(self):
        return hash(''.join(self.estado))

    def __copy__(self):
        return Tabuleiro(self.estado)

    def __str__(self):
        text = """┌──┬──┬──┬──┐
│{}│{}│{}│{}│
├──┼──┼──┼──┤
│{}│{}│{}│{}│
├──┼──┼──┼──┤
│{}│{}│{}│{}│
├──┼──┼──┼──┤
│{}│{}│{}│{}│
└──┴──┴──┴──┘""" \
            .format(self.estado[0].rjust(2, '0'), self.estado[1].rjust(2, '0'), self.estado[2].rjust(2, '0'),
                    self.estado[3].rjust(2, '0'),
                    self.estado[4].rjust(2, '0'), self.estado[5].rjust(2, '0'), self.estado[6].rjust(2, '0'),
                    self.estado[7].rjust(2, '0'),
                    self.estado[8].rjust(2, '0'), self.estado[9].rjust(2, '0'), self.estado[10].rjust(2, '0'),
                    self.estado[11].rjust(2, '0'),
                    self.estado[12].rjust(2, '0'), self.estado[13].rjust(2, '0'), self.estado[14].rjust(2, '0'),
                    self.estado[15].rjust(2, '0')).replace("00", "  ")
        return text

    def __repr__(self):
        return str(self.estado)

    def __eq__(self, other):
        return self.estado == other

    def _findx(self):
        i = 0
        while self.estado[i] != '0':
            i += 1
        self.x, self.y = (int(i / 4), i % 4)

    def solvabilidade(self):
        # Par:1 ; Impar:0
        soma = 0
        for i in range(0, 16):
            for j in range(i + 1, 16):
                if self.estado[i] > self.estado[j] and self.estado[i] != '0' and self.estado[j] != '0':
                    soma += 1
        for i in range(0, 16):
            if self.estado[i] == '0':
                a = int(i / 4) % 2 == 0
                b = not (soma % 2 == 0)
                # print(i, soma)
                # print("a == b", a, b, a==b)
                self.solvable = (a == b)
                return self.solvable

    def getX(self):
        return self.x, self.y

    # Definicao dos movimentos
    def _left(self):
        move = copy.deepcopy(self.estado)
        btrack = copy.deepcopy(self.backtrack)
        if btrack is None:
            btrack = ['Left']
        else:
            btrack.append('Left')
        if self.y != 0:
            move[self.x * 4 + self.y] = move[self.x * 4 + self.y - 1]
            move[self.x * 4 + self.y - 1] = '0'
            tleft = Tabuleiro(move, parent=btrack, depth=self.profundidade + 1)
            self.filhos.append(tleft)

    def _right(self):
        move = copy.deepcopy(self.estado)
        btrack = copy.deepcopy(self.backtrack)
        if btrack is None:
            btrack = ['Right']
        else:
            btrack.append('Right')
        if self.y != 3:
            move[self.x * 4 + self.y] = move[self.x * 4 + self.y + 1]
            move[self.x * 4 + self.y + 1] = '0'
            tright = Tabuleiro(move, parent=btrack, depth=self.profundidade + 1)
            self.filhos.append(tright)

    def _up(self):
        move = copy.deepcopy(self.estado)
        btrack = copy.deepcopy(self.backtrack)
        if btrack is None:
            btrack = ['Up']
        else:
            btrack.append('Up')
        if self.x != 0:
            move[self.x * 4 + self.y] = move[(self.x - 1) * 4 + self.y]
            move[(self.x - 1) * 4 + self.y] = '0'
            tup = Tabuleiro(move, parent=btrack, depth=self.profundidade + 1)
            self.filhos.append(tup)

    def _down(self):
        move = copy.deepcopy(self.estado)
        btrack = copy.deepcopy(self.backtrack)
        if btrack is None:
            btrack = ['Down']
        else:
            btrack.append('Down')
        if self.x != 3:
            move[self.x * 4 + self.y] = move[(self.x + 1) * 4 + self.y]
            move[(self.x + 1) * 4 + self.y] = '0'
            tdown = Tabuleiro(move, parent=btrack, depth=self.profundidade + 1)
            self.filhos.append(tdown)

    def moves(self):
        if self.profundidade > 1:
            last = self.backtrack[self.profundidade-1]
        else:
            last = "0"
        if last != "Right":
            self._left()
        if last != "Left":
            self._right()
        if last != "Down":
            self._up()
        if last != "Up":
            self._down()
        return self.filhos