{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Hinomaru Puzzle Solver Using Constraints\n", "\n", "by Steve Witham\n", "\n", "The challenge is to write a Python program to construct a Japanese flag using (one side of each of) a set of two-sided, domino-like tiles. \n", "\n", "\n", "\n", "A more complete description by John Bohannon, is at http://puzzles.bostonpython.com/hinomaru.html His puzzle and piece data is next. The [original puzzle](http://www.pavelspuzzles.com/2007/08/hinomaru_the_japanese_flag_puz_1.html) is by Curtis Pavel. John suggests using the **numpy** library, which looks like it will be good for rotating the tiles, and for matching tiles to locations in the puzzle.\n", "\n", "In this code I try out my [`constrainer`](https://github.com/switham/constrainer/) module on the problem." ] }, { "cell_type": "code", "collapsed": false, "input": [ "from constrainer import State, BoolVar, BoolConstraint\n", "import numpy as np\n", "from collections import defaultdict\n", "from sys import stdout\n", "from time import clock\n", "\n", "# iPython notebook --pylab overrides the Python builtins \"any\" and \"all\"\n", "# with their Numpy namesakes -- restore the builtins.\n", "try:\n", " any = __builtins__.any\n", " all = __builtins__.all\n", "except:\n", " any = __builtins__[\"any\"]\n", " all = __builtins__[\"all\"]\n", "\n", "# Data by John Bohannon.\n", "\n", "# FLAG represents the picture we finally want to make\n", "# as an 12 x 18 grid of white (0) or red (1) spots.\n", "# Enough detail to tell which pieces fit in which places.\n", "# FLAG is replaced by an equivalent Numpy array below.\n", "\n", "FLAG = [\n", " (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),\n", " (0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0),\n", " (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),\n", " (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),\n", " (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),\n", " (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),\n", " (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),\n", " (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),\n", " (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),\n", " (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),\n", " (0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0),\n", " (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),\n", "]\n", "\n", "# This will be useful as a Numpy array of bytes.\n", "FLAG = np.array(FLAG, dtype=np.int8)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [ "# TILES represents the twelve tiles.\n", "# Each tile has two faces, and each face is a 3 x 6 grid.\n", "# NOTE: the program rewrites the data so the tiles' faces\n", "# are \"canonical\".\n", "\n", "TILES = [\n", " (\n", " ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),\n", " ((0,1,1,1,1,1), (0,1,1,1,1,1), (0,0,1,1,1,1)),\n", " ),\n", " (\n", " ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),\n", " ((1,1,0,0,0,0), (1,1,0,0,0,0), (1,0,0,0,0,0)),\n", " ),\n", " (\n", " ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),\n", " ((0,0,0,0,0,0), (1,1,0,0,0,0), (1,1,1,1,0,0)),\n", " ),\n", " (\n", " ((1,1,1,1,1,1), (0,1,1,1,1,0), (0,0,0,0,0,0)),\n", " ((1,1,1,1,0,0), (1,1,0,0,0,0), (0,0,0,0,0,0)),\n", " ),\n", " (\n", " ((1,1,1,1,1,1), (0,1,1,1,1,0), (0,0,0,0,0,0)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),\n", " ),\n", " (\n", " ((1,1,1,1,1,0), (1,1,1,1,1,0), (1,1,1,1,0,0)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (1,0,0,0,0,0)),\n", " ),\n", " (\n", " ((1,1,1,1,0,0), (1,1,1,1,1,0), (1,1,1,1,1,0)),\n", " ((0,0,1,1,1,1), (0,0,0,0,1,1), (0,0,0,0,0,0)),\n", " ),\n", " (\n", " ((0,0,0,0,0,0), (0,0,0,0,1,1), (0,0,1,1,1,1)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),\n", " ),\n", " (\n", " ((0,0,1,1,1,1), (0,0,0,0,1,1), (0,0,0,0,0,0)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,1)),\n", " ),\n", " (\n", " ((0,0,0,0,1,1), (0,0,0,0,1,1), (0,0,0,0,0,1)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),\n", " ),\n", " (\n", " ((0,0,0,0,0,1), (0,0,0,0,1,1), (0,0,0,0,1,1)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,1)),\n", " ),\n", " (\n", " ((0,0,0,0,0,1), (0,0,0,0,0,0), (0,0,0,0,0,0)),\n", " ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),\n", " ),\n", "]" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Digesting the Problem\n", "\n", "The puzzle has already been reduced to a 12 x 18 grid of ones and zeroes, which need to fill with twelve tiles, each **tile** being either 3 x 6 or 6 x 3 depending on how it's turned.\n", "\n", "All of the sizes are divisible by three, so the tiles can only be placed on coordinates that are divisible by three, making it more like a 4 x 6 grid of 3 x 3... call them **squares**, with each tile being 1 x 2 (or 2 x 1) squares. Each tile has two **faces**, and each face can only go in a place where it matches the 3 x 6 or 6 x 3 pattern of ones and zeroes of the flag.\n", "\n", "Squares will be represented by (row, column) two-tuples, with `0 <= row < 4`, `0 <= column < 6`, and `(0, 0)` the top-left corner. A **place** is a square location followed by either \"across\" or \"down\", e.g. `((1, 2), \"down\")`." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def squares_and_places(v, h):\n", " squares = set((row, col) for row in range(v) for col in range(h))\n", " places = set(((row, col), \"down\") for row in range(v - 1) for col in range(h)) \\\n", " | set(((row, col), \"across\") for row in range(v) for col in range(h - 1))\n", " # \"|\" is one way to get the set union.\n", " return squares, places\n", "\n", "SQUARES, PLACES = squares_and_places(4, 6)\n", "\n", "def place_squares(place):\n", " \"\"\" Return the two squares that constitute place. \"\"\"\n", " assert place in PLACES\n", " \n", " (row, col), orientation = place\n", " if orientation == \"across\":\n", " return (row, col), (row, col + 1)\n", " else:\n", " return (row, col), (row + 1, col)\n", " \n", "# Reverse index from a square to the places it's part of.\n", "SQUARE_PLACES = {square: [place for place in PLACES\n", " if square in place_squares(place)]\n", " for square in SQUARES}" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 35 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python can compare tuples for equality and use them as keys for dictionaries, so instead of giving a face a name or number we will just represent it by a 3 x 6 tuple-of-tuples. But faces need to be recognized as the same if they are rotated, so we will always use the horizontal orientation and treat the rotation that Python considers \"less\" as the canonical one. In order to rotate faces, we will convert them to numpy arrays, use Numpy's **rot90()** to rotate the array, then convert them back to tuples-of-tuples. Numpy can also easily cut a rectangular **slice** out of a 2D array (e.g., from FLAG)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def face_to_np(face):\n", " assert type(face) == tuple\n", " assert np.shape(face) == (3, 6)\n", " \n", " return np.array(face, dtype=np.int8)\n", "\n", "def np_to_face(np_face):\n", " assert type(np_face) == np.ndarray\n", " assert np_face.shape == (3, 6)\n", " \n", " return tuple(tuple(row) for row in np_face)\n", "\n", "def rot180(np_face):\n", " return np.rot90(np.rot90(np_face))\n", "\n", "def np_to_canonical_face(np_face):\n", " f1 = np_to_face(np_face)\n", " f2 = np_to_face(rot180(np_face))\n", " return min(f1, f2)\n", "\n", "def canonical_face(face):\n", " return np_to_canonical_face(face_to_np(face))\n", "\n", "def place_slice(place):\n", " \"\"\"\n", " Return a 3 x 6 slice out of FLAG, oriented in the \"across\" way\n", " even if the place is \"down\", \n", " i.e. rotate it 90 degrees if necessary.\n", " This returns an \"np_face\", not a canonical face.\n", " \"\"\"\n", " assert place in PLACES, place\n", " \n", " (row, col), orientation = place\n", " f_row, f_col = row * 3, col * 3\n", " if orientation == \"across\":\n", " return FLAG[f_row : f_row + 3, f_col : f_col + 6]\n", " else:\n", " return np.rot90(FLAG[f_row : f_row + 6, f_col : f_col + 3])\n", " \n", "def place_face(place):\n", " \"\"\"\n", " Return the canonical face from a place on the flag.\n", " \"\"\"\n", " return np_to_canonical_face(place_slice(place))\n", "\n", "def square_slice(square):\n", " \"\"\"\n", " Return a 3 x 3 array of ones and zeroes from a \n", " square of the flag (used to print the flag). \n", " \"\"\"\n", " assert square in SQUARES\n", " \n", " (row, col) = square\n", " f_row, f_col = row * 3, col * 3\n", " return FLAG[f_row : f_row + 3, f_col : f_col + 3]\n", "\n", "# Make the faces in our TILES data canonical.\n", "\n", "for i, (side1, side2) in enumerate(TILES):\n", " TILES[i] = (canonical_face(side1), canonical_face(side2))\n", " \n", "FACES = {face for tile in TILES for face in tile}\n", "assert FACES == {place_face(place) for place in PLACES}\n", "\n", "# Reverse index from a face to the places where it fits.\n", "FACE_PLACES = {face: [place for place in PLACES\n", " if place_face(place) == face]\n", " for face in FACES}\n", "\n", "# Reverse index from a face to the tiles it appears on.\n", "FACE_TILES = {face: [tile for tile in TILES if face in tile]\n", " for face in FACES}" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now the data is available in these ways:\n", "\n", "```\n", "SQUARES = set of valid squares (row, col tuples) on the flag.\n", "PLACES = set of valid places ((row, col), \"across\" or \"down\") \n", " where tiles can go.\n", "place_squares(place) => tuple of two squares.\n", "SQUARE_PLACES[square] => list of places the square is part of.\n", "\n", "TILES[] => the list of tiles. Each is a tuple of two canonical faces.\n", "tile[0 or 1] => canonical face.\n", "FACES = set of valid faces.\n", "FACE_PLACES[face] => list of places where it fits.\n", "FACE_TILES[face] => list of tiles that have it.\n", "```\n", "\n", "### Programming With Constraints\n", "\n", "A constraints program has a set of variables, and a set of \"constraints\" about the variables. Together the constraints say whether a combination of variable values is a solution or a dead end, without saying anything else about how to solve the problem. `constrainer` uses only true/false variables, so once you set up a problem correctly, you could search all the possible combinations of the variables until you found a solution.\n", "\n", "A constraint solver improves on that by taking advantage of the fact that the same constraints often let you infer the values of some variables from others', causing avalanches of results to \"propagate\" from single choices. That doesn't necessarily mean that no tree searching is needed, but it cuts down the search space.\n", "\n", "With `constrainer`, a problem is set up by creating and initializing objects in just these three Python classes:\n", "\n", "A **State** ties the whole problem together and has the top-level search method.\n", "\n", "A **BoolVar** is like a checkbox that is originally empty (actually set to [Maybe](https://github.com/switham/constrainer/blob/master/constrainer/maybies.py)), but eventually gets set to *True* or *False*. All of the choices in the problem have to be represented with BoolVars.\n", "\n", "A **BoolConstraint** is a rule that says, out of some set of BoolVars, at least *this* many, and at most *this* many, have to be true. \n", "\n", "> *Example:*\n", ">\n", "> state = State()\n", "> a = BoolVar(state)\n", "> b = BoolVar(state)\n", "> c = BoolConstraint(state, a, b, min_True=1, max_True=1)\n", "> \n", ">This means that exactly one out of {*a*, *b*} must be *True*. In other words, once we find out or guess one, the other must have the opposite truth value.\n", "\n", "There are more ideas in the [constrainer README](https://github.com/switham/constrainer#setup-patterns) about using these objects to represent problems, but typically BoolVars represent choices about relations between things (for instance, *This pig is in that house,*), and BoolConstraints represent rules about a given thing (for instance, *There can be at most three pigs in this house*).\n", "\n", "### Hinomaru Variables and Constraints\n", "\n", "With Hinomaru, the first set of choices is which side of each tile is facing up. There are two BoolVars for each tile, one for each face, constrained to be opposite each other. This could be done with one variable per tile, but it's more symmetrical and actually easier with two. These variables are stored in a nested dictionary `tile_shows_face[tile][face]`. (The code adds a `.tile` attribute to each of these variables, which is used later on.)" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_tile_shows_face(state):\n", " tile_shows_face = {tile: {face: BoolVar(state, tile=tile)\n", " for face in tile}\n", " for tile in TILES}\n", " return tile_shows_face" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "\n" ] } ], "prompt_number": 22 }, { "cell_type": "markdown", "metadata": {}, "source": [ "The constraint for each tile is stored in `shows_one_face[tile]`." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_shows_one_face(state, tile_shows_face):\n", " \"\"\" Constrain so that each tile shows one of two faces. \"\"\"\n", " shows_one_face = dict()\n", " for tile in TILES:\n", " # (tile_shows_face[tile].values() is a list of two BoolVars.)\n", " c = BoolConstraint(state, *tile_shows_face[tile].values(),\n", " min_True=1, max_True=1)\n", " shows_one_face[tile] = c\n", " return shows_one_face" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 23 }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are 38 places on the board where a tile *could* go, but it takes only twelve tiles to fill the board. The next dictionary of BoolVars, `place_is_used[place]`, says whether or not there will be a tile at a given place." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_place_is_used(state, places=PLACES):\n", " # Each place is either used or not.\n", " place_is_used = {place: BoolVar(state, place=place) \n", " for place in places}\n", " return place_is_used" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 24 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each square on the board is overlapped by two, three, or four places for tiles. The `under_one_tile[square]` constraint, for each square, says that exactly one of those places is used. That means the tiles can't overlap, and every square must get covered.\n", "\n", "This sets up a part of the problem that's like [filling the board with blank tiles](http://mathworld.wolfram.com/DominoTiling.html)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_under_one_tile(state, place_is_used):\n", " # Each square is covered by (a tile in) one of SQUARE_PLACES[square].\n", " under_one_tile = dict()\n", " for square in SQUARES:\n", " c = BoolConstraint(state, *[place_is_used[place]\n", " for place in SQUARE_PLACES[square]],\n", " min_True=1, max_True=1)\n", " under_one_tile[square] = c\n", " return under_one_tile" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 25 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Tiles to Faces to Places\n", "\n", "The code so far sets up choosing which side of each tile will show, and choosing which places on the board will have tiles, but not any relation between the two. In a way it's implicit: each place only matches one face. But a given face can potentially show up in multiple places and on multiple tiles.\n", "\n", "This could be arranged as a set of choices: for each side of a tile that is showing, choose which eligible place it will go. But those choices hardly matter. If there are two identical faces to go into two places, there are two ways to arrange that, and if the first arrangement leads eventually to a dead end, then so will the second, doubling the time spent searching. Each choice that doesn't matter is another multiplier of the search time.\n", "\n", "Better to leave those choices out and set a looser constraint: if and only if the number of tiles showing each face is equal to the number of places where a tile with that face goes on the board, the choices of tile-faces and places are consistent. The `shows_eq_places[face]` constraint expresses that.\n", "\n", "Once there's a solution in those terms, the solution-printing function arranges any group of tiles showing the same face among their places arbitrarily.\n", "\n", "Constraining two sets of BoolVars to have the same number of *True*s is a new use pattern for `constrainer`. It turns out it can be done with BoolVars and BoolConstraints, but it's packaged in the new function `constrain_same_n_true()`." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def constrain_same_n_true(state, vars1, vars2, **kwargs):\n", " \"\"\"\n", " Assert that the number of True variables in the list vars1\n", " is the same as the number of Trues in vars2.\n", " \"\"\"\n", " # Create one new var to be the opposite of each var in vars1.\n", " inv_vars1 = [BoolVar(state, oppo=var) for var in vars1]\n", " \n", " # Constrain each var to be the opposite of its counterpart:\n", " for ivar in inv_vars1:\n", " BoolConstraint(state, ivar, ivar.oppo, min_True=1, max_True=1)\n", " # Now constrain the union of inv_vars1 and vars2 to have\n", " # as many Trues as there are members of inv_vars1. Then,\n", " # All of vars1 and vars2 False\n", " # means all of inv_vars1 True,\n", " # and the constraint is satisfied.\n", " # and whenever a vars1 var turns True,\n", " # the corresponding inv_vars1 var turns False,\n", " # and a vars2 var must turn True to keep the balance.\n", " n = len(inv_vars1)\n", " return BoolConstraint(state, *(inv_vars1 + vars2),\n", " min_True=n, max_True=n, **kwargs)\n", "\n", "def init_shows_eq_places(state, tile_shows_face, place_is_used):\n", " \"\"\"\n", " Constrain each face to be turned face-up on as many tiles\n", " as places where it's supposed to show on the board.\n", " \"\"\"\n", " shows_eq_places = dict()\n", " for face in FACES:\n", " shown_vars = [tile_shows_face[tile][face] \n", " for tile in FACE_TILES[face]]\n", " placed_vars = [place_is_used[place] \n", " for place in FACE_PLACES[face]]\n", " c = constrain_same_n_true(state, shown_vars, placed_vars,\n", " tilevs=shown_vars,\n", " placevs=placed_vars)\n", " shows_eq_places[face] = c\n", " return shows_eq_places\n", "\n", "def init_constrainer():\n", " global state\n", " global tile_shows_face, place_is_used\n", " global shows_one_face, under_one_tile, shows_eq_places\n", " \n", " state = State()\n", " tile_shows_face = init_tile_shows_face(state)\n", " shows_one_face = init_shows_one_face(state, tile_shows_face)\n", " place_is_used = init_place_is_used(state)\n", " under_one_tile = init_under_one_tile(state, place_is_used)\n", " shows_eq_places = init_shows_eq_places(state, tile_shows_face,\n", " place_is_used)\n", " \n", "init_constrainer()\n", "print \"Initialized.\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Initialized.\n" ] } ], "prompt_number": 26 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Extracting Solution Details from `constrainer`\n", "\n", "Now that the variables and constraints are set up, the code to generate solutions will look roughly like this:\n", "\n", " for is_solution in state.generate_leaves():\n", " if is_solution:\n", " # Print the solution.\n", " else:\n", " # Make note of a dead end.\n", " \n", "The information for each solution has to be extracted from the BoolVars and BoolConstraints. Because constraints tend to center on things of interest, they tend to collect the choices related to each thing. The code above that set up the `tile_shows_face` and `place_is_used` BoolVars gave them `.tile` and `.place` attributes respectively. Given a constraint `c`, `c[True]` gives the subset of BoolVars attached to `c` that are True in the current solution. Here we use the constraints on squares to find out where the tiles are placed, and the constraints on faces to find out which tiles to place which side up on which places." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution_square_places():\n", " \"\"\"\n", " For each square, which (one) place does it belong to?\n", " returns a dict like {square: place, ...}.\n", " \"\"\"\n", " # under_one_tile[] constrains there to be only one True member,\n", " # but the simplest way to get the one member of the set is a for-loop.\n", " return dict((square, placev.place)\n", " for square in SQUARES\n", " for placev in under_one_tile[square][True])\n", "\n", "def solution_tile_placements():\n", " \"\"\"\n", " Which side up, and on which place, should each tile go?\n", " Return a dict like {tile: (face, place), ...}. (The whole solution, actually.)\n", " Identical-faced tiles are distributed among matching places arbitrarily.\n", " \"\"\"\n", " # For each possible face, we get a list of tiles with that face turned up,\n", " # and an equal-length list of places where it has been placed.\n", " # (For a face that hasn't been used, they're both empty lists.)\n", " tile_placements = dict()\n", " for face in FACES:\n", " constraint = shows_eq_places[face]\n", " tiles = [v.tile for v in constraint.tilevs if v]\n", " places = [v.place for v in constraint.placevs if v]\n", " assert len(tiles) == len(places)\n", " for tile, place in zip(tiles, places):\n", " tile_placements[tile] = (face, place)\n", " return tile_placements" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 27 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Printing Solutions\n", "\n", "Here's the code to print the solution based on the information extracted.\n", "The `solution_pic()` function produces a typewriter picture of the board with tile outlines,\n", "and pictures of the tiles with instructions telling where and which way they go.\n", "The placement instructions number rows and columns starting from 1.\n", "\n", "Typewriter pictures are represented as lists of strings (one per line), and a lot of this section\n", "is about lining pictures up and pasting them together." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def square_pic(square, sqp, left_edge=False, top_edge=False):\n", " \"\"\"\n", " Given square (row, col), return a typewriter picture of what's there.\n", " sqp is the output of solution_square_places.\n", " Right and bottom borders are present unless a tile\n", " extends across the corresponding division.\n", " See array_pic() for more details.\n", " \"\"\"\n", " assert square in SQUARES\n", " \n", " row, col = square\n", " right_edge = col >= 5 or sqp[square] != sqp[(row, col + 1)]\n", " bottom_edge = row >= 3 or sqp[square] != sqp[(row + 1, col)]\n", " ss = square_slice(square)\n", " assert ss.shape == (3, 3)\n", " return array_pic(ss, right_edge, bottom_edge, left_edge, top_edge)\n", "\n", "def array_pic(ar, right_edge, bottom_edge, left_edge=False, top_edge=False):\n", " \"\"\"\n", " Return a rectangular typewriter picture based on a 2D boolean array.\n", " ar is a 2D numpy array, tuple of tuples or list of lists.\n", " Output example:\n", " [\" |\",\n", " \" ##|\",\n", " \"######|\",\n", " \"------+\",]\n", " right_edge and bottom_edge say whether to draw edge lines.\n", " When a right or bottom edge is not present it's replaced by \n", " a duplicate of the character to the left or above, resp.\n", " The bottom-right character is always '+'.\n", " left_edge and top_edge *insert* edges (not present in the example).\n", " \"\"\"\n", " lc = \"+\" if left_edge else \"\"\n", " left = \"|\" if left_edge else \"\"\n", " if top_edge:\n", " pic = [lc + \"--\" * len(ar[0]) + \"+\"]\n", " else:\n", " pic = [] \n", " for row, row_data in enumerate(ar):\n", " line = \"\".join(\"##\" if bit else \" \" for bit in row_data)\n", " line += \"|\" if right_edge else line[-1]\n", " pic.append(left + line)\n", " pic.append(lc + (\"--\" * len(row_data) if bottom_edge else line[:-1]) + \"+\")\n", " return pic\n", "\n", "def pad_pic_height(pic, height):\n", " \"\"\" Add blank lines to pic to pad it to height. \"\"\"\n", " pad = height - len(pic)\n", " return pic if pad <= 0 else pic + [\"\"] * pad\n", "\n", "def pad_pic_heights(pix, min_height=0):\n", " \"\"\"\n", " Pad pics in pix to have identical heights.\n", " The vertical padding is not horizontally padded!\n", " Do pad_pic_widths after pad_pic_heights, or use pad_pic_heights_widths.\n", " \"\"\"\n", " height = max(min_height, max(len(pic) for pic in pix))\n", " if min(len(pic) for pic in pix) == height:\n", " return pix\n", " else:\n", " return [pad_pic_height(pic, height) for pic in pix]\n", "\n", "def pad_pic_width(pic, min_width=0):\n", " \"\"\" Pad pic to have uniform width within itself. \"\"\"\n", " width = max(max(len(line) for line in pic), min_width)\n", " return [line.ljust(width) for line in pic]\n", "\n", "def pad_pic_widths(pix, min_width=0):\n", " \"\"\"\n", " Pad each pic to be rectangular, not necessarily all to the same width.\n", " No vertical padding is done.\n", " Do pad_pic_heights before pad_pic_widths, or use pad_pic_heights_widths.\n", " \"\"\"\n", " return [pad_pic_width(pic, min_width) for pic in pix]\n", "\n", "def pad_pic_heights_widths(pix, min_height=0, min_width=0):\n", " \"\"\"\n", " Make each pic rectangular and all pics have the same height.\n", " \"\"\"\n", " return pad_pic_widths(pad_pic_heights(pix, min_height), min_width)\n", "\n", "def join_pix_LR(pix, min_height=0, min_width=0):\n", " \"\"\"\n", " Pad a group of pictures to be compatible,\n", " then paste them together left-to right.\n", " Return a single picture (list of lines).\n", " \"\"\"\n", " pix = pad_pic_heights_widths(pix, min_height, min_width)\n", " height = len(pix[0])\n", " return [\"\".join(pic[i] for pic in pix) for i in range(height)]\n", "\n", "def board_pic(sqp):\n", " \"\"\"\n", " Return a typewriter picture of the board as tiled.\n", " sqp is the output of solution_square_places.\n", " \"\"\"\n", " result = []\n", " for row in range(4):\n", " row_pix = [square_pic((row, col), sqp, \n", " top_edge=(row == 0), left_edge=(col == 0))\n", " for col in range(6)]\n", " result += join_pix_LR(row_pix)\n", " return result\n", "\n", "def tile_pic(tile, top_edge):\n", " \"\"\"\n", " A typewriter picture of a tile, shown as two horizontal faces\n", " side-by-side.\n", " \"\"\"\n", " assert np.shape(tile) == (2, 3, 6)\n", " \n", " side_pix = []\n", " for i, face in enumerate(tile):\n", " left_edge = (i == 0)\n", " side_pix.append(array_pic(face, True, True, left_edge, top_edge))\n", " return join_pix_LR(side_pix)\n", "\n", "def placement_pic(place, top_edge):\n", " \"\"\"\n", " Abbreviated placement instructions for a tile:\n", " The row, column and orientation of its place.\n", " \"\"\"\n", " (row, col), orientation = place\n", " pic = [\" \"] if top_edge else []\n", " pic += [\n", " \"row %d\" % (row + 1),\n", " \"col %d\" % (col + 1),\n", " orientation,\n", " ]\n", " return pad_pic_width(pic, 6)\n", "\n", "def tile_placement_pic(tiles, stp):\n", " \"\"\"\n", " Pic of a block of tiles with placement instructions.\n", " The instructions for each tile go next to the side of the tile that shows.\n", " The block has a top & bottom line, & borders but not gaps between tiles.\n", " stp is the output of solution_tile_placements,\n", " a dict like {tile: (face, place), ...}.\n", " \"\"\"\n", " pic = []\n", " for i, tile in enumerate(tiles):\n", " face, place = stp[tile]\n", " top_edge = (i == 0)\n", " tpic = tile_pic(tile, top_edge)\n", " ppic = placement_pic(place, top_edge)\n", " slug = [\" \".ljust(len(ppic[0]))]\n", " sp = [\" \"]\n", " if face == tile[0]:\n", " pic += join_pix_LR([sp, ppic, sp, tpic, sp, slug, sp])\n", " else:\n", " pic += join_pix_LR([sp, slug, sp, tpic, sp, ppic, sp])\n", " return pic\n", "\n", "def join_list(spacer, things):\n", " \"\"\"\n", " New list with spacer inserted between adjacent things.\n", " E.g.\n", " join_list(0, [1, 2, 3]) => [1, 0, 2, 0, 3]\n", " \"\"\"\n", " result = things[:1]\n", " for thing in things[1:]:\n", " result.append(spacer)\n", " result.append(thing)\n", " return result\n", "\n", "def solution_pic():\n", " \"\"\"\n", " Picture of the board and three blocks of \n", " placement instructions, like\n", " board block 1\n", " block 2 block 3\n", " \"\"\"\n", " sqp = solution_square_places()\n", " stp = solution_tile_placements()\n", " bp = board_pic(sqp)\n", " blocks = [bp]\n", " pic = []\n", " for i in range(0, len(TILES), 4):\n", " tiles = TILES[i : i + 4]\n", " blocks.append(tile_placement_pic(tiles, stp))\n", " for i in range(0, len(blocks), 2):\n", " pic += join_pix_LR(join_list([\" \"], blocks[i : i + 2]))\n", " return pic" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 11 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generating Solutions\n", "\n", "Now we call the setup functions above and then `state.generate_leaves()`, which launches the solver. The solver is a generator that yields *False* for every dead end it hits and *True* for every solution. While we're paused at a solution we can read it out from the constraints and variables." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def action():\n", " start = start_some = clock()\n", " init_constrainer()\n", " t = clock()\n", " print t - start_some, \"sec. to init.\"\n", " start_some = t\n", " stdout.flush()\n", " n_dead_ends = 0\n", " total_dead_ends = 0\n", " for is_solution in state.generate_leaves():\n", " if not is_solution:\n", " n_dead_ends += 1\n", " continue\n", "\n", " t = clock()\n", " print \" \", n_dead_ends, \"dead ends\"\n", " total_dead_ends += n_dead_ends\n", " n_dead_ends = 0\n", " print t - start_some, \"sec. depth =\", state.depth()\n", " print\n", " print \"\\n\".join(solution_pic())\n", " print\n", " start_some = t\n", " stdout.flush()\n", " t = clock()\n", " print \" \", n_dead_ends, \"dead ends\"\n", " total_dead_ends += n_dead_ends\n", " n_false = 0\n", " print t - start_some, \"sec.\"\n", " print \" \", total_dead_ends, \"total dead ends.\"\n", " print t - start, \"sec. total. Done.\"\n", " \n", "action()" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "0.005764 sec. to init.\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 62 dead ends\n", "0.224806 sec. depth = 8\n", "\n", "+------+------+------+------+------+------+ +------------+------------+ \n", "| | | | | |############| ##########| row 3 \n", "| | | ######### | | |############| ##########| col 2 \n", "| | ##|#############|## | |############| ########| across \n", "+ + ##+------+------+------+------+ +------------+------------+ \n", "| | ##|#############|## | | row 2 |############| ##| \n", "| | ####|#############|#### | | col 3 |############| ####| \n", "| | ####|#############|#### | | across |############| ####| \n", "+------+------+------+------+#### + + +------------+------------+ \n", "| | ###########|######|#### | | |############| | row 4 \n", "| | ###########|######|#### | | |############|#### | col 2 \n", "| | #########|######|## | | |############|######## | across \n", "+ +------+------+######+------+------+ +------------+------------+ \n", "| | #########|######|## | row 1 | | | \n", "| | ####|#### | | col 3 | ######## | ####| \n", "| | | | | across |############| ########| \n", "+------+------+------+------+------+------+ +------------+------------+ \n", " +------------+------------+ +------------+------------+ \n", " row 2 | | | row 1 | | | \n", " col 5 | ######## | | col 2 |#### | | \n", " down |############| | down |######## | ##| \n", " +------------+------------+ +------------+------------+ \n", " | ########| | row 1 | ####| | row 3 \n", " | ##########| | col 5 | ####| | col 1 \n", " | ##########|## | across | ##| | down \n", " +------------+------------+ +------------+------------+ \n", " row 3 | ##########| | | ##| | row 4 \n", " col 4 | ##########|#### | | ####| | col 5 \n", " down | ########|######## | | ####| ##| across \n", " +------------+------------+ +------------+------------+ \n", " | | | row 1 | | | row 2 \n", " | ####| | col 1 | | | col 6 \n", " | ########| | down |## | | down \n", " +------------+------------+ +------------+------------+ \n", "\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 5 dead ends\n", "0.028689 sec. depth = 5\n", "\n", "+------+------+------+------+------+------+ +------------+------------+ \n", "| | | | | |############| ##########| row 1 \n", "| | ####|#### | | |############| ##########| col 3 \n", "| ##|######|######### | | |############| ########| down \n", "+------+------+######+------+------+ + +------------+------------+ \n", "| | ##|######|######### | | row 3 |############| ##| \n", "| | ####|######|########### | | col 3 |############| ####| \n", "| | ####|######|########### | | across |############| ####| \n", "+ + ####+------+------+------+------+ +------------+------------+ \n", "| | ####|#############|#### | | |############| | row 1 \n", "| | ####|#############|#### | | |############|#### | col 4 \n", "| | ##|#############|## | | |############|######## | across \n", "+------+------+------+------+## + + +------------+------------+ \n", "| ##|#############|## | | row 4 | | | \n", "| | ######### | | | col 3 | ######## | ####| \n", "| | | | | across |############| ########| \n", "+------+------+------+------+------+------+ +------------+------------+ \n", " +------------+------------+ +------------+------------+ \n", " row 2 | | | row 3 | | | \n", " col 2 | ######## | | col 5 |#### | | \n", " down |############| | down |######## | ##| \n", " +------------+------------+ +------------+------------+ \n", " | ########| | row 4 | ####| | row 3 \n", " | ##########| | col 1 | ####| | col 6 \n", " | ##########|## | across | ##| | down \n", " +------------+------------+ +------------+------------+ \n", " row 2 | ##########| | | ##| | row 1 \n", " col 4 | ##########|#### | | ####| | col 1 \n", " across | ########|######## | | ####| ##| across \n", " +------------+------------+ +------------+------------+ \n", " | | | row 2 | | | row 1 \n", " | ####| | col 1 | | | col 6 \n", " | ########| | down |## | | down \n", " +------------+------------+ +------------+------------+ \n", "\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 289 dead ends\n", "1.113006 sec.\n", " 356 total dead ends.\n", "1.372265 sec. total. Done.\n" ] } ], "prompt_number": 12 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Conclusion\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A\n", "penny saved\n", "is a word\n", "to the wise." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_tiling(**state_kwargs):\n", " \"\"\"\n", " Prepare just the tiling-with-blank-tiles part of the problem.\n", " \"\"\"\n", " state = State(**state_kwargs)\n", " place_is_used = init_place_is_used(state)\n", " under_one_tile = init_under_one_tile(state, place_is_used)\n", " return state, place_is_used, under_one_tile\n", "\n", "def blank_tile_it(verbose=True):\n", " start = start_some = clock()\n", " state, place_is_used, under_one_tile = init_tiling()\n", " t = clock()\n", " print t - start_some, \"sec. to init.\"\n", " start_some = t\n", " stdout.flush()\n", " n_dead_ends = 0\n", " total_dead_ends = 0\n", " n_solutions = 0\n", " total_solutions = 0\n", " n_solutions_goal = 1\n", " for is_solution in state.generate_leaves():\n", " if not is_solution:\n", " n_dead_ends += 1\n", " continue\n", "\n", " n_solutions += 1\n", " if n_solutions < n_solutions_goal:\n", " continue\n", " \n", " t = clock()\n", " print \" \", n_dead_ends, \"dead ends\"\n", " total_dead_ends += n_dead_ends\n", " n_dead_ends = 0 \n", " total_solutions += n_solutions\n", " n_solutions = 0\n", " n_solutions_goal *= 2\n", " print t - start_some, \"sec. depth =\", state.depth(), \"solution\", total_solutions\n", " start_some = t\n", " stdout.flush()\n", " t = clock()\n", " print \" \", n_dead_ends, \"dead ends\"\n", " total_dead_ends += n_dead_ends\n", " n_dead_ends = 0\n", " total_solutions += n_solutions\n", " n_solutions = 0\n", " print t - start_some, \"sec.\"\n", " print \" \", total_dead_ends, \"total dead ends.\"\n", " print t - start, \"sec. total. \", total_solutions, \"solutions. Done.\"\n", " \n", "blank_tile_it()" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "0.001132 sec. to init.\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.005807 sec. depth = 10 solution 1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.003243 sec. depth = 8 solution 3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.008214 sec. depth = 7 solution 7\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.012931 sec. depth = 11 solution 15\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 2 dead ends\n", "0.020166 sec. depth = 8 solution 31\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.040838 sec. depth = 7 solution 63\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 2 dead ends\n", "0.089864 sec. depth = 8 solution 127\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 4 dead ends\n", "0.171155 sec. depth = 5 solution 255\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 0 dead ends\n", "0.031411 sec.\n", " 8 total dead ends.\n", "0.384761 sec. total. 281 solutions. Done.\n" ] } ], "prompt_number": 52 }, { "cell_type": "code", "collapsed": false, "input": [ "# replace np.product\n", "def product(sequence):\n", " result = 1\n", " for x in sequence:\n", " result *= x\n", " return result\n", "\n", "def n_domino_tilings(m, n):\n", " \"\"\"\n", " Return the number of domino tilings of an m x n rectangle.\n", " See http://en.wikipedia.org/wiki/Domino_tiling#Counting_tilings_of_regions\n", " \"\"\"\n", " return int(product(\n", " product( (4*cos(pi*j/(m+1))**2 + 4*cos(pi*k/(n+1))**2)\n", " for k in range(1, n + 1)\n", " )\n", " for j in range(1, m + 1)\n", " ) ** .25 + .5)\n", "\n", "n = n_domino_tilings(4, 6)\n", "print \"There are\", n, \"domino tilings of a 4 x 6 rectangle.\"\n", "print\n", "\n", "for i in range(1, 10):\n", " print n_domino_tilings(2, i),\n", "print" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "There are 281 domino tilings of a 4 x 6 rectangle.\n", "\n", "1 2 3 5 8 13 21 34 55\n" ] } ], "prompt_number": 50 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }