Files
  • main.py
main.py
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
from random import randint,choice
from copy import deepcopy
weightedRand = [1,2,2,2,3,3,3,3,4,4,4,5,5,6]

def draw(grid):
    print("+ "*len(grid[0]) + "+") # Print the top of the grid

    for r in range(len(grid)):
        row = grid[r]
        print(" ", end="") # Print the start of the row

        for i in range(len(row)): # Print the row
            print(str(row[i][0]) + {1:"|",0:" "}[(row[i][1]//2)%2], end="") # (row[i][1]//2)%2 is East
        print("\n",end="")

        for i in range(len(row)): # Print the border beneath the row
            print("+" + {1:"-",0:" "}[(row[i][1]//4)%2], end="") # (row[i][1]//4)%2 is South
        print("+")

def create(height,width):
    grid = []
    for _ in range(height):
        grid.append([(None,0)]*width)
    used = []

    while True:
        blockSize = choice(weightedRand)

        selec = [choice([ (i,j) for i in range(height) for j in range(width) if (i,j) not in used ])] # Find a random unused cell
        grid[selec[0][0]][selec[0][1]] = (1,0) # Put a 1 in it
        #print("Started block from "+str(selec[0])+" with size "+str(blockSize))
        #print("Grid is now "+str(grid))

        # Grow the block
        for i in range(1,blockSize):

            availables = []
            # Determine the available cells
            for cell in selec: # For each cell in the selection
                for j in [(-1,0),(0,1),(1,0),(0,-1)]: # For each cell bordering that cell
                    #print("Checking if "+str((cell[0] + j[0], cell[1] + j[1]))+" is available")

                    if cell[0] + j[0] in range(height) and cell[1] + j[1] in range(width): # If the cell is in the grid
                        if (cell[0] + j[0], cell[1] + j[1]) not in used + selec + availables: # If the cell is not already used or in the selection or already counted
                            availables.append((cell[0] + j[0], cell[1] + j[1])) # Add the cell to the availables list
                            #print(str((cell[0] + j[0], cell[1] + j[1]))+" is available")
                        else:
                            #print(str((cell[0] + j[0], cell[1] + j[1]))+" is already used, in the selection, or marked as available")
                            pass
                    else:
                        #print(str((cell[0] + j[0], cell[1] + j[1]))+" is not in grid")
                        pass

            if len(availables) == 0: # Stop if there is nowhere to grow to
                #print("Nothing is available, ending block ")
                break

            chosen = choice(availables)
            selec.append(chosen) # Choose an available cell and add it to the selection
            grid[selec[i][0]][selec[i][1]] = (i+1,0) # Add a number to that cell
            #print(str(availables)+" are available")
            #print("Chosen "+str(chosen)+" and given it the number "+str(i+1))
            #print("Grid is now "+str(grid))


        #print("Finished block")
        used += selec

        # Draw the borders of the block
        for cell in selec: # For each cell in the selection
                for j in [(-1,0),(0,1),(1,0),(0,-1)]: # For each cell bordering that cell
                    if cell[0] + j[0] in range(height) and cell[1] + j[1] in range(width): # If the cell is in the grid
                        if (cell[0] + j[0], cell[1] + j[1]) not in selec: # If the cell is not in the selection
                            # Draw the border
                            if j == (-1,0): # Offset is North
                                grid[cell[0]][cell[1]] = (grid[cell[0]][cell[1]][0], grid[cell[0]][cell[1]][1] | 1) # North border for source
                                grid[cell[0]+j[0]][cell[1]+j[1]] = (grid[cell[0]+j[0]][cell[1]+j[1]][0], grid[cell[0]+j[0]][cell[1]+j[1]][1] | 4) # South border for target
                            elif j == (0,1): # Offset is East
                                grid[cell[0]][cell[1]] = (grid[cell[0]][cell[1]][0], grid[cell[0]][cell[1]][1] | 2) # East border for source
                                grid[cell[0]+j[0]][cell[1]+j[1]] = (grid[cell[0]+j[0]][cell[1]+j[1]][0], grid[cell[0]+j[0]][cell[1]+j[1]][1] | 8) # West border for target
                            elif j == (1,0): # Offset is South
                                grid[cell[0]][cell[1]] = (grid[cell[0]][cell[1]][0], grid[cell[0]][cell[1]][1] | 4) # South border for source
                                grid[cell[0]+j[0]][cell[1]+j[1]] = (grid[cell[0]+j[0]][cell[1]+j[1]][0], grid[cell[0]+j[0]][cell[1]+j[1]][1] | 1) # North border for target
                            elif j == (0,-1): # Offset is West
                                grid[cell[0]][cell[1]] = (grid[cell[0]][cell[1]][0], grid[cell[0]][cell[1]][1] | 8) # West border for source
                                grid[cell[0]+j[0]][cell[1]+j[1]] = (grid[cell[0]+j[0]][cell[1]+j[1]][0], grid[cell[0]+j[0]][cell[1]+j[1]][1] | 2) # East border for target

        #print("Borders drawn, grid is now "+str(grid))


        if len(used) == width * height:
            #print("All cells used, grid finished")
            break

    return grid

def isBlock(grid,coords):
    if sorted( [grid[i[0]][i[1]][0] for i in coords] ) != [i for i in range(1,len(coords)+1)]: # Do the numbers form a valid block
        return False

    # Are the cells continuously connected
    selec = [coords[0]]
    while True:
            availables = []
            # Determine the available cells
            for cell in selec: # For each cell in the selection
                for j in [(-1,0),(0,1),(1,0),(0,-1)]: # For each cell bordering that cell
                    if (cell[0] + j[0], cell[1] + j[1]) in coords: # If the cell is in the list of cells to absorb
                        if (cell[0] + j[0], cell[1] + j[1]) not in selec + availables: # If the cell is not already in the selection or already counted
                            if grid[cell[0]][cell[1]][1]//{(-1,0):1,(0,1):2,(1,0):4,(0,-1):8}[j]%2 == 0: #If the cell is not blocked by a wall
                                availables.append((cell[0] + j[0], cell[1] + j[1])) # Add the cell to the availables list

            if len(availables) == 0: # If there is nowhere to grow to, then check if all the cells are absorbed
                if len(selec) == len(coords):
                    return True # All the cells are continuously connected
                else:
                    return False # The cells are not continuously connected

            selec += availables # Absorb the adjacent cells


def waysToGrab(unplaced,thingsToGrab):
    # Start with a list, then multiply it by the number of ways to grab each number to grab
    possibilities = [[]]
    for i in thingsToGrab:
        possibilities = [k + [j] for j in unplaced[i] for k in possibilities]
    return possibilities

def findPossibleBlocks(grid,placed,cell):
    # Find all the 1s, all the 2s, etc
    unplaced = {}
    # Initialise the array first to prevent errors, then populate it
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            unplaced[grid[i][j][0]] = []

    for i in range(len(grid)):
        for j in range(len(grid[i])):
            unplaced[grid[i][j][0]].append((i,j))

    # Accumulate a list of all possibilities. The loop iterates through each possibility of which numbers are grabbed
    totalPoss = waysToGrab(unplaced,range(1,grid[cell[0]][cell[1]][0]))
    for i in range(grid[cell[0]][cell[1]][0]+1, max(unplaced.keys())+1):
        totalPoss += waysToGrab(unplaced, [j for j in range(1,grid[cell[0]][cell[1]][0])] + [j for j in range(grid[cell[0]][cell[1]][0]+1,i+1)])

    # Check if the blocks are valid
    validBlocks = []
    for i in totalPoss:
        if isBlock(grid,[cell]+i):
            validBlocks.append([cell]+i)
    return validBlocks


def isInValidBlock(grid,row,col):
    # Determine the block that that cell is in
    selec = [(row,col)]

    while True:
        availables = []
        # Determine the available cells
        for cell in selec: # For each cell in the selection
            for j in [(-1,0),(0,1),(1,0),(0,-1)]: # For each cell bordering that cell
                if cell[0] + j[0] in range(len(grid)) and cell[1] + j[1] in range(len(grid[0])): # If the cell is in the grid
                    if (cell[0] + j[0], cell[1] + j[1]) not in selec + availables: # If the cell is not already in the selection or already counted
                        if grid[cell[0]][cell[1]][1]//{(-1,0):1,(0,1):2,(1,0):4,(0,-1):8}[j]%2 == 0: #If the cell is not blocked by a wall
                            availables.append((cell[0] + j[0], cell[1] + j[1])) # Add the cell to the availables list

        if len(availables) == 0: # If there are no available cells and the block is complete
            break

        selec += availables

    # After determining the block, return whether the block is valid or not
    return sorted( [grid[i[0]][i[1]][0] for i in selec] ) == [i for i in range(1,len(selec)+1)]


def solve(grid):
    toReturn = []

    # Determine the cells that are not in a valid block
    unfCells = []
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            if not isInValidBlock(grid,row,col):
                unfCells.append((row,col))

    # If all cells are in valid blocks, grid is solved
    if len(unfCells) == 0:
        toReturn.append(grid)
        return toReturn

    nextSteps = findPossibleBlocks(grid,[(row,col) for col in range(len(grid[row])) for row in range(len(grid)) if (row,col) not in unfCells],unfCells[0]) # Determine the possible blocks for the next unfinished cell

    for selec in nextSteps:
        # Assemble a temporary grid with the necessary borders added
        tempgrid = deepcopy(grid)

        for cell in selec: # For each cell in the selection (the proposed next step for drawing a block)
                for j in [(-1,0),(0,1),(1,0),(0,-1)]: # For each cell bordering that cell
                    if cell[0] + j[0] in range(len(tempgrid)) and cell[1] + j[1] in range(len(tempgrid[0])): # If the cell is in the grid
                        if (cell[0] + j[0], cell[1] + j[1]) not in selec: # If the cell is not in the selection
                            # Draw the border
                            if j == (-1,0): # Offset is North
                                tempgrid[cell[0]][cell[1]] = (tempgrid[cell[0]][cell[1]][0], tempgrid[cell[0]][cell[1]][1] | 1) # North border for source
                                tempgrid[cell[0]+j[0]][cell[1]+j[1]] = (tempgrid[cell[0]+j[0]][cell[1]+j[1]][0], tempgrid[cell[0]+j[0]][cell[1]+j[1]][1] | 4) # South border for target
                            elif j == (0,1): # Offset is East
                                tempgrid[cell[0]][cell[1]] = (tempgrid[cell[0]][cell[1]][0], tempgrid[cell[0]][cell[1]][1] | 2) # East border for source
                                tempgrid[cell[0]+j[0]][cell[1]+j[1]] = (tempgrid[cell[0]+j[0]][cell[1]+j[1]][0], tempgrid[cell[0]+j[0]][cell[1]+j[1]][1] | 8) # West border for target
                            elif j == (1,0): # Offset is South
                                tempgrid[cell[0]][cell[1]] = (tempgrid[cell[0]][cell[1]][0], tempgrid[cell[0]][cell[1]][1] | 4) # South border for source
                                tempgrid[cell[0]+j[0]][cell[1]+j[1]] = (tempgrid[cell[0]+j[0]][cell[1]+j[1]][0], tempgrid[cell[0]+j[0]][cell[1]+j[1]][1] | 1) # North border for target
                            elif j == (0,-1): # Offset is West
                                tempgrid[cell[0]][cell[1]] = (tempgrid[cell[0]][cell[1]][0], tempgrid[cell[0]][cell[1]][1] | 8) # West border for source
                                tempgrid[cell[0]+j[0]][cell[1]+j[1]] = (tempgrid[cell[0]+j[0]][cell[1]+j[1]][0], tempgrid[cell[0]+j[0]][cell[1]+j[1]][1] | 2) # East border for target

        # Run self further down the tree
        toReturn += solve(tempgrid)

    return toReturn


def bruteSet(height,width,target,drawSolution=True):
    grid = create(height,width)
    if drawSolution:
        draw(grid)
        print("\n\n")

    # Accumulate a list of boundaries in the grid
    boundaries = []
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            if (grid[row][col][1]//2) % 2 == 1: # East boundaries
                boundaries.append((row,col,2))
            if (grid[row][col][1]//4) % 2 == 1: # South boundaries
                boundaries.append((row,col,4))

    boundsRemoved = 0
    while True:
        # If the target number of boundaries has been removed, return the grid
        if target != "fiendish":
            if boundsRemoved >= target:
                return grid

        # Remove a random boundary
        if len(boundaries) == 0:
            return grid

        boundary = choice(boundaries)
        #print("Trying to remove boundary "+str(boundary))
        grid[boundary[0]][boundary[1]] = (grid[boundary[0]][boundary[1]][0], grid[boundary[0]][boundary[1]][1] & (15-boundary[2])) # Assigns the 2s or 4s digit to zero, depending on what is necessary
        if boundary[2] == 2: # Assign the boundary of the cell on the other side
            grid[boundary[0]][boundary[1]+1] = (grid[boundary[0]][boundary[1]+1][0], grid[boundary[0]][boundary[1]+1][1] & 7)
        elif boundary[2] == 4:
            grid[boundary[0]+1][boundary[1]] = (grid[boundary[0]+1][boundary[1]][0], grid[boundary[0]+1][boundary[1]][1] & 14)

        # If not uniquely solvable, put back the border
        sols = len(solve(grid))
        if sols != 1:
            #print("Not uniquely solvable, putting back boundary")
            #print("Got "+str(sols)+" solutions")

            grid[boundary[0]][boundary[1]] = (grid[boundary[0]][boundary[1]][0], grid[boundary[0]][boundary[1]][1] | (boundary[2])) # Assigns the 2s or 4s digit to one, depending on what is necessary
            if boundary[2] == 2: # Assign the boundary of the cell on the other side
                grid[boundary[0]][boundary[1]+1] = (grid[boundary[0]][boundary[1]+1][0], grid[boundary[0]][boundary[1]+1][1] | 8)
            elif boundary[2] == 4:
                grid[boundary[0]+1][boundary[1]] = (grid[boundary[0]+1][boundary[1]][0], grid[boundary[0]+1][boundary[1]][1] | 1)


        # Update the list
        boundaries.remove(boundary)
        if sols == 1:
            #print("Successfully removed")
            boundsRemoved += 1


draw(bruteSet(5,5,"fiendish"))
Python 3.6.1 (default, Dec 2015, 13:05:11) [GCC 4.8.2] on linux