Skip to content

Instantly share code, notes, and snippets.

@afvanwoudenberg

afvanwoudenberg/sudoku.ipynb

Created May 1, 2023 08:26
Show Gist options
  • Save afvanwoudenberg/8a7c6599d7170c0134fa17bade510e4c to your computer and use it in GitHub Desktop.
Save afvanwoudenberg/8a7c6599d7170c0134fa17bade510e4c to your computer and use it in GitHub Desktop.
Download ZIP
A Sudoku widget and solver
Display the source blob
Display the rendered blob
Raw
sudoku.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Sudoku\n",
"\n",
"Aswin van Woudenberg (https://www.aswinvanwoudenberg.com | https://github.com/afvanwoudenberg)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from traitlets import Unicode, Bool, Int, List, validate, observe, TraitError, All\n",
"from ipywidgets import DOMWidget, register\n",
"import copy\n",
"\n",
"@register\n",
"class Sudoku(DOMWidget):\n",
" _view_name = Unicode('SudokuView').tag(sync=True)\n",
" _view_module = Unicode('sudoku_widget').tag(sync=True)\n",
" _view_module_version = Unicode('0.1.0').tag(sync=True)\n",
" \n",
" # Attributes\n",
" fixed = List(trait=Bool(), default_value=[False] * 81, minlen=81, maxlen=81, help=\"A list of booleans that indicate whether a value is part of the puzzle.\").tag(sync=True)\n",
" _value = List(trait=Int(), default_value=[0] * 81, minlen=81, maxlen=81, help=\"A list of integers for each cell.\").tag(sync=True)\n",
" disabled = Bool(False, help=\"Enable or disable user changes.\").tag(sync=True)\n",
"\n",
" # Basic validator for value\n",
" @validate('_value')\n",
" def _valid_value(self, proposal):\n",
" for i in proposal['value']:\n",
" if i < 0 or i > 9:\n",
" raise TraitError('Invalid value: all elements must be numbers from 0 to 9')\n",
" return proposal['value']\n",
" \n",
" @property\n",
" def value(self):\n",
" return copy.deepcopy(self._value)\n",
" \n",
" @value.setter\n",
" def value(self, v):\n",
" self._value = v\n",
"\n",
" def __init__(self,*args,**kwargs):\n",
" kwargs['_value'] = kwargs.pop('value', [0]*81)\n",
" DOMWidget.__init__(self,*args,**kwargs)\n",
" \n",
" def __getitem__(self,index):\n",
" return self._value[index]\n",
" \n",
" \n",
" def __setitem__(self,index,val):\n",
" vals = self.value\n",
" vals[index] = val\n",
" self._value = vals"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"application/javascript": [
"require.undef('sudoku_widget');\n",
"\n",
"define('sudoku_widget', [\"@jupyter-widgets/base\"], function(widgets) {\n",
" \n",
" // Define the SudokuView\n",
" class SudokuView extends widgets.DOMWidgetView {\n",
" \n",
" // Render the view.\n",
" render() {\n",
" this.sudoku_table = document.createElement('table');\n",
" this.sudoku_table.style.borderCollapse = 'collapse';\n",
" this.sudoku_table.style.marginLeft = '0';\n",
" \n",
" for (let i=0; i<3; i++) {\n",
" let colgroup = document.createElement('colgroup');\n",
" colgroup.style.border = 'solid medium';\n",
" for (let j=0; j<3; j++) {\n",
" let col = document.createElement('col');\n",
" col.style.border = 'solid thin';\n",
" col.style.width = '2em';\n",
" colgroup.appendChild(col);\n",
" }\n",
" this.sudoku_table.appendChild(colgroup);\n",
" }\n",
" \n",
" for (let t=0; t<3; t++) {\n",
" let tbody = document.createElement('tbody');\n",
" tbody.style.border = 'solid medium';\n",
" for (let r=0; r<3; r++) {\n",
" let tr = document.createElement('tr');\n",
" tr.style.height = '2em';\n",
" tr.style.border = 'solid thin';\n",
" for (let c=0; c<9; c++) {\n",
" let td = document.createElement('td');\n",
" tr.appendChild(td);\n",
" }\n",
" tbody.appendChild(tr);\n",
" }\n",
" this.sudoku_table.appendChild(tbody);\n",
" }\n",
" \n",
" this.el.appendChild(this.sudoku_table);\n",
" \n",
" this.model_changed();\n",
" \n",
" // Python -> JavaScript update\n",
" this.model.on('change', this.model_changed, this);\n",
" }\n",
"\n",
" model_changed() {\n",
" let tds = this.sudoku_table.getElementsByTagName('td');\n",
" let disabled = this.model.get('disabled');\n",
" \n",
" for (let i=0; i < 81; i++) {\n",
" let td = tds[i];\n",
" td.innerText = ''; // Delete td contents\n",
" td.style.textAlign = 'center';\n",
" td.style.height = '2em';\n",
" let value = this.model.get('_value')[i];\n",
" let fixed = this.model.get('fixed')[i];\n",
"\n",
" if (fixed && value > 0) {\n",
" let b = document.createElement('b');\n",
" b.innerText = value;\n",
" td.appendChild(b);\n",
" } else if (disabled && value > 0) {\n",
" td.innerText = value;\n",
" } else if (!disabled && !fixed) {\n",
" let input = document.createElement('input');\n",
" input.type = 'text';\n",
" input.maxLength = 1;\n",
" input.style.top = 0;\n",
" input.style.left = 0;\n",
" input.style.margin = 0;\n",
" input.style.height = '100%';\n",
" input.style.width = '100%';\n",
" input.style.border = 'none';\n",
" input.style.textAlign = 'center';\n",
" input.style.marginTop = 0;\n",
" input.style.padding = 0;\n",
" input.value = (value > 0 ? value : '');\n",
" input.oninput = this.input_input.bind(this, i);\n",
" input.onchange = this.input_changed.bind(this, i); // JavaScript -> Python update\n",
" td.appendChild(input);\n",
" }\n",
" }\n",
" \n",
" }\n",
" \n",
" input_input(i) {\n",
" this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value = \n",
" this.sudoku_table.getElementsByTagName('td')[i].\n",
" getElementsByTagName('input')[0].value.replace(/[^1-9]/g,'');\n",
" }\n",
" \n",
" input_changed(i) {\n",
" this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value = \n",
" this.sudoku_table.getElementsByTagName('td')[i].\n",
" getElementsByTagName('input')[0].value.replace(/[^1-9]/g,'');\n",
" let v = parseInt(this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value) || 0;\n",
" let value = this.model.get('_value').slice();\n",
" value[i] = v;\n",
" this.model.set('_value', value);\n",
" this.model.save_changes();\n",
" }\n",
" \n",
" }\n",
"\n",
" return {\n",
" SudokuView: SudokuView\n",
" }\n",
" \n",
"});\n"
],
"text/plain": [
"<IPython.core.display.Javascript object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%javascript\n",
"require.undef('sudoku_widget');\n",
"\n",
"define('sudoku_widget', [\"@jupyter-widgets/base\"], function(widgets) {\n",
" \n",
" // Define the SudokuView\n",
" class SudokuView extends widgets.DOMWidgetView {\n",
" \n",
" // Render the view.\n",
" render() {\n",
" this.sudoku_table = document.createElement('table');\n",
" this.sudoku_table.style.borderCollapse = 'collapse';\n",
" this.sudoku_table.style.marginLeft = '0';\n",
" \n",
" for (let i=0; i<3; i++) {\n",
" let colgroup = document.createElement('colgroup');\n",
" colgroup.style.border = 'solid medium';\n",
" for (let j=0; j<3; j++) {\n",
" let col = document.createElement('col');\n",
" col.style.border = 'solid thin';\n",
" col.style.width = '2em';\n",
" colgroup.appendChild(col);\n",
" }\n",
" this.sudoku_table.appendChild(colgroup);\n",
" }\n",
" \n",
" for (let t=0; t<3; t++) {\n",
" let tbody = document.createElement('tbody');\n",
" tbody.style.border = 'solid medium';\n",
" for (let r=0; r<3; r++) {\n",
" let tr = document.createElement('tr');\n",
" tr.style.height = '2em';\n",
" tr.style.border = 'solid thin';\n",
" for (let c=0; c<9; c++) {\n",
" let td = document.createElement('td');\n",
" tr.appendChild(td);\n",
" }\n",
" tbody.appendChild(tr);\n",
" }\n",
" this.sudoku_table.appendChild(tbody);\n",
" }\n",
" \n",
" this.el.appendChild(this.sudoku_table);\n",
" \n",
" this.model_changed();\n",
" \n",
" // Python -> JavaScript update\n",
" this.model.on('change', this.model_changed, this);\n",
" }\n",
"\n",
" model_changed() {\n",
" let tds = this.sudoku_table.getElementsByTagName('td');\n",
" let disabled = this.model.get('disabled');\n",
" \n",
" for (let i=0; i < 81; i++) {\n",
" let td = tds[i];\n",
" td.innerText = ''; // Delete td contents\n",
" td.style.textAlign = 'center';\n",
" td.style.height = '2em';\n",
" let value = this.model.get('_value')[i];\n",
" let fixed = this.model.get('fixed')[i];\n",
"\n",
" if (fixed && value > 0) {\n",
" let b = document.createElement('b');\n",
" b.innerText = value;\n",
" td.appendChild(b);\n",
" } else if (disabled && value > 0) {\n",
" td.innerText = value;\n",
" } else if (!disabled && !fixed) {\n",
" let input = document.createElement('input');\n",
" input.type = 'text';\n",
" input.maxLength = 1;\n",
" input.style.top = 0;\n",
" input.style.left = 0;\n",
" input.style.margin = 0;\n",
" input.style.height = '100%';\n",
" input.style.width = '100%';\n",
" input.style.border = 'none';\n",
" input.style.textAlign = 'center';\n",
" input.style.marginTop = 0;\n",
" input.style.padding = 0;\n",
" input.value = (value > 0 ? value : '');\n",
" input.oninput = this.input_input.bind(this, i);\n",
" input.onchange = this.input_changed.bind(this, i); // JavaScript -> Python update\n",
" td.appendChild(input);\n",
" }\n",
" }\n",
" \n",
" }\n",
" \n",
" input_input(i) {\n",
" this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value = \n",
" this.sudoku_table.getElementsByTagName('td')[i].\n",
" getElementsByTagName('input')[0].value.replace(/[^1-9]/g,'');\n",
" }\n",
" \n",
" input_changed(i) {\n",
" this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value = \n",
" this.sudoku_table.getElementsByTagName('td')[i].\n",
" getElementsByTagName('input')[0].value.replace(/[^1-9]/g,'');\n",
" let v = parseInt(this.sudoku_table.getElementsByTagName('td')[i].getElementsByTagName('input')[0].value) || 0;\n",
" let value = this.model.get('_value').slice();\n",
" value[i] = v;\n",
" this.model.set('_value', value);\n",
" this.model.save_changes();\n",
" }\n",
" \n",
" }\n",
"\n",
" return {\n",
" SudokuView: SudokuView\n",
" }\n",
" \n",
"});"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"import ipywidgets as widgets"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"puzzle1 = [\n",
" 0,8,5, 0,6,1, 0,0,0,\n",
" 9,0,4, 0,0,0, 0,0,0,\n",
" 0,0,0, 0,0,2, 3,0,8,\n",
" \n",
" 0,4,0, 0,0,0, 0,0,2,\n",
" 7,0,0, 0,9,0, 5,0,0,\n",
" 0,0,0, 0,3,0, 8,0,0,\n",
" \n",
" 0,0,0, 0,5,8, 0,0,0,\n",
" 0,0,0, 7,0,0, 0,1,0,\n",
" 6,0,0, 0,0,0, 0,0,4]\n",
"\n",
"puzzle2 = [\n",
" 3,6,0, 0,0,0, 0,0,5,\n",
" 0,1,0, 0,9,0, 2,0,8,\n",
" 0,5,0, 1,8,0, 0,0,7,\n",
" \n",
" 5,0,0, 0,0,6, 4,0,0,\n",
" 2,4,6, 0,5,0, 7,0,0,\n",
" 0,0,0, 0,7,0, 0,0,0,\n",
" \n",
" 0,0,0, 0,0,7, 1,0,3,\n",
" 0,0,3, 9,4,0, 0,0,0,\n",
" 0,0,0, 0,0,1, 0,0,0]\n",
"\n",
"puzzle3 = [\n",
" 0,2,0, 0,4,0, 0,0,5,\n",
" 0,5,8, 0,0,0, 0,0,0,\n",
" 0,1,0, 8,0,0, 4,0,0,\n",
" \n",
" 7,0,0, 0,0,8, 0,4,0,\n",
" 0,0,1, 9,0,5, 7,0,0,\n",
" 0,3,0, 7,0,0, 0,0,2,\n",
" \n",
" 0,0,4, 0,0,3, 0,1,0,\n",
" 0,0,0, 0,0,0, 9,6,0,\n",
" 2,0,0, 0,1,0, 0,5,0\n",
"]\n",
"\n",
"sudoku = Sudoku(value=puzzle1, fixed=[v > 0 for v in puzzle1], disabled=False)\n",
"example_dropdown = widgets.Dropdown(\n",
" options=[('Empty', [0] * 81), ('Example 1', puzzle1), ('Example 2', puzzle2), ('Example 3', puzzle3)], \n",
" value=puzzle1,\n",
" layout=widgets.Layout(margin='10px 0px 0px 20px', width='150px')\n",
")\n",
"solve_button = widgets.Button(\n",
" description=\"Solve\", \n",
" layout=widgets.Layout(margin='20px 0px 0px 20px', width='150px')\n",
")\n",
"next_button = widgets.Button(\n",
" description=\"Next\", \n",
" layout=widgets.Layout(margin='20px 0px 0px 20px', width='150px', display='none')\n",
")\n",
"vbox = widgets.VBox([example_dropdown, solve_button, next_button])\n",
"hbox = widgets.HBox([sudoku, vbox])\n",
"label = widgets.Label()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"# global variables\n",
"gen = None\n",
"solution = None\n",
"\n",
"def on_example_dropdown_change(change):\n",
" if change['type'] == 'change' and change['name'] == 'value':\n",
" value = change['new']\n",
" fixed = [v > 0 for v in value]\n",
" sudoku.value = value\n",
" sudoku.fixed = fixed\n",
" label.value = \"\"\n",
" solve_button.layout.display = 'inline-block'\n",
" next_button.layout.display = 'none'\n",
"\n",
"example_dropdown.observe(on_example_dropdown_change)\n",
"\n",
"def on_solve_button_clicked(b):\n",
" global gen\n",
" global solution\n",
" \n",
" val = sudoku.value.copy()\n",
" sudoku.fixed = [v > 0 for v in val]\n",
" gen = solve_sudoku(val)\n",
" try:\n",
" solution = next(gen)\n",
" sudoku.value = solution\n",
" except StopIteration:\n",
" label.value = \"This sudoku has no solution.\"\n",
" sudoku.fixed = [False] * 81\n",
" return\n",
" \n",
" try:\n",
" solution = next(gen).copy()\n",
" label.value = \"This sudoku has multiple solutions.\"\n",
" solve_button.layout.display = 'none'\n",
" next_button.layout.display = 'inline-block'\n",
" except StopIteration:\n",
" label.value = \"\"\n",
" solve_button.layout.display = 'none'\n",
" \n",
"solve_button.on_click(on_solve_button_clicked)\n",
"\n",
"def on_next_button_clicked(b):\n",
" global gen\n",
" global solution\n",
" \n",
" sudoku.value = solution\n",
" try:\n",
" solution = next(gen)\n",
" except StopIteration:\n",
" label.value = \"\"\n",
" next_button.layout.display = 'none'\n",
"\n",
"next_button.on_click(on_next_button_clicked)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"def solve_sudoku(puzzle, index=0):\n",
" if index == 81:\n",
" # Solution found\n",
" yield puzzle\n",
" elif puzzle[index] > 0:\n",
" # Already filled\n",
" yield from solve_sudoku(puzzle, index + 1)\n",
" else:\n",
" for v in range(1,10):\n",
" # Fill in a digit and check constraints\n",
" puzzle[index] = v\n",
" if is_valid_square(puzzle, index):\n",
" yield from solve_sudoku(puzzle, index + 1)\n",
" puzzle[index] = 0"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"def get_column(puzzle, k):\n",
" column = []\n",
" for i in range(9):\n",
" column.append(puzzle[i*9 + k])\n",
" return column\n",
"\n",
"def get_row(puzzle, r):\n",
" return puzzle[r*9:(r+1)*9]\n",
"\n",
"def get_block(puzzle, b):\n",
" block = []\n",
" for r in range(3):\n",
" for k in range(3):\n",
" block.append(puzzle[[0,3,6,27,30,33,54,57,60][b]+9*r+k])\n",
" return block\n",
"\n",
"def is_valid(l):\n",
" # Check for duplicate values\n",
" digits = [v for v in l if v > 0]\n",
" s = set(digits)\n",
" return len(digits) == len(s)\n",
"\n",
"def is_valid_square(puzzle, i):\n",
" k = i % 9\n",
" r = int(i / 9)\n",
" b = int(r / 3) * 3 + int(k / 3)\n",
" \n",
" return is_valid(get_row(puzzle, r)) and is_valid(get_column(puzzle, k)) and is_valid(get_block(puzzle, b))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "62e1d721b66345efa498982b1620e0ee",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"HBox(children=(Sudoku(fixed=[False, True, True, False, True, True, False, False, False, True, False, True, Fal…"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "b7b63943753f4687a8a193b3e0d4fb3c",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"Label(value='')"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(hbox, label)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.9.16"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment