{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## COMP SCI 1MD3 Introduction to Programming, Winter 2018\n",
"\n",
"### Douglas Stebila (Instructor), Joey Legere, Karl Knopf, Natalie Chin, Victor Chen (TAs)\n",
"### Final Exam Saturday, April 21, 9:00 - 11:00 AM\n",
"\n",
"### Explanation of short solution for Question 17 Sudoku\n",
"\n",
"Here is the question:\n",
"\n",
"> #### Question 17: Sudoku [2 points, plus up to 3 bonus]\n",
"> \n",
"> Sudoku is a puzzle game where the objective is to fill a 9x9 grid with numbers so that each column, each row, and each subgrid (that is, each group of 9 cells in the grid separated by the thicker lines) contain all of the digits from 1 to 9. An example of a \"winning\" board is below:\n",
"> \n",
"> \n",
"> \n",
"> Write a program `sudoku(b)` that, given a sudoku board `b` represented as a 2 dimensional list (where each sublist represents a row in the board), determines if the board is filled out correctly. Return `True` if the board is correct, and `False` otherwise.\n",
"> \n",
"> You can receive up to 3 bonus marks for a solution that is correct **and** short. The shortest solution we came up with was 143 characters. You will receive 1 bonus mark if your solution is correct and shorter than 600 characters, an additional 1 bonus mark if it is correct and shorter than 400 characters, and a third additional 1 bonus mark if it is correct and shorter than 200 characters. There's a function at the end which shows how we measure the length of a solution."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# some test cases\n",
"\n",
"WINNING = [\n",
" [4, 3, 5, 2, 6, 9, 7, 8, 1],\n",
" [6, 8, 2, 5, 7, 1, 4, 9, 3],\n",
" [1, 9, 7, 8, 3, 4, 5, 6, 2],\n",
" \n",
" [8, 2, 6, 1, 9, 5, 3, 4, 7],\n",
" [3, 7, 4, 6, 8, 2, 9, 1, 5],\n",
" [9, 5, 1, 7, 4, 3, 6, 2, 8],\n",
" \n",
" [5, 1, 9, 3, 2, 6, 8, 7, 4],\n",
" [2, 4, 8, 9, 5, 7, 1, 3, 6],\n",
" [7, 6, 3, 4, 1, 8, 2, 5, 9]\n",
"]\n",
"LOSING = [\n",
" [4, 3, 5, 6, 6, 9, 7, 8, 1],\n",
" [6, 8, 2, 5, 7, 1, 4, 9, 3],\n",
" [1, 9, 7, 8, 3, 4, 5, 6, 2],\n",
" \n",
" [8, 2, 6, 1, 9, 5, 3, 4, 7],\n",
" [3, 7, 4, 6, 8, 2, 9, 1, 5],\n",
" [9, 5, 1, 7, 4, 3, 6, 2, 8],\n",
" \n",
" [5, 1, 9, 3, 2, 6, 8, 7, 4],\n",
" [2, 4, 8, 9, 5, 7, 1, 3, 6],\n",
" [7, 6, 3, 4, 1, 8, 2, 5, 9]\n",
"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Initial solution\n",
"\n",
"Here's our inital solution. A few key ideas:\n",
"\n",
"- We make use of sets, which eliminate duplicates and don't care about order..\n",
"- We go through each row, and check if that row is equal (as a set) to {1, ..., 9}.\n",
"- Then we go through each column and check if that row is equal (as a set) to {1, ..., 9}. We construct an extra list `Z` that represents the column by using a *list comprehension* `Z = [B[row][col] for row in range(9)]`.\n",
"- Finally we go through the 9 sub squares. Again we use a list comprehension to create a list representing the entries in that sub square. "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 400 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set([1,2,3,4,5,6,7,8,9])\n",
" for row in range(9):\n",
" if set(B[row]) != s: return False\n",
" for col in range(9):\n",
" Z = [B[row][col] for row in range(9)]\n",
" if set(Z) != s: return False\n",
" for r in range(3):\n",
" for c in range(3):\n",
" Z = [B[3*r+R][3*c+C] for R in range(3) for C in range(3)]\n",
" if set(Z) != s: return False\n",
" return True\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Making it shorter\n",
"\n",
"All of those `if whatever: return False` take up a lot of characters. So we'll instead keep a single status variable `ret`, and update that with every row/column/subsquare validity. We use `ret &= row/column/subsquare valid`, and since we're using `&` (the `and` operator), as soon as any one of them is false, `ret` will always remain false."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 384 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set([1,2,3,4,5,6,7,8,9])\n",
" ret = True\n",
" for row in range(9):\n",
" ret &= set(B[row]) == s\n",
" for col in range(9):\n",
" Z = [B[row][col] for row in range(9)]\n",
" ret &= set(Z) == s\n",
" for r in range(3):\n",
" for c in range(3):\n",
" Z = [B[3*r+R][3*c+C] for R in range(3) for C in range(3)]\n",
" ret &= set(Z) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now let's look for duplicate code or things that can be shorter:\n",
"\n",
"- `s = set(range(1,10))` is a few characters shorter than `s = set([1,2,3,4,5,6,7,8,9])`\n",
"- We have two for loops going over `range(9)`, so we can combine those.\n",
"- In fact our for loops going over `range(9)` could iterate over a new variable `t = list(range(9))` instead of writing `range(9)` every time."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 354 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set(range(1,10))\n",
" t = list(range(9))\n",
" ret = True\n",
" for x in t:\n",
" ret &= set(B[x]) == s\n",
" Z = [B[row][x] for row in t]\n",
" ret &= set(Z) == s\n",
" for r in range(3):\n",
" for c in range(3):\n",
" Z = [B[3*r+R][3*c+C] for R in range(3) for C in range(3)]\n",
" ret &= set(Z) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we have to start getting creative. First we'll use some modular arithmetic to make our subsquare checking have fewer loops:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 301 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set(range(1,10))\n",
" t = list(range(9))\n",
" ret = True\n",
" for x in t:\n",
" ret &= set(B[x]) == s\n",
" Z = [B[row][x] for row in t]\n",
" ret &= set(Z) == s\n",
" for x in t:\n",
" Z = [B[3*(x//3)+y//3][3*(x%3)+y%3] for y in t]\n",
" ret &= set(Z) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Some more loop consolidation:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 285 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set(range(1,10))\n",
" t = list(range(9))\n",
" ret = True\n",
" for x in t:\n",
" ret &= set(B[x]) == s\n",
" Z = [B[row][x] for row in t]\n",
" ret &= set(Z) == s\n",
" Z = [B[3*(x//3)+y//3][3*(x%3)+y%3] for y in t]\n",
" ret &= set(Z) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Remember that we can put multiple statements on a single line using `;`. This would save lots of indentation. I'll show briefly the improvements we get from doing so, but then subsequent improvements will still use multiple lines for sake of readability. Right at the end we'll go back to the one-line solution."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 242 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set(range(1,10)); t = list(range(9));ret = True\n",
" for x in t: ret &= set(B[x]) == s; Z = [B[row][x] for row in t]; ret &= set(Z) == s; Z = [B[3*(x//3)+y//3][3*(x%3)+y%3] for y in t]; ret &= set(Z) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And let's put multiple `&` statements together, as well as save on creating variables:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 227 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" s = set(range(1,10))\n",
" t = list(range(9))\n",
" ret = True\n",
" for x in t:\n",
" ret &= set(B[x]) == s & set(B[row][x] for row in t) == s & set(B[3*(x//3)+y//3][3*(x%3)+y%3] for y in t) == s\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rather than comparing to `s` every time, we could use set intersection (the `&` operator on sets):"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 203 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t = list(range(9))\n",
" ret = True\n",
" for x in t:\n",
" ret &= set(range(1,10)) == set(B[x])&set(B[row][x] for row in t)&set(B[3*(x//3)+y//3][3*(x%3)+y%3] for y in t)\n",
" return ret\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's use single letter variable names, remove unnecessary spaces, and unnecessary parentheses:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 179 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t=list(range(9))\n",
" r=True\n",
" for x in t:\n",
" r&=set(range(1,10))==set(B[x])&set(B[y][x]for y in t)&set(B[x//3*3+y//3][x%3*3+y%3]for y in t)\n",
" return r\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can use the `all` operator which basically does what our `r=True, for x in t: r &= whatever` lines do:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 154 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t=list(range(9))\n",
" return all(set(range(1,10))==set(B[x])&set(B[y][x]for y in t)&set(B[x//3*3+y//3][x%3*3+y%3]for y in t)for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we'll do a trick to save on the use of the word `set` everywhere. We can create dictionaries rather than sets, using `{ ... }`, and we can convert a set into a list by using the \"star map\" which expands a list into a literal sequence, and then putting it inside braces. In other words, we'll write `{*L}` instead of `set(L)`."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 141 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t={*range(9)}\n",
" return all({*range(1,10)}=={*B[x]}&{B[y][x]for y in t}&{B[x//3*3+y//3][x%3*3+y%3]for y in t}for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`{*range(1,10)}` and `t={*range(9)}` are pretty close to each other. We can construct one from the other by using **set difference**. Recall that set difference means that you take all the things in either set, but not in both sets. For example, `{1,2,3}^{2,3,4}=={1,4}`. So we can make `{*range(1,10)}` from `t` by writing `t^{0,9}`."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 134 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t={*range(9)}\n",
" return all(t^{0,9}=={*B[x]}&{B[y][x]for y in t}&{B[x//3*3+y//3][x%3*3+y%3]for y in t}for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Set difference is going to help us out even more. We have three sets that we're intersecting together, instead we will difference them one after the other: `ROW ^ COL ^ SUBSQ`. If all of these are exactly 1 up to 9, then `ROW ^ COL` will cancel each other out yielding the empty set, and then `ROW ^ COL ^ SUBSQ` will be back to 1 up to 9. If any of them is not exactly 1 up to 9, then we won't get 1 up to 9. "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 134 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t={*range(9)}\n",
" return all(t^{0,9}=={*B[x]}^{B[y][x]for y in t}^{B[x//3*3+y//3][x%3*3+y%3]for y in t}for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That didn't actually make it shorter, but it did set us up to be able to make it shorter. It would be nice if we could compare `t` with our giant set on line 3, but `t` goes from 0 to 8, whereas our giant set on line 3 goes from 1 up to 9. We'll change one of the three sets that are being differenced together (`ROW ^ COL ^ SUBSQ`) to go from 0-8 (`ROW(1-9) ^ COL(0-8) ^ SUBSQ(1-9)`). If each set was exactly 1-9, then we get left with 0-8, which is exactly `t`."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 130 characters long.\n"
]
}
],
"source": [
"def sudoku(B):\n",
" t={*range(9)}\n",
" return all(t=={*B[x]}^{B[y][x]-1for y in t}^{B[x//3*3+y//3][x%3*3+y%3]for y in t}for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And now we put it all on line to save on indentation and line endings to get:\n",
"\n",
"## Our shortest solution"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"This solution is 121 characters long.\n"
]
}
],
"source": [
"def sudoku(B):t={*range(9)};return all(t=={*B[x]}^{B[y][x]-1for y in t}^{B[x//3*3+y//3][x%3*3+y%3]for y in t}for x in t)\n",
"\n",
"assert sudoku(WINNING) and not sudoku(LOSING)\n",
"\n",
"import inspect\n",
"print(\"This solution is {:d} characters long.\".format(len(inspect.getsource(sudoku))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That's as short as we could get.\n",
"\n",
"Trying to come up with the shortest solution to a problem is called **code golf**. Check out https://code-golf.io/ for some challenges. They don't have a Sudoku checker on their list of challenges. I couldn't find a shorter Sudoku checker in Python anywhere with Google, but if you find one I'm curious to know.\n",
"\n",
"Let me reassure you that Joey and I actually have lives and were not at all emailing each other back and forth for several days trying to out-do each other with shorter solutions. And I am not at all bitter that Joey beat me by 4 characters."
]
}
],
"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.6.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}