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")