yangs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# yangs - Yet Another NonoGram Solver\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aim\n",
    "\n",
    "Solve the first part of the GCHQ Christmas puzzle using a concise, easy-to-understand Python program.\n",
    "\n",
    "## Method\n",
    "\n",
    "The [puzzle](http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx) is a 25x25 [nonogram](https://en.wikipedia.org/wiki/Nonogram). I decided to write a program that uses the same method that I would use if solving the puzzle by hand:\n",
    "\n",
    "1. For each row and column, **generate the set of patterns** that match the given clues\n",
    "2. For each row, **eliminate the patterns** that don't match the cells we already know\n",
    "3. For each row, **deduce the known cells** based on the reduced pattern set\n",
    "4. For each column, **eliminate the patterns** that don't match the cells we already know\n",
    "5. For each column, **deduce the known cells** based on the reduced pattern set\n",
    "6. Go back to 2. and repeat, unless we've solved it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports and settings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from itertools import combinations_with_replacement\n",
    "SHOW_TESTS = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Input data\n",
    "\n",
    "Put all the clues into a list of lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ROW_CLUES = [\n",
    "    [7, 3, 1, 1, 7,],\n",
    "    [1, 1, 2, 2, 1, 1,],\n",
    "    [1, 3, 1, 3, 1, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 6, 1, 3, 1,],\n",
    "    [1, 3, 1, 5, 2, 1, 3, 1,],\n",
    "    [1, 1, 2, 1, 1,],\n",
    "    [7, 1, 1, 1, 1, 1, 7,],\n",
    "    [3, 3,],\n",
    "    [1, 2, 3, 1, 1, 3, 1, 1, 2,],\n",
    "    [1, 1, 3, 2, 1, 1,],\n",
    "    [4, 1, 4, 2, 1, 2,],\n",
    "    [1, 1, 1, 1, 1, 4, 1, 3,],\n",
    "    [2, 1, 1, 1, 2, 5,],\n",
    "    [3, 2, 2, 6, 3, 1,],\n",
    "    [1, 9, 1, 1, 2, 1,],\n",
    "    [2, 1, 2, 2, 3, 1,],\n",
    "    [3, 1, 1, 1, 1, 5, 1,],\n",
    "    [1, 2, 2, 5,],\n",
    "    [7, 1, 2, 1, 1, 1, 3,],\n",
    "    [1, 1, 2, 1, 2, 2, 1,],\n",
    "    [1, 3, 1, 4, 5, 1,],\n",
    "    [1, 3, 1, 3, 10, 2,],\n",
    "    [1, 3, 1, 1, 6, 6,],\n",
    "    [1, 1, 2, 1, 1, 2,],\n",
    "    [7, 2, 1, 2, 5,],\n",
    "]\n",
    "\n",
    "COL_CLUES = [\n",
    "    [7, 2, 1, 1, 7,],\n",
    "    [1, 1, 2, 2, 1, 1,],\n",
    "    [1, 3, 1, 3, 1, 3, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 5, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 4, 1, 3, 1,],\n",
    "    [1, 1, 1, 2, 1, 1,],\n",
    "    [7, 1, 1, 1, 1, 1, 7,],\n",
    "    [1, 1, 3,],\n",
    "    [2, 1, 2, 1, 8, 2, 1,],\n",
    "    [2, 2, 1, 2, 1, 1, 1, 2,],\n",
    "    [1, 7, 3, 2, 1,],\n",
    "    [1, 2, 3, 1, 1, 1, 1, 1,],\n",
    "    [4, 1, 1, 2, 6,],\n",
    "    [3, 3, 1, 1, 1, 3, 1,],\n",
    "    [1, 2, 5, 2, 2,],\n",
    "    [2, 2, 1, 1, 1, 1, 1, 2, 1,],\n",
    "    [1, 3, 3, 2, 1, 8, 1,],\n",
    "    [6, 2, 1,],\n",
    "    [7, 1, 4, 1, 1, 3,],\n",
    "    [1, 1, 1, 1, 4,],\n",
    "    [1, 3, 1, 3, 7, 1,],\n",
    "    [1, 3, 1, 1, 1, 2, 1, 1, 4,],\n",
    "    [1, 3, 1, 4, 3, 3,],\n",
    "    [1, 1, 2, 2, 2, 6, 1,],\n",
    "    [7, 1, 3, 2, 1, 1,],\n",
    "]\n",
    "\n",
    "ROW_LEN = len(COL_CLUES)\n",
    "COL_LEN = len(ROW_CLUES)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Set up a grid to contain the result, and fill in the cells we already know.\n",
    "\n",
    "Notes:\n",
    "- I'm using 1 to represent a known filled cell, 0 for a known blank cell, and None for an unknown cell.\n",
    "- The rows must be repeated using list comprehension. Using list repetition **(i.e. result = [[None] \\* ROW_LEN] * COL_LEN)** would result in a list of references to the same row list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Create blank results grid\n",
    "result = [[None] * ROW_LEN for c in range(COL_LEN)]\n",
    "\n",
    "# Fill in the cells we already know\n",
    "known_coords = {3: (3, 4, 12, 13, 21),\n",
    "                8: (6, 7, 10, 14, 15, 18),\n",
    "                16: (6, 11, 16, 20),\n",
    "                21: (3, 4, 9, 10, 15, 20, 21)\n",
    "               }\n",
    "\n",
    "for row, cols in known_coords.items():\n",
    "    for col in cols:\n",
    "        result[row][col] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper functions\n",
    "\n",
    "Define some functions to display the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 1 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 2 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 3 [? ? ? # # ? ? ? ? ? ? ? # # ? ? ? ? ? ? ? # ? ? ?]\n",
      " 4 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 5 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 6 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 7 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      " 8 [? ? ? ? ? ? # # ? ? # ? ? ? # # ? ? # ? ? ? ? ? ?]\n",
      " 9 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "10 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "11 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "12 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "13 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "14 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "15 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "16 [? ? ? ? ? ? # ? ? ? ? # ? ? ? ? # ? ? ? # ? ? ? ?]\n",
      "17 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "18 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "19 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "20 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "21 [? ? ? # # ? ? ? ? # # ? ? ? ? # ? ? ? ? # # ? ? ?]\n",
      "22 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "23 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n",
      "24 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]\n"
     ]
    }
   ],
   "source": [
    "SYMBOLS = {None: '?', 1:'#', 0:'.'}\n",
    "\n",
    "def print_row(row, i=0):\n",
    "    print '%s [%s]' % (str(i).rjust(2), ' '.join(SYMBOLS[cell] for cell in row))\n",
    "        \n",
    "def print_grid(rows):\n",
    "    col_labels = [str(i).rjust(2) for i in range (len(rows[0]))]\n",
    "    print '   ', ' '.join(cl[0] for cl in col_labels)\n",
    "    print '   ', ' '.join(cl[1] for cl in col_labels)\n",
    "    for i, row in enumerate(rows):\n",
    "        print_row(row, i)\n",
    "\n",
    "# Test\n",
    "if SHOW_TESTS:\n",
    "    print_grid(result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And a function to count the number of unknown cells in the results. We'll use this to check if we've solved the puzzle, or if we're not making progress."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unknowns = 603\n"
     ]
    }
   ],
   "source": [
    "def count_unknowns(rows):\n",
    "    return sum(row.count(None) for row in rows)\n",
    "\n",
    "# Test\n",
    "if SHOW_TESTS:\n",
    "    print 'Unknowns = %s' % count_unknowns(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generate sets of patterns\n",
    "\n",
    "Terminology:\n",
    "- Block = one or more consecutive filled cells\n",
    "- Space = an unfilled cell\n",
    "- Clue = the lengths of each block\n",
    "- Pattern = a series of cells that match the clue\n",
    "\n",
    "The **generate_patterns** function does step 1 of the general approach: give it the clue and the pattern length, and it generates all the possible patterns.\n",
    "\n",
    "For the clue [7, 3, 1, 1, 7] and length = 25:\n",
    "\n",
    "- There are 5 blocks, comprising 7 + 3 + 1 + 1 + 7 = 19 filled cells.\n",
    "- There are 6 **positions** where spaces can be inserted (numbered 0 through 5)\n",
    "- The middle 4 positions all must have at least one space - so there are 4 **fixed spaces**\n",
    "- That means there are 25 - 19 - 4 = 2 **movable spaces**, which can go in any permutation of the 6 positions\n",
    "- Therefore, there are 6CR2 = 21 different patterns that match this clue\n",
    "\n",
    "\n",
    "| position                | 0 | 1       | 1 |  2  | 2 | 3 | 3 | 4 | 4 | 5       | 5 |\n",
    "|-\n",
    "| blocks and fixed spaces |   | 1111111 | 0 | 111 | 0 | 1 | 0 | 1 | 0 | 1111111 |   |\n",
    "| movable spaces (any 2 of 6 positions)      | ? |         | ? |     | ? |   | ? |   | ? |         | ? | \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [. . # # # # # # # . # # # . # . # . # # # # # # #]\n",
      " 1 [. # # # # # # # . . # # # . # . # . # # # # # # #]\n",
      " 2 [. # # # # # # # . # # # . . # . # . # # # # # # #]\n",
      " 3 [. # # # # # # # . # # # . # . . # . # # # # # # #]\n",
      " 4 [. # # # # # # # . # # # . # . # . . # # # # # # #]\n",
      " 5 [. # # # # # # # . # # # . # . # . # # # # # # # .]\n",
      " 6 [# # # # # # # . . . # # # . # . # . # # # # # # #]\n",
      " 7 [# # # # # # # . . # # # . . # . # . # # # # # # #]\n",
      " 8 [# # # # # # # . . # # # . # . . # . # # # # # # #]\n",
      " 9 [# # # # # # # . . # # # . # . # . . # # # # # # #]\n",
      "10 [# # # # # # # . . # # # . # . # . # # # # # # # .]\n",
      "11 [# # # # # # # . # # # . . . # . # . # # # # # # #]\n",
      "12 [# # # # # # # . # # # . . # . . # . # # # # # # #]\n",
      "13 [# # # # # # # . # # # . . # . # . . # # # # # # #]\n",
      "14 [# # # # # # # . # # # . . # . # . # # # # # # # .]\n",
      "15 [# # # # # # # . # # # . # . . . # . # # # # # # #]\n",
      "16 [# # # # # # # . # # # . # . . # . . # # # # # # #]\n",
      "17 [# # # # # # # . # # # . # . . # . # # # # # # # .]\n",
      "18 [# # # # # # # . # # # . # . # . . . # # # # # # #]\n",
      "19 [# # # # # # # . # # # . # . # . . # # # # # # # .]\n",
      "20 [# # # # # # # . # # # . # . # . # # # # # # # . .]\n"
     ]
    }
   ],
   "source": [
    "def generate_patterns(clue, length):\n",
    "    blocks = [0] + clue\n",
    "    fixed_spaces = [0] + [1] * (len(clue) - 1) + [0]\n",
    "    positions = range(len(blocks))\n",
    "    n_movable_spaces = length - sum(clue) - len(clue) + 1\n",
    "    for space_positions in combinations_with_replacement(positions, n_movable_spaces):\n",
    "        movable_spaces = [space_positions.count(p) for p in positions]\n",
    "        yield sum(([1] * b + [0] * (fs + ms) for b, fs, ms in zip(blocks, fixed_spaces, movable_spaces)), [])\n",
    "\n",
    "# Test\n",
    "if SHOW_TESTS:\n",
    "    test_pats = list(generate_patterns([7, 3, 1, 1, 7], 25))\n",
    "    print_grid(test_pats)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Eliminate patterns\n",
    "\n",
    "The **eliminate_patterns** function does steps 2 and 4 of the general approach: give it a list of patterns, and it will eliminate the patterns that don't match the already-known cells.\n",
    "\n",
    "Notes:\n",
    "- The set of patterns is iterated in reverse order so that deleting an item won't change the indices of the items yet to be iterated.\n",
    "- The **any** function will short circuit as soon as it finds a cell in the pattern that conflicts with the known cells\n",
    "- I've used **del patterns[i]** instead of **patterns.pop(i)** because we don't need to do anything with the item after it's removed from the list\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before:\n",
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [. . # # # # # # # . # # # . # . # . # # # # # # #]\n",
      " 1 [. # # # # # # # . . # # # . # . # . # # # # # # #]\n",
      " 2 [. # # # # # # # . # # # . . # . # . # # # # # # #]\n",
      " 3 [. # # # # # # # . # # # . # . . # . # # # # # # #]\n",
      " 4 [. # # # # # # # . # # # . # . # . . # # # # # # #]\n",
      " 5 [. # # # # # # # . # # # . # . # . # # # # # # # .]\n",
      " 6 [# # # # # # # . . . # # # . # . # . # # # # # # #]\n",
      " 7 [# # # # # # # . . # # # . . # . # . # # # # # # #]\n",
      " 8 [# # # # # # # . . # # # . # . . # . # # # # # # #]\n",
      " 9 [# # # # # # # . . # # # . # . # . . # # # # # # #]\n",
      "10 [# # # # # # # . . # # # . # . # . # # # # # # # .]\n",
      "11 [# # # # # # # . # # # . . . # . # . # # # # # # #]\n",
      "12 [# # # # # # # . # # # . . # . . # . # # # # # # #]\n",
      "13 [# # # # # # # . # # # . . # . # . . # # # # # # #]\n",
      "14 [# # # # # # # . # # # . . # . # . # # # # # # # .]\n",
      "15 [# # # # # # # . # # # . # . . . # . # # # # # # #]\n",
      "16 [# # # # # # # . # # # . # . . # . . # # # # # # #]\n",
      "17 [# # # # # # # . # # # . # . . # . # # # # # # # .]\n",
      "18 [# # # # # # # . # # # . # . # . . . # # # # # # #]\n",
      "19 [# # # # # # # . # # # . # . # . . # # # # # # # .]\n",
      "20 [# # # # # # # . # # # . # . # . # # # # # # # . .]\n",
      "\n",
      "Apply Knowns:\n",
      " 0 [# ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #]\n",
      "\n",
      "After:\n",
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [# # # # # # # . . . # # # . # . # . # # # # # # #]\n",
      " 1 [# # # # # # # . . # # # . . # . # . # # # # # # #]\n",
      " 2 [# # # # # # # . . # # # . # . . # . # # # # # # #]\n",
      " 3 [# # # # # # # . . # # # . # . # . . # # # # # # #]\n",
      " 4 [# # # # # # # . # # # . . . # . # . # # # # # # #]\n",
      " 5 [# # # # # # # . # # # . . # . . # . # # # # # # #]\n",
      " 6 [# # # # # # # . # # # . . # . # . . # # # # # # #]\n",
      " 7 [# # # # # # # . # # # . # . . . # . # # # # # # #]\n",
      " 8 [# # # # # # # . # # # . # . . # . . # # # # # # #]\n",
      " 9 [# # # # # # # . # # # . # . # . . . # # # # # # #]\n"
     ]
    }
   ],
   "source": [
    "def eliminate_patterns(patterns, knowns):\n",
    "    for i in reversed(range(len(patterns))):\n",
    "        if any(k not in (p, None) for p, k in zip(patterns[i], knowns)):\n",
    "            del patterns[i]\n",
    "\n",
    "# Test\n",
    "if SHOW_TESTS:\n",
    "    print 'Before:'\n",
    "    print_grid(test_pats)\n",
    "    print\n",
    "    print 'Apply Knowns:'\n",
    "    test_knowns = [1] + [None]*23 + [1]\n",
    "    print_row(test_knowns)\n",
    "    print\n",
    "    print 'After:'\n",
    "    eliminate_patterns(test_pats, test_knowns)\n",
    "    print_grid(test_pats)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deduce known cells\n",
    "\n",
    "The **generate_knowns** function does steps 3 and 5 of the general approach: give it a set of patterns, and it will deduce which cells are now known.\n",
    "\n",
    "For each cell, if all the patterns have the same value for each cell, then that is the only possible value for that cell.\n",
    "\n",
    "Notes:\n",
    "- **zip(*patterns)** transposes the pattern set so that we check one column at a time instead of one row a time\n",
    "- the **all** function will short circuit as soon as it finds a cell that doesn't match the cell in first pattern"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Patterns:\n",
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [# # # # # # # . . . # # # . # . # . # # # # # # #]\n",
      " 1 [# # # # # # # . . # # # . . # . # . # # # # # # #]\n",
      " 2 [# # # # # # # . . # # # . # . . # . # # # # # # #]\n",
      " 3 [# # # # # # # . . # # # . # . # . . # # # # # # #]\n",
      " 4 [# # # # # # # . # # # . . . # . # . # # # # # # #]\n",
      " 5 [# # # # # # # . # # # . . # . . # . # # # # # # #]\n",
      " 6 [# # # # # # # . # # # . . # . # . . # # # # # # #]\n",
      " 7 [# # # # # # # . # # # . # . . . # . # # # # # # #]\n",
      " 8 [# # # # # # # . # # # . # . . # . . # # # # # # #]\n",
      " 9 [# # # # # # # . # # # . # . # . . . # # # # # # #]\n",
      "\n",
      "Knowns:\n",
      " 0 [# # # # # # # . ? ? # ? ? ? ? ? ? . # # # # # # #]\n"
     ]
    }
   ],
   "source": [
    "def generate_knowns(patterns):\n",
    "    for col in zip(*patterns):\n",
    "        yield col[0] if all(c == col[0] for c in col) else None\n",
    "\n",
    "# Test\n",
    "if SHOW_TESTS:\n",
    "    print 'Patterns:'\n",
    "    print_grid(test_pats)\n",
    "    print\n",
    "    print 'Knowns:'\n",
    "    test_knowns = list(generate_knowns(test_pats))\n",
    "    print_row(test_knowns)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solve it\n",
    "\n",
    "Do step 1: generate sets of patterns that match the clues given for each row and column."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rows_valid_patterns = [list(generate_patterns(c, ROW_LEN)) for c in ROW_CLUES]\n",
    "cols_valid_patterns = [list(generate_patterns(c, COL_LEN)) for c in COL_CLUES]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate how many unknowns there are before we start trying to solve:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "unknowns = [count_unknowns(result)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Repeat through steps 2-5 until either:\n",
    "- There are no more unknowns i.e. we've solved it\n",
    "- The number of unknowns hasn't decreased since the last pass i.e. we've solved as much as possible\n",
    "\n",
    "Notes:\n",
    "- **map** is used to apply **eliminate_patterns** and **generate_knowns** to multiple rows/columns\n",
    "- **zip(\\*)** is used to transpose the **results** grid when working on columns, and transpose it back again before working on rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "while len(unknowns) < 2 or unknowns[-1] not in (0, unknowns[-2]):\n",
    "    map(eliminate_patterns, rows_valid_patterns, result)\n",
    "    result = map(generate_knowns, rows_valid_patterns)\n",
    "    map(eliminate_patterns, cols_valid_patterns, zip(*result))\n",
    "    result = zip(*map(generate_knowns, cols_valid_patterns))\n",
    "    unknowns.append(count_unknowns(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pass 0: 603 unknowns\n",
      "pass 1: 317 unknowns\n",
      "pass 2: 58 unknowns\n",
      "pass 3: 10 unknowns\n",
      "pass 4: 0 unknowns\n",
      "                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2\n",
      "    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4\n",
      " 0 [# # # # # # # . # # # . . . # . # . # # # # # # #]\n",
      " 1 [# . . . . . # . # # . # # . . . . . # . . . . . #]\n",
      " 2 [# . # # # . # . . . . . # # # . # . # . # # # . #]\n",
      " 3 [# . # # # . # . # . . # # # # # # . # . # # # . #]\n",
      " 4 [# . # # # . # . . # # # # # . # # . # . # # # . #]\n",
      " 5 [# . . . . . # . . # # . . . . . . . # . . . . . #]\n",
      " 6 [# # # # # # # . # . # . # . # . # . # # # # # # #]\n",
      " 7 [. . . . . . . . # # # . . . # # # . . . . . . . .]\n",
      " 8 [# . # # . # # # . . # . # . # # # . # . . # . # #]\n",
      " 9 [# . # . . . . . . # # # . # # . . . . # . . . # .]\n",
      "10 [. # # # # . # . # # # # . # # . # . . . . # # . .]\n",
      "11 [. # . # . . . # . . . # . # . # # # # . # . # # #]\n",
      "12 [. . # # . . # . # . # . . . . . . # # . # # # # #]\n",
      "13 [. . . # # # . # # . # # . # # # # # # . # # # . #]\n",
      "14 [# . # # # # # # # # # . # . # . . # # . . . . # .]\n",
      "15 [. # # . # . . # # . . . # # . # # # . . . . . # .]\n",
      "16 [# # # . # . # . # . . # . . . . # # # # # . # . .]\n",
      "17 [. . . . . . . . # . . . # # . # # . . . # # # # #]\n",
      "18 [# # # # # # # . # . . # # . . . # . # . # . # # #]\n",
      "19 [# . . . . . # . # # . . # . . # # . . . # # . # .]\n",
      "20 [# . # # # . # . . . # # # # . . # # # # # . . # .]\n",
      "21 [# . # # # . # . # # # . # # # # # # # # # # . # #]\n",
      "22 [# . # # # . # . # . . # # # # # # . # # # # # # .]\n",
      "23 [# . . . . . # . . # # . . . . . . # . # . # # . .]\n",
      "24 [# # # # # # # . # # . . . # . # # . . . # # # # #]\n"
     ]
    }
   ],
   "source": [
    "for i, u in enumerate(unknowns):\n",
    "    print 'pass %s: %s unknowns' % (i, u)\n",
    "print_grid(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}