KenKen solver - Python

Question

Here is my code for the KenKen puzzle:

The user must fill in each embolded regions with numbers in the range 1-n where n is the board dimensions (e.g: 4*4, n=4) such that the total of that region equals the target number in the corner using the designated symbol.

Each row and column MUST contain the numbers 1-4 only once.

So the top square must use the numbers 1-4 to create 36 using the multiplication operand (e.g: 4*3*3*1). This is valid if the two threes are placed in a diagonal relationship to each other

When filling in a region, the order is arbitrary. So for example if considering the bottom left corner with a target of 2 and operand of "minus" then placing 2 above 1 or 1 above 2 would not be relevant.

If you don't understand, please see here.

import operator
from itertools import product, permutations

import numpy as np


def calculate(numbers, target, op):
    operator_dict = {"+": operator.add,
                     "-": operator.sub,
                     "*": operator.mul,
                     "/": operator.truediv}

    running_total = numbers[0]
    for number in numbers[1:]:
        running_total = operator_dict[op](running_total, number)

    if running_total == target:
        return True
    return False


def valid_number(row, column, board, size):
    valid_row = set()
    for number in range(1, size + 1):
        if number not in board[row]:
            valid_row.add(number)

    valid_column = set()
    column_numbers = [int(board[i, column]) for i in range(size)]
    for number in range(1, size + 1):
        if number not in column_numbers:
            valid_column.add(number)

    valid_numbers = valid_row & valid_column
    yield from valid_numbers


def is_valid_sum(board, instruction_array, number_groups):
    for group in range(1, number_groups + 1):
        coordinates = []
        list_numbers = []
        next_group = 0
        for i, j in product([row for row in range(size)], [column for column in range(size)]):
            if instruction_array[i][j][0] == group:
                if len(instruction_array[i][j]) == 2:
                    next_group = 1
                    break
                target = instruction_array[i][j][1]
                op = instruction_array[i][j][2]
                list_numbers.append(int(board[i, j]))
        if next_group == 1:
            continue
        combination_numbers = permutations(list_numbers, len(list_numbers))
        for combination in combination_numbers:
            target_reached = calculate(combination, target, op)
            if target_reached:
                break
        if target_reached:
            continue
        else:
            return False
    return True


def is_full(board, size):
    for row in range(size):
        for column in range(size):
            if board[row, column] == 0:
                return False
    return True


def solve_board(board, instruction_array, size, number_groups):
    if is_full(board, size):
        if is_valid_sum(board, instruction_array, number_groups):
            return True, board
        return False, board
    for i, j in product([row for row in range(size)],
                        [column for column in range(size)]):  # Product is from itertools library
        if board[i, j] != 0:
            continue
        for number in valid_number(i, j, board, size):
            board[i, j] = number
            is_solved, board = solve_board(board, instruction_array, size, number_groups)
            if is_solved:
                return True, board
            board[i, j] = 0
        return False, board
    return False, board


def fill_obvious(board, instruction_array, size):
    # Fill fixed numbers
    for row in range(size):
        for column in range(size):
            if len(instruction_array[row][column]) == 2:
                board[row, column] = instruction_array[row][column][1]
    return board


if __name__ == "__main__":
    # Instructions in the array are in the format groupID, target, symbol.
    # The group ID is necessary for the situation where two neighbouring groups have the same target AND symbol
    # Which is possibility in the game
    # Squares which have a fixed number take a group number and the number as input. DO NOT place a symbol in the square
    instruction_array = [[[1, 36, "*"], [1, 36, "*"], [6, 1, "-"], [6, 1, "-"]],
                         [[1, 36, "*"], [1, 36, "*"], [5, 12, "*"], [7, 2, "/"]],
                         [[2, 2, "-"], [5, 12, "*"], [5, 12, "*"], [7, 2, "/"]],
                         [[2, 2, "-"], [3, 3, "+"], [3, 3, "+"], [4, 3]]]
    number_groups = 7
    size = len(instruction_array[0])
    board = np.zeros(size * size).reshape(size, size)
    board = fill_obvious(board, instruction_array, size)
    is_solved, solved = solve_board(board, instruction_array, size, number_groups)
    if is_solved:
        print(solved)
    else:
        print("Cannot solve")

Answer 1

You use numpy to represent your board but don't take advantage of some of its capabilities to simplify your code. Some loops are unnecessary as they can be performed by a numpy operation.

You also use itertools.product to loop over indices where a double enumerate for-loop would fit better. You also use it in solve_board to search for the first entry which is still 0 and then stop afterwards; better use a generator of possible indexes and extract the first using next to make it more explicit. This will also allows you to check for completion of the board, if the generator is exhausted and raise StopIteration.

Your is_valid_sum function would also benefit from being split in two to be able to return early instead of using all those flags.

And a solve or main function that would perform the boilerplate that you do in your if __name__ == '__main__' guard would be appreciated.

Proposed changes:

import itertools
import numpy as np


OPERATORS = {
        '+': np.add,
        '-': np.subtract,
        '*': np.multiply,
        '/': np.true_divide,
}


def valid_number(row, column, size):
    candidates = np.arange(1, size + 1)
    candidates = np.setdiff1d(candidates, row, assume_unique=True)
    candidates = np.setdiff1d(candidates, column, assume_unique=True)
    return candidates


def check_group(board, instructions, group):
    group_numbers = []
    for i, row in enumerate(instructions):
        for j, instruction in enumerate(row):
            if instruction[0] != group:
                continue
            try:
                _, target, operation = instruction
            except ValueError:
                # Case of fixed-number groups
                return board[i, j] == instruction[1]
            else:
                group_numbers.append(board[i, j])

    for combination in itertools.permutations(group_numbers):
        if OPERATORS[operation].reduce(combination, dtype=float) == target:
            return True

    return False


def is_valid_sum(board, instructions, groups):
    for group in groups:
        if not check_group(board, instructions, group):
            return False
    return True


def solve_board(board, instructions, groups):
    empty_rows, empty_cols = np.where(board == 0)
    try:
        i, j = next(zip(empty_rows, empty_cols))
    except StopIteration:
        # Board is full
        return is_valid_sum(board, instructions, groups)

    row = board[i]
    column = board[:, j]
    for number in valid_number(row, column, *row.shape):
        board[i, j] = number
        if solve_board(board, instructions, groups):
            return True
        board[i, j] = 0
    return False


def solve(instructions):
    size = len(instructions)
    board = np.zeros((size, size), dtype=int)

    groups = set()
    for i, row in enumerate(instructions):
        assert size == len(row)
        for j, instruction in enumerate(row):
            if len(instruction) == 2:
                board[i, j] = instruction[1]
            groups.add(instruction[0])

    is_solved = solve_board(board, instructions, groups)
    return board if is_solved else None


if __name__ == "__main__":
    # Instructions in the array are in the format groupID, target, symbol. The
    # group ID is necessary for the situation where two neighbouring groups
    # have the same target AND symbol; which is a possibility in the game.

    # Squares which have a fixed number take a group number and the number as
    # input. DO NOT place a symbol in the square

    board = solve([
        [[1, 36, "*"], [1, 36, "*"], [6, 1, "-"],  [6, 1, "-"]],
        [[1, 36, "*"], [1, 36, "*"], [5, 12, "*"], [7, 2, "/"]],
        [[2, 2, "-"],  [5, 12, "*"], [5, 12, "*"], [7, 2, "/"]],
        [[2, 2, "-"],  [3, 3, "+"],  [3, 3, "+"],  [4, 3]],
    ])

    if board is None:
        print("Cannot solve")
    else:
        print(board)

You may also be able to simplify the is_valid_sum and check_group functions by storing more than the group numbers; e.g. target, op and list of indices for said group.

Answer 2

In calculate I see a few things:

• I'd put the translation dictionary outside of the function. I think it makes more sense as a "global constant" than it does as something local to that function. That also gives you a way to check for the validity of an operator string for free if you ever need that:

  if some_string in operator_dict:
  

• Your accumulation loop that splits the head off then iterates the rest could be made much neater by using a reduction. If you don't supply an initial value for a reduction, it automatically uses the first element as the starting accumulator.

• Your return could be simplified down to just returning the condition. I also wouldn't put the return True inside the if body, then not put the return False in an else.

I'd write this closer to:

from functools import reduce

OPERATOR_SYM_TO_FUNC = {"+": operator.add,
                        "-": operator.sub,
                        "*": operator.mul,
                        "/": operator.truediv}

def calculate(numbers, target, op_sym):
    op = OPERATOR_SYM_TO_FUNC[op_sym]

    total = reduce(op, numbers)

    return total == target

---

In solve_board, I can't offhand see why you're returning board in this case. If board were immutable, ya, that would make sense. You're directly mutating the board that's passed in though. I think it creates necessary bulk, especially in lines like:

 is_solved, board = solve_board(board, instruction_array, size, number_groups)

The boards are the same, so there's not really any gain.

With how you have it, I would just return the boolean status. It may make sense however to make a copy of the input board, then mutate and return the copy. This prevents the original board from getting mutated by accident. If you chose to do that, instead of returning a True/False to indicate success, you could return the board on a successful solve, and None when the board is unsolvable.

I'll also point out that you have the lines:

for i, j in product([row for row in range(size)],
                    [column for column in range(size)]):  # Product is from itertools library

I think instead of that comment, you should just use a qualified name:

import itertools

for i, j in itertools.product([row for row in range(size)],
                              [column for column in range(size)]):

That's a little bulky, but your list comprehensions in there are unnecessary. [row for row in range(size)] is basically just range(size). If you really wanted it as a strict list, it would likely be neater to use list(range(size)) instead. Strictness likely isn't beneficial here though, so I'd just use ranges:

for i, j in itertools.product(range(size), range(size)]):

Answer 3

In addition to the comments Carcigenicate provided, there are some places where you can improve the efficiency. For example, the following code in valid_number() iterates over the row size times to fill valid_row. Then the same thing is done to fill valid column.

valid_row = set()
for number in range(1, size + 1):    <- this loops 'size' times
    if number not in board[row]:     <- this also loops 'size' times
        valid_row.add(number)

This can be improved by starting with a full set and removing numbers that are already in the row or column.

def valid_number(row, column, board, size):

    valid_numbers = set(range(1,size+1))

    for number in range(1, size+1):
        valid.discard(board[row, i])
        valid.discard(board[i, column])

    yield from valid_numbers

Every time is_valid_sum() is called, the entire instruction array is scanned once for each group to determine which cells are in the group, and what the op is. This information doesn't change, so it would be more efficient to calculate that information up front. make_group() builds a dictionary mapping group numbers to the target value, operator and cells for that group. It should be created and passed as an argument to solve_board().

TARGET = 0
OP = 1
CELLS = 2

def make_groups(instruction_array):
    groups = {}

    for r in range(1, size+1):
        for c in range(1, size+1):
            # this presumes all instruction have an op
            # use 'None' for pre-filled cells
            group_number,target,op = instruction_array[r][c]

            if op:

                if group_number not in groups:
                    groups[group_number] = [target, op, []]

                groups[group_number][CELLS].append((r,c))

    return groups

Then, is_valid_sum() can be simplified to something like:

def is_valid_sum(board, groups):
    for target, op, cells in groups.items():
        list_numbers = [board[r,c] for r,c in cells]

        combination_numbers = permutations(list_numbers, len(list_numbers))
        for combination in combination_numbers:
            if calculate(combination, target, op):
                break            # the beak skips over the else
        else:
            continue             # this is done if the loop finishes normally

        return False             
    return True

I used the else with the for combination... loop to clarify the logic. Although it might make more sense to move the permutation calculations and the loop into the calculate function. If the op is '+' or '*', the permutations are not needed. If the op is '-' or '/', the largest number should be first unless the target can be a fraction or negative.

One last observation, is_full() is called by solve_board() to determine if the boards is filled up. solve_board() is a recursive function that tries to fill a cell on every recursion. Pass it a count of the number of cells that need to be filled and decrement the count with each level of recursion. When the count reaches zero the board is full. So is_full() is not needed. Like so, where num_cells is the number of cells left to fill:

def solve_board(board, instruction_array, size, groups, num_cells):
    if num_cells == 0:
        return is_valid_sum(board, instruction_array, number_groups), board

    for i, j in product(range(size),range(size)):

            ...
            is_solved, board = solve_board(board, instruction_array, size, groups, num_cells-1)
            ...

There are other optimizations that could be made, but that's all for now.