FilesExpand file tree

 master

/

fifteen_sq_wrong.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

121 lines (102 loc) · 2.78 KB

 master

/

fifteen_sq_wrong.py

Copy path

Top

File metadata and controls

• Code
• Blame

121 lines (102 loc) · 2.78 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# https://en.wikipedia.org/wiki/15_puzzle

# This is inefficient/wrong solution using the backtracking or depth first approach

# It leads to the stack overflow.

LEFT = (-1, 0)

RIGHT = (1, 0)

UP = (0, -1)

DOWN = (0, 1)

solution = range(1,16)

solution.append(0)

# find

def find_blank(mat):

for i in range(len(mat)):

if mat[i] == 0:

return i

def hash(mat):

return "_".join(map(lambda x: str(x), mat))

def toidx(i, j):

return i*4 + j

def toij(i):

return (i/4, i%4)

def copy_arr(mat):

state = []

for i in mat:

state.append(i)

return state

def add_tu(t1, t2):

return (t1[0] + t2[0], t1[1] + t2[1])

# Moves up

def step(mat, idx, di):

if mat[idx] != 0:

print("Ouch! mat at idx is not 0")

return -1;

(i, j) = toij(idx)

print("di: ", str(di))

print("(i,j) ", str((i,j)))

(ii, jj) = add_tu((i, j), di)

if ii < 0 or jj < 0 or ii > 3 or jj > 3:

return (None, False, -1)

state = copy_arr(mat)

newidx = toidx(ii, jj)

state[idx] = state[newidx]

state[newidx] = 0

return (state, True, newidx)

# mat is an array of 16 numbers. the 0 represents blank

# it should print steps of the movement of space: Up, Down, Left, Right

def solve_slow(mat, idx, visited, path = []):

print("=== Problem ===")

print_mat(mat)

print("-------------")

global LEFT, RIGHT, UP, DOWN, solution

if solution == mat:

# print(path)

return path;

#i = find_blank(mat)

for di in [LEFT, RIGHT, UP, DOWN]:

(state, can_move, newidx) = step(mat, idx, di)

if not can_move:

continue

state_str = hash(state)

if not state_str in visited:

visited[state_str] = True

path.append(di)

soln_path = solve(state, newidx, visited, path)

if soln_path:

return soln_path

path.pop()

return None

import sys

def print_mat(mat):

for i in range(4):

for j in range(4):

idx = i*4 + j

sys.stdout.write(str(mat[idx]) + ' ')

print('')

def solve_entry(mat):

visited = {}

visited[hash(mat)] = True

idx = find_blank(mat)

soln_path = solve(mat, idx, visited)

def to_str(di):

if di == LEFT:

return "LEFT"

if di == RIGHT:

return "RIGHT"

if di == UP:

return "UP"

if di == DOWN:

return "DOWN"

return " ERR "

def main():

mat_str = "10 5 4 3 0 2 11 6 1 7 15 12 9 13 8 14"

mat = map(lambda x: int(x), mat_str.split())

soln_path = solve_entry(mat)

print(" == Solution === ")

state = mat

idx = find_blank(mat)

for di in soln_path:

(state, can_move, idx) = step(state, idx, di)

print_mat(state)

print("-------------")

if __name__ == '__main__':

main()