tag:blogger.com,1999:blog-24154932647788997942024-03-14T08:56:22.009+05:30My BlogNumerical Computation, Circuits, Puzzles, Python, Linux.Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-2415493264778899794.post-63158392502230253492012-11-05T21:47:00.001+05:302017-01-13T13:18:15.299+05:30Optical Components of an Optical Mouse (with real photos of mouse internals)<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
The working of an optical mouse can be divided into 2 broad areas -<ol style="text-align: left;">
<li>The OPTICAL part (discussed in this post)</li>
</ol>
<ol style="text-align: left;">
<li>The ELECTRONICS (DIGITAL SIGNAL PROCESSING) part (not discussed in this post)</li>
</ol>
</h3>
<br />
<span style="font-size: large;">This post completely describes the optical aspect of the optical mouse (only). The electronics aspect is not discussed here.</span><br />
<br />
<div style="text-align: left;">
<span style="font-weight: normal;"><u><i><span style="font-size: x-large;"><br /></span></i></u></span></div>
<div style="text-align: left;">
<span style="font-weight: normal;"><u><i><span style="font-size: x-large;">Intended Audience -</span></i></u></span></div>
<div style="text-align: justify;">
This post is intended for those having elementary optics knowledge. If you wish to revise your preliminary optics knowledge, you can go through the <u>beginning</u> of these weblinks - <a href="http://en.wikipedia.org/wiki/Refraction" target="_blank">refraction</a>, <a href="http://en.wikipedia.org/wiki/Total_internal_reflection" target="_blank">total internal reflection</a>, <a href="http://hyperphysics.phy-astr.gsu.edu/hbase/hframe.html" target="_blank">convex lens</a>.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: left;">
<span style="font-weight: normal;"><span style="font-size: x-large;"><i><u>Working of an optical mouse[in brief] -</u></i></span></span><br />
<span style="font-weight: normal;"><span style="text-align: justify;">At the bottom of your mouse, you can see a red light (or sometimes blue or no light, meaning infrared) When you move the mouse, this light strikes the bottom surface on which the mouse is moving, gets reflected back and falls on the another part of the mouse, where a lens collects all the light and focuses it on a sensor with a DSP chip. This chip handles the computational aspect of the mouse working where it decides, depending upon the light falling on it, the direction in which the mouse moved and accordingly sends the signals to the computer. The optical components of the mouse are discussed below in greater detail.</span></span><br />
<span style="font-weight: normal;"><span style="text-align: justify;"><br /></span></span> <span style="font-weight: normal;"><span style="text-align: justify;"><br /></span></span></div>
<div style="text-align: left;">
<span style="font-weight: normal;"><span style="font-size: x-large;"><i><u>Mouse Internals -</u></i></span></span><br />
<span style="font-weight: normal;"><span style="text-align: justify;">The mouse internals have been shown pictorially, for easy understanding.</span></span><br />
<span style="font-weight: normal;"><span style="text-align: justify;"><br /></span></span></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisLGFZ4cf33ikZM1TLdjVok0e0336gTsNfcai9ghBxGjQEUU-qOjlNZBT314p4erirjUzlDzMuwPiBBzH8NX3DPe2QskkYDcA4ZvvJ3a7cgiHBKrp53MIl-dVx8h7-T1dXH5o4oJMxG50W/s1600/mouse-internals-details.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisLGFZ4cf33ikZM1TLdjVok0e0336gTsNfcai9ghBxGjQEUU-qOjlNZBT314p4erirjUzlDzMuwPiBBzH8NX3DPe2QskkYDcA4ZvvJ3a7cgiHBKrp53MIl-dVx8h7-T1dXH5o4oJMxG50W/s1600/mouse-internals-details.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">On removing the top cover of the mouse. Visible components are labelled.</td></tr>
</tbody></table>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwRYfBmlsXUUWeSUWM-Y_3gl_hl7Zb5KfvjK9Aba5n-jrqj1hK6eM4bFCQYH79deFeuKQe4bWdjNx43Fm1i6nXKCVFhiPTRB5MBQP5ufi5L6gDaVRWEpeLcCBP8TFND0iwavMAMLCEySok/s1600/DSC00252.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwRYfBmlsXUUWeSUWM-Y_3gl_hl7Zb5KfvjK9Aba5n-jrqj1hK6eM4bFCQYH79deFeuKQe4bWdjNx43Fm1i6nXKCVFhiPTRB5MBQP5ufi5L6gDaVRWEpeLcCBP8TFND0iwavMAMLCEySok/s1600/DSC00252.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Separating the electrical (top part) and the optical (bottom part) components, with the inverted view of the electrical component. The tiny camera converts light falling on it into electrical signals for further processing.</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhT9U1ULkERl_RddT1hlxYaUX6K6gOikWdQwNJvks3e4Nys3dM_LpEdYpWWlGW5Z9PJfJCc1v8dZcHCOUwMG0SnXVv_ZhegMuHG0JbTvhI9ZEYG5upYQ9R2lN19BlJ3kQd44-y-Y7Fzuxhd/s1600/DSC00249.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto; text-align: right;"><img border="0" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhT9U1ULkERl_RddT1hlxYaUX6K6gOikWdQwNJvks3e4Nys3dM_LpEdYpWWlGW5Z9PJfJCc1v8dZcHCOUwMG0SnXVv_ZhegMuHG0JbTvhI9ZEYG5upYQ9R2lN19BlJ3kQd44-y-Y7Fzuxhd/s640/DSC00249.JPG" width="593" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Separating the electrical (top part) and the optical (bottom part) components. The optical component is just the transparent part, placed on the bottom (orange) support.</td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhofC66P3jjPRzSBNf218voUQRRmpzm-O7XuuqenU_Bm8PZW9TjxfYl7hXZADxJwVO7TgPFcgRWY5QzRt65UgvjPPoFgxvgDgMrF-RQ8NsMUX9qNh8aWQczJJsGSjDHHayZRsqKvdkUFDAZ/s1600/opt-comp.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhofC66P3jjPRzSBNf218voUQRRmpzm-O7XuuqenU_Bm8PZW9TjxfYl7hXZADxJwVO7TgPFcgRWY5QzRt65UgvjPPoFgxvgDgMrF-RQ8NsMUX9qNh8aWQczJJsGSjDHHayZRsqKvdkUFDAZ/s1600/opt-comp.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The system consists of 2 simple optical components. Their side view is shown. </td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjD7ff5OkfmcW2RZ9R0EMQA1pI14tZLKP_G2izhPI1Ej_stQWo3vc98VuCV-i3e28LL5HhR21pGHN7WZonfINsmNWnSxdSKG0fF9B99XXq6hGob3Ta-K3bNL1PAxuHGtmRBSyS0xJN9e-M4/s1600/opt-comp-1.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjD7ff5OkfmcW2RZ9R0EMQA1pI14tZLKP_G2izhPI1Ej_stQWo3vc98VuCV-i3e28LL5HhR21pGHN7WZonfINsmNWnSxdSKG0fF9B99XXq6hGob3Ta-K3bNL1PAxuHGtmRBSyS0xJN9e-M4/s1600/opt-comp-1.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Front view of optical component #1</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
Optical Component #1: The complete blue highlighted part is the light transmitter. (There is a schematic below which can help in visualizing it better). It consists of a half convex lens/part and a long tunnel to carry light rays via TIR (<a href="https://en.wikipedia.org/wiki/Total_internal_reflection#/media/File:TIR_in_PMMA.jpg" target="_blank">Total Internal Reflection</a>). The convex part above is to increase the field of view ie to take in more light without loosing them out due to non TIR ie to the make critical angle effectively smaller </div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlTs53eo-qGflvSxl3oSbIPRLKLjsel_wFOAB2qfR1fANm17CPzKHA2bze74vnM_hpy7LGPmKIPJOykwX2pE1jf6kLerrYx2NpKHYI7_J8ZwMejA0ZmkP3hwrKRER4O0_Yf9UhRJZmQ-iv/s1600/opt-comp-2.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlTs53eo-qGflvSxl3oSbIPRLKLjsel_wFOAB2qfR1fANm17CPzKHA2bze74vnM_hpy7LGPmKIPJOykwX2pE1jf6kLerrYx2NpKHYI7_J8ZwMejA0ZmkP3hwrKRER4O0_Yf9UhRJZmQ-iv/s1600/opt-comp-2.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Top view of optical component #2</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: left;">
Optical Component #2: It is a simple convex lens, for magnifying the contents below it.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The small 42sec video below shows the 2 components from various angles. Note its size, as compared to my fingers.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="text-align: center;">
<iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="https://www.youtube.com/embed/dFK9KM4Tsfg" width="420"></iframe><br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<span style="font-size: x-large;"><i><u>Schematic and working of Optical System -</u></i></span><br />
<div style="text-align: justify;">
<br />
I have shown how the real optical components look like above. Here is a schematic of the same, from the side view -</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjI9RlguVdNzvSoMkTaFy4OhoDhPtHYkx949dipdvH7h8xh4CuujN66Fl7YYKI8SJ3VpnVbf7MHqTD4bTAtFRJgemO5QMl9aisLI1yhyphenhyphensZlkO_9uDJc2HJ1U5Y2ATCLWPucvMRM4KW3pYZd/s1600/Selection_015.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjI9RlguVdNzvSoMkTaFy4OhoDhPtHYkx949dipdvH7h8xh4CuujN66Fl7YYKI8SJ3VpnVbf7MHqTD4bTAtFRJgemO5QMl9aisLI1yhyphenhyphensZlkO_9uDJc2HJ1U5Y2ATCLWPucvMRM4KW3pYZd/s1600/Selection_015.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><br /></td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2U4QSiwWWwYylMWFlawKM4uQtVKgrLo6R5x3CLvvVDNi1nWz-uCxw9HTKVpWPtZv0uh7Bmr_VZ_zgCPpWEbYaw0XZsv7rgLJB4i1vVjKBC8S6QoA5cP3IKqBm2AUeMdi-edWgTEatMAbJ/s1600/Selection_014.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="341" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2U4QSiwWWwYylMWFlawKM4uQtVKgrLo6R5x3CLvvVDNi1nWz-uCxw9HTKVpWPtZv0uh7Bmr_VZ_zgCPpWEbYaw0XZsv7rgLJB4i1vVjKBC8S6QoA5cP3IKqBm2AUeMdi-edWgTEatMAbJ/s640/Selection_014.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Assume points P and U are on a rough surface, hence not getting reflected at same angles.</td></tr>
</tbody></table>
<br />
<br />
<u>Optical Working:</u><br />
Component #1 has 2 subcomponents -<br />
The convex lens of component #1 (bulge), which collects light from a large solid angle and passes it to 2. The transmitter of component #1 (slanted rectangular part), which transmits light received at input to its output using total internal reflection. Component #1 thus illuminates the surface on which the optical mouse is moved.<br />
<br />
Component #2 is a simple convex lens which focuses the illuminated surface below on the camera pin hole above, from .<br />
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<div style="text-align: left;">
<span style="font-size: x-large;"><u><i>Experiment -</i></u></span><br />
I performed a simple experiment to understand (and verify) the working of the optical component. The aim was to try to read, using the optical component, the alphabets "A B C D E F G H" written on the paper in a small font. (See pic below).<br />
<br /></div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5y692Z1Qq9C8o347gIDIYV6tvZ7Q-WOF37iesalDQdft1ZZQZxrbTGA436hz2CKecIvJR17Q3tMWT_XJtiZqOIY147OGjj_6uTO_0GiiB2otXFvNIzjlYxeU_HKyEnt5Sfyerqu7XKJbi/s1600/DSC00285.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5y692Z1Qq9C8o347gIDIYV6tvZ7Q-WOF37iesalDQdft1ZZQZxrbTGA436hz2CKecIvJR17Q3tMWT_XJtiZqOIY147OGjj_6uTO_0GiiB2otXFvNIzjlYxeU_HKyEnt5Sfyerqu7XKJbi/s1600/DSC00285.JPG" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The (transparent) optical system (along with its orange support) is moved on the paper which has handwritten letters "A B C D E F G H", just like we move the mouse on a plain surface.</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="https://www.youtube.com/embed/IOUiyLJuj4c" width="420"></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<u><i><span style="font-size: x-large;"><br /></span></i></u></div>
<div class="separator" style="clear: both; text-align: left;">
<u><i><span style="font-size: x-large;">Observation & Conclusion -</span></i></u></div>
<div class="separator" style="clear: both; text-align: justify;">
<u>Observation: </u>After illumination and magnification, the letters could easily be read using the optical component.</div>
<u>Conclusion: </u>The optical aspect involved in an optical mouse is theoretically quite simple.<br />
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
<u>The aftermath:</u></div>
<div class="separator" style="clear: both; text-align: justify;">
The DSP takes successive photos of the surface below & using the difference in successive images, figures out the direction in which the mouse moved. More information can be found on <a href="https://en.wikipedia.org/wiki/Optical_mouse" target="_blank">Wikipedia</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
--------------------------------------------------------------------------------------------------------------------------</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
In one of my advanced optics course (EPL445) at IITD, we were asked to give a small presentation on some optical system, stressing on the optical aspect of it. While most students gave presentations on complex optical systems, none were a complete explanation since they were too complex to be clearly explained in a short duration of 30 minutes. So, I decided to present on this topic (which was actually very simple considering the level of the course) in the interest of time. </div>
</div>
Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com1IIT Delhi, Indian Institute of Technology Delhi, IIT Campus, New Delhi, Delhi 110016, India28.545568 77.195434999999975-25.325040500000004 -5.0701900000000251 82.4161765 159.46105999999997tag:blogger.com,1999:blog-2415493264778899794.post-44135180854502659702012-01-01T16:05:00.002+05:302014-01-06T00:25:44.773+05:30Simple calculator display logic circuit (made using logisim)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: justify;">
The circuit consists of a 12 digit decimal display where you can insert numbers by pressing <i style="text-align: left;">buttons 0-9</i><span class="Apple-style-span" style="text-align: left;">, clear a recent number using the </span><i style="text-align: left;">backspace</i><span class="Apple-style-span" style="text-align: left;"> button or clear all digits using the </span><i style="text-align: left;">clear all</i><span class="Apple-style-span" style="text-align: left;"> button, </span><u style="text-align: left;">just like we observe on a handheld calculator device</u><span class="Apple-style-span" style="text-align: left;">. I have explained how I made the logic circuit in this post.</span></div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
Below is a video of how the <i>logisim</i> circuit looks like and how it works. (Alternatively, a high quality picture (~24 megapixels) of the complete circuit together can be found <a href="http://www.freeimagehosting.net/503bb" target="_blank">here</a>.) You can also try running/simulating the circuit in <i>logisim</i> yourself by downloading the <i>logisim circuit</i> file <a href="http://www.mediafire.com/?zqy157ls4ji5e1t" target="_blank">here</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div style="text-align: center;">
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/whR4FKiDIHE?feature=player_embedded' frameborder='0'></iframe></div>
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><u><i>Intended Audience -</i></u></span></div>
<div class="separator" style="clear: both; text-align: justify;">
This post is intended for those having elementary digital electronics knowledge (mainly logic gates and flip-flops). Prior knowledge of <a href="http://ozark.hendrix.edu/~burch/logisim/" target="_blank">logisim</a> software will be useful. (If you are new to logisim, you can find some tutorials <a href="http://ozark.hendrix.edu/~burch/logisim/docs/2.3.0/guide/index.html" target="_blank">here</a>. It is very easy to understand.)</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This is a simple, non-timed circuit and hence it is not necessary to program this on verilog/VHDL. Also, note that this might not be the way how the circuit is implemented practically on devices like handheld calculators, mobile phones, etc. But, this circuit will surely work if implemented.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<span class="Apple-style-span" style="font-size: large;"><u><i>Calculator Display -</i></u></span></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
The display part of the circuit looks as shown below. You can interact with the buttons (only).<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimMHEQ50Ka6MfniGrT3e2eE_5Se3yyzoFsg2qZkupSoIbSfId7FyAHUo_UTliSLX3fDZcW4sBI53sBbHBupzdw0G-fj6PEdYUJBdjb0BDAsleX3fOq14JcACcNw6tpPj7MGF84RIlx-bMj/s1600/the+display.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="221" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimMHEQ50Ka6MfniGrT3e2eE_5Se3yyzoFsg2qZkupSoIbSfId7FyAHUo_UTliSLX3fDZcW4sBI53sBbHBupzdw0G-fj6PEdYUJBdjb0BDAsleX3fOq14JcACcNw6tpPj7MGF84RIlx-bMj/s1600/the+display.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Note the labels <i>0,1, ..., 11, n0,n1, ..., n11, Clear All, Backspace</i>. <br />
They will be used <u>throughout</u> the post for discussing the circuit.<br />
[In <i>logisim</i>, they are the <i>Tunnel</i> elements, part of the <i>Wiring library]</i></td></tr>
</tbody></table>
<br />
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<i><span class="Apple-style-span" style="font-size: large;">The circuit consists of 3 important subcircuits - </span></i></div>
<div class="separator" style="clear: both; text-align: left;">
<i><br />
</i></div>
<div class="separator" style="clear: both; text-align: left;">
<span class="Apple-style-span" style="font-size: large;">1. <i><u>Taking input from buttons</u></i> -</span></div>
<div class="separator" style="clear: both; text-align: justify;">
We need to store the value of the button when it is pressed. <u>Note that pressing a button means logical 1 for a moment only; the button is not held continuously at logical 1 position.</u></div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
Directly understanding the circuit required for taking <u>decimal input</u> can be a bit confusing. Hence, it would be better to first understand the basic circuit required for taking a <u>boolean input</u> from the circuit below -</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgo5pOWfkrB6ezN1AhncywWcdBDT2ywrF8mHFobNldhBnBkXFyt1CDNhyphenhyphenSAIvLOKKYClMsJ__eKVVjunLoMu9XKfnuW2knwtekilBXa5ZjLjSlD0nheqAoaD1I6JipbPld12CM-2pAg44Ck/s1600/binary+input+from+buttons.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="150" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgo5pOWfkrB6ezN1AhncywWcdBDT2ywrF8mHFobNldhBnBkXFyt1CDNhyphenhyphenSAIvLOKKYClMsJ__eKVVjunLoMu9XKfnuW2knwtekilBXa5ZjLjSlD0nheqAoaD1I6JipbPld12CM-2pAg44Ck/s320/binary+input+from+buttons.gif" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Since we have a decimal display and not a boolean display, we won't use this circuit as it is.<span class="Apple-style-span" style="font-size: small;"> </span></td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
I have used the BCD representation (ie 0 -> 0000, 1 -> 0001, 2 -> 0010, ..., 8 -> 1000, 9 -> 1001) and so four bits are required to store one decimal value. So, we will require 4 similar subcircuits with slight modifications. Also, the output of each of these circuits will be connected to 12 bit shift registers, which corresponds to the display part of the circuit.<span class="Apple-style-span" style="text-align: left;"> </span>(This is discussed in the later part <i>"Bringing together the subcircuits".</i>) The shift registers are discussed next.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<span class="Apple-style-span" style="font-size: large;">2. <u style="font-style: italic;">Shifting the input</u><span style="font-style: italic;"> -</span> </span></div>
<div class="separator" style="clear: both; text-align: justify;">
As <i>buttons 0-9</i> are pressed, existing input should shift to accomodate new digits. Similarly, when <i>backspace</i> is pressed, the newest digit should be discarded and the entire remaining input should shift back one place. Thus, input needs to be shifted in both left and right directions.</div>
<div class="separator" style="clear: both; text-align: justify;">
Thus, we need a <i>left right shift register</i>. Since, our display is 12 digits wide, our left right shift registers should be 12 bits wide and we would need 4 such shift registers (for the BCD representation).</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
This is the circuit of a classic <i>4 bit left right shift register</i> (rem. we need "12" bit shift registers) -</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZ0Lu5I-1293CbBMG3YHyZBwjlw6e-_r1qxGjitk7VgkwF5NuJ5Ouxkx6Yl2gflWN591dXGij2WDB-svqzNp9OcYI6f87RpxTK2KR4YSEJamWzRypwKV4mEbaFsBWNRDfhP39wTgcJ2Kyr/s1600/4+bit+left+right+shift+register.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="121" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZ0Lu5I-1293CbBMG3YHyZBwjlw6e-_r1qxGjitk7VgkwF5NuJ5Ouxkx6Yl2gflWN591dXGij2WDB-svqzNp9OcYI6f87RpxTK2KR4YSEJamWzRypwKV4mEbaFsBWNRDfhP39wTgcJ2Kyr/s400/4+bit+left+right+shift+register.gif" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">4 bit left right shift register (click to view full size image)</td></tr>
</tbody></table>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4McBg2KYxZ1rX0GtRJyws-fwq-IYGL5kp_CtvBt-4vvy_dCUvzyS1STV__oS0Xu6cHaeBCHIbG51TyypSReJre50c7j3xsTemUppaBpNVKbk6Ybb6-0FfpYU-ZKXRg1IH4cb7qc-2CRaO/s1600/Symbol+4+bit+left+right+shift+register.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="138" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4McBg2KYxZ1rX0GtRJyws-fwq-IYGL5kp_CtvBt-4vvy_dCUvzyS1STV__oS0Xu6cHaeBCHIbG51TyypSReJre50c7j3xsTemUppaBpNVKbk6Ybb6-0FfpYU-ZKXRg1IH4cb7qc-2CRaO/s200/Symbol+4+bit+left+right+shift+register.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px;">Symbol for 4 bit l/r shift reg. subcircuit<br />
(It is used in the <u>next</u> subcircuit below)</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Using 3 such 4 bit shift registers, we can make a 12 bit shift register as shown in the below circuit.<br />
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdmpB78CfctVN28xRpaGmwVnbVtIUdOrhzgcRgwGquZIxEzeVHXWmvEAF0eAcy0nnr4sgJiHE40JfEzYoFyAyhur70oBDO9CAUgAeR-0sctdf9P9MB3ySlAsmdvyb1t7Hj93R5SQDdFcUq/s1600/12+bit+left+right+shift+register.gif" imageanchor="1" style="margin-left: auto; margin-right: auto; text-align: center;"><img border="0" height="184" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdmpB78CfctVN28xRpaGmwVnbVtIUdOrhzgcRgwGquZIxEzeVHXWmvEAF0eAcy0nnr4sgJiHE40JfEzYoFyAyhur70oBDO9CAUgAeR-0sctdf9P9MB3ySlAsmdvyb1t7Hj93R5SQDdFcUq/s320/12+bit+left+right+shift+register.gif" width="320" /></a> </td></tr>
<tr><td class="tr-caption" style="text-align: center;"><div style="text-align: left;">
<div style="text-align: center;">
12 bit left right shift register (click to view full size image)</div>
</div>
</td></tr>
</tbody></table>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td> <a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiN-pNBjZQfmG-5fQPeyq7dVPqSYK2oXcOVIhjcT978d5tGgmhssb1iX3H7xRmapZ4R-vXCRUj98AIielWZ8Hx1cPujsYcpBFeVbLV42EW5kthAhMgu9wtu2rfwIIOnpyGbLjg8Srk35C3j/s1600/Symbol+12+bit+register.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="113" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiN-pNBjZQfmG-5fQPeyq7dVPqSYK2oXcOVIhjcT978d5tGgmhssb1iX3H7xRmapZ4R-vXCRUj98AIielWZ8Hx1cPujsYcpBFeVbLV42EW5kthAhMgu9wtu2rfwIIOnpyGbLjg8Srk35C3j/s200/Symbol+12+bit+register.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px;">Symbol for 12 bit l/r shift reg. subcircuit<br />
(It is used in a subcircuit below)</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: center;">
<br /></div>
<div style="text-align: justify;">
Note that, in the above circuit, I have kept the value of <i>Data in left shift</i> as 0 because when <i>backspace</i> is pressed, we wish to insert 0's from the other end (the most significant digit's end). Also, we don't need the <i>Data out Left Shift</i>, as it is to be discarded! And <i>Data out Right Shift</i> won't be required, as the circuit is designed such that one cannot push in more digits once the display is full, so no data will ever come out on right shifting at any point of time.</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both; text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><span style="font-style: italic;">3. </span><u style="font-style: italic;">The clock</u><span style="font-style: italic;"> - </span></span></div>
<div class="separator" style="clear: both; text-align: justify;">
The clock is an essential part of any digital circuit which has memory. In this case the clock would be controlled by the buttons. When a button is pressed and held, it goes from logical 0 to logical 1 state and when it is released it goes from logical 1 to logical 0 state. These can be used as the rising and the falling edges of the clock respectively.</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTA8H2hl9nfS-HuRLfIgzl4SuWlsTbbibV8U6J0BxlHNC8pehiG4TzYu7pk9yaK_d85pss6Hd6pCri7u0yombhpbqGg1ajUvebK6sPCctRBCq0O653Gjgfs3mO92es29rn54a9HWlu1HWj/s1600/clock.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="185" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTA8H2hl9nfS-HuRLfIgzl4SuWlsTbbibV8U6J0BxlHNC8pehiG4TzYu7pk9yaK_d85pss6Hd6pCri7u0yombhpbqGg1ajUvebK6sPCctRBCq0O653Gjgfs3mO92es29rn54a9HWlu1HWj/s400/clock.png" width="400" /></a></td></tr>
<tr><td class="tr-caption"><span class="Apple-style-span" style="font-size: xx-small;">(Note: The label of the 12th bit is "11" because I have numbered the display bits starting from 0.)</span><br />
<span class="Apple-style-span" style="font-size: x-small;">(click to view full size image)</span></td></tr>
</tbody></table>
<br />
<div class="separator" style="clear: both; text-align: justify;">
When the display is full (ie the most significant digit, the 12th digit, is non-zero), we need to make sure that pressing <i>buttons 0-9</i> should not bring in any more digits as there is no space left (just like it happens on a handheld calculator). Hence, we need an additional small OR gate (at the bottom of the above circuit). Note that <i>backspace button</i> should work no matter the display is full or not and hence it is directly connected to the clock. The backspace button also controls the LEFT_RIGHT parameter of the left-right shift registers. </div>
<div class="separator" style="clear: both; text-align: justify;">
Also, note that <i>clear all</i> means reseting all digits to 0 <i><u>asynchronously</u></i>. Hence, the <i>clear all button</i> does not come into picture here (ie it does not control the clock).</div>
<br />
<br />
<div class="separator" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both;">
<i><span class="Apple-style-span" style="font-size: large;">Bringing together the subcircuits -</span></i></div>
<div class="separator" style="clear: both;">
<i><br />
</i></div>
<div class="separator" style="clear: both; text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>1. Connecting the input taking circuit to the shift registers-</u></i></span></div>
<div class="separator" style="clear: both; text-align: justify;">
This is the most important part of the circuit. To store upto 12 digits, we need to connect the input taking subcircuit with the 12 bit shift registers. (We would need 4 such connections as shown below.) The most important trick here is to make the <i><u>T flip flop</u></i> <u>rising clock edge</u> triggered and <i><u>shift registers</u></i> <u>falling clock edge</u> triggered, otherwise the circuit won't work! (It took quite a lot of time for me to get this trick. Infact, I went on vacations before completing this circuit as I was stuck at this point for a long time!)</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyZXSJ-e783WVG4Dyl35dytfe5ziP9tQnMpF9CAR4POFlP79_5ODY-d0Q-Ba7vBTGMcToiDd8VgHDj2ff7HzV0PciSKFZZ7oCLzihgTicqiklBPrbXIfoVIuryKDpCZvn7lPWtyE16Ovun/s1600/Taking+Inputs.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyZXSJ-e783WVG4Dyl35dytfe5ziP9tQnMpF9CAR4POFlP79_5ODY-d0Q-Ba7vBTGMcToiDd8VgHDj2ff7HzV0PciSKFZZ7oCLzihgTicqiklBPrbXIfoVIuryKDpCZvn7lPWtyE16Ovun/s640/Taking+Inputs.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Labels <i>bit0, bit1, bit2, bit3</i> correspond to the contents of the shift registers.</td></tr>
</tbody></table>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>2. Making the display - </u></i></span></div>
<div class="separator" style="clear: both; text-align: justify;">
There is nothing intelligent in this part. From the above subcircuit, we need to pull off 4 bits, 1 at a time from each shift register's contents (to make 1 unit of the 12 digit display), 12 times. If you don't understand this part, you can just ignore it here and try understanding it yourself by downloading the logisim circuit file (<a href="http://www.mediafire.com/?zqy157ls4ji5e1t" target="_blank">here</a>) and playing with the circuit elements.</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhV8wD9AGjszbLDFYn85VXAaru4391wZtLnPZPItqfTuG33S8qeTAL5kWPMmLB1tfN03oqEGKiXHvEfXM4rI5PO3gGR5FQvdCSU4xFByvCFDfj_EVwMe7MAg3pFLi66flojxldjvTrnhozw/s1600/making+the+display.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhV8wD9AGjszbLDFYn85VXAaru4391wZtLnPZPItqfTuG33S8qeTAL5kWPMmLB1tfN03oqEGKiXHvEfXM4rI5PO3gGR5FQvdCSU4xFByvCFDfj_EVwMe7MAg3pFLi66flojxldjvTrnhozw/s400/making+the+display.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The labels <i>0,1,2, ..., 11</i> correspond to the 12 units of the display.<br />
You must have seen these labels in the first picture in this post above.</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
The subcircuit for the <i>clock</i> is to be kept as it is.</div>
<div class="separator" style="clear: both; text-align: justify;">
A high quality picture (~24 megapixels) of the <u>complete circuit together</u> can be found <a href="http://www.freeimagehosting.net/503bb" target="_blank">here</a></div>
<div class="separator" style="clear: both; text-align: justify;">
You can also try running/simulating the circuit yourself by downloading the logisim circuit file <a href="http://www.mediafire.com/?zqy157ls4ji5e1t" target="_blank">here</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<span class="Apple-style-span" style="background-color: white; color: #222222; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">____________________________________________________</span></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both;">
</div>
<div style="text-align: justify;">
I have not copied any part of this circuit from anywhere - either web or books (except the <i>Shift Registers</i>, but that is a standard circuit.). I made this logic circuit all by myself just out of pure interest and fun!<span class="Apple-style-span" style="text-align: left;"> </span>I started making the circuit in the first week of December 2011, after I completed my 5th semester at <a href="http://www.iitd.ac.in/" target="_blank">IITD</a> in which I learnt the basics of digital electronics (course EEL201). After making the basic subcircuits, I got stuck at the part where the <i>input taking subcircuit</i> had to be clubbed with the <i>shift registers</i>. (I was keeping both the <i>T flip flop</i> and <i>shift registers</i> as falling edge triggered.) After thinking for about 2 days on it, I left the circuit incomplete, afraid that I would have to restructure the entire circuit again, and went on vacations. After 2 weeks, I took a casual look at the circuit and to my surprise, within 10 minutes, found the solution! It was such a simple trick! But the most important one! (The trick was just to make the <i>T flip flop</i> as rising edge triggered, keeping the <i>shift registers</i> as falling edge triggered!) I was really happy that day as I didn't had to alter even a slightest bit of the circuit structure to make it working! </div>
<div style="text-align: justify;">
I realized that small changes can actually solve big problems in our lives, if we are not reluctant to try.</div>
</div>
Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com30tag:blogger.com,1999:blog-2415493264778899794.post-16695036554517342282011-07-07T16:03:00.021+05:302011-12-31T20:27:31.335+05:30Sudoku Solver - The GUI (Part 3 of 4)<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: left;"><div style="text-align: justify;"><span class="Apple-style-span" style="-webkit-text-decorations-in-effect: none;">[This post is a part of the main post - <a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-with-gui-written-in.html" style="font-style: italic;">Sudoku Solver with GUI written in python</a>.]</span></div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">The <i>Sudoku Solver </i>has a simple and easy to use GUI.</div><div style="text-align: justify;">Lets us go through the picture gallery to understand it well -</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><i><u>#1. Startup</u></i></span></div><div style="text-align: justify;">This is how the <i>Sudoku Solver</i> looks when you start it -</div><div style="text-align: justify;"><br />
</div></div><div style="text-align: left;"><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_fp9pyOmrUHV5eWRnFlqu0iuxiyruaqwUrDT9ZntkHaqyaJHNlg1g5BbHnXxqcoLyDXv3cMkaB8Rr_vIRU8HKsBoYyBgNrtGJyajDYbD1_jtDP-wk9l6YNGdeqewAdPQ2aGD0-F0kkLdu/s640/Sudoku+Solver+%255Bblank%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_fp9pyOmrUHV5eWRnFlqu0iuxiyruaqwUrDT9ZntkHaqyaJHNlg1g5BbHnXxqcoLyDXv3cMkaB8Rr_vIRU8HKsBoYyBgNrtGJyajDYbD1_jtDP-wk9l6YNGdeqewAdPQ2aGD0-F0kkLdu/s640/Sudoku+Solver+%255Bblank%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #1</td></tr>
</tbody></table><div style="text-align: justify;">Note the maze-like colour combination for easy identification of the (specific) 3 x 3 boxes. Also, in the side pane, you have a big white coloured (initially empty) <i>Solution Box</i> and 4 buttons - <i>Save, Clear, Revert, Solve</i>.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><i><u>#2. Entering numbers -</u></i></span></div><div style="text-align: justify;">To enter numbers in the cells, you need to just scroll over the cells. Scrolling over a cell will rotate through its permissible numbers. <i>(Permissible numbers are those numbers which you can enter in the cell without immediately violating the Sudoku rules. The rules <u>may</u> later get violated.</i>)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">For example, consider this puzzle -</div><div style="text-align: justify;"><br />
</div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvl5WcI2fdJr2dNkX9t4d7JzleUCoSuyTqCB52wQHFX0yypTOp12WFpT3ze3DVi6u82zKrAB5S9_uKGXqXDKDwiKnorcWP8JxjOzGkXEWSYD9JNFN-J8SH80EtPr7svl2Bz5ATfIJmm0E5/s640/Sudoku+Solver+%255Bscroll1%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="530" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvl5WcI2fdJr2dNkX9t4d7JzleUCoSuyTqCB52wQHFX0yypTOp12WFpT3ze3DVi6u82zKrAB5S9_uKGXqXDKDwiKnorcWP8JxjOzGkXEWSYD9JNFN-J8SH80EtPr7svl2Bz5ATfIJmm0E5/s640/Sudoku+Solver+%255Bscroll1%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #2</td></tr>
</tbody></table><div style="text-align: justify;">Observe that for cell 5,5 {row 5, column 5}, the permissible numbers are 1,4,5 and 6. So you can scroll on cell (5,5) to rotate through these numbers (only). You cannot enter any other number in that cell. <i>Thus, the mechanism is such that it automatically prevents you from committing any mistakes while filling the grid.</i></div><div style="text-align: justify;"><br />
</div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1t3jjbEyehJFCzng3SdDdhRGEfLRNyA_T9__Ra-TqgRElbCNy743yi3XaGfUZsf71POrHJsAJghRgH248yYNAf6RHP0IymC2DyDx124AUi9mAXN92Wi9WdGJOxgZP3sXrsAn7LV1Dfmjb/s640/Sudoku+Solver+%255Bscroll%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="412" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1t3jjbEyehJFCzng3SdDdhRGEfLRNyA_T9__Ra-TqgRElbCNy743yi3XaGfUZsf71POrHJsAJghRgH248yYNAf6RHP0IymC2DyDx124AUi9mAXN92Wi9WdGJOxgZP3sXrsAn7LV1Dfmjb/s640/Sudoku+Solver+%255Bscroll%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #3 (Observe the cell (5,5) for each case.)</td></tr>
</tbody></table><div style="text-align: justify;"><u><span class="Apple-style-span" style="font-size: large;"><i>#3. Save, </i></span><span class="Apple-style-span" style="font-size: large;"><i>Clear, </i></span><span class="Apple-style-span" style="font-size: large;"><i>Revert -</i></span></u></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;">You can save a puzzle you have entered in the grid using the <i>Save </i>button.</div><div style="text-align: justify;">Use the <i>Clear</i> button to clear the grid (and make it again look like Picture #1 above).</div></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;">To load an already saved puzzle (the one saved using the <i>Save</i> button), use the <i>Revert</i> button.</div></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;"><br />
</div></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;"><u><span class="Apple-style-span" style="font-size: large;"><i>#4. Solve and the Solution</i></span><span class="Apple-style-span" style="font-size: large;"><i> -</i></span></u></div></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;">Once you have entered a puzzle, click <i>Solve</i> to solve the puzzle. The puzzle will be solved almost immediately. You can go through the solution (steps taken to solve the puzzle) in the <i>Solution Box</i>. </div></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;"><br />
</div></div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJeYhjKTWIAeCkLZIO40gWe5A7F5-VGXEKM9AKaG6Ntk_9D6mggTNyLcDNq8AUAVHHgnSXWi4NFInXLwqKDtEmHYJx-XXpyg2e9XEQJcmqaPmDBl5g_01dA4gOCQhyEV7CZTiOzrjW_ifm/s640/Solving+a+Sudoku+Puzzle.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="356" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJeYhjKTWIAeCkLZIO40gWe5A7F5-VGXEKM9AKaG6Ntk_9D6mggTNyLcDNq8AUAVHHgnSXWi4NFInXLwqKDtEmHYJx-XXpyg2e9XEQJcmqaPmDBl5g_01dA4gOCQhyEV7CZTiOzrjW_ifm/s640/Solving+a+Sudoku+Puzzle.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #4</td></tr>
</tbody></table><div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixY90IhgAQB_La8qOi_TaLaGWeYcRTacZOvFLdWqD1mxUNarTvYf1d5Is0HTZ9XF7yDZ5SCYcABinNoum4fUI_1RBdG9ef0xBjGExJIvQo_1rbt7jlIF7zd2oVU5aKYaNo84vU6maEj6aC/s640/Sudoku+Solver+%255BSolution+Box%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixY90IhgAQB_La8qOi_TaLaGWeYcRTacZOvFLdWqD1mxUNarTvYf1d5Is0HTZ9XF7yDZ5SCYcABinNoum4fUI_1RBdG9ef0xBjGExJIvQo_1rbt7jlIF7zd2oVU5aKYaNo84vU6maEj6aC/s640/Sudoku+Solver+%255BSolution+Box%255D.png" width="256" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #5</td></tr>
</tbody></table><br />
</div><div style="text-align: justify;">(Completely understanding the solution from the <i>Solution Box</i> is not easy and may take time. You will understand it better if you have gone through this post - <a href="http://guanidene.blogspot.com/2011/07/how-to-solve-sudoku-puzzle.html">How To Solve A Sudoku?</a>)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Don't worry if you forget any of the above. You can get these instructions in the <i>Sudoku Solver</i> application too - In the menu bar, simply go to Help -> How To Use?</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-size: x-small;">(In the above pictures you cannot see the menu bar, because these screen shots are from Ubuntu 11.04 in which the application menu bar is integrated </span></i><i><span class="Apple-style-span" style="font-size: x-small;">with the</span></i><i><span class="Apple-style-span" style="font-size: x-small;"> global menu bar at the top.)</span></i></div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-size: x-small;"><br />
</span></i></div><div style="text-align: justify;"><u><span class="Apple-style-span" style="font-size: large;"><i>#5. Additional</i></span></u><u><span class="Apple-style-span" style="font-size: large;"><i> -</i></span></u></div><div style="text-align: justify;">You can make the application span the entire screen using F11 (or from the menu bar, View -> Fullscreen.)</div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivt3b6Gh5p8xv-adOO5myg7A156eCK_1MMTBlYxozgMEtJCZpjZfvxPe-L_xQtm3eNxYzve9wbfJIN8VSn3crUaf6rCml-qjeZVuWpM5j1RQqzc4E64bg86WafdVkB6gxig3l-UpHtNrIu/s640/Sudoku+Solver+%255BFullscreen%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="360" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivt3b6Gh5p8xv-adOO5myg7A156eCK_1MMTBlYxozgMEtJCZpjZfvxPe-L_xQtm3eNxYzve9wbfJIN8VSn3crUaf6rCml-qjeZVuWpM5j1RQqzc4E64bg86WafdVkB6gxig3l-UpHtNrIu/s640/Sudoku+Solver+%255BFullscreen%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Picture #6</td></tr>
</tbody></table><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Also, when the mouse moves into the region of a (non empty) cell, the number within pops up. This can be noticed in the above picture too.</div></div></div>Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com2tag:blogger.com,1999:blog-2415493264778899794.post-41255227857189284612011-07-07T16:02:00.024+05:302011-12-31T19:32:58.789+05:30How to solve a Sudoku puzzle? (Part 2 of 4)<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;">[This post is a part of the main post - <a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-with-gui-written-in.html" style="font-style: italic;">Sudoku Solver with GUI written in python</a>.]</div><div style="text-align: justify;"><br />
This post explains the 'logic' required to solve Sudoku puzzles.</div><div style="text-align: justify;">(These are also exactly the same steps I have followed in my program, <i>Sudoku Solver, </i>to solve Sudoku puzzles.)<br />
<br />
</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><u><i>Sudoku rules -</i></u></span></div><div style="text-align: justify;">The objective of a Sudoku puzzle is to enter a number from 1-9 in each cell, in such a way that:</div><ul style="text-align: left;"><li style="text-align: justify;">Each (horizontal) row contains each number exactly once.</li>
<li style="text-align: justify;">Each (vertical) column contains each number exactly once.</li>
<li style="text-align: justify;">Each of the 9* 3x3 boxes (or subgrids) contain each number exactly once.</li>
</ul><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: x-small;">(* - not any 3x3 box. More info <a href="http://www.sudoku.ws/how-to-solve.htm">here</a>.)<br />
</span></div><div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: x-small;"></span></div><span class="Apple-style-span" style="font-size: large;"></span><br />
<div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><u><i>Steps involved in solving Sudoku puzzles -</i></u></span></div><div style="text-align: justify;">(Note: The steps described below are the steps <i>I</i> have followed in my program to solve Sudoku puzzles. There <i>can</i> be more ways to do the same.)<br />
<br />
</div>(If you are trying to understand the <i>logic.py</i> module <a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-source-code.html">(here)</a> - <br />
In the examples below, I have provided the name of the function (ie either Step1 or Stepk) in square brackets which contains the logic to solve that example,.)</div><div><br />
<div style="text-align: justify;"><i><u>Lets go through some easy steps first.</u></i></div><div style="text-align: justify;">In the very first approach, we will try to solve the puzzle <i>'exactly'</i> as far as possible. This is the simplest approach and the puzzle won't be significantly solved in most cases.</div><div style="text-align: justify;"><br />
<b>Rule #1:</b><br />
If there is only 1 permissible number in a cell, enter that number in the cell.<br />
<i>(Permissible numbers are those numbers which you can enter in the cell without immediately violating the Sudoku rules. The rules <u>may</u> later get violated.</i>)<br />
<br />
</div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-size: large;"><u>Example #1</u> </span></i><i>[Step1 (algorithm 1)]</i></div><div style="text-align: justify;">In a row, since the only numbers can be 1 - 9 and none can repeat, it is clear that, in the picture below, the only permissible number in the cell (2,5) {row 2, column 5} is '5'.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0L_DaEUnhPMszNeUIkP9BPzJA1UxaJUQOviQiccb7OHsjZ0HobTEgNzaFa7ONzuWnRqhJ886mQFiVMH9sQPbZJU4x_nUIge7tW1RspxpwPJPW-h-CetrUldioclEEnZltGr1uVZIamDRq/s1600/Step1+Algo1-1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0L_DaEUnhPMszNeUIkP9BPzJA1UxaJUQOviQiccb7OHsjZ0HobTEgNzaFa7ONzuWnRqhJ886mQFiVMH9sQPbZJU4x_nUIge7tW1RspxpwPJPW-h-CetrUldioclEEnZltGr1uVZIamDRq/s1600/Step1+Algo1-1.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Puzzle #1)</td></tr>
</tbody></table></div><div class="separator" style="clear: both; text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXmtxWU8wSZijg3XckxVQrccExqa-inE6MQvOtkoit4T0OogoD5idl3PMFxFjGffYJWIkEr7Khyphenhyphen19ltC-HxxzkuPpLL2US2GZifFhIr3H3FKADOcW4D3RYnTuTwUBEI3FQCY-AI7QKCbTP/s1600/Step1+Algo1-2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXmtxWU8wSZijg3XckxVQrccExqa-inE6MQvOtkoit4T0OogoD5idl3PMFxFjGffYJWIkEr7Khyphenhyphen19ltC-HxxzkuPpLL2US2GZifFhIr3H3FKADOcW4D3RYnTuTwUBEI3FQCY-AI7QKCbTP/s1600/Step1+Algo1-2.png" width="640" /></a></div><div class="separator" style="clear: both; text-align: justify;"><br />
</div><div class="separator" style="clear: both; text-align: justify;"><i><span class="Apple-style-span" style="font-size: large;"><u>Example #2</u> </span>[Step1 (algorithm 1)]</i></div><div class="separator" style="clear: both; text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal;">Similarly, in a column, since the only numbers can be 1 - 9 and none can repeat, it is clear that, in the picture below, the only permissible number in the cell (5,7) </span></i>{row 5, column 7} <i><span class="Apple-style-span" style="font-style: normal;">is '5'.</span></i></div><div class="separator" style="clear: both; text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal;"><br />
</span></i></div><div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwH5MPd4XHkfgX8ACZscHkRh8aCRrB0ledUDVROnNDUcDH9YpJn8F4XX3dFlhC7HP-ZmmH4er6rpoxk8BrJHhROrvIL0nxlTRy8b5b92ZuyJh3gu5HY24SE-fdax66p2xDrbZ6sSt433qS/s1600/Step1+Algo1-3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwH5MPd4XHkfgX8ACZscHkRh8aCRrB0ledUDVROnNDUcDH9YpJn8F4XX3dFlhC7HP-ZmmH4er6rpoxk8BrJHhROrvIL0nxlTRy8b5b92ZuyJh3gu5HY24SE-fdax66p2xDrbZ6sSt433qS/s1600/Step1+Algo1-3.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Puzzle #2)</td></tr>
</tbody></table></div><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1QMVSL6R9fIcxPAfwMC7qDWBf8_viG9pyyS3e3_qBa0w_wo0VKwankePqum91fa0spzjN5v0lTskjCLF1w6s1wG4XWPkJXfDRp2yNZlJStjNSWoKsYBQQtHvhDf_ODKj_bwt6exmGibWT/s1600/Step1+Algo1-4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1QMVSL6R9fIcxPAfwMC7qDWBf8_viG9pyyS3e3_qBa0w_wo0VKwankePqum91fa0spzjN5v0lTskjCLF1w6s1wG4XWPkJXfDRp2yNZlJStjNSWoKsYBQQtHvhDf_ODKj_bwt6exmGibWT/s1600/Step1+Algo1-4.png" width="640" /></a></div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-size: large;"><u>Example #3</u> </span>[Step1 (algorithm 1)]</i></div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal;">Similarly, in a box, since the only numbers can be 1 - 9 and none can repeat, it is clear that, in the picture below, the only permissible number in cell (2,2) </span></i>{row 2, column 2}<i><span class="Apple-style-span" style="font-style: normal;"> is '5'.</span></i></div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal;"><br />
</span></i></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoXfO1mpfcoNNCwaLMWIw9c_vVVjWGkZk_lgqSiq6HwRZ_qybowZ3hA3CAFFzQ7KTC5DccOR_QIHZPomfFsxBoulchWghOnjRHQhlOQCsR9buoGZEMUpa9ogzNYQjsDmLIirgRv40E36eE/s1600/Step1+Algo1-5.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoXfO1mpfcoNNCwaLMWIw9c_vVVjWGkZk_lgqSiq6HwRZ_qybowZ3hA3CAFFzQ7KTC5DccOR_QIHZPomfFsxBoulchWghOnjRHQhlOQCsR9buoGZEMUpa9ogzNYQjsDmLIirgRv40E36eE/s1600/Step1+Algo1-5.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Puzzle #3)</td></tr>
</tbody></table><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjau2jqjLK-FWSzM-YqsL3UC1bO9Gfj_JsPyjr4s-5iYYJ1j5vPg5FT6uW_eATSeLTp2TZoMO7j_ff-2gFlQ-tYZGlLVykztgvdMRcIhKzjdkQ5qbKA78mFi8VnMNwOnnodLz0MbIswZYVB/s1600/Step1+Algo1-6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjau2jqjLK-FWSzM-YqsL3UC1bO9Gfj_JsPyjr4s-5iYYJ1j5vPg5FT6uW_eATSeLTp2TZoMO7j_ff-2gFlQ-tYZGlLVykztgvdMRcIhKzjdkQ5qbKA78mFi8VnMNwOnnodLz0MbIswZYVB/s1600/Step1+Algo1-6.png" width="640" /></a><br />
(There can be more examples based on the same rule.)<br />
<br />
</div><div style="text-align: justify;"><i><u>Lets proceed 1 step further.</u></i></div><div style="text-align: justify;">Even in the next approach, we will try to solve the puzzle <i>'exactly'</i> as far as possible. However, this is not easily visible on the very first glance. Nevertheless, it is still easy!</div><div style="text-align: justify;"><br />
<b>Rule #2:</b><br />
If a number is permissible in only one of the cells in a <i>row</i>, then enter that number in that cell. That cell may <i>then</i> have more permissible numbers. Similarly, for <i>column</i> and <i>box</i>. (Below is an example for a <i>box.</i>)<br />
<br />
</div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-size: large;"><u>Example #4</u> </span></i><i>[Step1 (algorithm 2)]</i></div><i><span class="Apple-style-span" style="font-style: normal;">Have a look at the puzzle below. </span></i>Try to analyse the cell (2,8) {row 2, column 8}.<i><span class="Apple-style-span" style="font-style: normal;"><br />
</span></i><br />
<div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3XgNN5yBW1x2kmn5mod5RhPAcTwP7YF4bFFgtd1EnA4xh0q_90mIHU3xPPSbyy3MOffwIUtHD_2rJykzJPhIaRBEeefWGmLBHZWz76fN8cnmn_IsEAkELrrXNyYOjMKVKIIQF_Ac8eSK/s1600/Step1+Algo2-1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3XgNN5yBW1x2kmn5mod5RhPAcTwP7YF4bFFgtd1EnA4xh0q_90mIHU3xPPSbyy3MOffwIUtHD_2rJykzJPhIaRBEeefWGmLBHZWz76fN8cnmn_IsEAkELrrXNyYOjMKVKIIQF_Ac8eSK/s1600/Step1+Algo2-1.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Puzzle #4)</td></tr>
</tbody></table><span class="Apple-style-span">You will find that all numbers 1 through 9 are permissible for that cell. However, if you look carefully, you will find that it is the only cell in its box which can hold the number 1. Hence, we can be absolutely sure that the number in this cell should be 1.</span><br />
<span class="Apple-style-span"><br />
</span></div><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7nXhToroLYjwRoSSBwS0UR5jzm3V9WG1EWGecr1GRHAOHJAOXmZJYRE0SMu4bWHDY4yUdPaF47knrYaFMkRntteDRMGUSf221tLP50gtzA8-Tv09EZdr2sPoT9bfmLe9HAGmabN8plO_0/s1600/Step1+Algo2-2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7nXhToroLYjwRoSSBwS0UR5jzm3V9WG1EWGecr1GRHAOHJAOXmZJYRE0SMu4bWHDY4yUdPaF47knrYaFMkRntteDRMGUSf221tLP50gtzA8-Tv09EZdr2sPoT9bfmLe9HAGmabN8plO_0/s1600/Step1+Algo2-2.png" width="640" /></a><br />
(There can be more examples based on the same rule.)<br />
<br />
You can practise some <i>'easy'</i> level examples <a href="http://www.websudoku.com/?level=1">here</a> to memorize the above 2 approaches.</div><div style="text-align: justify;"><span class="Apple-style-span"><br />
</span><br />
<span class="Apple-style-span"><u style="font-style: italic;">Now, for something difficult.</u></span><br />
<span class="Apple-style-span">Until now we solved everything 'exactly'. However, in most situations these approaches <i>alone</i> cannot take us much far. What we have to resort to then is <i>assumptions! </i>This is an approach with the help of </span>which you can solve any Sudoku puzzle. It is like a universal tool (रामबाण).<br />
<br />
<b>Rule #3: </b><br />
When unable to solve any further using the above approaches, make an assumption, and then try to solve it further using the above approaches. If at some point Sudoku rules get violated, then it implies that your assumption was incorrect. If so, revert back to the point where you took the assumption, take the other assumption (on the same cell) and again proceed further as before. Otherwise, if you don't encounter any rule violations till the end, your assumption was correct (and you got lucky!).<br />
<span class="Apple-style-span"> This will be more clear from the example below.<br />
</span><br />
<span class="Apple-style-span">(Note: This approach is not actually difficult in the true sense, it is just laborious. Hence it is better to use this after <i>Rule #1</i> and <i>Rule #2</i>. However, you can always this before <i>Rules 1 and 2 </i>if you want to!)</span><br />
<span class="Apple-style-span"><br />
</span></div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large; font-style: italic;"><u>Example #5</u> </span><i>[Stepk (AssumptionLevel 1)]</i><br />
Observe the puzzle below. Let us try to solve this using <i>Rule #3</i>. Observe the cell (7,8) {row 7, column 8}.<br />
<br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdGBLFyrOGVmS66jInzfzlF7Gqz6EkFM-CXZi1drstm0gXJ_BDCOnDfffgh8Oj5qVYug34bwgcCMq5UErWYc_bekpupXibxlHvTwy82CJ4q9KsGEWNJqUrUdgXM7JGu66DGC-uDnaYCElL/s1600/Assumption1-Step1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdGBLFyrOGVmS66jInzfzlF7Gqz6EkFM-CXZi1drstm0gXJ_BDCOnDfffgh8Oj5qVYug34bwgcCMq5UErWYc_bekpupXibxlHvTwy82CJ4q9KsGEWNJqUrUdgXM7JGu66DGC-uDnaYCElL/s1600/Assumption1-Step1.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Puzzle #5)</td></tr>
</tbody></table><div class="separator" style="clear: both; text-align: justify;">You may notice that, for now, the only permissible numbers in that cell are 5 and 9. We cannot directly say at this point which one is correct (but only among them is correct!). <i>This is where we decide to take an assumption.</i> Let us assume the number <i>9</i> in that cell.</div><div class="separator" style="clear: both; text-align: justify;"><br />
</div><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8hRyjuMSMdOMmsKmYVjMKvfhqM-1ZKk3zILlqd4ohKMAFXIEZXEyDYt56PAYvia8IWazBuAKIBz5vih3Nr8Mr1f9nZzrt4EQeZhBkSoKaAWXAMOgFd5giWI4LZ00pZo-BActa7jGH73or/s1600/Assumption1-Step2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8hRyjuMSMdOMmsKmYVjMKvfhqM-1ZKk3zILlqd4ohKMAFXIEZXEyDYt56PAYvia8IWazBuAKIBz5vih3Nr8Mr1f9nZzrt4EQeZhBkSoKaAWXAMOgFd5giWI4LZ00pZo-BActa7jGH73or/s1600/Assumption1-Step2.png" width="640" /></a><br />
<br />
Now we will try to solve it further using our first 2 'exact' approaches. It can be immediately seen that, using <i>Rule #2</i>, the number in cell (3,7) {row 3, column 7} should be 9.<br />
<br />
</div><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtNFozcJMNU7X6DCPKURsZ97mbZ_g5X8Yos77fkIQJWgNsCWCmdzGqGsVYWtL5UvN2u3tY0bwt7TR56Hs4e6r8xhE0SLTpSwFqjt_lIyGnE0TSzlSOrG9oA-yRAF44YP_swXQ0nnzeVYhP/s1600/Assumption1-Step3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtNFozcJMNU7X6DCPKURsZ97mbZ_g5X8Yos77fkIQJWgNsCWCmdzGqGsVYWtL5UvN2u3tY0bwt7TR56Hs4e6r8xhE0SLTpSwFqjt_lIyGnE0TSzlSOrG9oA-yRAF44YP_swXQ0nnzeVYhP/s1600/Assumption1-Step3.png" width="640" /></a><br />
<br />
Similarly, again using <i>Rule #2</i>, the number in cell (2,3) {row 2, column 3} should be (again) 9.<br />
<br />
</div><div class="separator" style="clear: both; text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKkxwR0qNOCgDUNFmEYJFo7j7yFSpPpV0Kqs_O6BVJ8SWpY9mdfAUf6Q3qDr-jIJjZZLUA1sRPDFDgKtD8xxfgtAClWeIPUTL9RzJq3NzACtQYieY7s8h7owpAGQJORpsgm1SnWrf6MovR/s1600/Assumption1-Step4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKkxwR0qNOCgDUNFmEYJFo7j7yFSpPpV0Kqs_O6BVJ8SWpY9mdfAUf6Q3qDr-jIJjZZLUA1sRPDFDgKtD8xxfgtAClWeIPUTL9RzJq3NzACtQYieY7s8h7owpAGQJORpsgm1SnWrf6MovR/s1600/Assumption1-Step4.png" width="640" /></a></div><br />
Now, if you look carefully, you will find that there is some problem. You cannot fit 9 anywhere in the box (2,1) without violating the Sudoku rules. But this itself is a violation of the 3rd rule - <i>"Each of the 9 3 x 3 boxes (or subgrids) contain <u>each</u> <u>number</u> <u>exactly</u> <u>once.</u>"</i> But where did we go wrong?<br />
<div class="separator" style="clear: both; text-align: justify;"><br />
</div><div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXvmTVFEs9uDJ-P1yESlvFlK2qlQ4yj9M7FmxUF7av9PHnB-v86JyoDD4umCTKjqEUzu-nHtkEpaiX0lDEawVYtP69TY6Ki072O2xftJRS_ai2wNYBK90G5SyWGzeuyPYaG2g49NOZRI4j/s1600/Assumption1-Step5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXvmTVFEs9uDJ-P1yESlvFlK2qlQ4yj9M7FmxUF7av9PHnB-v86JyoDD4umCTKjqEUzu-nHtkEpaiX0lDEawVYtP69TY6Ki072O2xftJRS_ai2wNYBK90G5SyWGzeuyPYaG2g49NOZRI4j/s1600/Assumption1-Step5.png" width="640" /></a><br />
<br />
- at the point of assumption! We wrongly assumed the number in the cell (7,8) {row 7, column 8} (in <i>Puzzle #5)</i> to be 9. Although we were not sure about it then, we can now be sure that the number in the cell (7,8) {row 7, column 8} in <i>Puzzle #5</i> should be 5!<br />
(Note: This is the reason why we made an assumption on a cell which then had only 2 permissible numbers. Had we made an assumption on some other cell which had more than 2 permissible numbers, we would have not been able to deduce the correct number even at this stage!)<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC0QPHoSwlz7_ht9gtxVf9Fw-saGFXKjcIQCJRSHTtRdcVhv8se8JWwyWYiobIbgTB3u8Yl1uIeJPMcPrbUr92HQfFHK-X080ls_BiO-iDscsn-ySjiqMbh2a_RPc2TIVxzRq34OD25Y6T/s1600/Assumption1-Step6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC0QPHoSwlz7_ht9gtxVf9Fw-saGFXKjcIQCJRSHTtRdcVhv8se8JWwyWYiobIbgTB3u8Yl1uIeJPMcPrbUr92HQfFHK-X080ls_BiO-iDscsn-ySjiqMbh2a_RPc2TIVxzRq34OD25Y6T/s1600/Assumption1-Step6.png" width="640" /></a><br />
<br />
Now that we have the correct number in cell (7,8) {row 7, column 8}, we try to solve it further using <i>Rules 1 and 2</i>. You will notice that the puzzle now easily gets completely solved.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWG4G5rZXsE_WpeIi5U5Dk1szqNaGkZk1WoZ4NA0WHJhBocvvD9DkyICqdyA7PgY_-I7W_BQScfTp8mi2kKwy4F_WeWp2woGexQlPrB7GcATBWwQnHORyX0MIp9pFaeiPcY0CYWu_j7W-O/s1600/Assumption1-Step7.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWG4G5rZXsE_WpeIi5U5Dk1szqNaGkZk1WoZ4NA0WHJhBocvvD9DkyICqdyA7PgY_-I7W_BQScfTp8mi2kKwy4F_WeWp2woGexQlPrB7GcATBWwQnHORyX0MIp9pFaeiPcY0CYWu_j7W-O/s1600/Assumption1-Step7.png" style="cursor: move;" width="640" /></a></div><div style="text-align: justify;"><br />
This might take some time to understand. You can practise some <i>'medium'</i> level examples <a href="http://www.websudoku.com/?level=1">here</a> to better understand this approach.<br />
<br />
There still remains 1 unanswered question -<br />
<br />
<i><u>How to decide on which cell an assumption must be made?</u></i><br />
You can make an assumption on any cell as long as it has only exactly 2 permissible numbers. It is quite possible that you may <u>not</u> be able to make a decision (about the correct number in a cell) on the very first assumption itself (and this is what usually happens), where both the assumptions (on that particular cell) might seem to be true. In this case, you need to leave that cell and try for an assumption on some other cell.<br />
<br />
<i><u><span class="Apple-style-span" style="font-size: large;">The True Picture -</span></u></i><br />
<i>99.9%</i> of the Sudoku puzzles can be solved using this approach. For the rest <i>0.1%</i> you need to resort to <i>assumptions over assumptions</i>. This is again not difficult, but it becomes too laborious and should be kept as a measure of last resort after you have tried to solve the puzzle by making assumptions on all cells (with exactly 2 permissible numbers) and still you are not able to solve the puzzle completely.<br />
Don't worry, you normally won't come across any puzzle from this <i>0.1% </i>category<i>!</i><br />
(Not even the hard/extreme/evil Sudoku puzzles on most websites fall in this category!)<br />
<br />
I denote the nesting of assumptions by their <i>level</i>. In the above puzzle #5, we made only 1 assumption and solved the rest of the puzzle exactly (ie using no more assumptions.) This assumption is denoted as an <i>assumption of Level 1.</i> If you are taking an assumption on an assumption (and no more assumptions), the <i>later</i> assumption is an <i>assumption of Level 2. </i>Similarly there can be more levels.<br />
<br />
<br />
Remember the link to one of the toughest puzzles I gave at the beginning of the main post? (if not, it is <span class="Apple-style-span" style="font-size: x-small;"><a href="http://www.mumbaimirror.com/index.aspx?page=article&sectid=2&contentid=20100820201008200227455947563886b">here</a></span><span class="Apple-style-span" style="font-size: x-small;">).</span><br />
To solve it completely, it requires an <i>assumption of Level 3!</i></div></div></div>Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com5tag:blogger.com,1999:blog-2415493264778899794.post-84793855238865424712011-07-07T16:02:00.023+05:302013-12-31T00:11:19.089+05:30Sudoku Solver with GUI written in python (Part 1 of 4)<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;">
<div style="text-align: justify;">
Sudoku Solver is a small graphical app for solving <i>any</i> given Sudoku puzzle, almost instantaneously. It also shows the steps required to solve the same.</div>
<div style="text-align: justify;">
<span class="Apple-style-span" style="font-size: x-small;">(Have a look at one of the toughest Sudoku puzzles </span><span class="Apple-style-span" style="font-size: x-small;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilVgOK_q714LFvmLQxNmgt7RmtayO6AKkycakErIfRjGIF8F75D_Vp_TY4Bv1knbzZDw8zm2LFffmPizf65kh5BE4SSaUzBkmy3d3qxGDsC9jKIyLKStxEM916aXQ11n5q3Dbs96fSDPxm/s1600/Screenshot-Sudoku+Solver-2.png" target="_blank">here</a>. <i>Sudoku Solver</i> can solve it too, and it is the toughest one I have found till date!)</span></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<br /></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
This is how <i>Sudoku Solver</i> looks like -<br />
<br /></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="344" src="//www.youtube.com/embed/xS9VIbyYNWU" width="459"></iframe></div>
<br /></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<u><i><span class="Apple-style-span" style="font-size: large;">For what audience is this post intended?</span></i></u></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<span class="Apple-style-span">Although I have primarily written this post for sharing my python code, this can be useful for you if -</span></div>
</div>
<ol style="text-align: left;">
<li style="text-align: justify;">You want to learn how to solve a Sudoku puzzle by hand.</li>
<li style="text-align: justify;">You want to yourself make a Sudoku solving program/application.</li>
<li style="text-align: justify;">You want to see some large, fairly complicated, working python code.</li>
<li style="text-align: justify;">You don't care how the <i>Sudoku Solver</i> works, you just want to use it to solve some of your Sudoku puzzles.</li>
</ol>
<div style="text-align: left;">
<div style="text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>OK, I am interested. Give me some background of Sudoku.</u></i></span></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
Sudoku is a logic based placement puzzle. A Sudoku puzzle consists of a 9 x 9 grid cells which are divided into 9 rows, columns and subgrids (as shown above). The task is to place the numbers from 1 to 9 in the empty cells in such a way that, in every row, column and 3 × 3 subgrid, each number appears only once.</div>
<div style="text-align: justify;">
<br /></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<i><u><span class="Apple-style-span" style="font-size: large;">How to solve a Sudoku puzzle?</span></u></i></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
Although the rules of Sudoku are quite simple, solving it can sometimes become a tough task.<br />
I have posted this separately with lots of pictorial examples here - <a href="http://guanidene.blogspot.com/2011/07/how-to-solve-sudoku-puzzle.html">How To Solve A Sudoku puzzle?</a></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<br /></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<i><span class="Apple-style-span" style="font-size: large;"><u>So what can this program do? Show me some examples.</u></span></i></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
It can solve <u><i>any</i></u> Sudoku puzzle, <u><i>almost </i></u><u style="font-style: italic;">instantaneously</u>. </div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<i><u>Example</u> -</i> </div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
Take any Sudoku puzzle you like, from anywhere - newspapers, websites, etc. (For this example, I have taken the one from <a href="http://www.guardian.co.uk/lifeandstyle/2011/jul/05/sudoku-1917-medium">here</a>.) Fill up the Sudoku Solver accordingly (<a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-gui.html">How do I use the Sudoku Solver?</a>).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcLfskxPdzGs6Ajrcu5CPDw-g0BPo8QWZ-2oD2F-n7ZtqOnTNOKchcH9FUpAAhx9UihogCMI6yDWbVC5cGYC18YpXi13kKeNv2X7zofMQhfXdbd_FNQbiJsXoufYamOHqDrdHs6q3LK0X9/s1600/Screenshot-Sudoku+Solver.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcLfskxPdzGs6Ajrcu5CPDw-g0BPo8QWZ-2oD2F-n7ZtqOnTNOKchcH9FUpAAhx9UihogCMI6yDWbVC5cGYC18YpXi13kKeNv2X7zofMQhfXdbd_FNQbiJsXoufYamOHqDrdHs6q3LK0X9/s640/Screenshot-Sudoku+Solver.png" width="640" /></a></div>
</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Click on Solve. The puzzle will be solved instantly. Note that it shows the steps required to solve the puzzle in the side pane.<br />
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDxrZDrgxEVd2W2yOgeDy4m6lV439_kjYVf1lAHnNYUD9oRqpe0hx6vT0lFOW4jrz8oLUqlwQ4mXfplbvUVpSmXkMzAA-VACl29fhtx3Kxjqmy0yddiZWi5INyCNIxuZ4-_N-IPOZTJcOO/s1600/Screenshot-Sudoku+Solver-1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="524" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDxrZDrgxEVd2W2yOgeDy4m6lV439_kjYVf1lAHnNYUD9oRqpe0hx6vT0lFOW4jrz8oLUqlwQ4mXfplbvUVpSmXkMzAA-VACl29fhtx3Kxjqmy0yddiZWi5INyCNIxuZ4-_N-IPOZTJcOO/s640/Screenshot-Sudoku+Solver-1.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Note the time taken to solve the puzzle - 0.05 seconds!)</td></tr>
</tbody></table>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<span class="Apple-style-span"><span class="Apple-style-span" style="font-size: large; font-style: italic;"><u>What's different in this?</u></span></span></div>
<div style="text-align: justify;">
</div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
Mostly on the web, you will find either of these -</div>
<ul>
<li style="text-align: justify;">Lots of websites having tonnes of Sudoku puzzles to solve and their final answers (but they don't show the steps required to solve these puzzles).</li>
<li style="text-align: justify;">Some Sudoku solving apps/applets/programs, but they can solve only the simpler ones. </li>
</ul>
<div>
<div style="text-align: justify;">
With my app, you can -</div>
</div>
<div>
<ul>
<li style="text-align: justify;">Solve <i>any</i> Sudoku puzzle.</li>
<li style="text-align: justify;">Also see the steps required to solve the same.</li>
</ul>
<div style="text-align: justify;">
<br /></div>
</div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
</div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<u><i><span class="Apple-style-span" style="font-size: large;">OK, so where is the source code?</span></i></u></div>
<div style="text-align: justify;">
The project is hosted on <a href="https://github.com/guanidene/pySudokuSolver">GitHub</a> (version 1.2 onwards). <br />
If you simply wish to download the source code, see the next section.</div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>How do I run/install Sudoku Solver?</u></i></span></div>
</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
</div>
<ol style="text-align: left;">
<li style="text-align: justify;">Make sure you have Python 2.7 installed. <span class="Apple-style-span" style="font-size: x-small;"><br />(On Linux: sudo apt-get install python; Windows/Mac: <a href="http://www.python.org/getit/">download</a>)</span></li>
<li style="text-align: justify;">Make sure you have PyQt4 installed. <span class="Apple-style-span" style="font-size: x-small;"><br />(On Linux: sudo apt-get install python-qt4; Windows/Mac: <a href="http://www.riverbankcomputing.com/software/pyqt/download">download</a>)</span></li>
<li style="text-align: justify;">Click <a href="https://github.com/guanidene/pySudokuSolver/archive/v1.3.zip">here</a> to download the source files. Extract it.</li>
<li><div style="text-align: justify;">
Simply execute the module <i>sudoku_solver.py</i> in a terminal-</div>
<span class="Apple-style-span" style="background-color: #fefdfa; color: #333333; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-color: rgb(136, 136, 136); border-bottom-style: solid; border-bottom-width: 0px; border-color: initial; border-left-color: rgb(136, 136, 136); border-left-style: solid; border-left-width: 0px; border-right-color: rgb(136, 136, 136); border-right-style: solid; border-right-width: 0px; border-style: initial; border-top-color: rgb(136, 136, 136); border-top-style: solid; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; text-align: justify; vertical-align: baseline; width: auto;"><span class="Apple-style-span" style="font-family: 'Times New Roman'; white-space: normal;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="color: black;">$ python sudoku_solver.py</span></span></code></span></pre>
</span></li>
</ol>
<br />
To learn to use the GUI, refer to the post - <a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-gui.html">Sudoku Solver - The GUI</a>.<br />
<br />
<div style="text-align: left;">
<div style="text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>Coming to the programming part, how is the program structured?</u></i></span></div>
</div>
<div style="text-align: left;">
<div style="text-align: justify;">
The program consists of 2 parts -</div>
</div>
<ul style="text-align: left;">
<li style="text-align: justify;">The Graphical User Interface (GUI).</li>
<li style="text-align: justify;">The <i>logic</i> required to solve (any) Sudoku puzzle.</li>
</ul>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: left;">
<div style="text-align: justify;">
<span class="Apple-style-span" style="font-size: large;"><i><u>Tell me more about the GUI.</u></i></span></div>
</div>
<div style="text-align: justify;">
I have fully described the <i>Sudoku Solver </i>GUI with pictorial examples in this post - <a href="http://guanidene.blogspot.com/2011/07/sudoku-solver-gui.html">Sudoku Solver - The GUI</a>. </div>
<ul>
</ul>
<div>
<div style="text-align: left;">
<div style="text-align: justify;">
<div style="text-align: center;">
____________________________________________________</div>
<div style="text-align: center;">
<br /></div>
I started programming this in mid-May, 2011. It took around 10 days for me to complete it. A month later I decided to document it (which took much more time). Finally, I decided to host this as a project on <i>on <a href="http://pypi.python.org/pypi/pySudokuSolver">PyPI</a>.</i> It was fun! Now it is hosted on <a href="https://github.com/guanidene/pySudokuSolver">GitHub</a> (version 1.2 onwards).</div>
</div>
<ul style="text-align: left;"></ul>
</div>
</div>
Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com4tag:blogger.com,1999:blog-2415493264778899794.post-75462860515668686482011-06-27T22:42:00.020+05:302012-02-28T19:15:55.872+05:30Nested tar archives extractor (.tar/ .tgz/ .tbz/ .tb2/ .tar.gz/ .tar.bz2) written in python<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: center;"><div style="text-align: left;"><div style="text-align: justify;">I recently wrote a small script in python which can be used to recursively extract nested tar archives about which I have discussed in this post (in quick question-answer format).</div></div><div style="text-align: left;"><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><u><i><span class="Apple-style-span" style="font-size: large;">For what audience is this post intended?</span></i></u></div><div style="text-align: justify;">I have primarily written this post for sharing the program so it is mainly for those who have some background in python programming. However, if you just want to use this as a utility, then you can simply skip to the download part.</div><div style="text-align: justify;">(This post has been written assuming that the underlying Operating System is Linux. However, it should be applicable for Windows too.)<br />
<br />
</div><div style="text-align: justify;"><i>So, lets begin...</i></div><div style="text-align: justify;"><br />
</div></div><div style="text-align: left;"><div style="text-align: justify;"><i><u><span class="Apple-style-span" style="font-size: large;">What is a nested tar archive?</span></u></i></div></div></div><div style="text-align: justify;">It is a tar archive containing other tar archives which may further contain many more tar archives (and so on...)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><i><u><span class="Apple-style-span" style="font-size: large;">So what does this program do?</span></u></i></div><div style="text-align: justify;">It extracts tar archives recursively. (What/How? It can be made clear from the examples below.)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><i><u><span class="Apple-style-span" style="font-size: large;">What's different in this?</span></u></i></div><div style="text-align: justify;">Ordinary extractors normally just extract a tar archive once, ie they won't extract any other tar archives (if any) that are present in it. If it has more tar archives and you want to extract them too, then you have to yourself extract each of these archives. This can be a real headache if there are many tar archives (and are nested many levels deep). I have tried to make this thing easy using this tool.</div><br />
<u><i><span class="Apple-style-span" style="font-size: large;">Can you show me some examples?</span></i></u><br />
Yes, why not.<br />
<br />
<u>Example #1</u><br />
If this is the directory structure of a tar archive -<br />
<pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; margin-left: 0px; margin-right: 0px; margin-top: 0px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">parent</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
a
b
c
d</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
x
y
z</span></code></pre><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><i><br />
</i></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><div style="text-align: justify;">After extracting using a <i>regular</i> extractor -</div></div><pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; margin-left: 0px; margin-right: 0px; margin-top: 0px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">parent</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
a
b
c
d.tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/ </span></code><span class="Apple-style-span" style="color: grey;"># this was not extracted.</span><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"> x
y
z</span></code></pre><div><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><br />
</span></code></div><div style="text-align: justify;">After extracting using <i>my</i> extractor -</div><pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; margin-left: 0px; margin-right: 0px; margin-top: 0px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">parent</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
a
b
c
d</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
x
y
z</span></code></pre><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><http: -erepdgs8o4g="" 1.bp.blogspot.com="" aaaaaaaackq="" imageanchor="1" jdf4udc64aq="" s1600="" screenshot+2+%255bnested+tar+archive+extractor%255d.png"="" style="margin-left: auto; margin-right: auto;" tgzcor2u77i=""><img border="0" height="358" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht9vxjFwunUoBPl0cXDRav6PCJL7GP_92uwd9U6k7cxHaQ1L2yiaxaPsjrq5rPCzqlST0O6QGSxHN6m3UrmHqJaXMcOC02Cy0P18pQpyjbBIV6sRXyjH81kqRoTp-6Usb5G-QkhIWw5luy/s1600/Screenshot+2+%255BNested+tar+archive+extractor%255D.png" width="640" /></http:></td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Structure of the tar archive xyz.tar)</td></tr>
</tbody></table><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzzJ7zKaNteb9uUtf0VkvxKe9IVEvG1fvzCGVXcOm5DJrXrvU8tkXC5mlCZHLFKBnTpf3NAS8YjZFQ4xbpVMxGggw3-HZa3JzKnUHlmlsxoXwUJe1egWKN5RA_XFN4FFe37YyOnP1nTvgr/s1600/Screenshot+3+%255BNested+tar+archive+extractor%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="358" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzzJ7zKaNteb9uUtf0VkvxKe9IVEvG1fvzCGVXcOm5DJrXrvU8tkXC5mlCZHLFKBnTpf3NAS8YjZFQ4xbpVMxGggw3-HZa3JzKnUHlmlsxoXwUJe1egWKN5RA_XFN4FFe37YyOnP1nTvgr/s640/Screenshot+3+%255BNested+tar+archive+extractor%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; text-align: center;">(On extracting using a <i>regular</i> extractor. Note that 'd.tar' is still not extracted.)</td></tr>
</tbody></table><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_6W50JFB7vV8u0EBIK1wCBzqPInlvtMEYehnIsvSw7ra0zpHfZ0BybgLxkWEceX6Q7pxUXmPM-PFyqeJzcQriSIqvW40bw2V3wVz7QcT9B9adQNema6roOL4LkmTPyvhN1eEhMQBF4PuP/s1600/Screenshot+4+%255BNested+tar+archive+extractor%255D.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="358" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_6W50JFB7vV8u0EBIK1wCBzqPInlvtMEYehnIsvSw7ra0zpHfZ0BybgLxkWEceX6Q7pxUXmPM-PFyqeJzcQriSIqvW40bw2V3wVz7QcT9B9adQNema6roOL4LkmTPyvhN1eEhMQBF4PuP/s1600/Screenshot+4+%255BNested+tar+archive+extractor%255D.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; text-align: center;">(On extracting using <i>my</i> extractor. Note 'd.tar' has been extracted to the folder 'd')</td></tr>
</tbody></table><u>Example #2</u><br />
<div style="text-align: justify;">While extracting, my extractor also takes care about not replacing/overwriting already existing folders.</div><div style="text-align: justify;">So if this is the directory structure of a .tar archive -</div><pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; margin-left: 0px; margin-right: 0px; margin-top: 0px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">parent</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
a
b
c
d</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
x
y
z
a</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"> </span><span class="com" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: grey; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"># note if I extract this directly, it will
# replace/overwrite the contents of folder 'a'.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
m
n
o
p</span></code></pre><br />
<i><span class="Apple-style-span" style="font-style: normal;">After extracting using <i>my</i> extractor -</span></i><br />
<pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; margin-left: 0px; margin-right: 0px; margin-top: 0px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">parent</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">tar
xyz</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
a
b
c
d</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
x
y
z
a </span><span class="lit" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: maroon; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">1</span><span class="pun" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">/</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"> </span><span class="com" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: grey; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"># extracted 'a.tar' to the folder 'a 1' as
# folder 'a' already exists in the same folder.</span><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">
m
n
o
p</span></code></pre><br />
<i><u><span class="Apple-style-span" style="font-size: large;">What do I need on my PC to run this program?</span></u></i><br />
<div style="text-align: justify;">Either python 2.6 or python 2.7. I have written this program in python 2.7 and it requires no extra packages to be installed. It should also work on prior python 2.x versions but I have not tested it on any of these.<br />
<br />
<u><i><span class="Apple-style-span" style="font-size: large;">Is the program easy to understand?</span></i></u><br />
Yes, it is a very simple. Also, I have provided plenty of documentation (comments) at every step in my code below, so understanding it won't be difficult at all. In fact, you can easily customize it later to suit your needs.</div><div style="text-align: justify;"><br />
</div><span class="Apple-style-span" style="font-size: large;"><u><i>OK, so where is the code?</i></u></span><br />
Here it is -<span class="Apple-style-span" style="background-color: white;"></span><br />
<pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; margin-bottom: 10px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; vertical-align: baseline; width: auto;"><span class="Apple-style-span" style="font-family: 'Times New Roman'; white-space: normal;"><pre class="prettyprint">#! /usr/bin/env python
# -*- coding: UTF-8 -*-
"""A command line utility for recusively extracting nested tar archives."""
__author__ = "Pushpak Dagade (पुष्पक दगड़े)"
__date__ = "$4 July, 2011 3:00:00 PM$"
import os
import sys
import re
import tarfile
from argparse import ArgumentParser
major_version = 1
minor_version = 1
error_count = 0
file_extensions = ('tar', 'tgz', 'tbz', 'tb2', 'tar.gz', 'tar.bz2')
# Edit this according to the archive types you want to extract. Keep in
# mind that these should be extractable by the tarfile module.
__all__ = ['ExtractNested', 'WalkTreeAndExtract']
def FileExtension(file_name):
"""Return the file extension of file
'file' should be a string. It can be either the full path of
the file or just its name (or any string as long it contains
the file extension.)
Example #1:
input (file) --> 'abc.tar.gz'
return value --> 'tar.gz'
Example #2:
input (file) --> 'abc.tar'
return value --> 'tar'
"""
match = re.compile(r"^.*?[.](?P<ext>tar[.]gz|tar[.]bz2|\w+)$",
re.VERBOSE|re.IGNORECASE).match(file_name)
if match: # if match != None:
ext = match.group('ext')
return ext
else:
return '' # there is no file extension to file_name
def AppropriateFolderName(folder_fullpath):
"""Return a folder (path) such that it can be safely created in
without replacing any existing folder in it.
Check if the folder folder_fullpath exists. If no, return folder_fullpath
(without changing, because it can be safely created
without replacing any already existing folder). If yes, append an
appropriate number to the folder_fullpath such that this new folder_fullpath
can be safely created.
Examples:
folder_name = '/a/b/untitled folder'
return value = '/a/b/untitled folder' (no such folder already exists.)
folder_name = '/a/b/untitled folder'
return value = '/a/b/untitled folder 1' (the folder '/a/b/untitled folder'
already exists but no folder named
'/a/b/untitled folder 1' exists.)
folder_name = '/a/b/untitled folder'
return value = '/a/b/untitled folder 2' (the folders '/a/b/untitled folder'
and '/a/b/untitled folder 1' both
already exist but no folder
'/a/b/untitled folder 2' exists.)
"""
if os.path.exists(folder_fullpath):
folder_name = os.path.basename(folder_fullpath)
parent_fullpath = os.path.dirname(folder_fullpath)
match = re.compile(r'^(?P<name>.*)[ ](?P<num>\d+)$').match(folder_name)
if match: # if match != None:
name = match.group('name')
number = match.group('num')
new_folder_name = '%s %d' %(name, int(number)+1)
new_folder_fullpath = os.path.join(parent_fullpath, new_folder_name)
return AppropriateFolderName(new_folder_fullpath)
# Recursively call itself so that it can be check whether a
# folder with path new_folder_fullpath already exists or not.
else:
new_folder_name = '%s 1' %folder_name
new_folder_fullpath = os.path.join(parent_fullpath, new_folder_name)
return AppropriateFolderName(new_folder_fullpath)
# Recursively call itself so that it can be check whether a
# folder with path new_folder_fullpath already exists or not.
else:
return folder_fullpath
def Extract(tarfile_fullpath, delete_tar_file=True):
"""Extract the tarfile_fullpath to an appropriate* folder of the same
name as the tar file (without an extension) and return the path
of this folder.
If delete_tar_file is True, it will delete the tar file after
its extraction; if False, it won`t. Default value is True as you
would normally want to delete the (nested) tar files after
extraction. Pass a False, if you don`t want to delete the
tar file (after its extraction) you are passing.
"""
try:
print "Extracting '%s'" %tarfile_fullpath,
tar = tarfile.open(tarfile_fullpath)
extract_folder_fullpath = AppropriateFolderName(tarfile_fullpath[:\
-1*len(FileExtension(tarfile_fullpath))-1])
extract_folder_name = os.path.basename(extract_folder_fullpath)
print "to '%s'..." %extract_folder_name,
tar.extractall(extract_folder_fullpath)
print "Done!"
tar.close()
if delete_tar_file: os.remove(tarfile_fullpath)
return extract_folder_name
except Exception:
# Exceptions can occur while opening a damaged tar file.
print '(Error)\n(%s)' %str(sys.exc_info()[1]).capitalize()
global error_count
error_count += 1
def WalkTreeAndExtract(parent_dir):
"""Recursively descend the directory tree rooted at parent_dir
and extract each tar file on the way down (recursively)."""
try:
dir_contents = os.listdir(parent_dir)
except OSError:
# Exception can occur if trying to open some folder whose
# permissions this program does not have.
print 'Error occured. Could not open folder %s\n%s'\
%( parent_dir, str(sys.exc_info()[1]).capitalize())
global error_count
error_count += 1
return
for content in dir_contents:
content_fullpath = os.path.join(parent_dir, content)
if os.path.isdir(content_fullpath):
# If content is a folder, walk down it completely.
WalkTreeAndExtract(content_fullpath)
elif os.path.isfile(content_fullpath):
# If content is a file, check if it is a tar file.
if FileExtension(content_fullpath) in file_extensions:
# If yes, extract its contents to a new folder.
extract_folder_name = Extract(content_fullpath)
if extract_folder_name: # if extract_folder_name != None:
dir_contents.append(extract_folder_name)
# Append the newly extracted folder to dir_contents
# so that it can be later searched for more tar files
# to extract.
else:
# Unknown file type.
print 'Skipping %s. <Neither file nor folder>' % content_fullpath
def ExtractNested(tarfile_fullpath):
extract_folder_name = Extract(tarfile_fullpath, False)
if extract_folder_name: # if extract_folder_name != None
extract_folder_fullpath = os.path.join(os.path.dirname(
tarfile_fullpath), extract_folder_name)
WalkTreeAndExtract(extract_folder_fullpath)
# Given tar file is extracted to extract_folder_name. Now descend
# down its directory structure and extract all other tar files
# (recursively).
if __name__ == '__main__':
# Use a parser for parsing command line arguments
parser = ArgumentParser(description='Nested tar archive extractor %d.%d'\
%(major_version,minor_version))
parser.add_argument('tar_paths', metavar='path', type=str, nargs='+',
help='Path of the tar file to be extracted.')
extraction_paths = parser.parse_args().tar_paths
# Consider each argument passed as a file path and extract it.
for argument in extraction_paths:
if os.path.exists(argument):
#print # a blank line
ExtractNested(argument)
else:
print 'Not a valid path: %s' %argument
error_count += 1
if error_count !=0: print '%d error(s) occured.' %error_count</pre></span></pre><span class="Apple-style-span" style="font-size: large;"><i>(download source files from <a href="http://pypi.python.org/pypi/nested.tar.archives.extractor/1.1">PyPI</a>)<br />
</i></span><br />
<i><u><span class="Apple-style-span" style="font-size: large;">What coding conventions does the program follow?</span></u></i><br />
<div style="text-align: justify;">I have followed <a href="http://www.python.org/dev/peps/pep-0008/">PEP 8</a> coding style and <a href="http://www.python.org/dev/peps/pep-0257/">PEP 257</a> docstring conventions while writing the program (<i>with 1 small exception - I have used maximum line width of 80 characters while <a href="http://www.python.org/dev/peps/pep-0008/">PEP 8</a> suggests a maximum of 79 characters.</i>)</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><u><br />
</u></span></div><i><u><span class="Apple-style-span" style="font-size: large;">OK, now I have downloaded the source files.</span></u></i><br />
<i><span class="Apple-style-span" style="font-size: large;"><u>How do I use it to extract 'nested tar archives'?</u> OR</span></i><br />
<i><span class="Apple-style-span" style="font-size: large;"><u>How do I access it from the terminal?</u></span></i><br />
Simply follow these steps -<br />
<ol><li>Ensure you have either python 2.6 or python 2.7 installed.</li>
<li>Extract the downloaded file "nested.tar.archives.extractor-1.1 [python 2.x].tar.gz"</li>
<li>Copy the file "extractnested.py" to one of the folders in your <a href="http://en.wikipedia.org/wiki/PATH_(variable)">PATH environment variable</a><br />
(Note: For linux users, as you might know, to allow execution of extractnested.py as a bash script, you need to grant it permissions - <span class="Apple-style-span" style="background-color: #eeeeee;"><span class="Apple-style-span" style="font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;"><span class="Apple-style-span" style="font-size: 14px;">$ chmod ugo+rx extractnested.py)</span></span></span></li>
<li>Now you can extract any tar archive from the terminal - </li>
<li><pre class="default prettyprint" style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 10px; max-height: 600px; overflow-x: auto; overflow-y: auto; padding-bottom: 5px; padding-left: 5px; padding-right: 5px; padding-top: 5px; text-align: justify; vertical-align: baseline; width: auto;"><span class="Apple-style-span" style="font-family: 'Times New Roman'; white-space: normal;"><code style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;"><span class="pln" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; border-bottom-width: 0px; border-color: initial; border-left-width: 0px; border-right-width: 0px; border-style: initial; border-top-width: 0px; color: black; font-size: 14px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; vertical-align: baseline;">$ extractnested.py <i>path</i> [<i>path</i> ...]</span></code></span></pre>where <i>path</i> is the path of the tar archive you want to extract.</li>
</ol><div class="separator" style="clear: both; text-align: center;"></div><div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOk7cGiHvaMa-UszGh4EgjkBdlolYju6i2Ox4xVS2_UVRIO4Xm_AlEvPT2a701vTmsiUlo7Ia77tWaZ5fmzZLbF0xbcB6CJrApLXTw8GMFrshnXJy-gsda8C755KX2mVzgL907m_n8R6ff/s1600/Screenshot+4.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="418" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOk7cGiHvaMa-UszGh4EgjkBdlolYju6i2Ox4xVS2_UVRIO4Xm_AlEvPT2a701vTmsiUlo7Ia77tWaZ5fmzZLbF0xbcB6CJrApLXTw8GMFrshnXJy-gsda8C755KX2mVzgL907m_n8R6ff/s1600/Screenshot+4.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; text-align: center;">(Extracting the tar archive 'xyz.tar')</td></tr>
</tbody></table>You can also extract more than 1 archives in one command.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnxIESkkgK_qcxDIPpSTcprvl86q2tUCNNl8cqHBu4wDDz1J76GTWmkuhDuHgNms329-umnnwdMskfH-fEio5EVH8uc7-G0F2Cct8Id97oMPoHRkXQm6v88p0cVifivDTfRIPpwNvvSQAX/s1600/Screenshot+5.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="418" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnxIESkkgK_qcxDIPpSTcprvl86q2tUCNNl8cqHBu4wDDz1J76GTWmkuhDuHgNms329-umnnwdMskfH-fEio5EVH8uc7-G0F2Cct8Id97oMPoHRkXQm6v88p0cVifivDTfRIPpwNvvSQAX/s1600/Screenshot+5.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 13px; text-align: center;">(Extracting 'xyz.tar' and 'abc.tar' in the same command.)</td></tr>
</tbody></table><br />
<u><i><span class="Apple-style-span" style="font-size: large;">Any future plans for development?</span></i></u><br />
<span class="Apple-style-span">Well ....yes. I plan to extend this utility for extracting other archives like zip, 7z, rar, etc so it can be an <i>'all in one extraction utility'</i>. Also I intend to add this to context menus so that one can simply right click on any compressed archive and extract it with a single click!</span><br />
<div style="text-align: center;"><span class="Apple-style-span">____________________________________________________</span></div><div style="text-align: center;"><span class="Apple-style-span"><br />
</span></div><br />
I actually wrote this program in response to <a href="http://stackoverflow.com/questions/6077222/extracting-compressed-files/6478410#6478410">this question</a> asked on <a href="http://stackoverflow.com/"><i>StackOverflow</i></a> which then had an active bounty of 50 rep. points (<i>StackOverflow</i> users will understand what I am saying!) in the greed of winning the bounty. So I worked on the program for 2 days and then posted it on <i>StackOverflow</i>. Unfortunately, even after a few days the <i>user</i> did not reply and I did not get any bounty, not even a single rep. point. So, upset, I decided to upload this program (with slight changes) to PyPI and also here on the blog.<br />
<br />
<span class="Apple-style-span"> Now, coincidentally or not, I don't know, that night after I uploaded this to PyPI and also posted it here, the <i>user</i> replied and rewarded me with the bounty! I got 75 rep. points! Believe me, there was no way the user knew I will be posting this here on the blog! When I saw this the next morning (that I won the bounty), my joy knew no bounds! <br />
That day, I did not do any work in the office (@internship) as I was busy editing this post!</span></div></div>Pushpakhttp://www.blogger.com/profile/06451482629000962232noreply@blogger.com1Mumbai, Maharashtra, India19.0176147 72.85616440000001118.826811199999998 72.7533269 19.2084182 72.959001900000018