'''
2019 May Puzzler
Dave Vogel - 5/10/19 - dcvogel@gmail.com
In this puzzle, your goal is to divide the grid into rectangles in
such a way that each rectangle contains a single number and that number
must designate the number of cells comprising its rectangle. A
sample solution for a much smaller puzzle is shown to the right.
Can you solve this puzzle?
The following is a 10 rows x 20 columns of cells. The numbers indicate
the number of cells in a rectangle that contains that cell (C=12).
--9--2-6------8-----
------------8----6--
----6-----7---------
6------6--------6--4
----------9--C----2-
-----C-4-------8----
--6------6----4----4
-----------C----2---
------6-------6---8-
6---9---6-------4---
See here for a better picture of the puzzle:
https://sites.monroecc.edu/mathpuzzler/2019/05/01/may-2019-puzzle/
The approach below is as follows: There are 31 "small rectangles" that
contain a number which means there are 31 "big rectangles" to surround
them. The datafile contains possible "big rectangles" that can be made
from each. The rectangles are described in pseudo-Excel format
(upper left corner.lower right corner). If all possible big rectangles
are included there are far too many possibilities to test. After some
inspection, many of these can be proven to not be possible and can be
removed to make the search feasible.
First each pseudo-Excel "big rectangle" is converted to a list of
contained "small rectangles". Each of the possible combinations is
tested by creating a set of all the small rectangles from the 31
big rectanges. Once the set = 200, that is a solution since any
overlapping small rectangle will make the set short of 200.
'''
import graphics as g #Zelle's Graphics Module
# (https://mcsp.wartburg.edu//zelle/python/graphics.py)
# save to Python's Lib folder
import itertools as it
rectSize = 20 #Pixel size of the small rectangles
pos = rectSize / 2 #Position for the small rectangle size
xsize = 420 #X dimension for solution window
ysize = 220 #Y dimension for solution window
datafilename = 'defineRectangleSub.txt'
class LabeledRectangle():
'''
LabeledRectangle is a 'graphics' rectangle with a label. The label
is the size of the big rectangle in which it is contained.
'''
def __init__(self, x=0, y=0, label=''):
self.setPosition(x, y)
self.lbl = label
def draw(self, window):
'''
Create a 'graphics' rectange and draw the label
'''
self.rectangle = g.Rectangle(g.Point(self.x, self.y), g.Point(self.x+rectSize, self.y+rectSize))
self.label = g.Text(g.Point(self.x + pos, self.y + pos), self.lbl)
self.label.setSize(8)
self.rectangle.draw(window)
self.label.draw(window)
def setLabel(self, label):
'''
Setter for label
'''
self.lbl = label
def setPosition(self, x, y):
'''
Setter for position of the LabeledRectangle
'''
self.x = x * rectSize + pos
self.y = y * rectSize + pos
def __repr__(self):
return str(self.x) + " " + str(self.y) + " " + str(self.lbl) + " " +\
str(self.rectangle) + "\n"
def setFill(self, color):
'''
Setter for the fill color of a LabeledRectangle
'''
self.rectangle.setFill(color)
#End of LabeledRectangle
class BigRectangle():
'''
Rectangles that might represent pieces of the solution to the puzzle.
Each contain the number of small rectangles identified by the 'label'
'''
def __init__(self, name, size, possibilities):
self.name = name #The name is the Excel style address of small rectangle
# containing the size of the BigRectangle
self.size = size #The number of containing small rectangle
self.rectList = self.makeRects(possibilities)
def __repr__(self):
return str(self.name) + " " + str(self.size) + " " + str(self.possibilities) +\
"\n" + str(self.rectList) + "\n\n"
def convert(self, rect):
'''
Convert a pseudo-Excel representation of a range to a list of small
rectangles that are contained in the range. The psuedo-Excel code
has start and end rectangles separated by a period rather than a
colon. For example: a1.b2 is a range of the following cells:
a1, a2, b1 b2.
Returns a list of small rectangle coordiates
'''
rects = [] #List of small rectangles
start = rect.split('.')[0] #Cell in the upper-left corner of range
end = rect.split('.')[1] #Cell in the lower-right corner
startxy = decodePosition(start) #Decode Excel cell designation into
endxy = decodePosition(end) # a set of coordinates
for row in range(startxy[0], endxy[0]+1): #Make a list of all the
for col in range(startxy[1], endxy[1]+1): # cells contained in range
rects.append((row, col))
return rects
def makeRects(self, codeList):
'''
Receive a list of psuedu-Excel ranges return a list of lists of
coordinates represented by the ranges
'''
rects = []
for rect in codeList:
rects.append(self.convert(rect))
return rects
def showRect(self):
'''
Used only in testing of the datafile to visibly check for errors.
'''
for r in self.rectList[self.rectListPointer]:
rect[r[1]][r[0]].setFill('white')
self.rectListPointer += 1
if self.rectListPointer >= len(self.rectList):
self.rectListPointer = 0
for r in self.rectList[self.rectListPointer]:
rect[r[1]][r[0]].setFill('red')
def clearRect(self):
'''
Used only in testing of the datafile to visibly check for errors.
'''
for r in self.rectList[self.rectListPointer]:
rect[r[1]][r[0]].setFill('white')
#End of BigRectangle()
def decodePosition(code):
'''
Convert the Excel row/column designation to x, y coordinates for display.
Ex:
a1 => (0,0)
t10 => (19,9)
'''
x = ord(code[0:1]) - 97
y = int(code[1:]) - 1
return (x, y)
##########Main##############
if __name__ == '__main__':
datafile = open(datafilename, 'r')
numberOfPossibilities = 1
#Create the rectangles
rect = [[LabeledRectangle() for col in range(20)] for row in range(10)]
line = ' ' #Start the end of file flag not empty
bigRectangle = []
while(1):
rectCoords = []
line=datafile.readline()
if line[0:1] == "#":
continue
if line == '': #line is null at end of file
break
#Each dataline contains name of the big rectangle (small rectangle
# that contains its size), then the size, then a list of possible
# big rectangles that can be this big rectangle in the form of
# upper left corner <period> lower right corner. All separated by commas.
splitLine = line.split(',')
name = splitLine[0] #The BigRectangles name
size = splitLine[1] #The BigRectangles size
numberOfPossibilities *= (len(splitLine) - 2)
print(name, "\t", len(splitLine) - 2)
for n in splitLine[2:]: #The rest are BigRectable possibilities
rectCoords.append(n.strip()) #Make possibility list, remove whitespace
bigRectangle.append(BigRectangle(name, size, rectCoords))
print(numberOfPossibilities)
#quit()
for bRect in bigRectangle:
code = bRect.name
deCode = decodePosition(code)
x = deCode[0]
y = deCode[1]
(rect[y][x]).setLabel(bRect.size)
#Make an iterator of all possible combinations of bigRectangles
br = bigRectangle
possibilities = it.product(br[0].rectList, br[1].rectList, br[2].rectList, \
br[3].rectList, br[4].rectList, br[5].rectList, \
br[6].rectList, br[7].rectList, br[8].rectList, \
br[9].rectList, br[10].rectList, br[11].rectList, \
br[12].rectList, br[13].rectList, br[14].rectList, \
br[15].rectList, br[16].rectList, br[17].rectList, \
br[18].rectList, br[19].rectList, br[20].rectList, \
br[21].rectList, br[22].rectList, br[23].rectList, \
br[24].rectList, br[25].rectList, br[26].rectList, \
br[27].rectList, br[28].rectList, br[29].rectList, \
br[30].rectList)
win = [windows for windows in range(30)] #Make more than enough windows
#Each bigRectangle needs a unique color
colorNames = ['Aqua', 'Chartreuse', 'Beige', 'Blue', 'Brown', 'Coral', \
'Crimson', 'Cyan', 'Firebrick', 'Fuchsia', 'Gold', 'Gray', \
'Green', 'Honeydew', 'Indigo', 'Khaki', 'Lime', 'Magenta', \
'Maroon', 'Olive', 'Orange', 'Orchid', 'Red', 'Purple', \
'Plum', 'Pink', 'Sienna', 'Silver', 'Tan', 'Violet', 'Teal']
window = 0 #Each solution gets a separate window
#Make a set of all the little rectangles contained in the bigRectangles
# of this possible solution
for possibleSolution in possibilities:
complete = set()
for brCoord in possibleSolution: #For each bigRectangle coord list
complete.update(brCoord) # in the possible add the small
# rectangles coords to the set
if len(complete) == 200: # if the set contains 200 small
# rectangles, it is a solution
win[window] = \
g.GraphWin('', xsize, ysize) #Create a window to display
# the solution
for row in range(10): #Display the small rectangles
for col in range(20):
rect[row][col].setPosition(col, row)
rect[row][col].draw(win[window])
bigRectangleColor = 0 #Offset into the color array
for brCoord in possibleSolution: #For each bigRectangle coord list
for coord in brCoord: #For each coord, apply color
rect[coord[1]][coord[0]].setFill(colorNames[bigRectangleColor])
bigRectangleColor += 1
window += 1