'''
Sept 2016 Math Puzzler
Dave Vogel - 9/23/16
http://web.monroecc.edu/MathPuzzler/September16puzzle
Consider the rectangle below with dimensions 11 units by 12 units.
The challenge is to partition this rectangle (using only the gridlines
for edges) into 5 non-square rectangles so that no two rectangles have
a side length in common. The following example shows a failed
attempt since there are two rectangles that have a side of length 4.
a b
_______________________
|_|_|_|_|_|_|_|_1_|_|_|_|
|_|_|_|_|_|_|_|_1_|_|_|_|
h |_|_|_|_|_|_|_|_1_|_|_|_|
|_|_|_|_|_|_|_|_1_|_|_|_| c
|.|.|.1.|.|.|.|.1_|_|_|_|
|_|_|_1_|_|_|_|_1_|_|_|_|
|_|_|_1.|.|.|.|.1.|.|.|.|
|_|_|_1_|_|_|_|_|_|_|_|_|
g |_|_|_1_|_|_|_|_|_|_|_|_| d
|_|_|_1_|_|_|_|_|_|_|_|_|
|_|_|_1_|_|_|_|_|_|_|_|_|
f e
i and j represent the width and height of the inner rectangle, resp.
Since all rectangles must have unique sides and presuming the format of the
solution is formatted approximately as per the above then:
Search through the list of possibilities where the set (a, b, c, d, e, f,
g, h, i, j) contains 10 unique numbers in the range 1 - 12.
'''
import sys
if sys.version_info[0] < 3:
import Tkinter as tk
else:
import tkinter as tk
import time
class Rectangle:
'''
Rectangle
Defines a rectangle by its starting location (x, y) and its width,
height and fill color
'''
def __init__(self, x, y, w, h, c):
self.x = x
self.y = y
self.width = w
self.height = h
self.color = c
def __repr__(self):
'''
The text representation of a Rectangle. Used only during debugging
'''
return "x:" + str(self.x) + " y:" + str(self.y) + " width:" + \
str(self.width) + " height:" + str(self.height) + " color:" + self.color
##End class Rectangle############
class Solution:
'''
A Solution is a set of 5 Rectangles that satisfy the puzzle conditions. A
Solution hash is created from the length of each the periphery rectangles'
sides that constitute the periphery. Each of these sides is represented as
a single hex digit. The hash is used to remove the 'duplicates' which are
different only by rotation or reflection.
'''
def __init__(self, ul, ur, ll, lr, c):
'''
Add the 5 Rectangles to the Solution, create a "hash" that uniquely describes
the solution so that duplicates (rotated or reflected) can be ignored.
'''
self.upperLeft = ul #The upper left rectangle
self.upperRight = ur # ...
self.lowerLeft = ll
self.lowerRight = lr
self.center = c
#Create a text hash where each rectangle's side (around the puzzle perphery)
# is represented by a single hex digit.
a = hexDigit(self.upperLeft.width)
b = hexDigit(self.upperRight.width)
c = hexDigit(self.upperRight.height)
d = hexDigit(self.lowerRight.height)
e = hexDigit(self.lowerRight.width)
f = hexDigit(self.lowerLeft.width)
g = hexDigit(self.lowerLeft.height)
h = hexDigit(self.upperLeft.height)
tempHash = a + b + c + d + e + f + g + h
#Now make the mirror image
tempHashReflect = h + g + f + e + d + c + b + a
#Now we rotate the puzzle solution so the rectangle with the longest side
# is in the 'a' position so all possible rotations give the same hash
# Do this for both the solution hash and its mirror image (which is
# just a horizontal or vertical flip of another solution).
hashOrig = tempHash
hashReflect = tempHashReflect
for n in range(4):
#Simulate a 90 degree rotation of the solution and reflected solution
tempHash = tempHash[2:] + tempHash[:2]
tempHashReflect = tempHashReflect[2:] + tempHashReflect[:2]
#Force the longest rectangle to be in the 'a' position
if tempHash > hashOrig:
hashOrig = tempHash
if tempHashReflect > hashReflect:
hashReflect = tempHashReflect
#Now put the two hash components together to make a single
# hash. Again, put the larger one first so we generate the same
# hash for both a solution and its reflection
if hashOrig > hashReflect:
self.hash = hashOrig + hashReflect
else:
self.hash = hashReflect + hashOrig
def __repr__(self):
'''
A Solution 'toString' for debugging
'''
return str(self.upperLeft) + '; ' + str(self.upperRight) + '; ' \
+ str(self.lowerLeft) + '; ' + str(self.lowerRight) + '; ' \
+ str(self.center) + '\n\n'
def __hash__(self):
'''
Create an integer hash for the text hash string generated above
'''
return int(self.hash, 32)
def __eq__(self, val):
'''
Returns true if the two solutions are equal
'''
return val.hash == self.hash
def __ne__(self, val):
'''
Returns true if the two solutions are not equal
'''
return val.hash != self.hash
##End class Solution############
class RectDisplay(tk.Frame):
'''
UI to display the solutions to the puzzler. Buttons available to browse
through the solutions. A counter shows which solution is displayed
'''
def __init__(self, parent, solutions):
self.solutions = solutions #This object receives a list of Solutions to display
self.origin = 20 #Starting position in UI for grid (for both X and Y)
self.width = 20 #The size each grid square (for both X and Y)
self.solutionNo = 0 #Keeps track the solution number for multiple solutions
self.itemNo = tk.StringVar() #Displays which solution is being displayed
self.itemNo.set(" Solution: 1 ")
##Initialize the UI
self.parent = parent
tk.Frame.__init__(self, self.parent)
self.parent.title("9/2016 Math Puzzler")
self.pack(fill=tk.BOTH, expand=1)
self.canvas = tk.Canvas(self)
self.canvas.pack(fill=tk.BOTH, expand=1)
self.placeRectangles(self.solutions[0]) #Draw all the Rectangles for the first solution
self.drawGrid() #Draw the grid over the Rectangles
#Add the buttons to browse through the solutions
nextButton = tk.Button(self.parent, text="Next >", command = self.switchNext)
prevButton = tk.Button(self.parent, text="< Prev", command = self.switchPrev)
#Add a label to display which solution is being displayed
itemNumber = tk.Label(self.parent, textvariable=self.itemNo)
#Place the buttons/item number display
nextButton.pack(side=tk.LEFT)
itemNumber.pack(side=tk.LEFT)
prevButton.pack(side=tk.LEFT)
def drawGrid(self):
'''
Draw the 12x11 grid
'''
for n in range(13):
self.canvas.create_line(self.origin, n*self.width, 13*self.width, n*self.width)
for n in range(14):
self.canvas.create_line(n*self.width, self.origin, n*self.width, 12*self.width)
def clear(self):
'''
Clear the Canvas (grid and Rectangles)
'''
self.canvas.delete("all")
def placeRectangle(self, r):
'''
Received a Rectangle and draws in on the Canvas with lines that are
bolder than the grid and fill with the color defined in the Rectangle
'''
startx = self.origin + r.x * self.width
starty = self.origin + r.y * self.width
endx = startx + r.width * self.width
endy = starty + r.height * self.width
self.canvas.create_rectangle(startx, starty, endx, endy, width=2, \
fill=r.color)
def placeRectangles(self, solution):
'''
Received a Solution (list of Rectangles that represent one of the solutions
and calls placeRectangle to draw them on the Canvas. Then over-draw the grid.
'''
self.placeRectangle(solution.upperLeft)
self.placeRectangle(solution.upperRight)
self.placeRectangle(solution.lowerLeft)
self.placeRectangle(solution.lowerRight)
self.drawGrid()
def switchNext(self):
'''
When the next button is pushed: Draw the next solution and update the solution
number. If going past the last solution wrap to the first.
'''
self.clear()
self.solutionNo += 1
if self.solutionNo >= len(self.solutions):
self.solutionNo = 0
self.placeRectangles(self.solutions[self.solutionNo])
self.itemNo.set(" Solution: " + str(self.solutionNo + 1) + " ")
def switchPrev(self):
'''
When the Prev button is pushed: Draw the previous solution and update the solution
number. If going past the first solution wrap to the last.
'''
self.clear()
self.solutionNo -= 1
if self.solutionNo < 0:
self.solutionNo = len(self.solutions) - 1
self.placeRectangles(self.solutions[self.solutionNo])
self.itemNo.set(" Solution: " + str(self.solutionNo + 1) + " ")
##End class RectDisplay############
##Misc routines
def hexDigit(d):
'''
Convert the to a single hex string digit
'''
return '0123456789abcdef'[d]
##Main#####################################################################
if __name__ == "__main__":
solution = set() #A set containing the found solutions
#(By inspection) it seems that the only way to meet the "no two rectangles
# have a side length in common" is that the maximum component rectangle side
# be one less than the enclosing rectangle. so we'll use 10 and 11 as the
# limits and hence this algorithm.
puzzleWidth = 12
puzzleHeight = 11
minW = 1 #Rectangle's minimum width possible
maxW = puzzleWidth - 1 #Rectangle's maximum width possible
minH = 1 #Rectangle's minimum height possible
maxH = puzzleHeight - 1 #Rectangle's maximum height possible
widthRange = range(minW, maxW + 1) #Range of possible Rectangle widths
heightRange = range(minH, maxH +1) #Range of possible Rectangle lengths
#Test all possible Rectangle lengths and widths
for a in widthRange:
for c in heightRange:
for e in widthRange:
for g in heightRange:
for i in widthRange:
for j in heightRange:
#Force the edges to add up to 12 horizontal, 11 vertical
b = puzzleWidth - a
d = puzzleHeight - c
f = puzzleWidth - e
h = puzzleHeight - g
#Test overall width/height including center rectangle
if ((f + i + b == 12) & (h + j + d == 11)) or\
((a + i + e == 12) & (g + j + c == 11)): #This latter test is superfluous
# and just returns solutions that
# will be rejected as just
# rotations or reflections
#The set that contains the values of all the sides must
# be a length of 10 for all 10 to be different
if len(set([a,b,c,d,e,f,g,h,i,j])) == 10:
#If length is 10, then THIS is a solution; create the
# Rectangles
upperLeft = Rectangle(0, 0, a, h, 'green')
upperRight = Rectangle(a, 0, b, c, 'red')
lowerLeft = Rectangle(0, h, f, g, 'blue')
lowerRight = Rectangle(f, c, e, d, 'yellow')
center = Rectangle(f, h, i, j, 'white')
#Add this solution to the set of solutions
solution.add(Solution(upperLeft, upperRight, lowerLeft, lowerRight, center))
#All solutions are found, start the UI to display them
root = tk.Tk()
ui = RectDisplay(root, list(solution)) #Convert the Set of solutions to a list and
# send to the display UI
root.geometry("280x290+300+300")
ui.mainloop()