From 7428f8f3bbb74ac91a618b70ddfe7b11fe9b63dc Mon Sep 17 00:00:00 2001 From: Hamed Gorjiara Date: Mon, 13 Aug 2018 10:38:40 -0700 Subject: [PATCH] Fixing killerSudoku ... --- killerSudoku/csolversudoku.py | 78 +++++-- killerSudoku/testcase/2-25.killer | 343 ++++++++++++++++++++++++++++++ 2 files changed, 401 insertions(+), 20 deletions(-) create mode 100644 killerSudoku/testcase/2-25.killer diff --git a/killerSudoku/csolversudoku.py b/killerSudoku/csolversudoku.py index 7984a757..960fa7f8 100644 --- a/killerSudoku/csolversudoku.py +++ b/killerSudoku/csolversudoku.py @@ -8,14 +8,29 @@ def solveProblem(N, killerRules, serialize = False): return generateKillerSudokuConstraints(N, killerRules, serialize) +def getDomain(allPossible): + assert len(allPossible) > 0 + domainNum = len(allPossible[0]) + domain = [x[i] for x in allPossible for i in range(domainNum)] + return list(set(domain)) + +def validateElements(elems): + for row in elems: + for elem in row: + assert elem != None + +def generateSumRange(domain1, domain2, totalSum): + range = set() + for d1 in domain1: + for d2 in domain2: + if (d1+d2) <= totalSum: + range.add(d1+d2) + return range def generateKillerSudokuConstraints(N, killerRules, serialize): csolverlb = ps.loadCSolver() solver = csolverlb.createCCSolver() - s1 = [ i for i in range(1, N+1)] - set1 = (c_long* len(s1))(*s1) - s1 = csolverlb.createSet(solver, c_uint(1), set1, c_uint(N)) - problem = np.array([[csolverlb.getElementVar(solver,s1) for i in range(N)] for i in range(N)]) + problem = np.array([[None for i in range(N)] for i in range(N)]) elemConsts = [csolverlb.getElementConst(solver, c_uint(1), i) for i in range(1, N+1)] @@ -35,26 +50,48 @@ def generateKillerSudokuConstraints(N, killerRules, serialize): csolverlb.addConstraint(solver,b); def getElement(cage): + cageSum = cage[0] + cageSize = len(cage[1]) + cageCells = cage[1] + cb = combinations([ii for ii in range(1, N+1)], cageSize) + f = lambda x : sum(x) == cageSum + comb = ifilter(f, cb) # all valid combinations + allPossible = list(chain(comb)) + d1 = getDomain(allPossible) + set1 = (c_long* len(d1))(*d1) + s1 = csolverlb.createSet(solver, c_uint(1), set1, c_uint(len(d1))) + for i in range(len(cage[1])): + problem[cage[1][i][0]][cage[1][i][1]] = csolverlb.getElementVar(solver, s1); elems = [ problem[cage[1][i][0]][cage[1][i][1]] for i in range(len(cage[1])) ] + #Elements in each cage shouldn't be identical valid(elems) - return elems + return elems, d1 - def generateSumConstraint(sumCage, elements): - d = [] - for e in elements: - d.append(csolverlb.getElementRange(solver, e)) - domains = (c_void_p *len(d))(*d) + def generateSumConstraint(sumCage, elements, domain): + assert len(elements) >1 + parDomain = domain + parElem = elements[0] overflow = csolverlb.getBooleanVar(solver, c_uint(2)); + for i in range(len(elements)): + if i< len(elements) -1: + elem = elements[i+1] + set1 = (c_long* len(domain))(*domain) + s1 = csolverlb.createSet(solver, c_uint(1), set1, c_uint(len(domain))) + pS = (c_long* len(parDomain))(*parDomain) + parSet = csolverlb.createSet(solver, c_uint(1), pS, c_uint(len(parDomain))) + d = [s1, parSet] + domains = (c_void_p *len(d))(*d) + parDomain = generateSumRange(domain, parDomain, sumCage) + r = (c_long* len(parDomain))(*parDomain) + sumRange = csolverlb.createSet(solver, c_uint(1), r, c_uint(len(parDomain))) + f1 = csolverlb.createFunctionOperator(solver, ps.ArithOp.SATC_ADD, sumRange, ps.OverFlowBehavior.SATC_OVERFLOWSETSFLAG); + inp = [elem, parElem] + inputs = (c_void_p*len(inp))(*inp) + parElem = csolverlb.applyFunction(solver, f1, inputs, len(inp), overflow); esum = csolverlb.getElementConst(solver, c_uint(3), c_long(sumCage)) setSum = csolverlb.getElementRange(solver, esum) - f1 = csolverlb.createFunctionOperator(solver, ps.ArithOp.SATC_ADD, setSum, ps.OverFlowBehavior.SATC_OVERFLOWSETSFLAG); - inputs = (c_void_p*len(elements))(*elements) - added = csolverlb.applyFunction(solver, f1, inputs, len(elements), overflow); - - d = [setSum,setSum] - domain = (c_void_p *len(d))(*d) equals = csolverlb.createPredicateOperator(solver, c_uint(ps.CompOp.SATC_EQUALS)) - inp = [added,esum] + inp = [parElem,esum] inputs = (c_void_p*len(inp))(*inp) b = csolverlb.applyPredicate(solver,equals, inputs, c_uint(len(inp))) csolverlb.addConstraint(solver,b); @@ -66,9 +103,10 @@ def generateKillerSudokuConstraints(N, killerRules, serialize): if len(cage[1])==1: problem[cage[1][0][0]][cage[1][0][1]] = csolverlb.getElementConst(solver, c_uint(7), c_long(sumCage)) continue - elements = getElement(cage) - generateSumConstraint(sumCage, elements) - + elements, domain = getElement(cage) + generateSumConstraint(sumCage, elements, domain) + # Ensure there's no undefined element (for each cell we have a rule) + validateElements(problem) # ensure each cell at least has one value! for i,row in enumerate(problem): for j, elem in enumerate(row): diff --git a/killerSudoku/testcase/2-25.killer b/killerSudoku/testcase/2-25.killer new file mode 100644 index 00000000..3b45c5b0 --- /dev/null +++ b/killerSudoku/testcase/2-25.killer @@ -0,0 +1,343 @@ +11=(6, 1)+(5, 1) +16=(18, 22)+(18, 23) +18=(1, 19)+(1, 20) +33=(0, 5)+(1, 5) +14=(5, 24)+(5, 23) +41=(22, 21)+(22, 22) +27=(8, 16)+(9, 16) +22=(3, 4)+(2, 4) +43=(16, 21)+(16, 22) +42=(12, 19)+(12, 20) +28=(3, 14)+(2, 14) +22=(18, 16)+(18, 15) +31=(1, 17)+(0, 17) +34=(6, 22)+(5, 22) +16=(3, 23)+(3, 22) +22=(20, 21)+(20, 20) +25=(20, 12)+(19, 12) +23=(1, 22)+(1, 23) +37=(23, 6)+(23, 7) +20=(12, 22)+(11, 22) +26=(21, 10)+(21, 11) +25=(14, 0)+(14, 1) +29=(2, 3)+(3, 3) +18=(24, 19)+(24, 18) +35=(9, 9)+(10, 9) +25=(4, 11)+(5, 11) +34=(23, 20)+(23, 21) +47=(13, 11)+(13, 10) +24=(3, 17)+(3, 16) +33=(16, 18)+(17, 18) +23=(23, 4)+(23, 3) +35=(15, 16)+(14, 16) +19=(22, 1)+(22, 0) +26=(21, 14)+(21, 15) +24=(12, 24)+(12, 23) +27=(21, 3)+(22, 3) +12=(9, 14)+(9, 15) +38=(0, 23)+(0, 24) +30=(0, 7)+(1, 7) +8=(21, 22)+(21, 23) +21=(18, 10)+(17, 10) +34=(13, 3)+(13, 2) +23=(7, 4)+(7, 5) +23=(3, 12)+(4, 12) +33=(19, 1)+(20, 1) +24=(18, 13)+(17, 13) +26=(15, 1)+(15, 2) +23=(11, 14)+(10, 14) +10=(17, 0)+(18, 0) +24=(15, 22)+(15, 23) +21=(22, 15)+(22, 16) +13=(20, 6)+(21, 6) +27=(2, 0)+(1, 0) +18=(18, 3)+(18, 2) +31=(22, 7)+(21, 7) +19=(24, 11)+(23, 11) +43=(24, 5)+(23, 5) +30=(2, 9)+(2, 10) +35=(21, 24)+(22, 24) +16=(5, 6)+(5, 7) +46=(20, 3)+(20, 2) +20=(12, 6)+(12, 5) +19=(11, 17)+(11, 16) +15=(13, 16)+(13, 15) +37=(18, 7)+(18, 6) +18=(14, 19)+(14, 20) +13=(0, 2)+(1, 2) +21=(8, 14)+(7, 14) +37=(16, 14)+(16, 13) +48=(22, 19)+(21, 19) +21=(15, 3)+(14, 3) +17=(11, 9)+(11, 10) +28=(10, 18)+(9, 18) +22=(0, 9)+(0, 8) +35=(24, 7)+(24, 8) +37=(11, 1)+(10, 1) +5=(1, 10)+(0, 10) +41=(10, 5)+(11, 5) +33=(21, 12)+(22, 12) +17=(11, 12)+(10, 12) +22=(4, 8)+(4, 9) +21=(16, 2)+(16, 3) +29=(23, 17)+(22, 17) +14=(4, 24)+(3, 24) +41=(9, 6)+(10, 6) +32=(9, 22)+(9, 21) +33=(3, 20)+(3, 21) +5=(10, 13)+(11, 13) +30=(13, 5)+(14, 5) +29=(5, 20)+(5, 21) +27=(24, 2)+(24, 3) +22=(9, 2)+(8, 2) +31=(4, 0)+(4, 1) +29=(11, 4)+(11, 3) +37=(7, 23)+(8, 23) +30=(15, 24)+(16, 24) +19=(14, 21)+(13, 21) +10=(19, 22)+(20, 22) +28=(17, 1)+(18, 1) +36=(6, 13)+(5, 13) +35=(14, 14)+(14, 13) +27=(21, 8)+(22, 8) +29=(3, 6)+(2, 6) +20=(23, 23)+(23, 24) +18=(11, 7)+(11, 6) +11=(1, 12)+(0, 12) +13=(17, 6)+(16, 6) +37=(1, 21)+(0, 21) +9=(20, 16)+(20, 17) +30=(20, 11)+(20, 10) +25=(11, 15)+(10, 15) +29=(8, 17)+(7, 17) +31=(21, 5)+(21, 4) +26=(11, 21)+(10, 21) +48=(7, 7)+(7, 6) +25=(4, 15)+(5, 15) +24=(8, 3)+(8, 4) +27=(6, 5)+(6, 4) +15=(18, 20)+(18, 21) +29=(23, 14)+(23, 13) +20=(15, 18)+(15, 17) +30=(19, 5)+(18, 5) +11=(9, 19)+(10, 19) +31=(9, 1)+(9, 0) +10=(13, 7)+(14, 7) +30=(18, 8)+(17, 8) +31=(4, 19)+(4, 18) +17=(8, 5)+(8, 6) +8=(15, 10)+(15, 9) +14=(21, 2)+(22, 2) +15=(7, 20)+(7, 21) +16=(13, 1)+(12, 1) +25=(16, 15)+(17, 15) +41=(2, 11)+(3, 11) +26=(0, 4)+(0, 3) +30=(6, 2)+(5, 2) +41=(15, 4)+(14, 4) +27=(14, 8)+(15, 8) +24=(22, 11)+(22, 10) +35=(6, 17)+(5, 17) +7=(20, 9)+(21, 9) +27=(22, 13)+(21, 13) +34=(0, 15)+(1, 15) +37=(9, 4)+(9, 3) +8=(9, 8)+(10, 8) +33=(4, 21)+(4, 22) +13=(2, 20)+(2, 19) +16=(12, 10)+(12, 9) +30=(8, 13)+(8, 12) +36=(5, 9)+(6, 9) +34=(7, 12)+(7, 11) +33=(6, 24)+(6, 23) +39=(9, 10)+(8, 10) +30=(4, 5)+(3, 5) +27=(9, 12)+(9, 11) +21=(22, 9)+(23, 9) +41=(9, 23)+(10, 23) +20=(5, 14)+(4, 14) +30=(3, 10)+(3, 9) +22=(16, 23)+(17, 23) +17=(24, 0)+(23, 0) +9=(14, 11)+(14, 12) +39=(12, 14)+(12, 15) +9=(11, 2)+(12, 2) +3=(16, 8)+(16, 7) +13=(2, 22)+(2, 23) +22=(14, 15)+(15, 15) +27=(15, 14)+(15, 13) +21=(4, 13)+(3, 13) +26=(7, 1)+(7, 0) +34=(16, 17)+(16, 16) +43=(12, 12)+(13, 12) +38=(17, 21)+(17, 20) +23=(16, 1)+(16, 0) +36=(13, 20)+(13, 19) +41=(14, 6)+(15, 6) +11=(16, 5)+(17, 5) +19=(13, 17)+(12, 17) +29=(11, 24)+(11, 23) +17=(2, 8)+(2, 7) +32=(11, 11)+(12, 11) +34=(14, 17)+(14, 18) +25=(3, 15)+(2, 15) +7=(1, 3)+(1, 4) +41=(21, 20)+(22, 20) +25=(7, 9)+(8, 9) +11=(23, 2)+(23, 1) +25=(24, 6) +25=(6, 10)+(7, 10) +20=(19, 13)+(20, 13) +7=(15, 7) +26=(1, 18)+(0, 18) +32=(7, 22)+(8, 22) +32=(0, 11)+(1, 11) +24=(15, 12)+(15, 11) +19=(14, 2) +29=(16, 20)+(15, 20) +24=(7, 19)+(7, 18) +39=(10, 17)+(10, 16) +40=(18, 4)+(17, 4) +23=(24, 23)+(24, 24) +35=(7, 3)+(7, 2) +17=(8, 15)+(7, 15) +26=(4, 2)+(4, 3) +23=(6, 15)+(6, 16) +13=(22, 6)+(22, 5) +36=(14, 24)+(14, 23) +27=(4, 16)+(4, 17) +19=(6, 20)+(6, 21) +7=(4, 20) +24=(23, 8) +32=(17, 12)+(17, 11) +34=(2, 16)+(1, 16) +21=(7, 16) +30=(19, 14)+(20, 14) +44=(12, 8)+(11, 8) +22=(5, 12)+(6, 12) +29=(9, 20)+(10, 20) +40=(5, 18)+(5, 19) +15=(21, 17)+(21, 18) +7=(18, 17)+(19, 17) +25=(19, 6)+(19, 7) +17=(10, 22) +4=(22, 4) +45=(1, 9)+(1, 8) +27=(0, 13)+(1, 13) +28=(24, 17)+(24, 16) +20=(10, 3)+(10, 4) +2=(8, 11) +9=(12, 18)+(11, 18) +24=(15, 0) +26=(0, 20)+(0, 19) +26=(18, 19)+(18, 18) +35=(16, 11)+(16, 12) +23=(8, 7)+(9, 7) +25=(5, 3)+(5, 4) +37=(23, 15)+(24, 15) +37=(11, 19)+(11, 20) +28=(3, 1)+(2, 1) +10=(15, 21) +16=(23, 18)+(22, 18) +28=(2, 24)+(1, 24) +19=(24, 20)+(24, 21) +27=(8, 24)+(7, 24) +7=(12, 16) +17=(22, 23) +17=(24, 13)+(24, 12) +29=(4, 10)+(5, 10) +26=(12, 3)+(12, 4) +44=(2, 2)+(3, 2) +16=(24, 1) +42=(17, 24)+(18, 24) +43=(17, 9)+(18, 9) +19=(14, 9)+(14, 10) +24=(17, 3)+(17, 2) +22=(23, 12) +36=(19, 16)+(19, 15) +14=(18, 12)+(18, 11) +14=(5, 0)+(6, 0) +15=(13, 18) +3=(12, 21) +25=(20, 7)+(20, 8) +27=(23, 10)+(24, 10) +31=(3, 19)+(3, 18) +14=(4, 6)+(4, 7) +34=(8, 1)+(8, 0) +29=(6, 8)+(6, 7) +13=(24, 4) +19=(2, 5) +1=(13, 6) +13=(16, 19)+(15, 19) +18=(20, 23)+(20, 24) +11=(9, 5) +25=(17, 16)+(17, 17) +15=(6, 6) +18=(22, 14) +23=(0, 22) +12=(17, 22) +24=(3, 8)+(3, 7) +8=(7, 13) +44=(19, 18)+(20, 18) +14=(21, 21) +22=(10, 11)+(10, 10) +11=(9, 24)+(10, 24) +21=(13, 22)+(13, 23) +21=(21, 0)+(20, 0) +28=(18, 14)+(17, 14) +31=(13, 8)+(13, 9) +23=(17, 7) +26=(1, 6)+(0, 6) +33=(1, 1)+(0, 1) +19=(8, 21)+(8, 20) +4=(5, 5) +29=(19, 11)+(19, 10) +32=(20, 4)+(19, 4) +37=(19, 8)+(19, 9) +1=(20, 15) +18=(19, 21)+(19, 20) +24=(19, 24)+(19, 23) +15=(8, 19)+(8, 18) +37=(2, 12)+(2, 13) +21=(21, 1) +23=(6, 14) +13=(10, 7) +15=(7, 8)+(8, 8) +25=(24, 22)+(23, 22) +1=(24, 9) +30=(10, 0)+(11, 0) +36=(19, 3)+(19, 2) +12=(3, 0) +18=(23, 16) +37=(12, 13)+(13, 13) +10=(14, 22) +29=(20, 19)+(19, 19) +10=(20, 5) +16=(19, 0) +20=(13, 14) +3=(24, 14) +8=(0, 16) +19=(0, 0) +38=(13, 0)+(12, 0) +24=(4, 23) +33=(16, 9)+(16, 10) +3=(6, 11) +9=(1, 14)+(0, 14) +23=(2, 18)+(2, 17) +12=(12, 7) +10=(13, 4) +5=(13, 24) +1=(10, 2) +11=(16, 4) +16=(5, 16) +17=(21, 16) +8=(2, 21) +26=(6, 19)+(6, 18) +12=(23, 19) +16=(17, 19) +22=(9, 13) +12=(15, 5) +9=(6, 3) +13=(9, 17) +17=(5, 8) +8=(4, 4) -- 2.34.1