Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result
Blame Permalink
Sucessors.py 4.23 KiB
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
139
140 






def maze_successor(state):
    next_states = [(state[0] + 1, state[1]),
                   (state[0], state[1] + 1),
                   (state[0] - 1, state[1]),
                   (state[0], state[1] - 1)]
    next_states = [s for s in next_states if maze_allowed(s)]
    return next_states


def sudoku_successor(state):
    new_state = list(map(list, state))  # Convert state to a list of lists
    y, x = -1, -1
    for i, s in enumerate(state):
        if 0 in s:
            (y, x) = (i, s.index(0))
            break
    next_states = []
    for j in range(1, len(new_state) + 1):
        new_state[y][x] = j
        if sudoku_allowed((y, x, new_state)):
            next_states.append(tuple(map(tuple, new_state)))
    return next_states


def maze_allowed(state):
    maze = [[' ', 'W', ' ', ' ', 'G'],
            [' ', 'W', ' ', 'W', ' '],
            [' ', 'W', ' ', ' ', ' '],
            [' ', ' ', 'W', 'W', ' '],
            [' ', ' ', ' ', ' ', ' ']]
    if state[0] >= len(maze[0]) or state[0] < 0:
        return False
    if state[1] >= len(maze) or state[1] < 0:
        return False
    return maze[state[0]][state[1]] == ' ' or maze[state[0]][state[1]] == 'G'


def sudoku_allowed(state):
    (y, x, grid) = state
    """I'm making the state a triple on this one"""
    # (y, x, z): x,y is the coordinate and z is the value in the square

    # check if still inside the box
    if y < 0 or y >= len(grid[0]):
        return False
    if x < 0 or x >= len(grid):
        return False

    # inspect columns and rows
    if ([row[x] for row in grid].count(grid[y][x]) > 1) or (grid[y].count(grid[y][x]) > 1):
        return False

    # inspect minor square in teh sudoku
    inner_x = ((x - (x % 3)), (x - (x % 3) + 3))
    inner_y = (y - (y % 3))
    inner_square = grid[inner_y][inner_x[0]:inner_x[1]] + grid[inner_y + 1][inner_x[0]:inner_x[1]] + \
                   grid[inner_y + 2][inner_x[0]:inner_x[1]]
    if inner_square.count(grid[y][x]) > 1:
        return False

    return True


def puzzle_successor(state):
    y, x = -1, -1
    for i in range(len(state)):
        for j in range(len(state[i])):
            if state[i][j] == 0:
                y, x = i, j
                break
    
    possible_moves = [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
    next_states = []

    for move in possible_moves:
        new_y, new_x = move
        if 0 <= new_y < len(state) and 0 <= new_x < len(state[0]):
            # make a copy of the state
            new_state = [list(row) for row in state]
            # swap tiles
            new_state[y][x], new_state[new_y][new_x] = new_state[new_y][new_x], new_state[y][x]
            # Convert state to a tuple of tuples
            new_state_tuple = tuple(tuple(row) for row in new_state)
            if puzzle_allowed(new_state_tuple):
                next_states.append(new_state_tuple)

    return next_states


def queens_successor(state):
    new_state = list(map(list, state))  # Convert state to a list of lists
    y = -1
    for i in range(len(new_state)):
        if sum(new_state[i]) == 0:
            y = i
            break
    next_states = []
    for j in range(len(new_state[0])):
        new_state[y] = [False] * len(new_state[y])
        new_state[y][j] = True
        if queens_allowed((y, j, new_state)):
            next_states.append(tuple(map(tuple, new_state)))
    return next_states


def puzzle_allowed(state):
    return True


def queens_allowed(state):
    """in this case the state is also y, x, grid"""
    y, x, grid = state

    # check if still inside the box
    if y < 0 or y >= len(grid):
        return False
    if x < 0 or x >= len(grid[0]):
        return False

    # inspect columns and rows for queens
    if (sum([row[x] for row in grid]) > 1) or (sum(grid[y]) > 1):
        return False

    # inspect diagonal
    for i in range(1, len(grid)):

        # positive diagonal
        if x - i >= 0 and y - i >= 0 and grid[y - i][x - i]:
            return False
        if x + i < len(grid[0]) and y + i < len(grid) and grid[y + i][x + i]:
            return False

        # negative diagonal
        if x - i >= 0 and y + i < len(grid) and grid[y + i][x - i]:
            return False
        if x + i < len(grid[0]) and y - i >= 0 and grid[y - i][x + i]:
            return False

    return True