10 Kasım 2012 Cumartesi

Puzzling Computers - 1 - Easy as ABC




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 there still isn't any change, we will choose any cell with more than one candidates, guess any of them, and check if this leads to a broken puzzle. If it doesn't, it will get True from isDone() at the end. If it does, it will return False and we will eliminate the guess.
            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 True
And 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.