Enter the letters from 'A' to 'C' into the diagram, so that in every row and every column every letter occurs exactly once; in every row and every column one field remains empty. The letters at the borders indicate the letter that comes first in the corresponding row or column.[1]
Easy as ABC is a simple puzzle and a good starting point for our journey. We'll be using Python 2.7 all the time. If you are using a linux distro, it is probably already installed. (On arch linux you need to install and run python2). If you are on Windows, it is available for download here.
There are many variations of this puzzle, but we will just be solving the usual one.
Let's begin. We firstly need to create the puzzle and get user input.
class ABCPuzzle(object):
def __init__(self, size, letterCount):
self.count = letterCount
self.size = size
This should be clear. The puzzle is a square, so it has a size and a number of letters will be placed in each row and column. Now we can get the user input. The classical Easy as ABC puzzle begins with an empty matrix and clues on four sides. We will store the clues as integers. (We will implement all letters as numbers) So we can use loops in an easier a more effective way. So, we need to get input as a string (containing letters and spaces) and convert to an array of integers.
def getInput(self):
horizontalUpper = raw_input("Horizantal ^ (0 for empty):")
horizontalBottom = raw_input("Horizantal v (0 for empty):")
verticalLeft = raw_input("Vertical < (0 for empty):")
verticalRight = raw_input("Vertical > (0 for empty):")
self.horizontalUpper = []
self.horizontalBottom = []
self.verticalLeft = []
self.verticalRight = []
keys = {" ":0,"A":1,"B":2,"C":3,"D":4,"E":5}
for i in horizontalUpper:
self.horizontalUpper.append(keys[i])
for i in horizontalBottom:
self.horizontalBottom.append(keys[i])
for i in verticalLeft:
self.verticalLeft.append(keys[i])
for i in verticalRight:
self.verticalRight.append(keys[i])
This just works for puzzles with letter from a to e, but in order to keep it simple, I avoided a few tricks with ascii values and used a simple dictionary instead. If you like to, you can expand the code to support puzzles with more letters.
self.getInput()
We add this line to end of the __init__() function for obvious reasons.
We will begin with a matrix of all available numbers for each coordinate and eliminate them step by step.
def createPossibleMatrix(self):
self.possible = []
for i in range(self.size):
self.possible.append([])
for j in range(self.size):
self.possible[-1].append([])
for k in range(self.count+1):
self.possible[-1][-1].append(k)
This function creates a 3-dimensional array. First two dimensions are the coordinates and third is an array of possible numbers (letters)
There are many combinations of a row or a column. For any cell, if there is no valid combination with a certain number in it for its row or column, it means that this cell doesn't contain this number. Instead of creating this combinations again and again, it is better to create them at the beginning and iterate through this array when we need to.
def createCombinations(self):
combinations = [[]]
for number in range(self.count):
newCombs = []
for adress in range(self.size):
for comb in combinations:
if not adress in comb:
newCombs.append(comb + [adress])
combinations = newCombs
self.lines = []
for comb in combinations:
self.lines.append(self.size * [0])
for number in range(self.count):
self.lines[-1][comb[number]] = number + 1
The first loop creates an array of arrays, which hold each numbers (letter) index. The second one converts it into another array of array, which represent either a column or a row. For example [1,2,4] is converted to [0,1,2,0,3].
The first part is a little tricky. It firstly creates and array with all possible indexes for 1 (A). For example, if size is 3, the creates array is [[0],[1],[2]]. Then for the next number, all possible indexes are added to each element. The result is [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]. With each new number, they get longer by one element and the number of array is multiplied by count-n, where n represents the new number.
Then we call those two functions by adding these lines to __init__()
self.createCombinations()
self.createPossibleMatrix()
Now we are ready to start solving the puzzle
def solve(self, pmap=None):
if pmap==None:
pmap = []
for i in range(self.size):
pmap.append([])
for j in range(self.size):
pmap[-1].append(self.possible[i][j][:])
At this point, I should explain why the function is called with a pmap paramater. For some puzzles, we may need to use brute-force (yeah, not elegant, but it work pretty well) on some imaginary maps, so it is nice when the function is callable with maps other than self.possible. For the first call, this is not the case so we copy self.possible to pmap.
We need to iterate over self.possible again and again until we are done. Question is, when are we done? Answer is simple, when there is only one possible number for each cell. So, let's write an "is Done" function.
def isDone(self, pmap):
for i in range(self.size):
for j in range(self.size):
if len(pmap[i][j])>1:
return False
return True
Then, we will do the eliminations as long as we aren't done. We also need to check, whether a change has been made on self.possible. If not, we will need to think of something else (brute force :) ) as nothing would change the next time we go over the same array.
change = True
while not self.isDone(pmap):
if self.isBroken(pmap):
return False
if change:
So, this one is a good beginning for the solve function. That isBroken function returns True, if an impossible map is created, like a map with cells with no possible entry.
def isBroken(self, pmap):
for i in range(self.size):
for j in range(self.size):
if len(pmap[i][j])==0:
return True
return False
isBroken can return True, only when a cell is given a wrong value when using brute force. Otherwise the right value for the cell wouldn't be eliminated as long as the puzzle is a valid one. When a wrong guess is inserted in a cell, we create an invalid puzzle, which leads in long term to a broken one. If a guess is right, whole puzzle will be solved without getting broken, so if solve function returns False, it means we have been trying a wrong number for a cell.
Let's think of how to eliminate numbers without using brute force. Easy as ABC is Sudoku-like and the easiest method of eliminating numbers is checking the rows and columns and seeing whether it is repeated.
if change:
change = False
for i in range(self.size):
for j in range(self.size):
for k in pmap[i][j]:
if k:
if not self.simpleCheckCell(i,j,k, pmap):
change = True
pmap[i][j].remove(k)
For all cells (pmap[i][j]), all numbers excluding 0 checked, and the impossible ones are removed. If at least one candidate is eliminated, change is set to True and all cells will be check one more time. Else, we will have to use some other methods, as this one can't solve the whole puzzle. (For example, at the beginning, no candidate can be eliminated this way). But this one is much much lighter than checking all combinations of a line, so it speed up the solving process a bit.
def simpleCheckCell(self, x,y,guess, pmap):
for iy in range(self.size):
if pmap[x][iy] == [guess] and iy!=y:
return False
for ix in range(self.size):
if pmap[ix][y] == [guess] and ix!=x:
return False
return True
Now, for each cell, we will check whether there is at least one valid combination of the column and the row. If we can eliminate a candidate this way, we will go back to simple scan. Otherwise, we will have to use brute force.
if not change:
change = False
for i in range(self.size):
for j in range(self.size):
for k in range(self.count+1):
if k in pmap[i][j]:
if not self.checkCell(i,j,k, pmap):
change = True
pmap[i][j].remove(k)
The checkCell function checks is there a valid combination
def checkCell(self, x, y, guess, pmap = None):
return self.checkVertical(x,y, guess, pmap) and self.checkHorizontal(x,y,guess, pmap)
def checkHorizontal(self, x, y, guess, pmap = None):
if pmap == None:
pmap = []
for i in range(self.size):
pmap.append([])
for j in range(self.size):
pmap[-1].append(self.possible[i][j][:])
validCombExists = False
for comb in self.lines:
if comb[y] == guess:
combIsValid = True
for i in range (self.size):
number = comb[i]
if not (number in pmap[x][i]):
combIsValid = False
if combIsValid:
#check sides
upValid = False
bottomValid = False
if self.horizontalUpper[x]:
checkingSide = True
if getFirst(comb) == self.horizontalUpper[x]:
upValid = True
else:
continue
else:
upValid = True
if self.horizontalBottom[x]:
checkingSide = True
if getLast(comb) == self.horizontalBottom[x]:
bottomValid = True
else:
continue
else:
bottomValid = True
validCombExists = upValid and bottomValid
if validCombExists:
return True
else:
continue
return validCombExists
def checkVertical(self, x, y, guess, pmap = None):
if pmap == None:
pmap = []
for i in range(self.size):
pmap.append([])
for j in range(self.size):
pmap[-1].append(self.possible[i][j][:])
validCombExists = False
for comb in self.lines:
if comb[x] == guess:
combIsValid = True
for i in range (self.size):
if not (comb[i] in pmap[i][y]):
combIsValid = False
if combIsValid:
#check sides
leftValid = False
rightValid = False
if self.verticalLeft[y]:
checkingSide = True
if getFirst(comb) == self.verticalLeft[y]:
leftValid = True
else:
continue
else:
leftValid = True
if self.verticalRight[y]:
checkingSide = True
if getLast(comb) == self.verticalRight[y]:
rightValid = True
else:
continue
else:
rightValid = True
validCombExists = leftValid and rightValid
if validCombExists:
return True
else:
continue
return validCombExists
if not change:
x,y = self.getDoubtCell(pmap)
newmap = []
for x0 in range(self.size):
newmap.append([])
for y0 in range(self.size):
newmap[-1].append(pmap[x0][y0][:])
newmap[x][y] = [pmap[x][y][0]]
if self.solve(newmap):
return True
else:
pmap[x][y].remove(pmap[x][y][0])
change = True
So we copy the map, insert our guess and call the function again. The getDoubtCell function follows:
def getDoubtCell(self, pmap):
for i in range(self.size):
for j in range(self.size):
if len(pmap[i][j])>1:
return i,j
return False
So, only one little step left, displaying our victory!
def showSolution(self, pmap):
keys = {0:" ",1:"A",2:"B",3:"C",4:"D",5:"E"}
for y in range(self.size):
l = ""
for x in range(self.size):
l += keys[pmap[x][y][0]]
print l
Call this at the end of self.solve:
self.showSolution(pmap) return TrueAnd finally, a few more lines to run it:
size = input("size:")
rang = input("range:")
start = time()
a = ABCPuzzle(size,rang)
end = time()
print "Solved in %s seconds" %(end-start)
Lets test the example:
CBA CBA CBA A CB BA C Solved in 0.0127110481262 seconds
Feels good. In almost 1% of a second. Try easier and harder ones to see the results. You will need to make the program get input from a file instead of the keyboard to keep track of time. On arch-linux I simply run:
python2 main.py < inputfile
After typing everything in inputfile. So this was it. But there are still many things to be done. You can modify the input and output parts to show and get more letters than A to E. You can try to make it run faster. You can clean the code (for example check horizontal and check vertical could be the same function). I have left some little modifications that would speed it up to keep it simple, so you should be able to do soma changes. (For example you can add a few tricks like eliminating others if a number is only one cells candidate in a row). Please feel free to mail me your code (modifications, totally new algorithms), suggestions and please report any mistake you've noticed. As next, I will be solving Skyscrapers with some small changes on this one, so if you like to do it yourself, have fun! By the way, you can download the code is available for download here.
python2 main.py < inputfile
After typing everything in inputfile. So this was it. But there are still many things to be done. You can modify the input and output parts to show and get more letters than A to E. You can try to make it run faster. You can clean the code (for example check horizontal and check vertical could be the same function). I have left some little modifications that would speed it up to keep it simple, so you should be able to do soma changes. (For example you can add a few tricks like eliminating others if a number is only one cells candidate in a row). Please feel free to mail me your code (modifications, totally new algorithms), suggestions and please report any mistake you've noticed. As next, I will be solving Skyscrapers with some small changes on this one, so if you like to do it yourself, have fun! By the way, you can download the code is available for download here.
