{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig
2016, 2021
\n", "\n", "# KenKen Puzzles\n", "\n", "[KenKen](https://en.wikipedia.org/wiki/KenKen) is a fill-in-the-grid puzzle game, similar to Sudoku (solved [in another notebook](Sudoku.ipynb)), but with arithmetic as well as logic. \n", "\n", "An example puzzle and solution:\n", "\n", "  \n", "\n", "The rules of KenKen are:\n", "\n", "- Every **square** of the *N*×*N* grid must be filled with a **digit** from 1 to *N*.\n", "- No digit can appear twice in any **row** or **column**.\n", "- Thick lines divide the grid into contiguous groups of squares called **cages**:\n", " - Each cage is annotated with a **target number** and an arithmetic **operator**. For example:\n", " - \"11 +\" means the digits in the cage must add to 11 (e.g. `5 + 6`).\n", " - \"240 ×\" means the digits must form a product of 240 (e.g. `4 × 5 × 3 × 4`).\n", "
(Two `4`s in a cage are ok if they are in different rows and columns.)\n", " - \"2 ÷\" (or \"2 /\") means the digits, in some order, must form a quotient of 2 (e.g. `6 / 3` ).\n", " - \"3 -\" means the digits, in some order, must form a difference of 3 (e.g. `4 - 1`).\n", " - \"5 =\" means the cage must have one square, which is filled with `5`.\n", " - Evaluation is always left to right: `6 - 3 - 2 - 1` = `(((6 - 3) - 2) - 1)` = `0`\n", " \n", " \n", "# Strategy for Solving Puzzles\n", "\n", "The KenKen-solving program uses **constraint propagation** and **search**:\n", " - For each square, keep track of the set of digits that might possibly fill the square.\n", " - Use the constraints on rows, columns, and cages to eliminate some possible digits in some squares.\n", " - **Constraints** on one square can **propagate** to other squares in the row, column, or cage.\n", " - If that doesn't solve the puzzle, then **search**: pick a square and guess a digit to fill the square.\n", " - Recursively search from there.\n", " - If that leads to a solution, great; if it leads to a contradiction, back up and guess a different digit.\n", " \n", "\n", "# Data Types\n", "\n", "Throughout the program the following variable names represent the following data types:\n", "- `r` is a **row** label, e.g. `'A'`\n", "- `c` is a **column** label, e.g. `'3'`\n", "- `s` is a **square** label, e.g. `'A3'`\n", "- `d` is a **digit**, e.g. `9`\n", "- `u` is a **unit** (a row or column), e.g. `('A1', 'A2', 'A3', 'A4', 'A5', 'A6')`\n", "- `cage` is a Cage, consisting of a **target number**, an **operator**, and a list of squares\n", "- `values` is a dict of {square: set_of_possible_digits}, e.g. `{'A1': {5, 6}, 'B1': {6, 5}, ...}`\n", " - A `values` dict is a **solution** when every square has been filled with a single digit, and they satisfy all the constraints.\n", "- `kk` or `kenken` is a KenKen object, which describes the puzzle. It has these attributes:\n", " - `.N`: the number of squares on a side\n", " - `.digits`: the set of digits allowed: `{1, ..., N}`\n", " - `.squares`: a set of all squares in the grid\n", " - `.cages`: a list of all cages in the grid\n", " - `.cagefor`: a dict where `.cagefor[s]` is the cage that square `s` is part of.\n", " - `.unitsfor`: a dict where `.unitsfor[s]` is a tuple of the two units for square `s`.\n", " - `.units`: a set of all units\n", " - `.peers`: a dict where `.peers[s]` is a set of the `2 * (N - 1)` squares in the same column or row as `s`.\n", "- `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." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from typing import Dict, Set, List, Optional\n", "from itertools import product as crossproduct\n", "from collections import defaultdict\n", "from operator import add, sub, mul, truediv\n", "from dataclasses import dataclass\n", "from functools import reduce" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "Square = str\n", "Unit = tuple\n", "Values = Dict[Square, Set[int]] # The possible values that fill in the squares\n", "\n", "class KenKen:\n", " \"\"\"Describes a KenKen puzzle, but not the values used to fill in the puzzle squares.\"\"\"\n", " def __init__(self, N, cage_descriptions, sep=\";\"):\n", " self.N = N\n", " self.digits = set(range(1, N + 1))\n", " self.cols = '123456789'[:N]\n", " self.rows = 'ABCDEFGHI'[:N]\n", " self.squares = {r + c for r in self.rows for c in self.cols}\n", " self.cages = [make_cage(description) for description in cage_descriptions.split(sep)]\n", " self.cagefor = {s: first(cage for cage in self.cages if s in cage.squares)\n", " for s in self.squares}\n", " self.unitsfor= {s: (Unit(s[0]+c for c in self.cols), Unit(r+s[1] for r in self.rows))\n", " for s in self.squares}\n", " self.units = union(self.unitsfor.values())\n", " self.peers = {s: union(self.unitsfor[s]) - {s}\n", " for s in self.squares}\n", " s1 = sorted(self.squares)\n", " s2 = sorted(s for cage in self.cages for s in cage.squares)\n", " assert s1 == s2, f\"Cage descriptions don't cover all squares:\\n{s1}\\n{s2}\"\n", "\n", "@dataclass\n", "class Cage:\n", " \"\"\"A collection of squares that must evaluate to `target` when `op` is applied to them.\"\"\"\n", " target: int\n", " op: str\n", " squares: List[Square]\n", " \n", "def make_cage(description) -> Cage:\n", " \"\"\"Make a cage from a description such as '3 + A1 A2'.\"\"\"\n", " num, op, *squares = description.upper().split()\n", " assert op in OPS\n", " return Cage(int(num), op, squares)\n", "\n", "OPS = {'+': add, '-': sub, '×': mul, '*': mul, 'X': mul, '/': truediv, '÷': truediv, '=': add}\n", " \n", "def first(iterable) -> Optional[object]: return next(iter(iterable), None)\n", "\n", "def union(sets) -> set: return set().union(*sets)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Example Puzzle \n", "\n", "Let's make a `KenKen` object for the example puzzle (repeated here):\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "kk6 = KenKen(6, \"\"\"\n", " 11 + A1 B1; 2 / A2 A3; 20 × A4 B4; 6 × A5 A6 B6 C6; \n", " 3 - B2 B3; 3 / B5 C5;\n", " 240 × C1 C2 D1 D2; 6 × C3 C4; \n", " 6 × D3 E3; 7 + D4 E4 E5; 30 × D5 D6; \n", " 6 × E1 E2; 9 + E6 F6;\n", " 8 + F1 F2 F3; 2 / F4 F5\"\"\")" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('A1', 'A2', 'A3', 'A4', 'A5', 'A6'),\n", " ('A1', 'B1', 'C1', 'D1', 'E1', 'F1'),\n", " ('A2', 'B2', 'C2', 'D2', 'E2', 'F2'),\n", " ('A3', 'B3', 'C3', 'D3', 'E3', 'F3'),\n", " ('A4', 'B4', 'C4', 'D4', 'E4', 'F4'),\n", " ('A5', 'B5', 'C5', 'D5', 'E5', 'F5'),\n", " ('A6', 'B6', 'C6', 'D6', 'E6', 'F6'),\n", " ('B1', 'B2', 'B3', 'B4', 'B5', 'B6'),\n", " ('C1', 'C2', 'C3', 'C4', 'C5', 'C6'),\n", " ('D1', 'D2', 'D3', 'D4', 'D5', 'D6'),\n", " ('E1', 'E2', 'E3', 'E4', 'E5', 'E6'),\n", " ('F1', 'F2', 'F3', 'F4', 'F5', 'F6')}" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kk6.units" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Cage(target=11, op='+', squares=['A1', 'B1']),\n", " Cage(target=2, op='/', squares=['A2', 'A3']),\n", " Cage(target=20, op='×', squares=['A4', 'B4']),\n", " Cage(target=6, op='×', squares=['A5', 'A6', 'B6', 'C6']),\n", " Cage(target=3, op='-', squares=['B2', 'B3']),\n", " Cage(target=3, op='/', squares=['B5', 'C5']),\n", " Cage(target=240, op='×', squares=['C1', 'C2', 'D1', 'D2']),\n", " Cage(target=6, op='×', squares=['C3', 'C4']),\n", " Cage(target=6, op='×', squares=['D3', 'E3']),\n", " Cage(target=7, op='+', squares=['D4', 'E4', 'E5']),\n", " Cage(target=30, op='×', squares=['D5', 'D6']),\n", " Cage(target=6, op='×', squares=['E1', 'E2']),\n", " Cage(target=9, op='+', squares=['E6', 'F6']),\n", " Cage(target=8, op='+', squares=['F1', 'F2', 'F3']),\n", " Cage(target=2, op='/', squares=['F4', 'F5'])]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kk6.cages" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'A2', 'A3', 'A4', 'A5', 'A6', 'B1', 'C1', 'D1', 'E1', 'F1'}" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kk6.peers['A1']" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(('A1', 'A2', 'A3', 'A4', 'A5', 'A6'), ('A1', 'B1', 'C1', 'D1', 'E1', 'F1'))" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kk6.unitsfor['A1']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Verifying a Solution\n", "\n", "A solution to a KenKen puzzle is a dict of the form `{square: {value}, ...}` such that:\n", "- Every square has only a single possible value remaining.\n", "- Every unit (row or column) has each of the digits 1 to *N* as values, once each.\n", "- Every cage has a collection of values that, in some order, evaluates to the cage's target under the cage's operator." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "def is_solution(values, kenken) -> bool:\n", " \"\"\"Is `values` a solution to `kenken`?\"\"\"\n", " def singleton(s) -> bool: return len(values[s]) == 1\n", " def pandigits(u) -> bool: return union(values[s] for s in u) == kenken.digits\n", " def cage_good(c) -> bool: return cage_solved(c, [first(values[s]) for s in c.squares])\n", " return (all(singleton(s) for s in kenken.squares) and \n", " all(pandigits(u) for u in kenken.units) and \n", " all(cage_good(c) for c in kenken.cages))\n", "\n", "def cage_solved(cage, numbers) -> bool:\n", " \"\"\"Do `numbers`, in some order, solve the equation in this cage?\"\"\"\n", " op = OPS[cage.op]\n", " return any(reduce(op, nums) == cage.target\n", " for nums in orderings(op, numbers))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What orderings of the numbers in a cage do we have to try? That depends on the operator:\n", "- Addition and multiplication are commutative, so we only need to try one order:\n", " - `1 + 2 + 3 + 4` is the same as `4 + 3 + 2 + 1` (or any other order).\n", "- Subtraction and division are not commutative: \n", " - `4 - 3 - 2 - 1` is different from `1 - 2 - 3 - 4`. \n", "\n", "Remember, the grouping is always left-to-right: `(((4 - 3) - 2) - 1)`.\n", "\n", "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:\n", " - `4 - 3 - 2 - 1` = `4 - (3 + 2 + 1)`, so all 6 permutations of `(3, 2, 1)` give the same result, `-2`.\n", " - `3 - 4 - 2 - 1` = `3 - (4 + 2 + 1)`, so all 6 permutations of `(4, 2, 1)` give the same result, `-4`.\n", " - `2 - 4 - 3 - 1` = `2 - (4 + 3 + 1)`, so all 6 permutations of `(4, 3, 1)` give the same result, `-6`.\n", " - `1 - 4 - 3 - 2` = `1 - (4 + 3 + 2)`, so all 6 permutations of `(4, 3, 2)` give the same result, `-8`." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "def orderings(op, numbers: List[int]) -> List[List[int]]:\n", " \"\"\"What orderings of `numbers` do we try with `op` to try to reach a target?\"\"\"\n", " if op in {add, mul}: # commutative, only need one ordering\n", " return [numbers] \n", " else: # try all rotations, to put each number first in one of the orderings\n", " return [numbers[i:] + numbers[:i] for i in range(len(numbers))]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Constraint Propagation\n", "\n", "Similar to [the Sudoku program](Sudoku.ipynb), we propagate constraints with these two functions:\n", "- `fill` fills in square *s* with digit *d*. It does this by eliminating all the other digits.\n", "- `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.\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def fill(kenken, values, s, d) -> Optional[Values]:\n", " \"\"\"Eliminate all the other values (except d) from values[s] and propagate.\n", " Return values, except return None if the eliminations are not possible.\"\"\"\n", " ok = all(eliminate(kenken, values, s, d2) for d2 in values[s] if d2 != d)\n", " return values if ok else None\n", "\n", "def eliminate(kk: KenKen, values, s, d) -> bool:\n", " \"\"\"Eliminate d from values[s]; return True if all consistency checks are True.\"\"\"\n", " if d not in values[s]:\n", " return True ## Already eliminated\n", " values[s] = values[s] - {d}\n", " return (values[s] and\n", " arc_consistent(kk, values, s) and \n", " dual_consistent(kk, values, s, d) and \n", " cage_consistent(kk, values, s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:\n", "\n", "1. If a square *s* is reduced to one value *d2*, then eliminate *d2* from the peers.\n", "2. If a unit *u* is reduced to only one place for a value *d*, then put it there.\n", "3. If some value assignments are no longer valid within the cage for `s`, then eliminate them." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def arc_consistent(kk, values, s) -> bool:\n", " \"\"\"If a square s is reduced to one value d2, then eliminate d2 from the peers.\"\"\"\n", " [d2, *others] = values[s]\n", " return others or all(eliminate(kk, values, s2, d2) for s2 in kk.peers[s])\n", " \n", "def dual_consistent(kk, values, s, d) -> bool:\n", " \"\"\"If a unit u is reduced to only one place for a value d, then put it there.\"\"\"\n", " def place_for_d(u) -> bool:\n", " places = [s for s in u if d in values[s]]\n", " return places and (len(places) > 1 or fill(kk, values, places[0], d))\n", " return all(place_for_d(u) for u in kk.unitsfor[s])\n", "\n", "def cage_consistent(kk, values, s) -> bool:\n", " \"\"\"Make sure that there is some assignment that satisfies the cage for square s,\n", " and eliminate the values that are impossible.\"\"\"\n", " cage = kk.cagefor[s]\n", " possible = possible_cage_values(values, cage)\n", " return (possible and\n", " all(eliminate(kk, values, s1, d)\n", " for s1 in cage.squares\n", " for d in values[s1] if d not in possible[s1]))\n", "\n", "def possible_cage_values(values, cage) -> Values:\n", " \"\"\"Return a dict of {s: possible_digits} for each square s in the cage.\"\"\"\n", " possible = defaultdict(set)\n", " for numbers in crossproduct(*[values[s] for s in cage.squares]):\n", " if cage_solved(cage, numbers):\n", " for (s, v) in zip(cage.squares, numbers):\n", " possible[s].add(v)\n", " return possible" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def initial_values(kenken) -> Values:\n", " \"\"\"Assign initial values to each square, just considering cages, not rows/columns.\"\"\"\n", " values = {s: kenken.digits for s in kenken.squares}\n", " for cage in kenken.cages:\n", " values.update(possible_cage_values(values, cage))\n", " return values" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'B6': {1, 2, 3, 6},\n", " 'B5': {1, 2, 3, 6},\n", " 'C6': {1, 2, 3, 6},\n", " 'D3': {1, 2, 3, 6},\n", " 'A6': {1, 2, 3, 6},\n", " 'D6': {5, 6},\n", " 'E2': {1, 2, 3, 6},\n", " 'D4': {1, 2, 3, 4, 5},\n", " 'E3': {1, 2, 3, 6},\n", " 'A3': {1, 2, 3, 4, 6},\n", " 'A5': {1, 2, 3, 6},\n", " 'F5': {1, 2, 3, 4, 6},\n", " 'F1': {1, 2, 3, 4, 5, 6},\n", " 'A2': {1, 2, 3, 4, 6},\n", " 'E5': {1, 2, 3, 4, 5},\n", " 'F4': {1, 2, 3, 4, 6},\n", " 'B3': {1, 2, 3, 4, 5, 6},\n", " 'D2': {2, 3, 4, 5, 6},\n", " 'B2': {1, 2, 3, 4, 5, 6},\n", " 'F6': {3, 4, 5, 6},\n", " 'C1': {2, 3, 4, 5, 6},\n", " 'F2': {1, 2, 3, 4, 5, 6},\n", " 'B4': {4, 5},\n", " 'C3': {1, 2, 3, 6},\n", " 'E4': {1, 2, 3, 4, 5},\n", " 'C2': {2, 3, 4, 5, 6},\n", " 'A1': {5, 6},\n", " 'F3': {1, 2, 3, 4, 5, 6},\n", " 'E1': {1, 2, 3, 6},\n", " 'A4': {4, 5},\n", " 'D1': {2, 3, 4, 5, 6},\n", " 'D5': {5, 6},\n", " 'B1': {5, 6},\n", " 'E6': {3, 4, 5, 6},\n", " 'C4': {1, 2, 3, 6},\n", " 'C5': {1, 2, 3, 6}}" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "values = initial_values(kk6)\n", "values" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Cage(target=11, op='+', squares=['A1', 'B1'])" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cage = kk6.cagefor['A1']\n", "cage " ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "assert possible_cage_values(values, cage) == {'A1': {5, 6}, 'B1': {5, 6}}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Search\n", "\n", "We use depth-first-search to find a solution:\n", "- If all squares have exactly one possible value, that's a solution.\n", "- Otherwise, choose an unfilled square *s* with the minimum number of possible values.\n", "- For each possible value *d* for square *s*, try filling *s* with *d* and recursively searching for a solution.\n", " - Recursive calls use `values.copy()`, so that if we have to back up, `values` is unchanged. " ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "def solve(kenken) -> Values:\n", " \"\"\"Solve a KenKen puzzle with search, assert the solution is valid, and return the solution.\"\"\"\n", " values = search(kenken, initial_values(kenken))\n", " assert is_solution(values, kenken)\n", " return values\n", "\n", "def search(kenken, values) -> Optional[Values]:\n", " \"\"\"Using depth-first search and constraint propagation, find values that solve puzzle.\"\"\"\n", " if values is None:\n", " return None ## Failed earlier\n", " if all(len(values[s]) == 1 for s in kenken.squares):\n", " assert is_solution(values, kenken)\n", " return values ## Solved!\n", " ## Chose the unfilled square s with the fewest possibilities and try each possible value for s\n", " s = min((s for s in kenken.squares if len(values[s]) > 1), key=lambda s: len(values[s]))\n", " return first_true(search(kenken, fill(kenken, values.copy(), s, d))\n", " for d in values[s])\n", "\n", "def first_true(iterable): return first(x for x in iterable if x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can see that search solves the example puzzle, finding a single value for every square:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'B6': {3},\n", " 'B5': {2},\n", " 'C6': {1},\n", " 'D3': {1},\n", " 'A6': {2},\n", " 'D6': {6},\n", " 'E2': {3},\n", " 'D4': {2},\n", " 'E3': {6},\n", " 'A3': {3},\n", " 'A5': {1},\n", " 'F5': {3},\n", " 'F1': {1},\n", " 'A2': {6},\n", " 'E5': {4},\n", " 'F4': {6},\n", " 'B3': {4},\n", " 'D2': {4},\n", " 'B2': {1},\n", " 'F6': {4},\n", " 'C1': {4},\n", " 'F2': {2},\n", " 'B4': {5},\n", " 'C3': {2},\n", " 'E4': {1},\n", " 'C2': {5},\n", " 'A1': {5},\n", " 'F3': {5},\n", " 'E1': {2},\n", " 'A4': {4},\n", " 'D1': {3},\n", " 'D5': {5},\n", " 'B1': {6},\n", " 'E6': {5},\n", " 'C4': {3},\n", " 'C5': {6}}" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve(kk6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Display\n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "from IPython.core.display import HTML, display\n", "\n", "def show(kenken, values=None):\n", " \"\"\"Display a KenKen puzzle, with the values filled in.\"\"\"\n", " if values is None:\n", " values = solve(kenken)\n", " result = ['\\n']\n", " for r in kenken.rows:\n", " result += ['']\n", " for c in kenken.cols:\n", " s = r + c\n", " result += [cell(kenken, s, values.get(s, set(['X'])))]\n", " result += ['
']\n", " return display(HTML(''.join(result)))\n", "\n", "def cell(kenken, s, val) -> str:\n", " \"\"\"HTML for a single table cell; if it is the first cell in a cage, show target/op.\n", " Make a thick border with every neighboring cell that is not in the same cage.\"\"\"\n", " cage = kenken.cagefor[s]\n", " T, R, B, L = [1 if same_cage(kenken, s, s2) else 8 for s2 in neighbors(s)]\n", " borders = f\"border: solid black; border-width: {T}px {R}px {B}px {L}px;\"\n", " header = f'{cage.target}{cage.op}' if s == min(cage.squares) else ''\n", " nums = ''.join(map(str, val))\n", " return f'{header}
{nums}' \n", "\n", "def neighbors(s: Square) -> List[Square]: \n", " \"\"\"The neighboring squares in [top, right, bottom, left] directions.\"\"\"\n", " r, c = map(ord, s)\n", " return [chr(r + Δr) + chr(c + Δc)\n", " for (Δr, Δc) in ((-1, 0), (0, 1), (1, 0), (0, -1))]\n", "\n", "def same_cage(kenken, s1, s2) -> bool:\n", " \"\"\"Are squares s1 and s2 in the same cage in kenken?\"\"\"\n", " return kenken.cagefor.get(s1) == kenken.cagefor.get(s2)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(kk6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That looks much better!\n", "\n", "# More Puzzles\n", "\n", "We can solve more puzzles. Here is a list of ten puzzles of various sizes:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "kenkens = [\n", " 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\"),\n", " 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\"),\n", " 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\"),\n", " 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;\n", " 3 - d1 e1; 16 × d2 e2 e3; 1 - d4 e4; 2 - d5 e5\"\"\"),\n", " KenKen(5, \"\"\"8 + a1 b1 c1; 2 - a2 a3; 4 × a4 a5 b5; 2 / b2 b3; 1 - b4 c4; 3 = c5;\n", " 4 - c2 d2; 10 + c3 d3 d4; 48 × d1 e1 e2; 2 / e3 e4; 3 - d5 e5\"\"\"),\n", " KenKen(5, \"\"\"3 - a1 a2; 1 - a3 a4; 15 × a5 b5 b4; 12 × b1 b2 c2; 10 + b3 c3 d3;\n", " 1 = c1; 2 / c4 c5; 2 / d1 d2; 20 × d4 d5 e5; 8 + e1 e2; 3 + e3 e4\"\"\"),\n", " kk6,\n", " KenKen(7, \"\"\"3 - a1 b1; 108 × a2 a3 b3; 13 + a4 b4 b5; 2 / a5 a6; 13 + a7 b6 b7;\n", " 3 - b2 c2; 70 × c1 d1 e1; 5 = d2; 504 × c3 c4 d3 e3 e4; 60 × c5 d4 d5 e5;\n", " 4 - c6 c7; 1 - d6 d7; 6 - e6 e7; 2 / f1 g1; 2 / g2 g3; 30 × e2 f2 f3; \n", " 140 × f4 f5 g4; 1 - g5 g6; 14 + f6 f7 g7\"\"\"),\n", " KenKen(7, \"\"\"3 = a1; 15 + a2 a3 b3; 12 + a4 a5 a6; 1 - a7 b7;\n", " 6 / b1 b2; 7 + b4 b5; 7 = b6; 8 × c1 c2; 2 / c3 c4; 35 × c5 c6 c7;\n", " 11 + d1 e1 e2; 5 - d2 d3; 3 / d4 e4; 30 × d5 d6; 9 + d7 e7; 2 - e5 e6;\n", " 8 + e3 f3 g3; 24 × f1 f2; 35 × g1 g2; 10 + f4 f5; 2 × f6 f7; 6 + g4 g5; 3 - g6 g7\"\"\"),\n", " KenKen(8, \"\"\"3 / a1 a2; 9 + a3 a4; 210 × a5 b5 c5 b4 c4; 19 + a6 b6 c6; 90 × a7 a8 b7;\n", " 10 × b1 b2; 8 - b3; 4 / b8 c8;\n", " 7 + c1 d1; 7 = c2; 1 - c3 d3; 4 = c7; 2 / d2 e2; 17 + d4 e4 f4; 6 / d5 d6; 6 × d7 d8;\n", " 16 + e1 f1 f2 g2; 7 = e3; 5 - e5 e6; 12 × e7 e8 f8; 7 + f3 g3; 80 × f5 f6 f7;\n", " 8 / g1 h1; 4 - h2 h3; 1 - g4 h4; 15 + g5 h5 h6; 1 = g6; 12 + g7 h7; 1 - g8 h8\"\"\")\n", "]" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "
7+
4		1-
2
3		2/
1

3		3-
1
4
2
2/
2		3=
3		12×
1
4

1		2/
4
2
3
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
1-
3
4		2/
2		5+
1
2/
2		5+
3
1
4

1
2		1-
4		6X
3
4X
4
1
3
2
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
48X
3
4
2		5+
1

2		2/
1		12X
3
4
5+
1
2
4		1-
3

4		2-
3
1
2
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "
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
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 240 ms, sys: 4.26 ms, total: 244 ms\n", "Wall time: 243 ms\n" ] } ], "source": [ "%%time\n", "for kk in kenkens:\n", " show(kk)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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](SudokuJava.ipynb). 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}`.\n", "\n", "# Tests\n", "\n", "Here are some unit tests to give partial code coverage, and to show how the subfunctions work:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def tests():\n", " \"\"\"Unit tests.\"\"\"\n", " for kk in kenkens:\n", " assert len(kk.units) == 2 * kk.N\n", " assert len(kk.peers) -- kk.N ** 2\n", " assert all(len(kk.peers[s]) == 2 * kk.N - 2 for s in kk.squares)\n", " \n", " kk4 = kenkens[0]\n", " soln = {'A1': {4}, 'A2': {2}, 'A3': {3}, 'A4': {1}, \n", " 'B1': {3}, 'B2': {1}, 'B3': {4}, 'B4': {2}, \n", " 'C1': {2}, 'C2': {3}, 'C3': {1}, 'C4': {4}, \n", " 'D1': {1}, 'D2': {4}, 'D3': {2}, 'D4': {3}}\n", " assert solve(kk4) == soln\n", " assert is_solution(soln, kk4)\n", " \n", " cage = kk6.cagefor['D4']\n", " assert cage == Cage(target=7, op='+', squares=['D4', 'E4', 'E5'])\n", " assert cage == make_cage('7 + d4 e4 e5')\n", " assert cage_solved(cage, [2, 1, 4])\n", " assert not cage_solved(cage, [2, 1, 3])\n", " \n", " assert orderings(add, [2, 1, 4]) == [[2, 1, 4]]\n", " assert orderings(sub, [2, 1, 4]) == [[2, 1, 4], [1, 4, 2], [4, 2, 1]]\n", " \n", " vals = {'D4': kk6.digits, 'E4': kk6.digits, 'E5': kk6.digits}\n", " assert possible_cage_values(vals, cage) == {\n", " 'D4': {1, 2, 3, 4, 5},\n", " 'E4': {1, 2, 3, 4, 5},\n", " 'E5': {1, 2, 3, 4, 5}}\n", " \n", " assert first([0, 1, 2, 3]) == 0\n", " assert first({3}) == 3\n", " \n", " assert first_true([0, '', False, 4]) == 4\n", " assert first_true([0, '', False]) == None\n", " \n", " assert union([{1, 2, 3}, {3, 4, 5}]) == {1, 2, 3, 4, 5}\n", " \n", " assert neighbors('B2') == ['A2', 'B3', 'C2', 'B1']\n", " \n", " assert same_cage(kk6, 'A1', 'B1')\n", " assert not same_cage(kk6, 'A1', 'A2')\n", "\n", " return True\n", "\n", "tests()" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.6" } }, "nbformat": 4, "nbformat_minor": 4 }