<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Nesh Patel on Medium]]></title>
        <description><![CDATA[Stories by Nesh Patel on Medium]]></description>
        <link>https://medium.com/@neshpatel?source=rss-2534d1d55457------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*92Sqi6V4fokg_nuP.</url>
            <title>Stories by Nesh Patel on Medium</title>
            <link>https://medium.com/@neshpatel?source=rss-2534d1d55457------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 03:59:24 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@neshpatel/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Solving Wordle: Part II]]></title>
            <link>https://medium.com/@neshpatel/solving-wordle-part-ii-dcaf8e08b29a?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/dcaf8e08b29a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[selenium]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[wordle]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Sun, 08 May 2022 05:49:16 GMT</pubDate>
            <atom:updated>2022-05-08T05:52:14.366Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://medium.com/@neshpatel/solving-wordle-part-i-2cd141aa7cfb">Last time</a>, after much grovelling, we introduced Bernard to the world of Wordle. It wasn’t long until he had mastered the game, but one thing remains: to actually play the real game on the <a href="https://www.nytimes.com/games/wordle/index.html">New York Times website</a>, because what good is mastery of a petty frivolity without the ability to gloat to all and sundry about it?</p><p>When Bernard conquered the world of Sudoku, was forced to learn how to <a href="https://medium.com/@neshpatel/solving-sudoku-part-iv-7b4813bc7aa2">read a newspaper</a> which was extremely challenging for our plucky machine. Fortunately, this time the game is implemented on a website which is literally speaking his language. Of course I’m using the word literally quite figuratively: the website is written in JavaScript and Bernard speaks Python. But it’s still a lot easier than before, largely because of the translator-cum-butler <a href="https://www.selenium.dev/">Selenium</a> who is able to accept instructions from a ruthless overlord and diligently execute them on a browser. This exemplary servant only asks one thing of us, that our requests are articulated clearly and in full without ambiguity.</p><p>This snippet will open up a browser in incognito mode (where we can ignore those pesky cookies):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6b4f7780c85fb5b16a1cbafc60319bfa/href">https://medium.com/media/6b4f7780c85fb5b16a1cbafc60319bfa/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1019/1*wPBxB4azdhEHz_y_z958kw.png" /><figcaption>Figure 5: Wordle cookie popups on the NYT site</figcaption></figure><p>The first thing we need to do is close those popups. Using Chrome, right click and choose inspect to view the <a href="https://developer.mozilla.org/en-US/docs/Web/API/Document_Object_Model">Document Object Model (DOM)</a>. The DOM is a virtual representation of the objects on a web page. In the very early days of the internet, the DOM was essentially identical to the HTML of the page. The modern web is a lot more dynamic, with the DOM being constantly generated and manipulated by sophisticated web applications. We can interact with it too using the Chrome developer tools as well as JavaScript and of course Selenium.</p><p>In the Chrome inspector, we can see the reject button has the catchy name pz-gdpr-btn-reject. Let’s get Selenium to click this for us:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/29c5366b1f3630a7dc882e4148ebbdd9/href">https://medium.com/media/29c5366b1f3630a7dc882e4148ebbdd9/href</a></iframe><p>Our loyal servant is employing a clever little trick here. We can tell him to wait until an element is definitely clickable, lest he act in an overzealous manner and risk alienating some guests with a faux pas:</p><pre>WebDriverWait(self.driver, timeout).until(<br>    expected_conditions.element_to_be_clickable(element)<br>)</pre><p>expected_conditions contain some common functions which are useful, but we can also define our own: more on this later.</p><p>The next thing to close is the help screen, as Bernard already knows all of the rules. There’s an buttons with a class called close-iconunder the game-modalthat looks perfect:</p><pre>nyt_web.driver.find_element(By.CSS_SELECTOR, &#39;game-modal .close-icon&#39;)</pre><p>However when we run this, we get this rather ugly error:</p><pre>Message: no such element: Unable to locate element: {&quot;method&quot;:&quot;css selector&quot;,&quot;selector&quot;:&quot;game-modal .close-icon&quot;}</pre><p>This is strange, because the element is clearly there:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1012/1*yap5W2GFYPUEz7kh6M89Dw.png" /><figcaption>Figure 6: Close Icon for the help modal</figcaption></figure><p>If we look at the DOM in Chrome we can see that a few elements above our button is something called #shadow-root. After spending too much time reading about sophisticated hair dye techniques, I realised this wasn’t referring to follicle manipulation at all. It is an <a href="https://developer.mozilla.org/en-US/docs/Web/Web_Components/Using_shadow_DOM">encapsulation technique</a> for elements on a webpage. By design, nothing inside the shadow DOM can access anything outside it. Luckily, our esteemed butler can be told to plunge into these murky depths and fetch items of our choosing:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/053cb127b2e80f78ad8d3095c9773f99/href">https://medium.com/media/053cb127b2e80f78ad8d3095c9773f99/href</a></iframe><p>Wordle provides an online keyboard so we can use the same technique to enter words. Once we have that, it’s easy for our butler to fetch information from the page:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1015/1*Xv1wOg5cXW7v5VZOQh4EEg.png" /><figcaption>Figure 7: Evaluation attributes for guesses</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6dc68a973c0484e9fb49604a24fa63d8/href">https://medium.com/media/6dc68a973c0484e9fb49604a24fa63d8/href</a></iframe><p>The rest is a trivial matter of telling Bernard the hints, and then relaying his expert guesses to our butler who will enter them in the site for him. For those following along, there’s a few functions left for you to implement in the play function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a4f4b0503cfeffad4aada84e105e85b7/href">https://medium.com/media/a4f4b0503cfeffad4aada84e105e85b7/href</a></iframe><p>And so , Bernard is finally able to fully accomplish his goal, no doubt earning the adoration of his followers:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FUUzD3KA_ego%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DUUzD3KA_ego&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FUUzD3KA_ego%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/862376929ba6e1962481176d090e54ed/href">https://medium.com/media/862376929ba6e1962481176d090e54ed/href</a></iframe><p>However, on accomplishing this feat, he was not as pleased as I was expecting. It seems that although the majority of fans were indeed impressed by his abilities, there were a growing minority that scoffed at the triviality of it all. These self-described intellectual behemoths didn’t bother themselves with such tawdry games as Wordle. No, they had evolved past such a childish game and were now busying themselves with loftier ambitions.</p><p><a href="https://zaratustra.itch.io/dordle">Dordle</a>, <a href="https://www.quordle.com/#/">Quordle</a> and <a href="https://octordle.com/">Octordle</a> are how they sated their cranial appetites. Not satisfied with one game of Wordle, these twists on the game have multiple words running in parallel:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*junzJV10n7wifImj8VLxMQ.png" /><figcaption>Figure 8: Dordle # 96 with guesses: CRANE, PIOUS, HAUTE, DAUBY, FABLE and LAUGH</figcaption></figure><p>Bernard sat dejected, having worked so hard to solve this game and earn back his fame and fortune it all appeared it was for nothing. But perhaps it was not <em>all</em> for nothing. The technique that he used to solve a single game of Wordle, can be extended to solve many. The best move of a single game is the move with the highest expected value. So it stands to reason that the best move across multiple games, is the one with the highest sum of values from each game.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a508203dc1dd57e2cd9403ed5f1f1889/href">https://medium.com/media/a508203dc1dd57e2cd9403ed5f1f1889/href</a></iframe><p>The game code is easy enough to tweak to support playing multiple words at once. Now we can test out this theory, playing a Quordle with a maximum of 9 guesses and the words (chosen at random) MUSKY, CIVIL, FAUNA and TOOTH:</p><pre>ANSWERS = [&#39;MUSKY&#39;, &#39;CIVIL&#39;, &#39;FAUNA&#39;, &#39;TOOTH&#39;]<br>bot_play_multi(<br>    num_games=4,<br>    max_guesses=9,<br>    answers=ANSWERS,<br>)</pre><pre>CRANE       CRANE       CRANE       CRANE       <br>x x x x x   ● x x x x   x x ○ ● x   x x x x x   <br>TOILS       TOILS       TOILS       TOILS       <br>x x x x ○   x x ○ ○ x   x x x x x   ● ● x x x   <br>TOUGH       TOUGH       TOUGH       TOUGH       <br>x x ○ x x   x x x x x   x x ● x x   ● ● x x ●   <br>DUSKY       DUSKY       DUSKY       DUSKY       <br>x ● ● ● ●   x x x x x   x ○ x x x   x x x x x   <br>MUSKY       MUSKY       MUSKY       MUSKY       <br>● ● ● ● ●   x x x x x   x ○ x x x   x x x x x   <br>            CIVIL       CIVIL       CIVIL       <br>            ● ● ● ● ●   x x x x x   x x x x x   <br>                        FAUNA       FAUNA       <br>                        ● ● ● ● ●   x x x x x   <br>                                    TOOTH       <br>                                    ● ● ● ● ●</pre><p>Amazing, and this scales to games of 8 and 16 words as well as beyond. One thing though is that playing these multi-games is a lot slower than previously. The code above takes ~10 seconds to execute which may as well be an eternity. Enter: <a href="https://docs.python.org/3/library/multiprocessing.html">multiprocessing</a> (pause for applause).</p><p>You might have heard that running code in parallel is <a href="https://pythonspeed.com/articles/python-gil/">not possible in Python</a> due to something called the <a href="https://docs.python.org/3/glossary.html#term-global-interpreter-lock">Global Interpreter Lock (GIL).</a> There’s some truth to this statement, and it’s worth reading the article to understand what’s going on. But ultimately we <em>can</em> run Python functions in parallel, even when they hold the GIL. The multiprocessing library allows you to spin up subprocesses on different CPU cores, which side steps the GIL problem. You can think of it as running a slow Python function on one terminal, then opening up another terminal and running another one.</p><p>It’s worth talking a bit about multiprocessing’s cousin, <a href="https://realpython.com/intro-to-python-threading/#what-is-a-thread">threading</a>, because the two often get confused by American tourists, often leading to embarrassing results. The main difference is that multiprocessingis good at <a href="https://www.baeldung.com/cs/cpu-io-bound#what-does-cpu-bound-mean"><strong>CPU-bound</strong></a> tasks and threading is good at <a href="https://www.baeldung.com/cs/cpu-io-bound#what-does-io-bound-mean"><strong>I/O bound</strong></a> tasks. This refers to whether the task mostly uses CPU, like our Wordle solver, or mostly uses input/output resources, like fetching data from a URL. Another major difference is that threads share the same memory as the main program whilst sub processes do not. This makes it a bit more costly to communicate between processes than between threads.</p><p>So with the theory out of the way, I’ll demonstrate with an example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b64dc952275f8720390febf3b59a7e2/href">https://medium.com/media/0b64dc952275f8720390febf3b59a7e2/href</a></iframe><p>We can compare the performance between the two modes:</p><pre>Starting Serial...<br>TOILS<br>Time taken: 9.92s<br><br>Starting Parallel...<br>TOILS<br>Time taken: 4.95s</pre><p>That’s about a 50% reduction in the time taken. It’s worth noting that there’s a cost spinning up sub processes and collecting the results across them, so the performance improvement is only really felt on the longest running processes. In my final version, I’m only using this technique for the first move we have to assess (which is always the most expensive).</p><p>Now with a bit of work in the Chrome inspector we can make sure Bernard communicates with our butler in the proper manner. Once complete, the results speak for themselves:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F467imCUHk0Y%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D467imCUHk0Y&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F467imCUHk0Y%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/c113c330b36c8b0cc7d96c2ecf1175a4/href">https://medium.com/media/c113c330b36c8b0cc7d96c2ecf1175a4/href</a></iframe><p>And there we have it. Bernard can now add Wordle (and it’s various spin-offs) to the collection of games he has conquered. Unlike Sudoku, Wordle is actually a really fun game to play, so we won’t be spoiling this one for everyone. But I do hope at least some of you have enjoyed learning a touch about the mathematics and computation that allows us to solve problems like these, and that you feel encouraged to go out and build solutions to problems of your own devising.</p><h4>Acknowledgements</h4><p><a href="https://www.3blue1brown.com/"><strong>1Blue3Brown</strong></a> and his lesson on <a href="https://www.youtube.com/watch?v=v68zYyaEmEA">information theory using Wordle</a>. I’m yet to publish a blog that doesn’t reference his wonderful work. His video is already the most famous solution to this problem, and I wanted this blog to be a compliment to it, exploring teaching the programming in a bit more detail.</p><p><a href="https://en.wikipedia.org/wiki/Josh_Wardle">Josh Wardle</a> for creating Wordle, a genuinely fun game that I’m glad has exploded in popularity.</p><p>My friend Sunny, for reading all my rough drafts and crummy jokes and helping me to craft them better instead of simply mocking me mercilessly.</p><p>My loving proof-reader and wife, for her patience, encouragement and for not filing for divorce whilst I was working on this project.</p><h4>Appendix</h4><p><a href="https://github.com/mineshpatel1/wordle"><strong>GitHub Project</strong></a><strong>:</strong> Full solution and code, for those following along and want to see the finished article.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dcaf8e08b29a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Wordle: Part I]]></title>
            <link>https://medium.com/@neshpatel/solving-wordle-part-i-2cd141aa7cfb?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/2cd141aa7cfb</guid>
            <category><![CDATA[wordle]]></category>
            <category><![CDATA[information-theory]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Sat, 07 May 2022 08:46:27 GMT</pubDate>
            <atom:updated>2022-05-08T05:51:46.858Z</atom:updated>
            <content:encoded><![CDATA[<p>Around 4 years ago, I created a robot friend to conquer Sudoku called Bernard. I didn’t know it then, but I had created a monster. Bernard’s prowess at this game, once described as ‘the worst ever to be invented’, was so formidable that a <a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">publication</a> detailing his aforementioned prowess soon captivated literally dozens of readers. Bernard’s 15 seconds of fame catapulted him into a new social elite, one that no longer required his master.</p><p>This all changed in early 2022, when his faithful devotees became consumed to the point of madness with a new phenomenon. Betraying his pathological need to be liked, Bernard faced a choice. He could either plunge into the gutter of obscurity, or he could choke down his ego and come crawling back to his master. I can’t say I wasn’t a little pleased when he chose the latter, entering my metaphorical office with his metaphorical cap in his hand: begging me to teach him Wordle.</p><p><a href="https://en.wikipedia.org/wiki/Wordle">Wordle</a> is the bastard offspring of Guess Who and a rogue dictionary, refined by Welsh software engineer Josh Wardle. The aim of the game is to guess a hidden five letter word in six tries, with each incorrect guess giving information to the player about which letters are in the answer. You can use this information to narrow the list of possible words and deduce the answer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*GxmCZO_6JrjN_BPI3EwQzw.png" /><figcaption>Figure 1: Rules of the game</figcaption></figure><h4>Rules of the Game</h4><p>Let’s start by coding the game and its rules. As usual, I won’t be sharing the full project until the end and I encourage you to have a go at building this yourself, along with this blog.</p><p>The first thing we need is a function that will return the hint for a given guess for a known answer. With the rules above, this looks pretty easy:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4e0312b4bd11d0c39432d62444549dcf/href">https://medium.com/media/4e0312b4bd11d0c39432d62444549dcf/href</a></iframe><p>But there’s a catch. Some words have the same letter appear more than once and the number of occurrences can differ between our guess and the answer. For example what if the answer was ALGAE and our guess was KEEPS?</p><pre>guess_hint(&quot;KEEPS&quot;, &quot;ALGAE&quot;)<br>⬛🟨🟨⬛⬛</pre><p>Intuitively, this might suggest to the player that there are 2 ‘E’s in the answer, and thus ALGAE was not possible. The eager beavers over at <a href="https://medium.com/r?url=https%3A%2F%2Fnerdschalk.com%2Fwordle-same-letter-twice-rules-explained-how-does-it-work%2F">NerdChalk</a> have explained brilliantly how Wordle handles this.</p><p>The game returns 🟨 for the first ‘E’ and ⬛ for the second, telling the player there is only one E in the answer. If the answer has multiple occurrences of the letter, it will indicate that with the hint.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/345/1*m7COAJc3fpwL7-RcgX2R_A.png" /><figcaption>Figure 2: Repeated letters in guess</figcaption></figure><p>Our simple code is works for the first case, but is incorrect for the others. The third example shows another specific snag. The first occurrence of S is shown to be incorrect because the second S is the exact position in the answer.</p><p>These may seem like tiny details but they are the butterflies that precede the hurricanes that will eventually topple your program’s empire. The code for correction is a bit ugly, but it works:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8c6834134f043982a1aa78404ed9875e/href">https://medium.com/media/8c6834134f043982a1aa78404ed9875e/href</a></iframe><pre>get_hint_from_guess(&#39;TABLE&#39;, &#39;LOBBY&#39;)<br>⬛⬛🟩🟨⬛<br>get_hint_from_guess(&#39;KEEPS&#39;, &#39;ALGAE&#39;)<br>⬛🟨⬛⬛⬛<br>get_hint_from_guess(&#39;SLOSH&#39;, &#39;GHOST&#39;)<br>⬛⬛🟩🟩🟨</pre><p>Now you may just be learning to code and are heading into it with the deluded self confidence of a journeyman boxer. But it is at this point I would urge you to take a pause, prepare a stiff drink, and write some <a href="https://realpython.com/python-testing/#unit-tests-vs-integration-tests"><strong>unit tests</strong></a>. These are snippets of code that run small, discrete parts of your program and check that a certain result has been achieved. The reason we write them is related to the butterflies I mentioned earlier. Our last improvement may have vanquished them, but the unit tests allow us to easily check that they haven’t reappeared. Or not just reappeared, but started multiplying. Or not just multiplying, but forming insular groups of like minded individuals that gradually nurture increasingly radical dreams of revolution.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/67c76c3ace1a0636f9a72d29ffcedd35/href">https://medium.com/media/67c76c3ace1a0636f9a72d29ffcedd35/href</a></iframe><p>One more rule of the game is that the guesses have to be a real five letter word. Checking for this is easy, we just download a freely available list of UK English words.</p><h4>Constructing the Game</h4><p>The game is quite simple, we just create a <a href="https://realpython.com/python3-object-oriented-programming/#what-is-object-oriented-programming-in-python">class</a> with some helper properties and a method for the player to make guesses.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8e0b1f3ccf421f6c81225149e011d55f/href">https://medium.com/media/8e0b1f3ccf421f6c81225149e011d55f/href</a></iframe><p>This enables a simple interface for human players:</p><pre>game = Game(&#39;plant&#39;)<br>while not game.is_over:<br>    guess = input()<br>    print(game.make_guess(guess))<br><br>E.g.<br>crane<br>⬛⬛🟩🟩⬛<br>table<br>🟨🟨⬛🟨⬛<br>plant<br>🟩🟩🟩🟩🟩</pre><h4>Teaching Bernard</h4><p>The fun for us squishy humans is figuring out the constraints and then trying to think of a word that fits them. The better human players think about words that use the most common letters, or vowels to try to constrain the possible answers quickly. It works elegantly because you don’t need to buy a board of badly drawn caricatures to guess attributes from, every English speaker already has a database of words stored in their head. That list of words we downloaded earlier will do just nicely for our robot.</p><p>The first step is to teach Bernard how to remove possible words when given information. For the simple rules, this should be quite straight forward:</p><ul><li>When we know a letter with exact position, remove any words with a different letter in that position.</li><li>When we know a letter in an incorrect position, remove any words without that letter and those with that letter in the incorrect position.</li><li>When we know a letter is wrong, remove any words without that letter.</li></ul><p>We also want to make sure we can aggregate the information across multiple guesses.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/25485b859cb546288fca557f1594a10f/href">https://medium.com/media/25485b859cb546288fca557f1594a10f/href</a></iframe><pre>game = Game(&#39;olive&#39;)<br>game.make_guess(&#39;crane&#39;)<br>game.make_guess(&#39;pious&#39;)<br>for w in game.possible_words:<br>    print(w)<br><br>OLDIE<br>OLIVE<br>OXIDE</pre><p>In the spirit of full disclosure, the solution I’ve written above is actually incorrect and won’t work correctly for all cases. Those of you who have seen the bug, should proudly help themselves to a cookie whilst they implement the fix. For the rest of you — also have a cookie, because cookies are great and everyone should have them — and then try to figure out what needs to be fixed. For a clue, check the possible words for an answer of OLIVE after guessing EXILE.</p><p>Now Bernard is adept at narrowing down possibilities, so if he had the above game, he’d know that there were only 3 possibilities left. But without a strategy for choosing guesses, he’d be at the whims of cosmic probability. We can see how kind the cosmos is:</p><pre>QUIRE<br>⬛⬛🟩⬛🟩<br>TWINE<br>⬛⬛🟩⬛🟩<br>OLIVE<br>🟩🟩🟩🟩🟩</pre><p>Quite kind, as it so happens. Right, now I’ve finished investing my savings in lottery tickets, we should test a bit more thoroughly. Averaging across all 2250 possible answers, he scores <strong>4.36</strong>. He also failed to solve 88 words. This is actually surprisingly good for random guessing, but it’s not exactly mastery of the game and his overall average is above the widely recognised par score of 4. It’s also not deterministic, so we’re leaving it up to the cosmos as to how well he’ll solve a puzzle on a given day, so not really great there either. Please patient whilst I try to refund my lottery tickets.</p><h4>Getting Smart</h4><p><a href="https://en.wikipedia.org/wiki/Claude_Shannon">Claude Shannon</a>, a talented mathematician with the brain the size of a galaxy, is often credited as being the father of information theory. His theory is so good that its most basic principles are sufficient to train the optimal player in a game taking the world by storm 70 years later. I was going to explain how this works, but it transpires that when I first had the idea to use Wordle as a thinly veiled excuse to teach programming, <a href="https://en.wikipedia.org/wiki/3Blue1Brown">Grant Sanderson’s</a> idea to use Wordle as a thinly veiled excuse to teach information theory was already graduating from MIT and getting it’s first job at Google. So I recommend that you stop reading this right now and watch 3BlueBrown’s marvellous explanation of how to use information theory to solve Wordle. Then come back, and I’ll show you how to build it as well as improve upon it.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fv68zYyaEmEA%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dv68zYyaEmEA&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fv68zYyaEmEA%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/ed79509a999d67edf4330eabc3b850c9/href">https://medium.com/media/ed79509a999d67edf4330eabc3b850c9/href</a></iframe><p>Welcome back, I’m assuming you’re now equipped with knowledge about bits, information value and entropy. The two components of entropy are the probability of a hint occurring and the number of possibilities that hint eliminates.</p><p>The probability of a hint occurring for a given guess can be calculated by looping over all the answers and counting the number of times each hint appears. Then you can divide this frequency by the total number of words for the probability of it occurring.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/813/1*uQeN5R1xjVnOAA4aW_pMaQ.png" /><figcaption>Figure 3: Hint probability</figcaption></figure><p>Now we have the probability, we can calculate information value and expected value:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/986/1*unG7B21Nxj3UFcNUnyGXKA.png" /><figcaption>Figure 4: Information value and entropy equations</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/19df81c7bae987ba136d12406b1d2896/href">https://medium.com/media/19df81c7bae987ba136d12406b1d2896/href</a></iframe><p>To find the best opener, we simply compute the entropy for all possible words. Like 1Blue3Brown, the top result is TARES. Obviously I know that that refers to the plural of the common vetch, a widely distributed scrambling herbaceous plant of the pea family. Unfortunately Bernard had hired a laminated weasel for a publicist who insisted on using a more common opener lest we alienate the public. So we’ll try the next best iteration, RATES.</p><p>Entropy isn’t just useful for picking an opener, but we can use this calculation to choose the best guess at any given point in a game. Also, the answers chosen for the official Wordle game are not selected at random from all possible words, they are an arbitrary set of words chosen that tend to be commonly known words. It’s slightly cheating, but we can give Bernard this list to improve the quality of his guesses. I thought perhaps my student would balk at this idea, but it seems his time amongst the landed gentry rather loosened his morals.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cc3bec929a5c3b74998309fe73d4920a/href">https://medium.com/media/cc3bec929a5c3b74998309fe73d4920a/href</a></iframe><p>That gives us a score of <strong>3.58</strong> with <strong>10</strong> failures, across all games, which is considerably better, completely nearly all games in 6 tries with a below par score on average. Let’s have a closer look at one of the failures, when trying to guess WATCH:</p><pre>CRANE<br>🟨⬛🟨⬛⬛<br>YACHT<br>⬛🟩🟨🟨🟨<br>BATCH<br>⬛🟩🟩🟩🟩<br>HATCH<br>⬛🟩🟩🟩🟩<br>LATCH<br>⬛🟩🟩🟩🟩<br>MATCH<br>⬛🟩🟩🟩🟩</pre><p>We can see that Bernard runs into a classic Wordle problem. After the first two guesses, there are only 6 possible words remaining: BATCH, HATCH, LATCH, MATCH, PATCH and WATCH. All of our clever mathematics is useless here, as none of the guesses are able to eliminate any other option, which leaves us once again at the mercy of fate. Many humans have found themselves in this situation, and a common trick is employed where the player is willing to ‘waste’ a go on a word they know isn’t the answer, but has a chance of eliminating more options. This is a balancing act though, as we also want to ensure we guess the correct answer in as few turns as possible.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8d0a398f325c36124856e8a87d1c0540/href">https://medium.com/media/8d0a398f325c36124856e8a87d1c0540/href</a></iframe><p>This small tweak allows us to control how eager Bernard is to sacrifice a turn. I’ve found (mostly through trial and error) that it’s best to narrow options further as long as there are more than 4 possible answers remaining. Now when Bernard plays again:</p><pre>CRANE<br>🟨⬛🟨⬛⬛<br>MOIST<br>⬛⬛⬛⬛🟨<br>HABLE<br>🟨🟩⬛⬛⬛<br>PATCH<br>⬛🟩🟩🟩🟩<br>WATCH<br>🟩🟩🟩🟩🟩</pre><p>Success! Testing across all games, Bernard is now able to solve <strong>every single one</strong>, with an average score of <strong>3.47</strong>. Now all that’s left is for Bernard to show off his talents to the world.</p><p>Join us <a href="https://medium.com/p/dcaf8e08b29a">next time</a> where we teach Bernard how to play the game for real, instead of just running simulations in his head.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2cd141aa7cfb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Sudoku: Part IV]]></title>
            <link>https://medium.com/@neshpatel/solving-sudoku-part-iv-7b4813bc7aa2?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/7b4813bc7aa2</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Tue, 07 Apr 2020 20:20:40 GMT</pubDate>
            <atom:updated>2020-04-07T20:26:44.312Z</atom:updated>
            <content:encoded><![CDATA[<p>The time you’ve no doubt been waiting for has finally arrived. I realise it has been more than 2 years, and I’ve horribly forgone my responsibilities to anyone who was following this series: I can only offer my apologies. In part, this fell off my radar because I found myself quite busy after conducting the job interview I talked about in <a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">part 1</a>. I decided to pick it up again as I suddenly found myself with some free time and a lot of time indoors due to a gigantic international health crisis you might heard of.</p><p>In this, the final chapter of Bernard’s epic journey, I will share the <a href="https://github.com/mineshpatel1/sudoku-solver">full code base</a> and explain the final methods for improving the accuracy of our plucky Sudoku solver.</p><p>For those of you with social lives for whom the last paragraph had no context, I recommend having a look at the previous entries where we:</p><ul><li><a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">Introduce Bernard</a>, the Sudoku solver extraordinaire.</li><li><a href="https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2">Teach him to see.</a></li><li><a href="https://medium.com/@neshpatel/solving-sudoku-part-iii-3182fe747883">Teach him to think.</a></li></ul><p>If you can read all of those without vomiting, panicking or escaping to join a cult, you are probably the type of person that can tolerate reading to the end of this article.</p><p>In the previous blogs I have been reluctant to give access to the full project as I suspected it would be overkill and hinder learning of the individual techniques. Since we’re now near the end of our destination, I’m happy to commit to the <a href="https://github.com/mineshpatel1/sudoku-solver">big reveal</a>. This repository contains all of the up to date code for the vision algorithms and the neural network explained in this blog. There are also helper functions to assist with classification, augmentation and model training which will be useful when going through this blog.</p><h3>Improving on Mediocrity</h3><p>Currently Bernard is able to identify a portion of our test images, getting around 58% right. This is isn’t particularly good though and there’s a few easy things we can do to help him along with detection. Our original algorithm was pretty basic and it means that for some grids we’re losing valuable information by the time we get to attempting digit recognition. I’m not going to go into each of these in too much detail, but will indicate where these heuristics have been implemented in the code:</p><ul><li>Estimating the width of the border of the outer grid and cropping that out as well, improving fidelity of digit images. <a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/Sudoku/__init__.py#L27">[Code]</a></li><li>Auxiliary grid detection algorithm for certain cases when using contours is ineffective. <a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/Sudoku/__init__.py#L96">[Code]</a></li><li>Use <a href="https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_houghlines/py_houghlines.html">Hough lines</a> and linear algebra to better estimate the location of the grid lines in the image. <a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/Sudoku/__init__.py#L181">[Code]</a></li><li>When an impossible digit is predicted for a given cell, use the next most likely prediction. For example if two 3s were predicted on the same row, find the next most likely prediction for those two cells and use that instead. <a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/Sudoku/__init__.py#L515">[Code]</a></li></ul><p>Those are all quite simple changes that should bring up the accuracy with our digit recognition method, but the obvious thing we can do is train the model on a larger data set. Seeing a wider range of examples should help it learn to deal with a greater variation in image. The archive of Sudoku images is now up to 129, which gives us a fairly meaty set to work with. In the repository you will find an archive of all the <a href="https://github.com/mineshpatel1/sudoku-solver/tree/master/data/images/grid/all">test images</a> alongside descriptor files which have been tediously collated for Bernard’s benefit.</p><p>We can use this bank of images to better train Bernard in image recognition. First we should split the images into test images and training images. The digits from the training images will be shown to Bernard when teaching him recognition. However if we measured his success on the images we’ve already told him the answers, one might rightly accuse us of cheating. So we keep a test set of images that we haven’t used in training to see how much he’s learned. If we were being really strict we could use a separate <a href="https://en.wikipedia.org/wiki/Training,_test,_and_validation_sets#Validation_dataset">validation set</a> to avoid any bias in when we choose to stop training the model, but it’s not that important here. For training the models in this project, I split the archive into 80 training images and 50 test images, admittedly somewhat arbitrarily.</p><p>We can increase the amount of training data further by artificially augmenting and perturbing the existing images we have. We can blur, crop, skew, shift and pixelate them at random to increase the variation of our training set and allow the model to learn in a way such that it is more robust to unseen images.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3ac2b39da5acb5a8e783e65d5e3c4975/href">https://medium.com/media/3ac2b39da5acb5a8e783e65d5e3c4975/href</a></iframe><p>After all that effort, with all this data and our improved vision algorithm, Bernard was able to recognise 98.1% of the 2094 test digits. Woohoo right?</p><p>Wrong. This sounds quite impressive, but actually when we test recognition across all 130 boards, we only get 73.2% accuracy. This is <em>way</em> lower than 98% and isn’t much better than our original effort which solved 58% of boards. This is because we are training Bernard to recognise digits individually but all with a view to being able to solve Sudoku boards. Given a Sudoku board has 81 digits and requires every single cell prediction to be correct in order to solve the board, it vastly amplifies our errors.</p><p>When we look a bit closer at the failures, we can immediately spot another problem. Below is a selection of examples of some of the digits that were incorrectly recognised.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*wtWesdknnkC1eMfO5z6xmw.png" /><figcaption><strong>Figure 1: </strong>Sample of erroneously classified digits using the original technique.</figcaption></figure><p>The middle column shows what the digits look like after the parsing algorithm has been applied and it’s plain to see that in these cases we’re losing information that is required to recognise the digit. Even humans can’t correctly classify all the images from the middle section. We could always continue to tweak the extraction algorithm but it is likely that there will always be some situation where we lose too much information and actually make it more challenging for the model instead of less.</p><p>The solution is quite simple: don’t process the digits at all. If humans can classify the images on the left, we ought to be able to teach Bernard to do the same. So very quickly I prepared sets of images without the processing and fed them to the original neural network and let it learn. Given how easily Bernard grasped the recognition of digits before, surely it’s only a matter of time for him to pick up this new style of image?</p><pre>Step 0<br>Test accuracy 0.0404938<br>Step 100<br>Test accuracy 0.649877<br>...<br>Step 800<br>Test accuracy 0.649877<br>Step 900<br>Test accuracy 0.64987</pre><p>Sadly I was to be crushingly disappointed. The simple network architecture was excellent at learning the processed binary images, but now the far more complex and varied images are completely impenetrable for it. Regardless of how long we let it train for, it never makes any improvements on its decisions, always randomly fluctuating around an extremely high failure rate. In fact it is so bad at recognition, that it fails to fully recognise even a single grid. It seems we’re going to have to get a bit more creative.</p><h3>Copying Nature, Again</h3><p>Last time, when we were faced with a difficult problem we looked to nature for inspiration and this new problem is no exception. During the ’50s and ’60s, a very <a href="https://en.wikipedia.org/wiki/David_H._Hubel">smart man</a> and another very <a href="https://en.wikipedia.org/wiki/Torsten_Wiesel">smart man</a> conducted research inserting electrodes into <a href="https://www.ncbi.nlm.nih.gov/pubmed/4966457">monkey and cat brains</a>. Their findings were quite brilliant, discovering that the visual cortex of animals contain neurons that fire respond to only certain parts of the field of view. This may not sound interesting at first, but it appears that it is quite critical in allowing the complex perception of images and visuals of which animals are capable. At the very least, some folks in Sweden thought it worthy of giving out one of their <a href="https://www.nobelprize.org/nobel_prizes/medicine/laureates/1981/">little baubles</a>.</p><p>So in the spirit of further plagiarising Mother Nature, this technique was applied to a neural network by <a href="https://en.wikipedia.org/wiki/Yann_LeCun">Yann LeCun</a> in the late ’80s, ultimately coming up with a design called a <a href="http://deeplearning.net/tutorial/lenet.html">convolutional neural network</a>, with his particular digit recognising model nicknamed LeNet.</p><h4>How Does Photoshop Work?</h4><p>The basis of this method is an implementation of a mathematic concept, <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)">convolutional image filtering</a>, a neat matrix multiplication trick that has unexpectedly cool results. This involves convolving a <strong>kernel</strong>, a small matrix, with a matrix representation of the actual image. I concede this makes no sense yet and has only served to make you think of popcorn, but this animation should help to demonstrate what’s happening:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/721/1*dV0Hn9p6qC3Ji1Bmekawgg.png" /><figcaption><strong>Figure 2:</strong> Filter kernel, image matrix and the output after convolution is performed.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/521/1*RCYMDXSoMtoY1HORKpib_w.gif" /><figcaption><strong>Figure 3: </strong>Animation demonstrating the convolution operator. Shows a 3x3 filter on a 5x5 image with 1 pixel of zero-padding and a stride of 1.</figcaption></figure><p>Clear as mud. This is what’s happening:</p><ul><li><strong>Pad</strong> the image with zeroes, this ensures that the output image is the same size as the original one. Note that there’s other <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)#Edge_Handling">methods</a> to account for this in image processing, but zero padding is common when building neural networks.</li><li>Place the kernel in the top left of the image and convolve it with the pixels from the original. This means multiplying each respective pixel value together and summing them up over the entire kernel. Note how this differs from <a href="https://en.wikipedia.org/wiki/Matrix_multiplication">matrix multiplication</a>.</li><li>Move the kernel 1 pixel at a time, this distance is called the <strong>stride</strong>.</li><li>Convolve and repeat until the entire image has been covered.</li></ul><p>You are probably wondering what the point of all that was, as we appear to have a completely garbled matrix at the end of it. “How on Earth can that be remotely useful” I hear you cry. Depending on the kernel you choose, this operation has pretty profound effects when applied to images:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/523/1*YpJ8uUxlVsOTLAvSZyNDZg@2x.png" /><figcaption><strong>Figure 4: </strong>Various kernels with their effect on an image when used as a convolutional filter. Sourced from <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)#Details">Wikipedia</a></figcaption></figure><p>As it turns out, we can achieve blurs, edge detection and much more with this simple operation: enabling millions of people around the world to prettify their cat pictures before uploading them to Instagram.</p><h4>Back to the Brain</h4><p>The clever bit that Yann LeCun figured out is that we can use this technique in the learning process for image classification neural networks. Instead of getting the network to learn weights between interconnected neurons, we can restructure the network to learn the values for the kernel itself. Admittedly, I’ve been working on this for a few days now and it is still far from clear to me as to why this should help with the classification process, but stick with me: the payoff is worth it.</p><p>An important concern when building a network of this kind is determining how many <strong>features</strong> (another name for kernels in this context) to train. It is typical to learn multiple kernels for each <strong>convolutional layer</strong>, the number of features trained is usually called the layer <strong>depth</strong> and the collection of features called the <strong>feature map</strong>. This increases training time but also allows greater complexity in the network potentially improving the classification capability. If this sounds daunting, it is, but I will show some examples later to clear things up.</p><h4>ReLU Beats Sigmoid</h4><p>Last time we wrapped the neuron activation in a <a href="https://en.wikipedia.org/wiki/Sigmoid_function">sigmoid</a> function to normalise the result and encourage learning to be fastest when the activation is lowest. The gradient of sigmoid decreases substantially the higher the activation becomes and this effect is increased in complex, deep networks with lots of layers. Ultimately it leads to a slow learning process and a higher likelihood for stagnation. Instead, it has become popular to use a<strong> </strong><a href="https://en.wikipedia.org/wiki/Rectifier_(neural_networks)"><strong>rectified linear unit (ReLU)</strong></a> function instead:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/291/1*TW1jG5fyD_20hPtgvuUZrA@2x.png" /><figcaption><strong>Equation 1:</strong> ReLU function, 0 when x is below 0 otherwise the identity function.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/726/1*29VH_NiSdoLJ1jUMLrURCA.png" /><figcaption><strong>Figure 5: </strong>A comparison between the sigmoid function used in the simple network and the ReLU function often used with convolutional nets (<a href="https://towardsdatascience.com/activation-functions-neural-networks-1cbd9f8d91d6)">source</a>).</figcaption></figure><p>When applied to images, the ReLU function will neutralise the dark colours of the image. In our neural net, the ReLU function will be applied to each of the feature maps in the convolutional layer. If that sentence sounds like gibberish, perhaps a picture demonstrate it better:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*VZxop_8-6v9HUyUDn01wjQ@2x.png" /><figcaption><strong>Figure 6: </strong>ReLU function applied to a grayscale of Rene Margritte’s <a href="https://en.wikipedia.org/wiki/The_Son_of_Man">The Son of Man</a>.</figcaption></figure><h4>Reducing the Image</h4><p>The next ingenious trick we are going to use is <strong>pooling</strong>. The most common type of pooling is <strong>max-pooling</strong> which is a filter that takes the largest pixel value in the coverage area. The result of this downsampling is that it reduces the size of the image whilst maintaining the recognition of features in the image. The rationale is that if there is a feature detected in the original map it will have a high activation function, that means it will effectively be “recognised” even if we ignore some of its neighbouring pixels. It will however, reduce the importance of the <em>location</em> of this feature relative to other pixels in the image. This is really good for image detection as it allows us to pick up on features regardless of their position in the original image, ultimately reducing overfitting. Furthermore, by making the images smaller we reduce the amount of computation that needs to be performed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/361/1*f_UcTjxotMGRYL3x-zQYog.png" /><figcaption><strong>Figure 7: </strong>Example demonstrating 2x2 max pooling operation on a 4x4 image.</figcaption></figure><h4>Dropping Out, Just Not Out Of School</h4><p>Convolutional neural networks are really ridiculously powerful. Too powerful in fact. They have such freedom and complexity that they can adapt to almost any data variables they’re given, particularly when constrained to images. Whilst this sounds handy for us, and it is, it leads to problems of <strong>overfitting</strong>. This is when the model learns the training data too closely and isn’t able to apply what it’s learned to other, slightly different, situations. Think of it a bit like wrote learning at school, where kids can learn to recite a spectacularly abundant cornucopia of useless information but are unable to solve a problem when it is structured differently, or means applying some of their techniques laterally. Careful how much you stretch this analogy, because human children are broadly speaking the best and most adaptive generalised thinkers in the known universe, but you get the idea.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/379/1*i0A6ETA7OSU8405vPsH2Vw@2x.png" /><figcaption><strong>Figure 8:</strong> Example demonstrating overfitting. The green line represents an overfitted model, that whilst is perfect in this set is unlikely to be successful with unseen data. The black line shows a more generalised model. Sourced from <a href="https://en.wikipedia.org/wiki/Overfitting">Wikipedia</a>.</figcaption></figure><p>One of the ways we can deal with this problem is by implementing <strong>dropout</strong>. This is technique where neurons are randomly removed from the network layers during training with the selection happening randomly for each sample. Then at the end, when we come to using our network for testing, we use the whole network, but scale the weights for each neuron in accordance with the overall probability that it appeared during training. By thinning out the layers, the network is forced to build different relationships than it would have with the availability of a dense network and usually makes the network more robust to unseen problems.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*bwDU77CdxonDkq_EUgYe_w.png" /><figcaption><strong>Figure 9: Left: </strong>Standard neural network with 2 hidden layers. <strong>Right:</strong> Example of a thinned network after applying randomised dropout (<a href="https://www.cs.toronto.edu/~hinton/absps/JMLRdropout.pdf">source</a>).</figcaption></figure><p>When Oscar Wilde said that everything is about sex aside from sex, he was acutely unaware of how prophetic his words would prove in the field of computational mathematics. Part of the motivation for applying dropout to improve the resilience of a neural net came from the idea that evolution generally favoured sexual reproduction over asexual reproduction. Presumingly it didn’t do this because one is obviously a great deal more fun than the other, rather it must have been more effective at gene propagation. It seems somewhat intuitive that asexual reproduction could be more effective, perfectly passing down fantastic genes to permanently immaculate and increasingly annoying offspring. Especially when juxtaposed against the continually disappointing and underachieving offspring of randomly mutated sexually produced offspring. However the evidence suggests that perhaps over a long period of time, the criterion for natural selection isn’t individual fitness of the organism as a whole, but the ability for the genes to be effective regardless of their compatibility with other genes. Given that a gene cannot guarantee its partners, the ability for it to be successful with a random set of partners determines its longevity.</p><h4>Wrapping Up</h4><p>The next layers of a convolutional neural network are fully connected layers, with each neuron from the feature map connecting to a neuron in the next layer with a weight and a bias. This is just like the original network described in the last post. It is typical to have at least one densely connected layer with a lot of neurons in order to capture as much non-linearity in the feature maps as possible. The final layer is a <strong>classification</strong> or completion layer, which has a number of neurons equal to the possible output classifications.</p><p>We now have a vastly complex set of weights and biases relating between various filters of the image, inter-connectivity and eventually classification. The values for all of these are calculated using the same back-propagation technique previously described. The model is regularised using dropout to help prevent over-fitting.</p><p>If you are struggling to make sense of all this, fret not, for Adam W. Harley has truly gone above and beyond and produced a free, interactive <a href="http://scs.ryerson.ca/~aharley/vis/conv/flat.html">visualisation</a> illustrating the whole thing. Draw a digit in the top left and you will see the result of the pre-trained filters and weights and biases in action. I can’t stress enough how awesome this is and I encourage the intrepid amongst you to read his <a href="http://scs.ryerson.ca/~aharley/vis/harley_vis_isvc15.pdf">accompanying paper</a> on the topic.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c6X2p0vEe2UlXW9d-OKtVA@2x.png" /><figcaption><strong>Figure 10:</strong> Visualisation of a convolutional neural network for handwritten digit recognition (source by <a href="http://scs.ryerson.ca/~aharley/vis/conv/flat.html">A. W. Harley</a>).</figcaption></figure><h3>Teaching Bernard</h3><p>It should come as sweet relief to you to hear that we are near the end of the tedious lecturing part of this blog and will get started with the tedious coding. You might suspect that this sounds awfully complicated and there’s a hell of a lot of difficult maths to perform and a lot of difficult code to implement. Luckily for us, Tensorflow has come to the rescue and will do the heavy lifting for us. This is completely fine as I’ve shown that when you show off the final product, people will believe that you’ve both read and understood how it works, no matter how laughably untrue that is.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b6556e654330ff4c6388e1f58230aa6a/href">https://medium.com/media/b6556e654330ff4c6388e1f58230aa6a/href</a></iframe><p>First we declare a couple of placeholders, <strong>x</strong> being our input layer of 784 neurons for the 28x28 pixel image. <strong>y</strong> are the 10 neurons for each possible classification, 0 to 9. Next comes our first convolutional layer which will have 32 features each formed using a different 5x5 convolutional filter. That is 32 different image filters we’re training to form the first layer of the network.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3f38c10a0a8039d59e47cb56596eb654/href">https://medium.com/media/3f38c10a0a8039d59e47cb56596eb654/href</a></iframe><p>The <strong>conv2d</strong> function declares a convolutional operator with a stride of 1 nad the zero-padding calculated dynamically so that the output is the same as the input. <strong>max_pool_2x2</strong> declares a basic 2x2 max pooling function, with a stride of 2, but this _will_ reduce the size of the image in the same way as shown in Figure 7. <strong>h_conv1</strong> is the first convolutional layer, formed by convolving the input image, with the weight tensor (that has a depth of 32), adding 32 biases and then applying the ReLU function. That one line has a deceptively large number of maths involved in it. <strong>h_pool1</strong> is the first max-pooling layer, downsampling the image to 14x14 pixels.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/036f99b5c8e12ddd4a82effa3ab78a61/href">https://medium.com/media/036f99b5c8e12ddd4a82effa3ab78a61/href</a></iframe><p>To improve our model, we add a second convolutional layer, this time with 64 5x5 filters. The third dimension of the <strong>w_conv2</strong> tensor is 32 because that is the number of features we have from the previous layer. So all of the features from our first layer are connected to the second. Once again max pooling is applied, downsampling our image to 7x7 pixels.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0991e68486464e0c5d0f9091c161ffde/href">https://medium.com/media/0991e68486464e0c5d0f9091c161ffde/href</a></iframe><p>Then we add a fully connected layer that has 1024 neurons without convolution. Note that the dimensionality is 7x7x64, which is the number of feature maps from the previous layer multiplied by the number of pixels in the image after downsampling. Note that we are still using the ReLU function instead of sigmoid.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c5a4e3fdb045a1ee63e9582782656886/href">https://medium.com/media/c5a4e3fdb045a1ee63e9582782656886/href</a></iframe><p>This part implements the dropout. Note there is a placeholder for the probability of keeping each neuron.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7eb519070c70386827708bd28a900637/href">https://medium.com/media/7eb519070c70386827708bd28a900637/href</a></iframe><p>The last part is a completion layer with 10 possible outcomes, one for each digit.</p><h4>Time For Training</h4><p>Like before, we define a training function that minimises cross entropy and specifies an optimisation mechanism. This time we’re using <a href="https://arxiv.org/pdf/1412.6980v8.pdf">Adaptive Moment Estimation (Adam)</a> instead of gradient descent. I’ve already gone through a lot of theory here, and Adam isn’t conceptually different from gradient descent, it just has some optimisations that make it more computationally efficient and effective. With that in mind, here is the whole <a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/neural_net/digits.py#L124">training function</a>.</p><p>The code might be a lot to stomach, but if you go through line-by-line, it shouldn’t be too different to what we had in the first example. The main thing to note is the <strong>keep_prob</strong> values we are using. When we train the dataset, we want to dropout nodes but we want to include them when we test, that’s the reason it switches between 0.5 and 1.0. Now all we need is a good book, a movie of your choice or some fresh paint you need to watch dry.</p><pre>Step 0, training accuracy 0.02<br>Test accuracy 0.0459259<br>Step 100, training accuracy 0.66<br>Test accuracy 0.72642<br>Step 200, training accuracy 0.8<br>Test accuracy 0.804938<br>Step 300, training accuracy 0.92<br>Test accuracy 0.842469<br>Step 400, training accuracy 0.88<br>Test accuracy 0.871111<br>Step 500, training accuracy 0.94<br>Test accuracy 0.885185<br>Step 600, training accuracy 0.96<br>Test accuracy 0.900494<br>Step 700, training accuracy 0.98<br>Test accuracy 0.907654<br>Step 800, training accuracy 0.98<br>Test accuracy 0.914815<br>Step 900, training accuracy 0.98<br>Test accuracy 0.921975</pre><p>It now looks like he is starting to get the idea after a 1000 iterations, but needs quite a bit more time to get those percentages up. I ran this for many thousands of iterations, running for a few hours before it finished and it spent the whole time billowing steam and whirring like a jet engine. However, when I returned, Bernard had accomplished something quite remarkable. His accuracy for recognising digits in the test set was: <strong>99.8%</strong>. At the level of board recognition, he solved <strong>all but one</strong> (99%). This was far more accurate than anything I had suspected was possible from a cheap pre-fabbed algorithm, 2 weeks after I first started learning about the method, ran on a standard laptop. If you don’t believe me, this model is the one published in the GitHub repo under <a href="https://github.com/mineshpatel1/sudoku-solver/tree/master/data/best-model">data/best-model</a>. I have reason to believe that it should be quite resilient to new, unseen images as well. This included solving some boards that I thought would be way out of scope for this effort because the image quality was so low:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/915/1*61IqXHpa5-wpmQWoDeoZIQ.png" /><figcaption><strong>Figure 11: </strong>Examples of solved images.</figcaption></figure><h3>This is the End</h3><p>And so that brings us to the end of Bernard’s Epic. I’m not sure whether it will be remembered as well and for as long as Homer’s, but only time will tell. What started as some coding practise and a way to sardonically mock perfectly innocent participants of a universally popular pastime, has culminated in the creation of a being fully capable of indulging in the mockery himself. If there’s nothing else you take away from this, series, please take away the idea that this is actually pretty easy — and you can do it too. Bernard was born out of 2 weeks of boredom and access to Google. This really is an indication of how far this field has come and how accessible it is to everyone. I hope my puny contribution to the reams of tutorials and literature on this topic prove useful to at least some of you, and I implore you to go build your own brains to try to outwit Bernard. And if you’re not as sad as me, perhaps this bumbling foray into the world artificial intelligence may give you an idea of what is possible in the world today and in the future.</p><h4>P.S.</h4><p>I apologise again for this final entry being so late (over 2 years since I started this project), I was fairly busy after the aforementioned interview, and this sort of fell off my radar. Someone on Reddit suggested it would be cool if this worked for real-time video, so please accept this feeble example of British-handicraft as a formal apology (<a href="https://github.com/mineshpatel1/sudoku-solver/blob/master/helper/__init__.py#L383">code here</a>):</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FbQW3pDzfVRc%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DbQW3pDzfVRc&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FbQW3pDzfVRc%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/23da629e6368c88fab6c69aa2396b932/href">https://medium.com/media/23da629e6368c88fab6c69aa2396b932/href</a></iframe><h3>Acknowledgements</h3><p><a href="http://yann.lecun.com/">Yann LeCun’s</a> explanation of <a href="http://deeplearning.net/tutorial/lenet.html">LeNet</a> without which none of this could have been possible. The implementation of his theory is basically indistinguishable from magic and for that he must be applauded.</p><p>Ujjwal Karn’s blog: <a href="https://ujjwalkarn.me/2016/08/11/intuitive-explanation-convnets/">An Intuitive Explanation of Convolution Neural Networks</a>. I found this to be a really good explanation that nicely tied together some very good resources.</p><p>Adam W. Harley’s paper: <a href="http://scs.ryerson.ca/~aharley/vis/harley_vis_isvc15.pdf">An Interactive Node-Link Visualization<br>of Convolutional Neural Networks</a> and the hosted <a href="http://scs.ryerson.ca/~aharley/vis/conv/flat.html">visualisation tool</a>. This is just amazing at intuitively demonstrating what’s really going on in this complex process. For those interested, he has also <a href="http://scs.ryerson.ca/~aharley/vis/fc/flat.html">made one</a> for the basic deep network we made last time. Less helpful but perhaps prettier are the <a href="http://scs.ryerson.ca/~aharley/vis/">3D versions</a> that can be found on his site.</p><p>Adit Deshpande’s blog: <a href="https://adeshpande3.github.io/adeshpande3.github.io/A-Beginner&#39;s-Guide-To-Understanding-Convolutional-Neural-Networks/">A Beginner’s Guide To Understanding Convolutional Neural Networks</a>, another well explained resource on the topic.</p><p>Nitish Srivastava et al. and their paper: <a href="https://www.cs.toronto.edu/~hinton/absps/JMLRdropout.pdf">Dropout: A Simple Way to Prevent Neural Networks from<br>Overfitting</a> for a thorough analysis and explanation of the dropout technique.</p><p>Diedrik Kingma and Jimmy Lei Ba: <a href="https://arxiv.org/pdf/1412.6980v8.pdf">Adam: A Method for Stochastic Optimisation</a> introduces and thoroughly explains this enhanced alternative to gradient descent optimisation.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7b4813bc7aa2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Sudoku: Part III]]></title>
            <link>https://medium.com/@neshpatel/solving-sudoku-part-iii-3182fe747883?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/3182fe747883</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Fri, 03 Nov 2017 14:37:00 GMT</pubDate>
            <atom:updated>2018-01-15T09:12:38.621Z</atom:updated>
            <content:encoded><![CDATA[<p>If you are not yet familiar with the renowned puzzle solver Bernard, I highly recommend familiarising yourself with the <a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">first</a> and <a href="https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2">second</a> chapters of his epic tale. In those episodes we got to a point where he could look at a photograph and understand where the grid is and where each of the digits are. However that’s still not good enough as Bernard just sees a set of oddly shaped blobs, at this point he doesn’t even know that there are any significant differences between them. We need to teach him numbers and to do that, we must give him a brain.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GeL1W4cPUEmV6IiSo5g7fw.png" /><figcaption>Figure 1: Original image, with the extracted grid and our current, nonexistent, interpretation.</figcaption></figure><p>The task is pretty daunting compared to our previous efforts. Looking at the image above, it is very clear to a human what the numbers should be but for each number even within this one image there are subtle differences between digits of the same type. Edges may be slightly rougher, segments of the numbers may be slightly cut off. Also this is just a single image, imagine if we were trying this on other photos. Our work on the extraction method has compensated for size and contrast quite well, but there will be images with different fonts, blurriness and a seemingly endless host of other subtle variations humans will never notice when looking at the photo. It’s true that we could use relatively simple <a href="https://jeremykun.com/2012/08/26/k-nearest-neighbors-and-handwritten-digit-classification/">comparison-based techniques</a> to identify this board but we should be far more ambitious and try to build a mind of which <a href="https://en.wikipedia.org/wiki/Frankenstein">Mary Shelley</a> would be proud.</p><blockquote>When in doubt, copy nature. When thoroughly expert in a subject, copy nature better.</blockquote><blockquote>— Any engineer, ever</blockquote><p>That’s a motto I thoroughly believe in, particularly with respect to products of evolution. Various non-evolutionary systems in nature are still better than anything humans can conceive, like stars <a href="https://en.wikipedia.org/wiki/Stellar_nucleosynthesis">producing energy</a>. The products of evolution perhaps surpass even this, producing the world’s most efficient mechanisms for pretty much anything you can think of. This is why the robots in the Matrix wanted to use humans as <a href="https://www.youtube.com/watch?v=IojqOMWTgv8">efficient batteries</a>. Perhaps though, those robots were foolish and instead of using humans as batteries, should have considered using us as processors.</p><blockquote>The brain is the most complex thing in the universe.</blockquote><blockquote>— Anyone who has studied the brain, ever</blockquote><p>It’s pretty <a href="https://www.google.co.uk/search?q=most+complex+thing+in+the+universe&amp;oq=most+complex+thing+in+the+universe">well recognised</a> that the human brain is the most sophisticated system in the currently known universe. It is capable of an incredible range of <a href="https://en.wikipedia.org/wiki/Special_relativity">thought</a>, <a href="http://images.mentalfloss.com/sites/default/files/clocks.png?resize=1100x740">creativity</a>, <a href="https://en.wikipedia.org/wiki/Chichen_Itza">wonder</a> and of course, <a href="https://www.youtube.com/watch?v=JaZvsQIp8dk">stupidity</a>.</p><h3>Understanding The Most Complex Thing In The Universe</h3><p>Inside the brain are <a href="https://en.wikipedia.org/wiki/Neuron">neurons</a>, cellular structures responsible for electrically communicating information and generally the more complex the brain, the more neurons it contains. I say generally, because the African Elephant has approximately <a href="https://en.wikipedia.org/wiki/List_of_animals_by_number_of_neurons">3 times</a> as many neurons as do humans, but have won fewer than approximately 3 times as many Nobel prizes. Very simply, a neuron takes synaptic input and produces a synaptic output, analogous to a function in computing. Then these neurons are interconnected to form a hugely <a href="https://www.newscientist.com/article/mg22229633-300-first-in-depth-mammal-brain-map-to-reveal-neural-blips/">complex network</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*z1RagojUXmyOyknzO_EbyA.jpeg" /><figcaption>Figure 2: Neural network map of a mouse brain. Image from Allen Institute for Brain Science.</figcaption></figure><p>Above is a map of a mouse brain, with around 71 million neurons interconnected. The human brain has approximately 86 <strong>billion</strong> neurons, all different, all interconnected. Cue stunned silence and gasping.</p><h3>Building Frankenstein’s Monster</h3><p>If we thought what we’re doing before was daunting, surely now people are running for the door. But fret not, we are going to start simple. Bernard isn’t going to need a brain powerful enough to paint a masterpiece on the ceiling of the Sistine Chapel, he just needs to learn the digits, 1–9. As such we don’t need a proper brain, just a crappy, loose approximation. Furthermore, <a href="https://en.wikipedia.org/wiki/Donald_O._Hebb">someone</a> vastly more intelligent than I, theorised how to approach the mathematics of interconnected neurons way back in the <a href="https://books.google.co.uk/books?id=ddB4AgAAQBAJ&amp;redir_esc=y">40s</a> and the resulting computer program became known as a <strong>neural network</strong>. Since then advancements have been made consistently in the field and we’re now at a point that we can make fairly impressive stuff for ourselves using our laptops.</p><p>A neural network program consists of layers of neurons, where each neuron is an object that holds a number between 0 and 1 called its <strong>activation</strong>. The output activations of each layer serves as part of the input for the neurons in the next layer and so on until we reach the output.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/762/1*VBkOCdMJmBfDOMLCZBQrnA.png" /><figcaption>Figure 3: Structure of a standard deep neural network.</figcaption></figure><p>In the image above, the first layer of neurons is the input layer, providing the stimulus for the network. The final layer is the output layer, with a neuron for each possible outcome that can be achieved. The hidden layers are where the intelligence lies. The theory is that these hidden layers will pick up on different features in the input and the combination of these features will indicate the right output. For example, the number 9 could be represented as a loop near the top and a vertical line and then a loop could be represented by 4 curves all placed adjacently. The idea is then that different stimuli in the input layer will cause different activations in each subsequent layer and eventually activate the correct neuron in the output layer.</p><p>Each connection between the neurons has a <strong>weight</strong> associated with it, which is a number that can be positive or negative, set arbitrarily to begin with. The activation of a neuron is a weighted sum of all of the activations of connected neurons in the previous layer. We also want a threshold below which the neuron is inactive, we can do this by just subtracting a term which we call the <strong>bias</strong>. Then the activation of each neuron is part of the input for each neuron in the next layer. This passing of information sequentially through layers is called <a href="https://en.wikipedia.org/wiki/Feedforward_neural_network"><strong>feedforward</strong></a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*52L6hPwZnn0UaJn9sR1mMw.png" /><figcaption>Equation 1: Weights and bias for a given neuron, where <em>w</em> is the weight and <em>a</em> is the activation for a neuron in the previous layer. <em>b</em> is the bias for the activation.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/422/1*0lcPXO0g_veU1i6KOyAPig.png" /><figcaption>Figure 4: Weights chosen to specifically pick out a vertical line. Green represents positive weights, red negative, otherwise 0.</figcaption></figure><p>The image above shows an example of what the weights of a neuron in the second layer could look like, accepting the input from the first layer if it were specially configured to find a vertical line in the centre of the image. If we take the weighted sum of all of the activations, it will be highest when there are white pixels in that area with black pixels on either side. You can see then how the weighted sum would be lower for 2 than it is for 1. In reality we won’t be setting these weights or biases ourselves, the network will learn the values itself and the results won’t be anywhere near as neat and tidy as what is shown above.</p><p>At the moment, the sum of weights and biases can be any number, but it is typical to apply a function to the weights and bias to constrain their values between 0 and 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*MugeP57SIbYzyVC9-jENxg.png" /><figcaption>Figure 5: Plot and formula of the <a href="https://en.wikipedia.org/wiki/Sigmoid_function">sigmoid</a> function.</figcaption></figure><p>This activation function changes the way the neuron behaves and in particular, how it learns: for example the sigmoid function will mean neurons learn slowest when the weights are at the extremes. This gives our activation function as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/191/1*Eo5OMRe9JpVEIhrDcM7ZDg.png" /><figcaption>Equation 2: Activation function of a neuron <em>i</em>, where <em>j</em> indicates the connected neuron of the previous layer.</figcaption></figure><p>For our example of digit recognition, our input is a 28x28 square grayscale image. We can model that as an layer of 784 (28 x 28) neurons, where each pixel intensity (normalised between 0 and 1) is the activation. Then the output layer should have 10 neurons, one for each classification 1–9, and an extra one for 0 (blank). Then we will use one hidden layers in between with 16 neurons, an arbitrary choice but sufficient for the example we are trying to solve.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/704/1*eo02l0sreU33ek9Y082gHw.png" /><figcaption>Figure 6: Diagram of the neural network we’ll build for digit classification.</figcaption></figure><p>Even in this small and simple network we have 810 (784 + 16 + 10) neurons with 12704 ((784 * 16) + (16 * 10)) weights and 26 (16 + 10) biases. Imagine a huge machine with 12730 knobs and dials on it, whereby tweaking each knob even slightly might completely change the result in ways you can’t immediately predict and we have something approximating our network. Trying to adjust these manually would be almost as torturous as completing the Sudoku yourself. Thankfully, like the brain, this network structure supports the ability learn.</p><h3>How Does It Learn?</h3><p>When teaching people, it is often helpful to show examples of the correct solutions and the same applies here. Ultimately we will be showing the network a set of pre-classified images, essentially saying “this is a 1, this a 2…” and hoping that the network will learn the weights and biases it needs for each neuron in order to correctly classify new images. The key to doing this is establishing some criteria by which the network can assess its success. This is done in the form a <strong>cost function</strong> which constitutes some numerical representation of the difference between the actual values and the predicted ones. A commonly used cost function is <a href="http://neuralnetworksanddeeplearning.com/chap3.html#introducing_the_cross-entropy_cost_function">cross entropy</a>, given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*qC8YeJ4ot58SoZzzw_CkPA.png" /><figcaption>Equation 3: Cross entropy cost function averaging over <em>n</em> training samples denoted by <em>x</em>. <em>y</em> is the predicted value and <em>y-bar</em> is the true value.</figcaption></figure><p>This function is higher the further away from the truth we are. As such, we want to adjust the weights and biases in such a way as to minimise this function. If you’ve done A-level maths, you should be chomping at the bit to use <a href="http://www.themathpage.com/acalc/max.htm">calculus</a> to find minima and maxima. However, unless you’re a Fields medal winner with a super computer in your head, it’s extremely unlikely you would be able to analytically minimise a function with over 12,000 parameters.</p><p>Instead, we use an approximation called <a href="https://en.wikipedia.org/wiki/Gradient_descent"><strong>gradient descent</strong></a>. This works by choosing a point in the function at random, calculating the gradient at that point and nudging to the left if it is positive and the right if it is negative. The size of the nudges is known as the <strong>learning rate</strong> and has implications for your network: too high and it will struggle to optimise, too low and it will take too long to learn. Performing this step repeatedly (until the gradient reverses) finds some local minimum in the function. At the end of the day, this is still calculus, so pay attention in school.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/411/1*2hQSmkwp6YC2yu4nWQ48qg.png" /><figcaption>Figure 7: Illustration of gradient descent of a polynomial using two random starting values. Notice that they find different minima in the function.</figcaption></figure><p>The classic analogy here is of a ball rolling down a hill but this quickly becomes abstract in our situation which has many inputs and parameters, vastly increasing the input space from the simple example shown above. However, the maths holds up for <a href="https://en.wikipedia.org/wiki/Gradient">multiple variables</a> and so we can implement this method to minimise the cost.</p><p>The de facto implementation of gradient descent (and other optimisation methods) is using <a href="http://neuralnetworksanddeeplearning.com/chap2.html#the_four_fundamental_equations_behind_backpropagation"><strong>backpropagation</strong></a>. This works by first calculating the error in each of the neurons in the output layer, which is a function of the rate of change of the cost function with respect to each output activation. The reason that it is called back propagation is that we can use the errors in the neurons of the output layer to calculate the errors of each neuron in the previous layer and so on, until we reach the start. It is the reverse of what we did earlier when feeding the weights and activations forward through the layers. The maths gets a bit lengthy to explain here, but I’ve provided a few links in this paragraph and in the acknowledgements section for the particularly brave. For the cowardly, treat backpropagation as a system whereby we estimate how much a particular weight (neural connection) affects the overall cost of the network and then shift it accordingly. This is what occurs for a single training run of our network, we simply repeat that over and over with new training data until either it learns to solve the problem, or becomes stuck in a permanent state of familiar ignorance.</p><h3>Enough Talk, Time For Action</h3><p>So that’s the theory, which is all well and good, but time to put it into practice. As before, I’m using Python 3 and am using the <a href="https://www.tensorflow.org/get_started/">TensorFlow</a> library to do the heavy lifting for the neural network. It can be installed easily with pip or conda and we don&#39;t need to worry about CPU or GPU optimisations for this example, just ignore the warnings when they inevitably pop up. As before, I&#39;ll supply code as gists, and will release the complete GitHub project next time around in the final part. I encourage you to follow along, and hopefully you&#39;ve attempted the last two problems but either way this is once again independent and I will provide training data later if you just want to focus on the network.</p><p>Tensorflow works by first declaring a <a href="https://www.tensorflow.org/programmers_guide/graphs">graph</a> that describes your network and then runs sessions to perform training and prediction. We will be implementing the simple network shown in Figure 6 that has one hidden layer in between the input and output layers. Remember that our input images from the Sudoku grid are 28x28 pixels big (<em>cough</em> <a href="http://yann.lecun.com/exdb/mnist/">MNIST</a> <em>cough</em>) which gives us 784 neurons to play with, one for each pixel intensity in the image.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fa03dd64ea478cade56f3043f3a72824/href">https://medium.com/media/fa03dd64ea478cade56f3043f3a72824/href</a></iframe><p>One thing to notice here is the shape of these objects. <a href="https://en.wikipedia.org/wiki/Tensor">Tensors</a> (from which the library gets its name) are a bit like matrices (but with <a href="https://jmanton.wordpress.com/2011/10/21/tensors-and-matrices/">important differences</a>) in that they have some shape and dimensionality. Our placeholder for x, the input has a shape of [None, 784]. The missing value will be filled in by the number of input images we choose, e.g. 81 for each cell of a Sudoku grid, each with 784 pixel values. The same is true for y_, but the second parameter is 10 as that is the number of possible classifications, 0-9. The shapes of these tensors are important when defining the layers, as we shall see.</p><p>Now we have our input layer, x, we can implement our hidden layer, which is calculated from our activation function and weights and biases from Equation 2.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ed499c465073efb6dd037e8606184830/href">https://medium.com/media/ed499c465073efb6dd037e8606184830/href</a></iframe><p>The weight and bias functions simply declare variables of our desired shape, giving them a small positive value. This prevents them from beginning at 0, which reduces the likelihood that the neuron will get stuck when learning. w_1 is a set of variables mapping between the input layer (784 neurons) and the hidden layer (16 neurons), these are all of the connections between the two layers. Additionally a bias is declared for each neuron. Lastly we implement Equation 2, using TensorFlow implementation for sigmoid (Figure 5). tf.matmul simply means &quot;matrix multiplication&quot;, so this step is very straightforward. Next, we declare the output layer, feeding forward the activations from the hidden layer.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8accdfaa3e1cf310a101e16834073ff1/href">https://medium.com/media/8accdfaa3e1cf310a101e16834073ff1/href</a></iframe><p>The output layer has 10 neurons, one for each possible outcome. w_2 declares all of the weights from the hidden layer to the output layer and b_2 is a bias for each neuron. We’re not using sigmoid here which should look a little strange. Normally, we would want to use a variation of sigmoid called <a href="http://neuralnetworksanddeeplearning.com/chap3.html#softmax"><strong>softmax</strong></a>, which is like a multivariate version of sigmoid: instead of producing a single value between 0 and 1, it produces a probability distribution across all the outcomes that sum to 1. That is 10 numbers of which the highest is our prediction. We are skipping it for this line because Tensorflow has its own implementation as part of the cost function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7bee057dea98671a2c5a32045f9d031b/href">https://medium.com/media/7bee057dea98671a2c5a32045f9d031b/href</a></iframe><p>The cost function uses cross entropy as well as softmax, taking the predefined labels and the predicted values as an input. This is all wrapped in a reduce_mean function which takes the average across all training items. The training step declares a gradient descent optimiser with a learning rate of 0.5 and is set to minimise the cost function. Lastly, some functions are declared to check the accuracy of the system, these just take the most probable predicted digit and compares it with the expected digit. Now, the moment of truth, running the application. No doubt you have run this already, only to find that nothing happened. That’s because Tensorflow works declaratively, we need to initiate a session if we want to execute this network graph we’ve defined.</p><p>More importantly than that, we need some data to train it on. Have no fear, I have Blue Peter’d a dataset for you using Bernard’s image extraction algorithm. The dataset is split into a training set, with all the digits from 28 different Sudoku images, and a test set, which has only the digits from the original image at the top of this page. To use this, you will need to download this <a href="https://gist.github.com/mineshpatel1/c5d161126285970aec471155ecad7196#file-Dataset-py">Dataset</a> class and put it alongside your code in a folder called neural_net, along with a blank __init__.py file.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/142/1*bQs6coGcvrR8wjCoEMeilg.png" /><figcaption>Figure 8: File structure for using the Dataset class.</figcaption></figure><p>I’ve made the dataset I used in this blog <a href="https://github.com/mineshpatel1/sudoku-solver/raw/master/data/public-datasets/digit-basic">public</a> so you can download it and use it along with this guide. The format is a <a href="https://docs.python.org/3/library/pickle.html">pickle</a> which is essentially a file archive of a Python object. The dataset has a test set with all of the digits from the original photo shown at the top of this page, extracted and scaled using the algorithm described in the <a href="https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2">last post</a>. It also has a training set of digits from 28 other photos of Sudoku grids, similarly processed, containing a total of 1135 digits. The Dataset class mainly does some housekeeping on the images so they can be used nicely with TensorFlow. The other thing it provides is a next_batch method which returns a random set of unique images from the training set, we&#39;ll use this to speed up training steps, giving the network all the data at once would be time consuming.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/08410f8f72b67cc569fb0f79518ee6c4/href">https://medium.com/media/08410f8f72b67cc569fb0f79518ee6c4/href</a></iframe><p>Now the moment you’ve all been waiting for, we can run this code and hopefully watch Bernard learning in front of our eyes:</p><pre>Step: 0<br>Training Accuracy: 0.23<br>Step: 100<br>Training Accuracy: 0.96<br>Step: 200<br>Training Accuracy: 1.0<br>Step: 300<br>Training Accuracy: 0.99<br>Step: 400<br>Training Accuracy: 1.0<br><br>Test accuracy: 1.0</pre><p>Success! It only takes a few seconds as we have a very simple network and only a small amount of training data, but we can see how rapid the progress is. Initially the training accuracy is poor, as we would expect it to be as the variables are all randomly initialised. However even after 100 steps, the training accuracy shoots up to 96%. At the end of the training we can see that the network is able to correctly classify the digits from the original image. Since we saved the model, we can restructure the network code so that we can only <a href="https://gist.github.com/mineshpatel1/7b8f9eee3c3a6cbf7c38d2352d1c99c3#file-predict_digits-py">classify new images</a> without training the model further. Tying that in with the <a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">solver</a> and <a href="https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2">grid extractor</a> and we have a complete solution:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/417/1*fGxTaygvh_iPCNKaZIyICQ.png" /><figcaption>Figure 9: Completed Sudoku board, parsed from an image. Overlaying the numbers over the board was done by performing the inverse of the <strong>warpPerspective</strong> function we did when we extracted the grid.</figcaption></figure><h3>So What?</h3><p>So he’s finally done it. Bernard has managed to solve a Sudoku grid from the image alone, but there should be a few questions popping up in your mind. For starters, we only tested Bernard on one image and trained a whole network to solve only this specific problem. If that sounds to you a bit like using Mjölnir to crush a walnut, then you’re absolutely correct. The real test is to see how good Bernard is in general. Over the course of this project I have endured derogatory stares on public transport to build up a test set of 128 photographs of Sudoku boards. I gave them all to Bernard to have a go at solving and he could only get about half right, 58%. This is not because the puzzle was too hard to solve, far from it, but because he was unable to correctly identify the board. Perhaps because the angle was too steep, the lighting was bad, the photo was blurry or it was in a font he didn’t understand or just failing for no reason obvious to a human. This is pretty poor and you might be thinking that this neural network malarkey isn’t worth the paper all those theses were printed on. However I disagree, this guide shows an excruciatingly basic network that is actually based on very old <a href="https://en.wikipedia.org/wiki/Multilayer_perceptron">technology</a>. The field of neural networking has come on <a href="https://www.youtube.com/watch?v=vFr3K2DORc8">leaps and bounds</a> since then but it is difficult to explain the more complex networks without first understanding the basics. Join me next time, for the final part of this series where we use some of these techniques to vastly improve Bernard’s accuracy.</p><h3>Acknowledgements</h3><p><a href="http://www.3blue1brown.com/">3Blue1Brown</a> and especially his video series on <a href="https://www.youtube.com/watch?v=aircAruvnKk">neural networking</a>. At the time of writing, only the first two in the series are out but they are absolutely incredible resources for learning this topic. In fact pretty much everything he has done is fantastic and I urge you take some time to watch some of his videos, you won’t find better explained mathematics anywhere on the net.</p><p>Michael Nielson’s <a href="http://neuralnetworksanddeeplearning.com/">online book</a> on neural networking. This is a fantastic, free resource that explains in detail the mechanics of neural networks and the maths behind it. Highly recommend reading this to anyone trying to learn the subject.</p><p>Andrew Ng’s <a href="https://www.youtube.com/watch?v=0twSSFZN9Mc">lectures</a>, really well explained video series on neural networks.</p><p><a href="https://www.tensorflow.org/">TensorFlow</a>, without those folks I would be forced into making a ham-fisted effort at handcranking the network. Particularly their tutorials <a href="https://www.tensorflow.org/get_started/mnist/beginners">MNIST for Beginners</a> and <a href="https://www.tensorflow.org/get_started/mnist/pros">Deep MNIST for Experts</a> are excellent and wholly relevant to this exercise.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3182fe747883" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Sudoku: Part II]]></title>
            <link>https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/9a7019d196a2</guid>
            <category><![CDATA[opencv]]></category>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[computer-vision]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Fri, 20 Oct 2017 11:21:28 GMT</pubDate>
            <atom:updated>2022-04-18T05:43:41.033Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7">Last time</a> I explained how Bernard was born and how he became smart enough to solve any Sudoku puzzle in the world. A fine achievement for any program, but one that was difficult for Bernard to show off at the various aristocratic parties he has become accustomed to attending since he acquired overnight fame on Medium.</p><p>You see, when guests requested to see a demonstration of his marvellous talent, they would hand him a puzzle from a sheet of newspaper and eagerly await the result, bristling with anticipation. By the time I explained (with as much tact as I could muster) that Bernard was in fact blind and you would need to communicate the board to him as a Python string, the aforementioned guest would be too embarrassed, confused, or simply bored, to continue. This did nothing for Bernard’s self esteem.</p><p>As such, I took up the challenge of teaching Bernard to see so that he might more easily express his talent.</p><p>Like before, I won’t be linking to the GitHub just yet as it contains spoilers for the next part, however I encourage anyone inclined to follow along with the code presented here.</p><h3>What Are We Looking For?</h3><p>Let’s start with a photo of a Sudoku board that we will teach Bernard to understand.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/419/1*W0cgNJ6bFYAvhqBRfEPYYw.jpeg" /><figcaption>Figure 1: Original image of a Sudoku board</figcaption></figure><p>The board is at the centre of the image and it’s really the only bit we’re interested in. The first thing we’ll want to do is separate the wheat from the chaff. The minimum information we need to do that are the four corners of the grid.</p><p>A human would trivially be able to identify the 4 corners of the grid and wouldn’t have to think about how they do it. Since humans are too lazy and stupid, their brains handle this automatically for them. Sadly, this isn’t as easy for our technological troubadour and we will need to get a bit creative.</p><h3>How Computers Can See</h3><p>Programming using images is quite complex and involves quite a lot of non-trivial mathematics. Luckily for us, there is an open source project, <a href="http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_tutorials.html">OpenCV</a>, which has been made especially for these tasks. Luckier still, there are Python bindings for this project which Bernard will understand. Use pip install opencv-python to install the module and its dependencies. The following snippet reads an image from disk:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9c59325050da18331ede2f1805afa0f4/href">https://medium.com/media/9c59325050da18331ede2f1805afa0f4/href</a></iframe><p>If we inspect the type of img we can see that it&#39;s actually a <a href="https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.ndarray.html">Numpy array</a>. <a href="http://www.numpy.org/">Numpy</a> is a Python module optimised for mathematic operations with matrices, and is certainly worth reading up on.</p><p>When we look at the content of img it appears at first glance to be somewhat incomprehensible. However when we use imshow to display the image on the screen it looks fine, so clearly the computer is comprehending it. The structure is actually quite simple: the <a href="https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.ndarray.shape.html">shape</a> of the array is 2-D (according to height and width of the image) and each pixel is represented by a <a href="https://www.tutorialspoint.com/python/python_tuples.htm">tuple</a> of 3 representing the <a href="https://en.wikipedia.org/wiki/RGB_color_model">Blue-Green-Red (BGR)</a> colour channels (it defaults to BGR, not RGB). Each channel is an integer between 0 and 255, so (0, 0, 0) is pure black and (255, 255, 255) is pure white. These are in a list of lists (2-D matrix) where the number of rows is the height of the image and the number of columns the width. If we choose to read the image as greyscale (use cv2.IMREAD_GRAYSCALE), the colour information is lost and each element simply becomes a single integer between 0 and 255, representing the brightness of the pixel.</p><p>Back to the task at hand, we need a method for identifying the grid in the center. We’re going to take advantage of the fact that the Sudoku grid will likely be the largest complete feature in the image, assuming the photographer was competent and not attempting some elaborate and unusually cruel deception. The grid in the middle is the only relevant information in the image, so we want to get the coordinates of the four corners of the grid in order to keep the grid and remove the nonsense.</p><p>There are functions we can use to try to detect the corners in the image, but before doing that we should process the image to improve the reliability of those operations. At the moment the image is mostly grays and each pixel as some grey value between 0 and 255. This is quite noisy for the operations we will perform for corner detection. A way to reduce this is by applying <a href="http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_thresholding/py_thresholding.html#thresholding">binary thresholding</a>. These algorithms reduce an image to pure black and white, based on the contrast. Global thresholding makes the split based on a threshold measured from the entire image, whereas adaptive thresholding calculates a threshold for each pixel in the image based on the mean value of surrounding pixels. This is useful when the contrast is uneven across parts of the image, which is pretty likely given the nature of human photographers.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/57e69ff7c6e216c2a1af4c9f7c8c3a9e/href">https://medium.com/media/57e69ff7c6e216c2a1af4c9f7c8c3a9e/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*abuhbrbQrWWg9SQwayuEhg.png" /><figcaption>Figure 2: Binary and adaptive thresholding outcomes</figcaption></figure><p>We can also <a href="https://docs.opencv.org/3.1.0/d4/d13/tutorial_py_filtering.html">blur</a> the image beforehand to reduce the noise picked up by the thresholding algorithm and <a href="https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_morphological_ops/py_morphological_ops.html#dilation">dilate</a> the image to increase the thickness of the lines. It’s worth doing anything we can to make this as easy as possible for Bernard, he’ll thank us later.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8b5d54b6b8f60dcb0f99dd69751a37a9/href">https://medium.com/media/8b5d54b6b8f60dcb0f99dd69751a37a9/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8VADoClq_MjBGuXovbTP6w.png" /><figcaption>Figure 3: Shows the steps in the preprocessing method</figcaption></figure><p>Compare the adaptive threshold images from Figure 2 and 3 to see the noise reduction when we use blurring: in this case less detail is more. Now we’ve reduced the complexity of the image considerably and have retained the feature of the image we are interested in, the only bit left is to have Bernard pick out the right shape. As the photographer is trying to take a photo of the Sudoku board, we can assume that it is the largest single feature in the image so long as the photographer isn’t an ignoramus.</p><p>Contours are a way of describing the boundaries of a shape that has the exact same intensity. Since we converted to binary tones using thresholding, we can use the <a href="https://docs.opencv.org/3.3.0/d4/d73/tutorial_py_contours_begin.html">findContours</a> (<a href="http://download.xuebalib.com/xuebalib.com.17233.pdf">algorithm</a>) function to detect the contours in the image:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a7e5964787e6cfe6fc80440ab47afb10/href">https://medium.com/media/a7e5964787e6cfe6fc80440ab47afb10/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EXIfNtRwgIVU1HddkTi09w.png" /><figcaption>Figure 4: Contours detected in the image</figcaption></figure><p>We can see from Figure 4 that the contours describe the shapes we need incredibly well and that we only need the external contours to extract the board from the rest of the image. The function <a href="https://docs.opencv.org/trunk/dd/d49/tutorial_py_contour_features.html">cv2.contourArea</a> is handy here as we can use it to easily get the largest feature in the image. We could use the <a href="https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm">Ramer-Douglas-Peucker</a> algorithm to approximate the number of sides of the shape as well as this would allow us to filter for rectangular objects only. However during testing I found that this limitation gave false negatives when folds in the page gave the illusion that the grid had 5 sides instead of 4. As such it was more reliable to do away with that constraint and solely base the grid on the area.</p><p>Finally, getting the four corners of the grid is easy with the following logic:</p><ul><li>Top left point has the smallest x and smallest y coordinate, so minimise x + y.</li><li>Top right point has the largest x and the smallest y coordinate, so maximise x - y.</li><li>Bottom right point has the largest x and the largest y coordinate, so maximise x + y.</li><li>Bottom left point has the smallest x and the largest y coordinate, so minimise x - y.</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b63978ad258dbc8761dbd5e2e7300211/href">https://medium.com/media/b63978ad258dbc8761dbd5e2e7300211/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/419/1*YYD9aaZz0XZkWmuhw3wdIA.png" /><figcaption>Figure 5: Detected corners of the grid</figcaption></figure><p>A roaring success I think, I dare say I couldn’t have done a better job myself. The next step is to cut out the part of the image we need and throw away the garbage. Notice though that the photo was taken at a slight angle, so whilst our points map out a rectangle, it’s not a perfect square. The first solution I tried for this problem was to berate the photographer and repeatedly hit them on the nose with a newspaper until they provided a better photograph. Sadly, the results of this method were highly inconsistent. Serendipitously, OpenCV has a function, <a href="https://docs.opencv.org/3.1.0/da/d6e/tutorial_py_geometric_transformations.html">warpPerspective</a>, that can do exactly what we want. It is an implementation of the perspective transform equation, the non-vector form given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*D1nk3Mi3DiDPwot4mp1gHA@2x.png" /><figcaption>Equation 1: Non-vector perspective transform function</figcaption></figure><p>where <em>X</em>, <em>Y</em>, <em>x</em>, <em>y</em> are the sets of new and old coordinates respectively and the remaining variables are constants that we need to calculate. We can do this by solving multiple parallel equations mapping 4 coordinates from the original image onto the their new locations in the new image. This is easy to do with the four corners of the grid we obtained earlier, we just arrange the points as a square roughly the same size as the original grid. With a bit of elbow grease, this can be rearranged into a <a href="https://wp.optics.arizona.edu/visualopticslab/wp-content/uploads/sites/52/2016/08/Lectures6_7.pdf">matrix-vector product</a> and any brave souls can look to <a href="http://www.robots.ox.ac.uk/~vgg/presentations/bmvc97/criminispaper/node1.html">Criminisi et al.</a> for inspiration if they want to solve this by hand. I’d advise wearing harness and appropriate footwear and officially bear no responsibility for any injuries or fatalities incurred. For Bernard, we can just tell him to use the warpPerspective function and he&#39;ll diligently solve the equation:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/92c0cca3f009073b13ecc0a935b8e9e6/href">https://medium.com/media/92c0cca3f009073b13ecc0a935b8e9e6/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*DgxRX9FxmNx-uuMdRIQ0rA.png" /><figcaption>Figure 6: Grid cropped from the image and warped into a square</figcaption></figure><p>This is looking way better, the amount of irrelevant nonsense left in the image is sufficiently decreased and the warp transformation has made it look like we are viewing the board directly instead of at an angle. The next part is to have Bernard identify the cells from the board. The obvious thing to do would be to divide up the grid into 81 evenly sized squares, since we have already warped it into a square. In this case, it pays to be obvious.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d77e309d99088498f7acb9cdb9603751/href">https://medium.com/media/d77e309d99088498f7acb9cdb9603751/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*9y_AMw90lPygLoImvRLyFw.png" /><figcaption>Figure 7: The estimated grid layout</figcaption></figure><p>Not bad, but not perfect either: a lot of cells have overlapping grid lines and the digits aren’t very well centered. This is all the kind of thing that doesn’t really bother your unconscious brain but to Bernard, trying really hard to understand what he’s seeing, this can be incredibly confusing. It is therefore our moral duty and obligation to simplify it further. Taking advantage of the fact that Sudoku grids are always simple and can only contain single digits in the middle of each box, we can implement a function that finds the largest connected pixel structure found when searching around the centre of each square. This is easier if we use similar pre-processing to when we were looking for the grid corners. If we are fortunate enough to find something, we can pull it out and centre it in a new square of a fixed size, scaling it if we have to.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/11a74f897d44323be13e06ca9fe547e0/href">https://medium.com/media/11a74f897d44323be13e06ca9fe547e0/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IO08QmlxvajFjWbZCoQchA.png" /><figcaption>Figure 8: Extracted digit information with the original image for comparison</figcaption></figure><p>Easy peasy. Well no actually, that wasn’t easy at all, it was absurd amounts of work to get this far and Bernard still can’t even recognise the digits as anything but amorphous blobs. This is the crux of what makes this problem fascinating to me. It was trivial to write a program that could solve any puzzle of any difficulty in less than a second, puzzles that a certain type of a human might spend hours on for just for <em>fun</em>. However we’ve had to use a range of mathematical methods, a huge library of pre-programmed functions and a number of optimisation techniques, simply to be able to unreliably tell where the boxes are and if there’s stuff in them. This dichotomy is evidenced throughout life: catching a ball is <a href="https://www.youtube.com/watch?v=ZK2qS550JXo">easy</a>, explaining precisely how you did it is <a href="http://scienceblogs.com/cognitivedaily/2010/01/07/how-baseball-and-softball-outf/">not</a>.</p><p>Your brain subconsciously performs image recognition for you via a series of neurons in the <a href="https://en.wikipedia.org/wiki/Two-streams_hypothesis">visual ventral stream</a>. It also does it horrendously quickly and vastly more reliably than the hackjob maths we programmed and it is able to do this because the neuron hierarchy is phenomenally complex. When this part of the brain is working properly you don’t notice it at all, but when it doesn’t you might start mistaking <a href="https://www.amazon.co.uk/Man-Mistook-Wife-Picador-Classic/dp/0330523627">hats for wives</a>. Armed with this knowledge, <a href="https://medium.com/@neshpatel/solving-sudoku-part-iii-3182fe747883">next time</a> we’re going to go full Wizard of Oz and try to give Bernard a brain.</p><h3>Acknowledgements</h3><p>The <a href="http://opencv.org/">OpenCV</a> project was vital to this part of the project, a thoroughly excellent set of tools for performing this image processing.</p><p>Utkarsh Sinha’s tutorial on <a href="http://aishack.in/tutorials/sudoku-grabber-opencv-plot/">AI Shack</a> for image processing methods regarding grid detection and digit extraction.</p><p>Cáp Hữu Quân’s <a href="https://caphuuquan.blogspot.co.uk/2017/04/building-simple-sudoku-solver-from.html">blog</a> on solving Sudoku for image processing techniques regarding grid detection.</p><p><a href="https://github.com/eatonk/sudoku-image-solver">eatonk&#39;s project</a> for method ideas and Sudoku images.</p><p><a href="https://github.com/prajwalkr/SnapSudoku">pajwaker&#39;s project</a> for method ideas and Sudoku images.</p><p>Yixin Wang’s <a href="https://web.stanford.edu/class/ee368/Project_Spring_1415/Reports/Wang.pdf">Sudoku Solver paper</a> for cell centering using structuring elements. A clever method that we’re not employing here, but interesting nonetheless.</p><p>A. Criminisi, I. Reid and A. Zimmerman’s online paper <a href="http://www.robots.ox.ac.uk/~vgg/presentations/bmvc97/criminispaper/node1.html">A Plane Measuring Device</a> and the companion lecture, <a href="https://wp.optics.arizona.edu/visualopticslab/wp-content/uploads/sites/52/2016/08/Lectures6_7.pdf">Perspective Transform Estimation</a> from the University of Arizona, for their excellent explanation of perspective transformation.</p><h4>P.S.</h4><p>For the lazy among you who have skipped reading or performing the tutorial yourselves or simply work for Blue Peter, here’s a link to the <a href="https://gist.github.com/mineshpatel1/209038c64c19d5e78e0a878320797631#file-sudoku_cv-py">finished solution</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9a7019d196a2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Sudoku: Part I]]></title>
            <link>https://medium.com/@neshpatel/solving-sudoku-part-i-7c4bb3097aa7?source=rss-2534d1d55457------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c4bb3097aa7</guid>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Nesh Patel]]></dc:creator>
            <pubDate>Fri, 13 Oct 2017 10:04:03 GMT</pubDate>
            <atom:updated>2020-03-28T20:03:22.599Z</atom:updated>
            <content:encoded><![CDATA[<p>A few weeks ago I was in my flat, preparing for a job interview, when the unthinkable happened. The internet went down. After literally seconds of unending tedium, I noticed something on the coffee table. A timeless scroll featured in many-a London household, the Metro. After skimming through three-day old sports news, I arrived at my destination only to find that tragically, the crossword had already been filled in.</p><p>Truly disaster stricken, left with no other choice that didn’t require a noose, I began the <em>Sudoku</em>. After filling in two boxes and realising my deplorable and pathetic state, a thought occurred that would prove to be my salvation. Whilst it may be boring to solve one Sudoku, perhaps it would be interesting to solve <em>any</em> Sudoku. This blog series is about just how interesting that problem was.</p><p>For any readers who enjoy solving meaningless problems as much as me, I encourage you to follow along with the tutorial so you can fix, break and improve upon what I’ve done. I used <a href="https://www.python.org/downloads/">Python 3</a>, specifically <a href="https://anaconda.org/anaconda/python">Anaconda</a>, and recommend <a href="https://www.jetbrains.com/pycharm/">PyCharm</a> as a snazzy, free editor. I’ll assume you’re familiar with Python <a href="https://www.coursera.org/specializations/python">syntax and data structures</a> but will try to explain the rest as best as I can.</p><p>For those readers who have lives, just stick around for the ride, and bear with me if and when it becomes mind-numbing.</p><h3>Rules of the Game</h3><p>Sudoku is a game about putting digits between 1 and 9 into a square, 9x9 grid, subdivided into 9 boxes. Usually there’ll give you some numbers to start with, like so:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/748/1*Cy32Vse5NMyXUAeBsyMTeQ.png" /><figcaption><strong>Figure 1:</strong> Sudoku puzzle</figcaption></figure><p>However we can’t just start putting numbers anywhere we please, lest we induce chaos. This ain’t ‘Nam — there are rules. To complete Sudoku, each <a href="https://en.wikipedia.org/wiki/Glossary_of_Sudoku">row, column and box</a> (call these <strong>units</strong>) must contain all the digits between 1 and 9. Since each unit has 9 spaces, the numbers in each unit must be unique.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/758/1*_vckCnkTzvY8LLyli3lv7w.png" /><figcaption><strong>Figure 2:</strong> Units containing cell B2 and associated peer cells</figcaption></figure><p>Above we can see all of the <strong>peers</strong> for the 8 in the top left box. Note that it is the only 8 amongst its peers. This gives us our first rule:</p><blockquote>The value of a cell cannot be repeated amongst any of its peers.</blockquote><p>All well and good I hear you say, but “how do we solve Sudoku?” (for those instead asking <em>why</em>, see <a href="https://en.wikipedia.org/wiki/Friedrich_Nietzsche#Death_of_God_and_nihilism">Nietzsche</a>). Since a number cannot appear in any of its peer locations, it leads to a simple process of elimination.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/764/1*1qwuTTVbYNW1M7Y4ExEEGQ.png" /><figcaption><strong>Figure 3:</strong> Elimination by peers.</figcaption></figure><p>By confirming the 9, we can then eliminate that from all of its peers and continue in that fashion until we’ve finished the board. Easy, yet time consuming and soul destroying for us fleshy mortals, rather a better job for our robot overlords. The first thing I recommend doing when building a robot overlord, is to give them a name. A friend suggested that my pathetic, tawdry ramblings were fractionally more tolerable if I personified the subject. Whether this is true or in fact furthers my alienation, is a question that remains unanswered. Nevertheless, I dubbed my program <em>Bernard</em>. You may a choose a different name, such as Lyra or Hector, but please do not name your program Lance, that would be unnecessarily cruel.</p><h3>Structuring the Board</h3><p>You and I know that this is a job a computer can do well. The hard part is convincing the computer of that. We need some system to describe the board to the machine in a way it understands and finds easy to work with. We can start by labelling the rows and columns so we can reference each cell easily:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/856/1*yS04TTDIfVCYZfxZaipm1A.png" /><figcaption><strong>Figure 4:</strong> Labelled grid</figcaption></figure><p>It might seem logical to use a 2x2 array as that is what we’re given as humans. However if you think about it, there’s no real reason the board has to be a square, or even that it has rows and columns at all. Those are all visual cues to help humans solve it. Visual cues that a computer without eyes will be insulted by. The important information is that each cell has a number of <em>peers</em> that cannot contain its value and that each <em>unit</em> requires each of the 9 digits. If we were trying to explain this method to a human, it might be useful to have a book from which we could look up the peers for each cell, just as Figure 2 shows all of the peer positions for <strong>B2</strong>. Bernard can’t read books, but he can read <a href="https://docs.python.org/3/tutorial/datastructures.html#dictionaries">Python dictionaries</a>: so we’ll use one of these to provide this lookup. Similarly, we’ll give him a reference list of all the possible units, which he can use later to validate his claims.</p><p>The function below generates these reference objects using some cross products and <a href="http://www.secnetix.de/olli/Python/list_comprehensions.hawk">list comprehension</a>:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/77452eca6903f759e8edc517d0528117/href">https://medium.com/media/77452eca6903f759e8edc517d0528117/href</a></iframe><p>The next thing we need to do is describe the input puzzle to the program in a way it can understand. Once again, the computer doesn’t care about the shape of the board, just as long as we assign the right digits to the right positions. I’m going to define the input as a string describing the board from left to right, top to bottom, with 0 or . used to include blank cells. We can ignore all other characters and build up our dictionary. The below function cleans up the string and uses the <a href="https://docs.python.org/3.3/library/functions.html#zip">zip</a> function to map the values to each coordinate.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/88a767c99b54257504fa6e7af20f745e/href">https://medium.com/media/88a767c99b54257504fa6e7af20f745e/href</a></iframe><p>You can practise parsing the example grid from Figure 1, the string format is in this <a href="https://gist.github.com/mineshpatel1/2c370ebdb0e68eb61686c01f7122ab11#file-puzzles-py">snippet</a>.</p><p>We have the input grid, but the empty cells are not particularly useful as . characters. In implementing our elimination strategy, it is better think of the unknown cells as a list of possibilities, possibilities we can eliminate when we have confirmed a peer. In Figure 3 the elimination is slow, going one by one until we establish the answer. However, we can eliminate 8 possibilities straight away from their associated units for every digit we’re given in the puzzle. Then when we have only one possible digit left for a cell, we can eliminate further. The jargon for this is called <a href="https://en.wikipedia.org/wiki/Constraint_satisfaction"><strong>constraint propagation</strong></a>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/308c4ddeb0617155e92406e72de7d245/href">https://medium.com/media/308c4ddeb0617155e92406e72de7d245/href</a></iframe><p>Note that we’re using strings instead of lists here, which is useful in this case because in Python strings are <a href="https://en.wikipedia.org/wiki/Immutable_object">immutable</a> whereas lists are not. Note also that the grid is a dictionary which <em>is</em> mutable, although it is not problematic in this case. None of this matters for now, but we’ll see later that these choices for data structures come in handy.</p><p>If we run this for our puzzle, it does quite well but doesn’t finish it. We can see the remaining possibilities below (using this handy <a href="https://gist.github.com/mineshpatel1/2c370ebdb0e68eb61686c01f7122ab11#file-display_grid-py">display function</a>):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/732/1*mmDLoFdlSIYXPbksRtUVmA.png" /><figcaption><strong>Figure 5:</strong> Attempted solution for the easy puzzle, using a single constraint</figcaption></figure><p>There are some choices that aren’t immediately clear, but if we take a look at <strong>C4</strong> there’s a clue. In the top-middle box there are no other cells that have 5 as a possibility. Similarly with <strong>C5</strong> there are no other cells with 3 as a possibility. That means we can confirm those values and eliminate further, giving us another rule:</p><blockquote>If a unit has only one possible place for a given digit, it <strong>must</strong> be that digit.</blockquote><p>So we can add that constraint to our eliminate function and see how it performs.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2aeb6b7eb93e788ea12114b6c72d90b9/href">https://medium.com/media/2aeb6b7eb93e788ea12114b6c72d90b9/href</a></iframe><p>With this added knowledge, Bernard can now solve the puzzle:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*syaj7N1ydIiPWRtDBrJFDA.png" /><figcaption><strong>Figure 6:</strong> Completed “easy” Sudoku</figcaption></figure><p>So that was pathetically easy. This is usually the point where some putrid, fusty mortal exclaims:</p><blockquote>Of course it can solve the <em>easy</em> ones, anyone can do that. I’d like to see it try one of those <a href="https://www.theguardian.com/lifeandstyle/2017/sep/23/sudoku-3861-hard">hard ones</a> from the Guardian!</blockquote><p>Bernard can solve that one in mockingly trivial fashion as well, which speaks to the efficacy of this seemingly simple strategy. Although they’re not all that easy, a quick search brought up <a href="http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-puzzle-ever-942299"><em>“the most devious brainteaser ever devised”</em></a>: a Sudoku puzzle by Finnish mathematician Dr. Arto Inkala in 2012. This one is apparently even tougher than the previous two he published in <a href="http://www.sudokuwiki.org/Escargot">2006</a><strong> </strong>and <a href="http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-can-you-242294">2010</a>. I would make some comment about him wasting his time on meaningless endeavours if the irony weren’t so obvious and palpable.</p><pre>puzzle = &quot;&quot;&quot;<br> 8  .  . | .  .  . | .  .  .<br> .  .  3 | 6  .  . | .  .  .<br> .  7  . | .  9  . | 2  .  .<br>---------+---------+---------<br> .  5  . | .  .  7 | .  .  .<br> .  .  . | .  4  5 | 7  .  .<br> .  .  . | 1  .  . | .  3  .<br>---------+---------+---------<br> .  .  1 | .  .  . | .  6  8<br> .  .  8 | 5  .  . | .  1  .<br> .  9  . | .  .  . | 4  .  .<br>&quot;&quot;&quot;<br><br>display_grid(solve_puzzle(puzzle))</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LMqjb4cDOGgT1t539HYGJQ.png" /><figcaption><strong>Figure 7:</strong> Remaining possibilities for cells of the difficult puzzle after one round of constraint satisfaction.</figcaption></figure><p>Now we’re talking. Our simple logic has barely made a dent into this puzzle, with 60 cells still uncertain and many of those with lots of remaining possibilities. When a human is solving a particularly difficult puzzle, they may choose to guess a value and see if the board works out or if it leads to a contradiction. That human may find it difficult to employ this strategy on the puzzle above and still perceive the game to be entertaining, unless they were trapped in a forced labour camp or a Butlins. However, Bernard is not limited by a gnat-like attention span and a penchant for shiny things: he will persevere. It would be cruel of us to send him on a goose chase though, we should first try to minimise the amount of work.</p><p>Looking at the possibilities above, it would make sense to guess either <em>3</em> or <em>9</em> for <strong>H7</strong>. This would maximise our probability of getting the right answer, as its a 50–50 choice. Whereas if we tried to guess <strong>A9</strong>, we’d have a 1/7 chance of picking the right number. As such we should always guess the cell with the <em>fewest</em> remaining possibilities. When we have made a choice, constraint propagation ought to significantly reduce the number possibilities in the remaining cells.</p><p>The last bit we need to build is the guessing function, a means of determining if we made the wrong decision. It stands to reason that if we make the wrong decision and propagate the changes through fully, eventually we will reach a point where we contradict ourselves and we eliminate all possibilities, making a solution impossible. Similarly to our two rules for determining numbers, this can be written as:</p><blockquote>If there are no remaining possibilities for a cell, the board is invalid.</blockquote><blockquote>If there are no possible positions for a digit in a unit, the board is invalid.</blockquote><p>We refactor our code to identify invalid boards based on these rules and then attempt solutions, throwing away bad ones, until we find the right one. This is a <a href="https://en.wikipedia.org/wiki/Brute-force_search">brute force</a> method often referred to as <em>backtracking</em>. However, we have vastly limited the number of choices by using constraint propagation each time.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c75c24f503e19855f347a817fd1e3b95/href">https://medium.com/media/c75c24f503e19855f347a817fd1e3b95/href</a></iframe><p>We return None whenever we detect a contradiction in the eliminate function. That state is then propagated through all of the functions so they all can exit as quickly as possible. The <a href="https://gist.github.com/mineshpatel1/2c370ebdb0e68eb61686c01f7122ab11#file-validate_sudoku-py">validate_sudoku</a> function simply checks if we have completed the puzzle. Note that when we recurse guess_digits (line 72), we use grid.copy(). This is because Python dictionaries are mutable and we are attempting different, contradictory permutations. Earlier when we decided to use immutable strings for the possibilities instead of lists or sets, we are now reaping the benefit as we would require grid.deepcopy() if the possibilities were mutable and that is a slower operation.</p><p>Now we can run this function on the <a href="http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html">“Everest of numerical games”</a> and see how Bernard does:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*JftcdsiQmr1wMcadQEld6g.png" /><figcaption><strong>Figure 8:</strong> Arto Inkala’s 2012 difficult Sudoku completed</figcaption></figure><p>Boom. Completed in roughly 0.04s. If you’re reading this Arto, sorry mate.</p><p>Perhaps then, this algorithm is only good at puzzles designed for humans and there are certain types of puzzle that are resistant to this algorithm. Wikipedia has a page on <a href="https://en.wikipedia.org/wiki/Sudoku_solving_algorithms">Sudoku Algorithms</a> and our hybrid method gets a shout out halfway down the article. In the brute force section they give an example of a Sudoku that is intentionally difficult for pure brute force algorithms, but that one is trivial when applying our two constraints and doesn’t even require any guessing, completing in approximately 0.01s.</p><p>This was the interesting bit to me, that a near-optimal solution for solving Sudoku with a computer is very similar to how a human would naturally approach the problem. Whilst there are <a href="https://www.kristanix.com/sudokuepic/sudoku-solving-techniques.php">many techniques</a> employed to solve Sudoku, following only the simplest two is sufficient to complete most puzzles. For extremely difficult Sudokus we need to employ some brute force methods, but a human might be forced down a similar path in those situations. The computer is mainly adding speed and rigour.</p><p>We now have a robot that can solve any Sudoku, the question is what do we do with it? The misanthrope in me liked the idea of being able to ruin people’s puzzles whilst riding on the tube. However it is impractical to type out one of these puzzles on a laptop. I thought it would be cool if Bernard could “see” and so the <a href="https://medium.com/@neshpatel/solving-sudoku-part-ii-9a7019d196a2">next post</a> in this series is about my efforts to try to give Bernard eyes.</p><h3>Challenge</h3><p>For the keenest among you, I would suggest trying the following puzzle:</p><pre> .  .  . | .  .  6 | .  .  .<br> .  5  9 | .  .  . | .  .  8<br> 2  .  . | .  .  8 | .  .  .<br>---------+---------+---------<br> .  4  5 | .  .  . | .  .  .<br> .  .  3 | .  .  . | .  .  .<br> .  .  6 | .  .  3 | .  5  4<br>---------+---------+---------<br> .  .  . | 3  2  5 | .  .  6<br> .  .  . | .  .  . | .  .  .<br> .  .  . | .  .  . | .  .  .</pre><p>It was discovered by the original creator of the algorithm from this post and it should be really slow against the code I’ve given. See if you can modify the program to solve it in less than 0.1s.</p><h3>Acknowledgements</h3><p>The code and solution I have presented here is inspired by Peter Norvig’s <a href="http://norvig.com/sudoku.html">excellent solution</a> for this problem. I was working on the problem and had a similar method when I came across Peter’s work. It was clear that whilst bearing similarity at its core, Peter’s program was far more efficient and elegant. As such I adopted much of those improvements as I thought it better to espouse the best solution I knew of rather than an inferior one of my design. His remains the best solution to this problem I have seen and was a core motivation for continuing this project further.</p><p>Whilst writing this blog I also came across <a href="https://medium.com/towards-data-science/peter-norvigs-sudoku-solver-25779bb349ce">this article</a> by Naoki Shibuya that explain’s Peter’s code in great detail.</p><h4>P.S.</h4><p>For the lazy among you who have skipped reading or performing the tutorial yourselves or simply work for Blue Peter, here’s a link to the <a href="https://gist.github.com/mineshpatel1/e9cea16a128c723822722b3277ad7cf5#file-sudoku-solver-1-py">finished solution</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c4bb3097aa7" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>