kenken1, Python 3 - rextester

Language: Layout:

#python 3.5.2

_n = 9

_regions = """
 1  2  2  3  4  5  5  5  6
 1  7  8  8  4  9  9 10  6
 7  7 11 11 11 11 12 10 13
14 14 15 15 16 17 12 10 13
18 19 20 21 16 17 17 22 23
18 19 20 21 16 24 25 22 23
18 26 26 27 27 24 25 28 28
29 29 30 31 32 32 32 32 28
33 33 30 31 34 34 34 35 35"""

_operations = "+10 +14 +8 +11 +11 +10 +11 +9 +7 +15 +30 +9 +7 +10 +6 +6 +20 +21 +6 +9 +10 +6 +17 +7 +10 +7 +12 +17 +8 +13 +8 +30 +10 +10 +10"

actions = []

# setval
# rempos
# mark
def add_action(actions, op, v, row, col):
    actions.append((op, v, row, col))

def create_regions(ops, cell_str, n):
	regions = {}
	cells = cell_str.split()
	for i in range(0,n):
		for j in range(0,n):
			index = i*n + j
			key = int(cells[index])
			if key in regions.keys():
				cell_list = regions[key]
			else:
				cell_list = []
			cell_list.append((i,j))
			regions[key] = cell_list
	operations = ops.split()
	i = 1
	for o in operations:
		oper = o[0]
		res = int(o[1:])
		cell_list = regions[i]
		regions[i] = (oper, res, cell_list)
		i += 1
	return regions

_operations = "+10 +14 +8 +11 +11 +10 +11 +9 +7 +15 +30 +9 +7 +10 +6 +6 +20 +21 +6 +9 +10 +6 +17 +7 +10 +7 +12 +17 +8 +13 +8 +30 +10 +10 +10"

# Create a 2-dimensional array of size nxn that initially holds 1-n for every cell
def create_possibles(n):
	res = []
	for i in range(0,n):
		row = []
		for j in range(0,n):
			poss = []
			for p in range(1,n+1):
				poss.append(p)
			row.append(poss)
		res.append(row)
	return res

# Create a 2-dimensional array of size nxn that initially holds 0 for every cell
def create_values(n):
	res = []
	for i in range(0,n):
		row = []
		for j in range(0,n):
			row.append(0)
		res.append(row)
	return res

def show_poss(possibles):
   n = len(possibles)
   for row in range(0,n):
      s = ''
      for col in range(0,n):
         p = possibles[row][col]
         for i in range(1,n+1):
            if i in p:
               s = s + str(i)
            else:
               s = s + ' '
         s = s + " | "
      print(s)

# Create a deep copy of a square 2-dimensional array
def copy_possibles(possibles):
	n = len(possibles)
	poss2 = []
	for rr in range(0,n):
		row = []
		for cc in range(0,n):
			p = (possibles[rr][cc]).copy()
			row.append(p)
		poss2.append(row)
	return poss2

# Return the total number of possible values in the possibles array
def get_possibles_number(possibles):
	n = len(possibles)
	res = 0
	for rr in range(0,n):
		for cc in range(0,n):
			res += len(possibles[rr][cc])
	return res

def is_poss(possibles, p, row, col):
    if p in possibles[row][col]:
        return True
    else:
        return False

def remove_poss(possibles, p, row, col):
	if p in possibles[row][col]:
		(possibles[row][col]).remove(p)

def add_poss(possibles, p, row, col):
	if p not in possibles[row][col]:
		(possibles[row][col]).append(p)

def remove_poss_from_row_col(possibles, p, row, col):
	n = len(possibles)
	for i in range(0,n):
		remove_poss(possibles, p, row, i)
		remove_poss(possibles, p, i, col)

def remove_all_poss(possibles, row, col):
	(possibles[row][col]).clear()

#recursive
def calc_possibles_commutative_region(op, goal_res, cell_list, possibles, good_permutations=None, res_so_far=-999, curr_perm=[]):
	if res_so_far == -999:  #first time call
		good_permutations = []
		if op == '+':
			so_far = 0
		elif op == '*':
			so_far = 1
	else:
		so_far = res_so_far
    #get coordinates of the first cell in the list
	row = cell_list[0][0]
	col = cell_list[0][1]
	poss = possibles[row][col]
	for p in poss:
		curr_perm.append(p)
		if op == '+':
			so_far2 = so_far + p
		elif op == '*':
			so_far2 = so_far * p
		possibles2 = copy_possibles(possibles)
		remove_poss_from_row_col(possibles2, p, row, col)
		if len(cell_list) > 1:
			calc_possibles_commutative_region(op, goal_res, cell_list[1:], possibles2, 
				good_permutations=good_permutations, res_so_far=so_far2, curr_perm=curr_perm)
		elif so_far2 == goal_res:
			good_permutations.append(curr_perm.copy())
		del curr_perm[len(curr_perm)-1]
	if res_so_far == -999:  #first time call, all recursion is over
		for row, col in cell_list:
			remove_all_poss(possibles, row, col)
		for perm in good_permutations:
			for i in range(0, len(perm)):
				val = perm[i]
				row = cell_list[i][0]
				col = cell_list[i][1]
				add_poss(possibles, val, row, col)

# make a deep copy of a list of native types
def copy_list(in_array):
    out_list = []
    for e in in_array:
        out_list.append(e)
    return out_list

# Return a list of all combinations of the given length choosing from numbers between 1 and n.
def get_all_combinations(length, n, poss=None):
    p = poss
    if p is None:
        p = [ x for x in range(1, n+1) ]
        
    if length == 1:
        return p
    res = []
    for i in range(0,len(p)-length+1):
        firstElement = p[i]
        combinations2 = get_all_combinations(length-1, n, p[(i+1):])
        for c in combinations2:
            combo = [firstElement]
            if length == 2:
                combo.append(c)
            else:
                for e in c:
                    combo.append(e)
            res.append(combo)
    return res

def get_all_permutations_recursive(length, n):
	if length == 1:
		return [ [x] for x in range(1, n+1) ]
	else:
		perms_b = get_all_permutations(length-1, n)
		all_perms = []
		for v in range(1, n+1):
			for prev in perms_b:
				cp = copy_list(prev)
				cp.append(v)
				all_perms.append( cp )
	return all_perms

# does not work if length>2, but I do not need it to
# division and subtraction are binary
def get_all_permutations(length, n, poss=None):
    p = poss
    if p is None:
        p = [ x for x in range(1, n+1) ]
        
    if length == 1:
        return p
    res = []
    for i in range(0,len(p)-length+1):
        firstElement = p[i]
        p2 = copy_list(p)
        p2.pop(i)
        combinations2 = get_all_combinations(length-1, n, p2)
        for c in combinations2:
            combo = [firstElement]
            if length == 2:
                combo.append(c)
            else:
                for e in c:
                    combo.append(e)
            res.append(combo)
    return res

def calc_possibles_noncommutative_region(op, goal_res, cell_list, possibles, good_permutations=None, res_so_far=-999, curr_perm=[]):
    if len(cell_list) != 2:
        return
    i = 0
    cellPoss0 = copy_list(possibles[cell_list[i][0]][cell_list[i][1]])
    remove_all_poss(possibles, cell_list[i][0], cell_list[i][1])
    i = 1
    cellPoss1 = copy_list(possibles[cell_list[i][0]][cell_list[i][1]])
    remove_all_poss(possibles, cell_list[i][0], cell_list[i][1])
    for a in cellPoss0:
        for b in cellPoss1:
            if op == '-':
                if (a-b) == goal_res or (b-a) == goal_res:
                    print((a,b))
                    i = 0
                    add_poss(possibles, a, cell_list[i][0], cell_list[i][1])
                    i = 1
                    add_poss(possibles, b, cell_list[i][0], cell_list[i][1])
            elif op == '/':
                if (a/b) == goal_res or (b/a) == goal_res:
                    i = 0
                    add_poss(possibles, a, cell_list[i][0], cell_list[i][1])
                    i = 1
                    add_poss(possibles, b, cell_list[i][0], cell_list[i][1])

# Set value and adjust the possibilites in the same row and column
def set_value(values, v, row, col, possibles):
    n = len(possibles)
    values[row][col] = v
    for i in range(0, n):
        remove_poss(possibles, v, i, col)
        remove_poss(possibles, v, row, i)
    possibles[row][col] = [v]
#    add_poss(possibles, v, row, col)

def process_all_regions(reg, values, possibles):
    for i in range(1, len(reg)+1):
        if reg[i][0] in ['+', '*']:
            calc_possibles_commutative_region(reg[i][0], reg[i][1], reg[i][2], possibles)
        elif reg[i][0] in ['-', '/']:
            calc_possibles_noncommutative_region(reg[i][0], reg[i][1], reg[i][2], possibles)

def process_all_single_possibles(values, possibles, n):
    for row in range(0, n):
        for col in range(0, n):
            if len(possibles[row][col]) == 1:
                v = possibles[row][col][0]
                set_value(values, v, row, col, possibles)

def get_row_as_list_of_coordinates(row, n):
    res = []
    for i in range(0,n):
        res.append((row,i))
    return res

def get_col_as_list_of_coordinates(col, n):
    res = []
    for i in range(0,n):
        res.append((i,col))
    return res

# return a list of the possible values remaining for this list of coordinates.  That is, values that have not been set.
def get_possibles_in_coordinate_list(coordinates, values, possibles, n):
    res = [ True for x in range(0,n+1) ]
    for c in coordinates:
        v = values[c[0]][c[1]]
        if v > 0:
            res[v] = False
    p = []
    for i in range(1,n+1):
        if res[i]:
            p.append(i)
    return p

# If only one cell in the list can have a given value, then assign that value to the cell.
def process_single_poss_in_coordinate_list(coordinates, possibles, values, n):
    plist = get_possibles_in_coordinate_list(coordinates, values, possibles, n)
    for v in plist:
        count,row,col = 0,0,0
        for c in coordinates:
            if is_poss(possibles, v, c[0], c[1]):
                count += 1
                row = c[0]
                col = c[1]
        if count == 1:
            set_value(values, v, row, col, possibles)
            
                
# If a combination of x possibles is repeated in only x cells, remove those possibles from the other cells.
def process_poss_groups_in_coordinate_list(coordinates, possibles, values, n):
    pass            
                
        
def process_rows(possibles, values, n):
    for row in range(0,n):
        rlist = get_row_as_list_of_coordinates(row, n)
        process_single_poss_in_coordinate_list(rlist, possibles, values, n)
    
        
def process_cols(possibles, values, n):
    for col in range(0,n):
        rlist = get_col_as_list_of_coordinates(col, n)
        process_single_poss_in_coordinate_list(rlist, possibles, values, n)

# Return True if all the possiblities are in the given list    
def has_all(poss, n):
    if len(poss) == 0:
        return False
    poss.sort()
    prev = -666
    count = 0
    for i in poss:
        if i != prev:
            prev = i
            count += 1
    return (count == n)
    
           
        
        
        
    
    
    
# Return True if
#   Every row has every value set or possible
#   No cells have zero possibles
#   No duplicate values in rows or columns
# Else return False
def puzzle_ok(possibles, values):
    n = len(possibles)
    for row in range(0,n):
        vals = []
        poss = []
        for col in range(0,n):
            if values[row][col] > 0:
                vals.append(values[row][col])
                poss.append(values[row][col])
            if len(possibles[row][col]) == 0:
                return False
            for p in possibles[row][col]:
                poss.append(p)
        if has_all(poss, n) == False:
            return False
        v1 = -1
        for v2 in vals:
            if v1 == v2:
                return False

for col in range(0,n):
        vals = []
        poss = []
        for row in range(0,n):
            if values[row][col] > 0:
                vals.append(values[row][col])
                poss.append(values[row][col])
            if len(possibles[row][col]) == 0:
                return False
            for p in possibles[row][col]:
                poss.append(p)
        if has_all(poss, n) == False:
            return False
        v1 = -1
        for v2 in vals:
            if v1 == v2:
                return False
            
    return True

def process_puzzle(possibles, values, regions):
    possNum1 = get_possibles_number(possibles)
    n = len(possibles)
    cont = True
    while cont:
        process_all_regions(regions, values, possibles)
        process_all_single_possibles(values, possibles, n)
        process_rows(possibles, values, n)
        process_cols(possibles, values, n)
        possNum2 = get_possibles_number(possibles)
        if possNum1 == possNum2:
            cont = False
        else:
            possNum1 = possNum2

guess_stack = []

# Create a deep copy of a square 2-dimensional array
def copy_state_to_stack(possibles, stackObj):
    n = len(possibles)
    for row in range(0,n):
        for col in range(0,n):
            stackObj.append((possibles[row][col]).copy())

# return the coordinates for a cell with the shortest possibles list
def find_cell_to_guess(possibles):
    n = len(possibles)
    res = (-1,-1)
    nn = n + 1
    for row in range(0,n):
        for col in range(0,n):
            g = len(possibles[row][col])
            if g < nn and g > 1:
                nn = g
                res = (row,col)
    return res

def restore_possibles(possibles, values, guessStack):
    n = len(possibles)
    startIndex = len(guessStack) -1 -1 -1 -(n*n)
    for row in range(0,n):
        for col in range(0,n):
            values[row][col] = 0
            possibles[row][col] = (guessStack[startIndex + row*n + col]).copy()

def advance_last_guess(possibles, values, guessStack):
    print('entering advance last guess')
    n = len(possibles)
    stackLen = len(guessStack)
    if stackLen == 0:
        print('Guess stack is empty.')
        return
    index = guessStack[stackLen - 1]
    guesses = guessStack[stackLen - 2]
    coordinates = guessStack[stackLen - 3]
    print('index is ' +str(index) + ', guesses are ' + str(guesses) + ', coordinates are ' + str(coordinates))
    newIndex = index + 1
    if newIndex < len(guesses):
        guessStack[stackLen - 1] = newIndex
        newGuess = guesses[newIndex]
        restore_possibles(possibles, values, guessStack)
        print('guess is ' + str(newGuess) + ' from list ' + str(guesses) + ' for cell ' + str(coordinates) + '   stack length is ' + str(len(guessStack)))
        set_value(values, newGuess, coordinates[0], coordinates[1], possibles)
    else:
        count = n*n + 3
        j = stackLen - count
        while count > 0:
            guessStack.pop(j)
            count -= 1
        advance_last_guess(possibles, values, guessStack)

def process_guess_method(possibles, values, regions, guessStack, maxIterations):
    #maxIterations = 2
    possNum = get_possibles_number(possibles)
    puzzleStillGood = True
    n = len(possibles)
    while possNum > (n*n):
        if puzzleStillGood == False:
            advance_last_guess(possibles, values, guessStack)
        else:
            guessCell = find_cell_to_guess(possibles)
            guesses = possibles[guessCell[0]][guessCell[1]]
        
            copy_state_to_stack(possibles, guessStack)
            guessStack.append(guessCell)
            guessStack.append(guesses)
            guessStack.append(0) #index of current guess
            print('guess is ' + str(guesses[0]) + ' from list ' + str(guesses) + ' for cell ' + str(guessCell) + '   stack length is ' + str(len(guessStack)))
            set_value(values, guesses[0], guessCell[0], guessCell[1], possibles)

process_puzzle(possibles, values, regions)
        puzzleStillGood = puzzle_ok(possibles, values)
        possNum = get_possibles_number(possibles)
        if maxIterations > 0:
            maxIterations -= 1
        else:
            return

reg = create_regions(_operations, _regions, _n)

#print (reg)

possibles = create_possibles(_n)
values = create_values(_n)
#remove_poss(possibles, 3, 0, 0)

if False:
    show_poss(possibles)
    i = 5
    calc_possibles_commutative_region(reg[i][0], reg[i][1], reg[i][2], possibles)
    print('-------------------------------')
    show_poss(possibles)

if False:
    remove_poss(possibles, 3, 0, 0)
    #remove_poss(possibles, 9, 0, 0)
    show_poss(possibles)
    i = 1
    calc_possibles_noncommutative_region('/', 3, reg[i][2], possibles)
    print('-------------------------------')
    show_poss(possibles)

if False:
    p6 = get_all_permutations(3, 5)
    print( len(p6) )
    print( p6 )

if False:
    p6 = get_all_combinations(3, 5)
    print( len(p6) )
    print( p6 )
#print( get_all_combinations(2, 7) )

if True:
    #remove_poss(possibles, 9, 0, 0)
    show_poss(possibles)
    process_puzzle(possibles, values, reg)
    print('-------------------------------')
    show_poss(possibles)
    
    #set_value(values, 5, 0, 1, possibles)  #9

process_puzzle(possibles, values, reg)
    print('cell to guess is ' + str(find_cell_to_guess(possibles)))
    process_guess_method(possibles, values, reg, guess_stack, 5)
    
    print('-------------------------------')
    show_poss(possibles)
    print(get_possibles_number(possibles))
    print( puzzle_ok(possibles, values) )

[ + ] Show input
Absolute running time: 3.39 sec, cpu time: 4.93 sec, memory peak: 7 Mb, absolute service time: 3,4 sec