Discrete : add 06-puzzle-challenge assignment

6 files changed, 312 insertions, 0 deletions

diff --git a/06-puzzle-challenge/allIntervalSeriesSolver.py b/06-puzzle-challenge/allIntervalSeriesSolver.py
new file mode 100755
index 0000000..9f973fd
--- /dev/null
+++ b/06-puzzle-challenge/allIntervalSeriesSolver.py
@@ -0,0 +1,72 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+def solveIt(n):
+    # Modify this code to run your puzzle solving algorithm
+    
+    # define the domains of all the variables (0..n-1)
+    domains = [range(0,n)]*n
+    
+    # start a trivial depth first search for a solution
+    sol = tryall([],domains)
+    
+    # prepare the solution in the specified output format
+    # if no solution is found, put 0s
+    outputData = str(n) + '\n'
+    if sol == None:
+        print 'no solution found.'
+        outputData += ' '.join(map(str, [0]*n))+'\n'
+    else: 
+        outputData += ' '.join(map(str, sol))+'\n'
+    
+    return outputData
+
+
+# this is a depth first search of all assignments
+def tryall(assignment, domains):
+    # base-case: if the domains list is empty, all values are assigned
+    # check if it is a solution, return None if it is not
+    if len(domains) == 0:
+        if checkIt(assignment):
+            return assignment
+        else:
+            return None
+    
+    # recursive-case: try each value in the next domain
+    # if we find a solution return it. otherwise, try the next value
+    else:
+        for v in domains[0]:
+            sol = tryall(assignment[:]+[v],domains[1:])
+            if sol != None:
+                return sol
+
+
+# checks if an assignment is feasible
+def checkIt(sol):
+    n = len(sol)
+    
+    items = set(sol)
+    if len(items) != n:
+        return False
+    
+    deltas = set([abs(sol[i]-sol[i+1]) for i in range(0,n-1)])
+    if len(deltas) != n-1:
+        return False
+    
+    return True
+
+
+import sys
+
+if __name__ == "__main__":
+    if len(sys.argv) > 1:
+        try:
+            n = int(sys.argv[1].strip())
+        except:
+            print sys.argv[1].strip(), 'is not an integer'
+        print 'Solving Size:', n
+        print(solveIt(n))
+
+    else:
+        print('This test requires an instance size.  Please select the size of problem to solve. (i.e. python allIntervalSeriesSolver.py 5)')
+
diff --git a/06-puzzle-challenge/handout.pdf b/06-puzzle-challenge/handout.pdf
new file mode 100644
index 0000000..9eca6bd
--- /dev/null
+++ b/06-puzzle-challenge/handout.pdf
diff --git a/06-puzzle-challenge/magicSeriesSolver.py b/06-puzzle-challenge/magicSeriesSolver.py
new file mode 100755
index 0000000..0d68803
--- /dev/null
+++ b/06-puzzle-challenge/magicSeriesSolver.py
@@ -0,0 +1,71 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+def solveIt(n):
+    # Modify this code to run your puzzle solving algorithm
+    
+    # define the domains of all the variables (0..n-1)
+    domains = [range(0,n)]*n
+    
+    # start a trivial depth first search for a solution
+    sol = tryall([],domains)
+    
+    # prepare the solution in the specified output format
+    # if no solution is found, put 0s
+    outputData = str(n) + '\n'
+    if sol == None:
+        print 'no solution found.'
+        outputData += ' '.join(map(str, [0]*n))+'\n'
+    else: 
+        outputData += ' '.join(map(str, sol))+'\n'
+        
+    return outputData
+
+
+# this is a depth first search of all assignments
+def tryall(assignment, domains):
+    # base-case: if the domains list is empty, all values are assigned
+    # check if it is a solution, return None if it is not
+    if len(domains) == 0:
+        if checkIt(assignment):
+            return assignment
+        else:
+            return None
+    
+    # recursive-case: try each value in the next domain
+    # if we find a solution return it. otherwise, try the next value
+    else:
+        for v in domains[0]:
+            sol = tryall(assignment[:]+[v],domains[1:])
+            if sol != None:
+                return sol
+
+
+# checks if an assignment is feasible
+def checkIt(sol):
+    n = len(sol)
+    count = {}
+    for i in range(0,n):
+        count[i] = 0
+    for i in range(0,n):
+        count[sol[i]] += 1
+    for i in range(0,n):
+        if sol[i] != count[i]:
+            return False
+    return True
+
+
+import sys
+
+if __name__ == "__main__":
+    if len(sys.argv) > 1:
+        try:
+            n = int(sys.argv[1].strip())
+        except:
+            print sys.argv[1].strip(), 'is not an integer'
+        print 'Solving Size:', n
+        print(solveIt(n))
+
+    else:
+        print('This test requires an instance size.  Please select the size of problem to solve. (i.e. python magicSeriesSolver.py 5)')
+
diff --git a/06-puzzle-challenge/magicSquareSolver.py b/06-puzzle-challenge/magicSquareSolver.py
new file mode 100755
index 0000000..ea69e8d
--- /dev/null
+++ b/06-puzzle-challenge/magicSquareSolver.py
@@ -0,0 +1,100 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+def solveIt(n):
+    # Modify this code to run your puzzle solving algorithm
+    
+    # to be consistent with other example code, we will
+    # represent the decision variables as an array (not a matrix)
+    # there is no need to do this in your solver
+    
+    # define the domains of all the variables (1..n*n)
+    domains = [range(1,n*n+1)]*(n*n)
+    
+    # start a trivial depth first search for a solution
+    sol = tryall([],domains)
+    
+    # prepare the solution in the specified output format
+    # if no solution is found, put 0s
+    outputData = str(n) + '\n'
+    if sol == None:
+        print 'no solution found.'
+        for i in range(0,n):
+            outputData += ' '.join(map(str, [0]*n))+'\n'
+    else: 
+        for i in range(0,n):
+            outputData += ' '.join(map(str, sol[i*n:(i+1)*n]))+'\n'
+    
+    return outputData
+
+
+# this is a depth first search of all assignments
+def tryall(assignment, domains):
+    # base-case: if the domains list is empty, all values are assigned
+    # check if it is a solution, return None if it is not
+    if len(domains) == 0:
+        if checkIt(assignment):
+            return assignment
+        else:
+            return None
+    
+    # recursive-case: try each value in the next domain
+    # if we find a solution return it. otherwise, try the next value
+    else:
+        for v in domains[0]:
+            if not v in assignment:
+                sol = tryall(assignment[:]+[v],domains[1:])
+                if sol != None:
+                    return sol
+
+
+# checks if an assignment is feasible
+# because sol is an array (not a matrix), checks are more cryptic
+import math
+def checkIt(sol):
+    n = int(math.sqrt(len(sol)))
+    m = n*(n*n+1)/2
+    
+    #for i in range(0,n):
+    #    print sol[i*n:(i+1)*n]
+    
+    items = set(sol)
+    if len(items) != len(sol):
+        #print len(items),len(sol) 
+        return False
+    
+    for i in range(0,n):
+        #print 'row',i,sol[i*n:(i+1)*n]
+        if sum(sol[i*n:(i+1)*n]) != m:
+            return False
+        #print 'column',i,sol[i:len(sol):n]
+        if sum(sol[i:len(sol):n]) != m:
+            return False
+        if i < n-1:
+            if sol[i*n+i] > sol[(i+1)*n+(i+1)]:
+                return False 
+    
+    #print 'diag 1',i,[sol[i*n+i] for i in range(0,n)]
+    if sum([sol[i*n+i] for i in range(0,n)]) != m:
+        return False
+    #print 'diag 2',i,[sol[i*n+(n-i-1)] for i in range(0,n)]
+    if sum([sol[i*n+(n-i-1)] for i in range(0,n)]) != m:
+        return False
+    
+    return True
+
+
+import sys
+
+if __name__ == "__main__":
+    if len(sys.argv) > 1:
+        try:
+            n = int(sys.argv[1].strip())
+        except:
+            print sys.argv[1].strip(), 'is not an integer'
+        print 'Solving Size:', n
+        print(solveIt(n))
+    
+    else:
+        print('This test requires an instance size.  Please select the size of problem to solve. (i.e. python magicSquareSolver.py 3)')
+
diff --git a/06-puzzle-challenge/queensSolver.py b/06-puzzle-challenge/queensSolver.py
new file mode 100755
index 0000000..b23c178
--- /dev/null
+++ b/06-puzzle-challenge/queensSolver.py
@@ -0,0 +1,69 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+def solveIt(n):
+    # Modify this code to run your puzzle solving algorithm
+    
+    # define the domains of all the variables (0..n-1)
+    domains = [range(0,n)]*n
+    
+    # start a trivial depth first search for a solution
+    sol = tryall([],domains)
+    
+    # prepare the solution in the specified output format
+    # if no solution is found, put 0s
+    outputData = str(n) + '\n'
+    if sol == None:
+        print 'no solution found.'
+        outputData += ' '.join(map(str, [0]*n))+'\n'
+    else: 
+        outputData += ' '.join(map(str, sol))+'\n'
+        
+    return outputData
+
+
+# this is a depth first search of all assignments
+def tryall(assignment, domains):
+    # base-case: if the domains list is empty, all values are assigned
+    # check if it is a solution, return None if it is not
+    if len(domains) == 0:
+        if checkIt(assignment):
+            return assignment
+        else:
+            return None
+    
+    # recursive-case: try each value in the next domain
+    # if we find a solution return it. otherwise, try the next value
+    else:
+        for v in domains[0]:
+            sol = tryall(assignment[:]+[v],domains[1:])
+            if sol != None:
+                return sol
+
+
+# checks if an assignment is feasible
+def checkIt(sol):
+    n = len(sol)
+    for i in range(0,n):
+        for j in range(i+1,n):
+            if sol[i] == sol[j] or \
+               sol[i] == sol[j] + (j-i) or \
+               sol[i] == sol[j] - (j-i):
+                return False
+    return True
+
+
+import sys
+
+if __name__ == "__main__":
+    if len(sys.argv) > 1:
+        try:
+            n = int(sys.argv[1].strip())
+        except:
+            print sys.argv[1].strip(), 'is not an integer'
+        print 'Solving Size:', n
+        print(solveIt(n))
+
+    else:
+        print('This test requires an instance size.  Please select the size of problem to solve. (i.e. python queensSolver.py 8)')
+
diff --git a/06-puzzle-challenge/submit.pyc b/06-puzzle-challenge/submit.pyc
new file mode 100644
index 0000000..6256a45
--- /dev/null
+++ b/06-puzzle-challenge/submit.pyc