KenKen is a fill-in-the-grid puzzle game, similar to Sudoku (solved in another notebook), but with arithmetic as well as logic.
An example puzzle and solution:
The rules of KenKen are:
5 + 6
).4 × 5 × 3 × 4
).
4
s in a cage are ok if they are in different rows and columns.)6 / 3
).4 - 1
).5
.6 - 3 - 2 - 1
= (((6 - 3) - 2) - 1)
= 0
The KenKen-solving program uses constraint propagation and search:
Throughout the program the following variable names represent the following data types:
r
is a row label, e.g. 'A'
c
is a column label, e.g. '3'
s
is a square label, e.g. 'A3'
d
is a digit, e.g. 9
u
is a unit (a row or column), e.g. ('A1', 'A2', 'A3', 'A4', 'A5', 'A6')
cage
is a Cage, consisting of a target number, an operator, and a list of squaresvalues
is a dict of {square: set_of_possible_digits}, e.g. {'A1': {5, 6}, 'B1': {6, 5}, ...}
values
dict is a solution when every square has been filled with a single digit, and they satisfy all the constraints.kk
or kenken
is a KenKen object, which describes the puzzle. It has these attributes:.N
: the number of squares on a side.digits
: the set of digits allowed: {1, ..., N}
.squares
: a set of all squares in the grid.cages
: a list of all cages in the grid.cagefor
: a dict where .cagefor[s]
is the cage that square s
is part of..unitsfor
: a dict where .unitsfor[s]
is a tuple of the two units for square s
..units
: a set of all units.peers
: a dict where .peers[s]
is a set of the 2 * (N - 1)
squares in the same column or row as s
.cage_descriptions
are strings, for example "11 + A1 B1"
means a cage whose target is 11, whose operator is addition, and whose squares are A1
and B1
. A semicolon separates cage descriptions.from typing import Dict, Set, List, Optional
from itertools import product as crossproduct
from collections import defaultdict
from operator import add, sub, mul, truediv
from dataclasses import dataclass
from functools import reduce
Square = str
Unit = tuple
Values = Dict[Square, Set[int]] # The possible values that fill in the squares
class KenKen:
"""Describes a KenKen puzzle, but not the values used to fill in the puzzle squares."""
def __init__(self, N, cage_descriptions, sep=";"):
self.N = N
self.digits = set(range(1, N + 1))
self.cols = '123456789'[:N]
self.rows = 'ABCDEFGHI'[:N]
self.squares = {r + c for r in self.rows for c in self.cols}
self.cages = [make_cage(description) for description in cage_descriptions.split(sep)]
self.cagefor = {s: first(cage for cage in self.cages if s in cage.squares)
for s in self.squares}
self.unitsfor= {s: (Unit(s[0]+c for c in self.cols), Unit(r+s[1] for r in self.rows))
for s in self.squares}
self.units = union(self.unitsfor.values())
self.peers = {s: union(self.unitsfor[s]) - {s}
for s in self.squares}
s1 = sorted(self.squares)
s2 = sorted(s for cage in self.cages for s in cage.squares)
assert s1 == s2, f"Cage descriptions don't cover all squares:\n{s1}\n{s2}"
@dataclass
class Cage:
"""A collection of squares that must evaluate to `target` when `op` is applied to them."""
target: int
op: str
squares: List[Square]
def make_cage(description) -> Cage:
"""Make a cage from a description such as '3 + A1 A2'."""
num, op, *squares = description.upper().split()
assert op in OPS
return Cage(int(num), op, squares)
OPS = {'+': add, '-': sub, '×': mul, '*': mul, 'X': mul, '/': truediv, '÷': truediv, '=': add}
def first(iterable) -> Optional[object]: return next(iter(iterable), None)
def union(sets) -> set: return set().union(*sets)
Let's make a KenKen
object for the example puzzle (repeated here):
kk6 = KenKen(6, """
11 + A1 B1; 2 / A2 A3; 20 × A4 B4; 6 × A5 A6 B6 C6;
3 - B2 B3; 3 / B5 C5;
240 × C1 C2 D1 D2; 6 × C3 C4;
6 × D3 E3; 7 + D4 E4 E5; 30 × D5 D6;
6 × E1 E2; 9 + E6 F6;
8 + F1 F2 F3; 2 / F4 F5""")
kk6.units
{('A1', 'A2', 'A3', 'A4', 'A5', 'A6'), ('A1', 'B1', 'C1', 'D1', 'E1', 'F1'), ('A2', 'B2', 'C2', 'D2', 'E2', 'F2'), ('A3', 'B3', 'C3', 'D3', 'E3', 'F3'), ('A4', 'B4', 'C4', 'D4', 'E4', 'F4'), ('A5', 'B5', 'C5', 'D5', 'E5', 'F5'), ('A6', 'B6', 'C6', 'D6', 'E6', 'F6'), ('B1', 'B2', 'B3', 'B4', 'B5', 'B6'), ('C1', 'C2', 'C3', 'C4', 'C5', 'C6'), ('D1', 'D2', 'D3', 'D4', 'D5', 'D6'), ('E1', 'E2', 'E3', 'E4', 'E5', 'E6'), ('F1', 'F2', 'F3', 'F4', 'F5', 'F6')}
kk6.cages
[Cage(target=11, op='+', squares=['A1', 'B1']), Cage(target=2, op='/', squares=['A2', 'A3']), Cage(target=20, op='×', squares=['A4', 'B4']), Cage(target=6, op='×', squares=['A5', 'A6', 'B6', 'C6']), Cage(target=3, op='-', squares=['B2', 'B3']), Cage(target=3, op='/', squares=['B5', 'C5']), Cage(target=240, op='×', squares=['C1', 'C2', 'D1', 'D2']), Cage(target=6, op='×', squares=['C3', 'C4']), Cage(target=6, op='×', squares=['D3', 'E3']), Cage(target=7, op='+', squares=['D4', 'E4', 'E5']), Cage(target=30, op='×', squares=['D5', 'D6']), Cage(target=6, op='×', squares=['E1', 'E2']), Cage(target=9, op='+', squares=['E6', 'F6']), Cage(target=8, op='+', squares=['F1', 'F2', 'F3']), Cage(target=2, op='/', squares=['F4', 'F5'])]
kk6.peers['A1']
{'A2', 'A3', 'A4', 'A5', 'A6', 'B1', 'C1', 'D1', 'E1', 'F1'}
kk6.unitsfor['A1']
(('A1', 'A2', 'A3', 'A4', 'A5', 'A6'), ('A1', 'B1', 'C1', 'D1', 'E1', 'F1'))
A solution to a KenKen puzzle is a dict of the form {square: {value}, ...}
such that:
def is_solution(values, kenken) -> bool:
"""Is `values` a solution to `kenken`?"""
def singleton(s) -> bool: return len(values[s]) == 1
def pandigits(u) -> bool: return union(values[s] for s in u) == kenken.digits
def cage_good(c) -> bool: return cage_solved(c, [first(values[s]) for s in c.squares])
return (all(singleton(s) for s in kenken.squares) and
all(pandigits(u) for u in kenken.units) and
all(cage_good(c) for c in kenken.cages))
def cage_solved(cage, numbers) -> bool:
"""Do `numbers`, in some order, solve the equation in this cage?"""
op = OPS[cage.op]
return any(reduce(op, nums) == cage.target
for nums in orderings(op, numbers))
What orderings of the numbers in a cage do we have to try? That depends on the operator:
1 + 2 + 3 + 4
is the same as 4 + 3 + 2 + 1
(or any other order).4 - 3 - 2 - 1
is different from 1 - 2 - 3 - 4
.Remember, the grouping is always left-to-right: (((4 - 3) - 2) - 1)
.
With n numbers in a subtraction or division cage you might think there are n! different possible results, but actually there are only n, because only the choice of which number goes first matters; any order of the remaining numbers gives the same result:
4 - 3 - 2 - 1
= 4 - (3 + 2 + 1)
, so all 6 permutations of (3, 2, 1)
give the same result, -2
.3 - 4 - 2 - 1
= 3 - (4 + 2 + 1)
, so all 6 permutations of (4, 2, 1)
give the same result, -4
.2 - 4 - 3 - 1
= 2 - (4 + 3 + 1)
, so all 6 permutations of (4, 3, 1)
give the same result, -6
.1 - 4 - 3 - 2
= 1 - (4 + 3 + 2)
, so all 6 permutations of (4, 3, 2)
give the same result, -8
.def orderings(op, numbers: List[int]) -> List[List[int]]:
"""What orderings of `numbers` do we try with `op` to try to reach a target?"""
if op in {add, mul}: # commutative, only need one ordering
return [numbers]
else: # try all rotations, to put each number first in one of the orderings
return [numbers[i:] + numbers[:i] for i in range(len(numbers))]
Similar to the Sudoku program, we propagate constraints with these two functions:
fill
fills in square s with digit d. It does this by eliminating all the other digits.eliminate
eliminates a digit d as a possibility for a square s, and checks if there are other possible digits that are consistent with the other squares.def fill(kenken, values, s, d) -> Optional[Values]:
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return None if the eliminations are not possible."""
ok = all(eliminate(kenken, values, s, d2) for d2 in values[s] if d2 != d)
return values if ok else None
def eliminate(kk: KenKen, values, s, d) -> bool:
"""Eliminate d from values[s]; return True if all consistency checks are True."""
if d not in values[s]:
return True ## Already eliminated
values[s] = values[s] - {d}
return (values[s] and
arc_consistent(kk, values, s) and
dual_consistent(kk, values, s, d) and
cage_consistent(kk, values, s))
The function eliminate
removes the digit d
from consideration for square s
, and makes these checks for consistency, propagating constraints from squares to peers along the way:
s
, then eliminate them.def arc_consistent(kk, values, s) -> bool:
"""If a square s is reduced to one value d2, then eliminate d2 from the peers."""
[d2, *others] = values[s]
return others or all(eliminate(kk, values, s2, d2) for s2 in kk.peers[s])
def dual_consistent(kk, values, s, d) -> bool:
"""If a unit u is reduced to only one place for a value d, then put it there."""
def place_for_d(u) -> bool:
places = [s for s in u if d in values[s]]
return places and (len(places) > 1 or fill(kk, values, places[0], d))
return all(place_for_d(u) for u in kk.unitsfor[s])
def cage_consistent(kk, values, s) -> bool:
"""Make sure that there is some assignment that satisfies the cage for square s,
and eliminate the values that are impossible."""
cage = kk.cagefor[s]
possible = possible_cage_values(values, cage)
return (possible and
all(eliminate(kk, values, s1, d)
for s1 in cage.squares
for d in values[s1] if d not in possible[s1]))
def possible_cage_values(values, cage) -> Values:
"""Return a dict of {s: possible_digits} for each square s in the cage."""
possible = defaultdict(set)
for numbers in crossproduct(*[values[s] for s in cage.squares]):
if cage_solved(cage, numbers):
for (s, v) in zip(cage.squares, numbers):
possible[s].add(v)
return possible
The initial dict of possible values is created by starting with the assumption that any square could be any digit, and then applying the cage constraints:
def initial_values(kenken) -> Values:
"""Assign initial values to each square, just considering cages, not rows/columns."""
values = {s: kenken.digits for s in kenken.squares}
for cage in kenken.cages:
values.update(possible_cage_values(values, cage))
return values
values = initial_values(kk6)
values
{'B6': {1, 2, 3, 6}, 'B5': {1, 2, 3, 6}, 'C6': {1, 2, 3, 6}, 'D3': {1, 2, 3, 6}, 'A6': {1, 2, 3, 6}, 'D6': {5, 6}, 'E2': {1, 2, 3, 6}, 'D4': {1, 2, 3, 4, 5}, 'E3': {1, 2, 3, 6}, 'A3': {1, 2, 3, 4, 6}, 'A5': {1, 2, 3, 6}, 'F5': {1, 2, 3, 4, 6}, 'F1': {1, 2, 3, 4, 5, 6}, 'A2': {1, 2, 3, 4, 6}, 'E5': {1, 2, 3, 4, 5}, 'F4': {1, 2, 3, 4, 6}, 'B3': {1, 2, 3, 4, 5, 6}, 'D2': {2, 3, 4, 5, 6}, 'B2': {1, 2, 3, 4, 5, 6}, 'F6': {3, 4, 5, 6}, 'C1': {2, 3, 4, 5, 6}, 'F2': {1, 2, 3, 4, 5, 6}, 'B4': {4, 5}, 'C3': {1, 2, 3, 6}, 'E4': {1, 2, 3, 4, 5}, 'C2': {2, 3, 4, 5, 6}, 'A1': {5, 6}, 'F3': {1, 2, 3, 4, 5, 6}, 'E1': {1, 2, 3, 6}, 'A4': {4, 5}, 'D1': {2, 3, 4, 5, 6}, 'D5': {5, 6}, 'B1': {5, 6}, 'E6': {3, 4, 5, 6}, 'C4': {1, 2, 3, 6}, 'C5': {1, 2, 3, 6}}
We see, for example, that the two squares in the "11 +" cage, A1
and B1
, must be either 5 or 6, because no other two digits sum to 11:
cage = kk6.cagefor['A1']
cage
Cage(target=11, op='+', squares=['A1', 'B1'])
assert possible_cage_values(values, cage) == {'A1': {5, 6}, 'B1': {5, 6}}
We use depth-first-search to find a solution:
values.copy()
, so that if we have to back up, values
is unchanged.def solve(kenken) -> Values:
"""Solve a KenKen puzzle with search, assert the solution is valid, and return the solution."""
values = search(kenken, initial_values(kenken))
assert is_solution(values, kenken)
return values
def search(kenken, values) -> Optional[Values]:
"""Using depth-first search and constraint propagation, find values that solve puzzle."""
if values is None:
return None ## Failed earlier
if all(len(values[s]) == 1 for s in kenken.squares):
assert is_solution(values, kenken)
return values ## Solved!
## Chose the unfilled square s with the fewest possibilities and try each possible value for s
s = min((s for s in kenken.squares if len(values[s]) > 1), key=lambda s: len(values[s]))
return first_true(search(kenken, fill(kenken, values.copy(), s, d))
for d in values[s])
def first_true(iterable): return first(x for x in iterable if x)
We can see that search solves the example puzzle, finding a single value for every square:
solve(kk6)
{'B6': {3}, 'B5': {2}, 'C6': {1}, 'D3': {1}, 'A6': {2}, 'D6': {6}, 'E2': {3}, 'D4': {2}, 'E3': {6}, 'A3': {3}, 'A5': {1}, 'F5': {3}, 'F1': {1}, 'A2': {6}, 'E5': {4}, 'F4': {6}, 'B3': {4}, 'D2': {4}, 'B2': {1}, 'F6': {4}, 'C1': {4}, 'F2': {2}, 'B4': {5}, 'C3': {2}, 'E4': {1}, 'C2': {5}, 'A1': {5}, 'F3': {5}, 'E1': {2}, 'A4': {4}, 'D1': {3}, 'D5': {5}, 'B1': {6}, 'E6': {5}, 'C4': {3}, 'C5': {6}}
The values
dict is not a visually pleasing portrayal of the solution. Let's develop a better one, using the HTML
and display
functions from the IPython.core.display
module:
from IPython.core.display import HTML, display
def show(kenken, values=None):
"""Display a KenKen puzzle, with the values filled in."""
if values is None:
values = solve(kenken)
result = ['<style>table td {table-layout:fixed; width:50px; height: 50px}</style>\n<table>']
for r in kenken.rows:
result += ['<tr>']
for c in kenken.cols:
s = r + c
result += [cell(kenken, s, values.get(s, set(['X'])))]
result += ['</table>']
return display(HTML(''.join(result)))
def cell(kenken, s, val) -> str:
"""HTML for a single table cell; if it is the first cell in a cage, show target/op.
Make a thick border with every neighboring cell that is not in the same cage."""
cage = kenken.cagefor[s]
T, R, B, L = [1 if same_cage(kenken, s, s2) else 8 for s2 in neighbors(s)]
borders = f"border: solid black; border-width: {T}px {R}px {B}px {L}px;"
header = f'{cage.target}{cage.op}' if s == min(cage.squares) else ''
nums = ''.join(map(str, val))
return f'<td style="{borders}">{header}<br><span style="font-size: 2.5em">{nums}</span></td>'
def neighbors(s: Square) -> List[Square]:
"""The neighboring squares in [top, right, bottom, left] directions."""
r, c = map(ord, s)
return [chr(r + Δr) + chr(c + Δc)
for (Δr, Δc) in ((-1, 0), (0, 1), (1, 0), (0, -1))]
def same_cage(kenken, s1, s2) -> bool:
"""Are squares s1 and s2 in the same cage in kenken?"""
return kenken.cagefor.get(s1) == kenken.cagefor.get(s2)
show(kk6)
11+ 5 | 2/ 6 | 3 | 20× 4 | 6× 1 | 2 |
6 | 3- 1 | 4 | 5 | 3/ 2 | 3 |
240× 4 | 5 | 6× 2 | 3 | 6 | 1 |
3 | 4 | 6× 1 | 7+ 2 | 30× 5 | 6 |
6× 2 | 3 | 6 | 1 | 4 | 9+ 5 |
8+ 1 | 2 | 5 | 2/ 6 | 3 | 4 |
That looks much better!
We can solve more puzzles. Here is a list of ten puzzles of various sizes:
kenkens = [
KenKen(4, "7 + A1 B1; 2 / C1 D1; 1 - A2 A3; 3 - B2 B3; 2 / A4 B4; 3 = C2; 12 × C3 C4 D4; 2 / D2 D3"),
KenKen(4, "1 - a1 a2; 2 / a3 b3; 5 + a4 b4; 2 / b1 c1; 5 + b2 c2; 1 - c3 d3; 6 x c4 d4; 4 x d1 d2"),
KenKen(4, "48 x a1 a2 a3 b1; 5 + a4 b4; 2 / b2 c2; 12 x b3 c3; 5 + c1 d1; 2 - d2 d3; 1 - c4 d4"),
KenKen(5, """12 × a1 b1; 2 - a2 b2; 4 - a3 a4; 2 / a5 b5; 2 / b3 b4; 2 / c1 c2; 15 + c3 c4 c5 d3;
3 - d1 e1; 16 × d2 e2 e3; 1 - d4 e4; 2 - d5 e5"""),
KenKen(5, """8 + a1 b1 c1; 2 - a2 a3; 4 × a4 a5 b5; 2 / b2 b3; 1 - b4 c4; 3 = c5;
4 - c2 d2; 10 + c3 d3 d4; 48 × d1 e1 e2; 2 / e3 e4; 3 - d5 e5"""),
KenKen(5, """3 - a1 a2; 1 - a3 a4; 15 × a5 b5 b4; 12 × b1 b2 c2; 10 + b3 c3 d3;
1 = c1; 2 / c4 c5; 2 / d1 d2; 20 × d4 d5 e5; 8 + e1 e2; 3 + e3 e4"""),
kk6,
KenKen(7, """3 - a1 b1; 108 × a2 a3 b3; 13 + a4 b4 b5; 2 / a5 a6; 13 + a7 b6 b7;
3 - b2 c2; 70 × c1 d1 e1; 5 = d2; 504 × c3 c4 d3 e3 e4; 60 × c5 d4 d5 e5;
4 - c6 c7; 1 - d6 d7; 6 - e6 e7; 2 / f1 g1; 2 / g2 g3; 30 × e2 f2 f3;
140 × f4 f5 g4; 1 - g5 g6; 14 + f6 f7 g7"""),
KenKen(7, """3 = a1; 15 + a2 a3 b3; 12 + a4 a5 a6; 1 - a7 b7;
6 / b1 b2; 7 + b4 b5; 7 = b6; 8 × c1 c2; 2 / c3 c4; 35 × c5 c6 c7;
11 + d1 e1 e2; 5 - d2 d3; 3 / d4 e4; 30 × d5 d6; 9 + d7 e7; 2 - e5 e6;
8 + e3 f3 g3; 24 × f1 f2; 35 × g1 g2; 10 + f4 f5; 2 × f6 f7; 6 + g4 g5; 3 - g6 g7"""),
KenKen(8, """3 / a1 a2; 9 + a3 a4; 210 × a5 b5 c5 b4 c4; 19 + a6 b6 c6; 90 × a7 a8 b7;
10 × b1 b2; 8 - b3; 4 / b8 c8;
7 + c1 d1; 7 = c2; 1 - c3 d3; 4 = c7; 2 / d2 e2; 17 + d4 e4 f4; 6 / d5 d6; 6 × d7 d8;
16 + e1 f1 f2 g2; 7 = e3; 5 - e5 e6; 12 × e7 e8 f8; 7 + f3 g3; 80 × f5 f6 f7;
8 / g1 h1; 4 - h2 h3; 1 - g4 h4; 15 + g5 h5 h6; 1 = g6; 12 + g7 h7; 1 - g8 h8""")
]
%%time
for kk in kenkens:
show(kk)
7+ 4 | 1- 2 | 3 | 2/ 1 |
3 | 3- 1 | 4 | 2 |
2/ 2 | 3= 3 | 12× 1 | 4 |
1 | 2/ 4 | 2 | 3 |
1- 3 | 4 | 2/ 2 | 5+ 1 |
2/ 2 | 5+ 3 | 1 | 4 |
1 | 2 | 1- 4 | 6X 3 |
4X 4 | 1 | 3 | 2 |
48X 3 | 4 | 2 | 5+ 1 |
2 | 2/ 1 | 12X 3 | 4 |
5+ 1 | 2 | 4 | 1- 3 |
4 | 2- 3 | 1 | 2 |
12× 4 | 2- 3 | 4- 1 | 5 | 2/ 2 |
3 | 5 | 2/ 2 | 4 | 1 |
2/ 1 | 2 | 15+ 5 | 3 | 4 |
3- 2 | 16× 4 | 3 | 1- 1 | 2- 5 |
5 | 1 | 4 | 2 | 3 |
8+ 2 | 2- 3 | 5 | 4× 1 | 4 |
5 | 2/ 2 | 4 | 1- 3 | 1 |
1 | 4- 5 | 10+ 2 | 4 | 3= 3 |
48× 4 | 1 | 3 | 5 | 3- 2 |
3 | 4 | 2/ 1 | 2 | 5 |
3- 5 | 2 | 1- 4 | 3 | 15× 1 |
12× 4 | 1 | 10+ 2 | 5 | 3 |
1= 1 | 3 | 5 | 2/ 4 | 2 |
2/ 2 | 4 | 3 | 20× 1 | 5 |
8+ 3 | 5 | 3+ 1 | 2 | 4 |
11+ 5 | 2/ 6 | 3 | 20× 4 | 6× 1 | 2 |
6 | 3- 1 | 4 | 5 | 3/ 2 | 3 |
240× 4 | 5 | 6× 2 | 3 | 6 | 1 |
3 | 4 | 6× 1 | 7+ 2 | 30× 5 | 6 |
6× 2 | 3 | 6 | 1 | 4 | 9+ 5 |
8+ 1 | 2 | 5 | 2/ 6 | 3 | 4 |
3- 4 | 108× 6 | 3 | 13+ 7 | 2/ 1 | 2 | 13+ 5 |
1 | 3- 7 | 6 | 2 | 4 | 5 | 3 |
70× 7 | 4 | 504× 1 | 3 | 60× 5 | 4- 6 | 2 |
2 | 5= 5 | 7 | 1 | 6 | 1- 3 | 4 |
5 | 30× 3 | 4 | 6 | 2 | 6- 7 | 1 |
2/ 3 | 2 | 5 | 140× 4 | 7 | 14+ 1 | 6 |
6 | 2/ 1 | 2 | 5 | 1- 3 | 4 | 7 |
3= 3 | 15+ 5 | 6 | 12+ 4 | 7 | 1 | 1- 2 |
6/ 6 | 1 | 4 | 7+ 5 | 2 | 7= 7 | 3 |
8× 2 | 4 | 2/ 3 | 6 | 35× 1 | 5 | 7 |
11+ 1 | 5- 2 | 7 | 3/ 3 | 30× 5 | 6 | 9+ 4 |
7 | 3 | 8+ 2 | 1 | 2- 6 | 4 | 5 |
24× 4 | 6 | 5 | 10+ 7 | 3 | 2× 2 | 1 |
35× 5 | 7 | 1 | 6+ 2 | 4 | 3- 3 | 6 |
3/ 6 | 2 | 9+ 1 | 8 | 210× 7 | 19+ 4 | 90× 3 | 5 |
10× 2 | 5 | 8- 8 | 1 | 3 | 7 | 6 | 4/ 4 |
7+ 3 | 7= 7 | 1- 6 | 5 | 2 | 8 | 4= 4 | 1 |
4 | 2/ 8 | 5 | 17+ 7 | 6/ 1 | 6 | 6× 2 | 3 |
16+ 5 | 4 | 7= 7 | 6 | 5- 8 | 3 | 12× 1 | 2 |
7 | 1 | 7+ 3 | 4 | 80× 5 | 2 | 8 | 6 |
8/ 8 | 3 | 4 | 1- 2 | 15+ 6 | 1= 1 | 12+ 5 | 1- 7 |
1 | 4- 6 | 2 | 3 | 4 | 5 | 7 | 8 |
CPU times: user 240 ms, sys: 4.26 ms, total: 244 ms Wall time: 243 ms
It took only about 1/4 second to correctly solve (and print) all 10 puzzles. That's not bad, but it is a lot slower than the Sudoku solver. I think part of the problem is that the code to handle cages could be more efficient; it could cache results instead of recomputing them, and it could consider the possible values for all the squares in a cage together, rather than just consider the values for each square independently. For example, in a 7×7 grid with a four-square "105 ×" cage, possible_cage_values
computes that each square must be one of {1, 2, 3, 5, 6, 7}
, but it would be better to make use of the fact that the four squares must be either {1, 5, 6, 7}
(in some order) or {2, 3, 5, 7}
.
Here are some unit tests to give partial code coverage, and to show how the subfunctions work:
def tests():
"""Unit tests."""
for kk in kenkens:
assert len(kk.units) == 2 * kk.N
assert len(kk.peers) -- kk.N ** 2
assert all(len(kk.peers[s]) == 2 * kk.N - 2 for s in kk.squares)
kk4 = kenkens[0]
soln = {'A1': {4}, 'A2': {2}, 'A3': {3}, 'A4': {1},
'B1': {3}, 'B2': {1}, 'B3': {4}, 'B4': {2},
'C1': {2}, 'C2': {3}, 'C3': {1}, 'C4': {4},
'D1': {1}, 'D2': {4}, 'D3': {2}, 'D4': {3}}
assert solve(kk4) == soln
assert is_solution(soln, kk4)
cage = kk6.cagefor['D4']
assert cage == Cage(target=7, op='+', squares=['D4', 'E4', 'E5'])
assert cage == make_cage('7 + d4 e4 e5')
assert cage_solved(cage, [2, 1, 4])
assert not cage_solved(cage, [2, 1, 3])
assert orderings(add, [2, 1, 4]) == [[2, 1, 4]]
assert orderings(sub, [2, 1, 4]) == [[2, 1, 4], [1, 4, 2], [4, 2, 1]]
vals = {'D4': kk6.digits, 'E4': kk6.digits, 'E5': kk6.digits}
assert possible_cage_values(vals, cage) == {
'D4': {1, 2, 3, 4, 5},
'E4': {1, 2, 3, 4, 5},
'E5': {1, 2, 3, 4, 5}}
assert first([0, 1, 2, 3]) == 0
assert first({3}) == 3
assert first_true([0, '', False, 4]) == 4
assert first_true([0, '', False]) == None
assert union([{1, 2, 3}, {3, 4, 5}]) == {1, 2, 3, 4, 5}
assert neighbors('B2') == ['A2', 'B3', 'C2', 'B1']
assert same_cage(kk6, 'A1', 'B1')
assert not same_cage(kk6, 'A1', 'A2')
return True
tests()
True