case
28Mar/090

Sudoku solver in python

lens1512255_sudoku12Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.
I'm really not a sudoku fan but I love solving problems and sudoku offers you a challenging one. So...here's a the shortest sudoku solver written in python

1
2
3
4
def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import *;r(argv[1])

If you want to test that, save it in a file and use the command line to execute the code. Execute the code as following: python solver.py puzzle - where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank space

python solver.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079

The problem with the above code is that is really slow. Here's another one that runs about 100x faster and is less cryptic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
 
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
 
def r(a):
  i = a.find('0')
  if i == -1:
    sys.exit(a)
 
  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])
 
  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])
 
if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
  else:
    print 'Usage: python sudoku.py puzzle'
23Feb/092

How To – Setup a Subversion server on Windows

What is subversion

Subversion (svn) is a version control system initiated in 2000 by CollabNet. It is used to maintain current and historical versions of files such as source code, web pages documentations etc. Google code also provides free Subversion hosting but if you want your own private server continue reading to learn how to set up your own svn server

First: get the Subversion setup and run it to install Subversion.

Installing svnserve as a service
 
The simplest way to set up a server on Windows is to use svnserv which can be installed as a Windows service.
Run these commands in order to get the service up and running:
 

1
2
   mkdir c:\svn
   svnadmin create c:\svn\repos

Start the service:

1
2
   sc create svn binpath= "\"C:\program files\Subversion\bin\svnserve.exe\" --service -r C:\svn" displayname= "Subversion Server" depend= Tcpip start= auto
   net start svn

Note: There really are spaces after the = signs.
Check that it worked by checking out the repository:

1
   svn checkout svn://localhost/repos

Adding security

Edit C:\svn\repos\conf\svnserve.conf, uncomment these lines and change anon-access to none:

1
2
3
4
   anon-access = none
   auth-access = write
   password-db = passwd
   realm = My Subversion Repository

Now edit C:\svn\repos\conf\passwd and add a user name and password to the users section:

1
2
   [users]
   myusername = mypassword

Delete your first checkout and try to check out the repository again, this time you will have to supply a user name and a password.

Using WebDAV via Apache 2.2

Get and install XAMPP, install Apache and MySQL as a service. Unblock ports as needed when the installation is finishing up.

As we are installing Apache 2.2 so we need builds of the Subversion Apache modules which are compatible with Apache 2.2 which are available here.

XAMPP has a prebuilt mod_dav_svn and mod_authz_svn - they don't work, replace them with the Apache 2.2 built ones which you have just downloaded, the zip file contains a complete build of Subversion but we only need the two Apache module files. The files to replace are mod_dav_svn and mod_authz_svn in c:\xampp\apache\modules.

Edit C:\xampp\apache\conf\httpd.conf and add:

1
   Include conf/extra/httpd-subversion.conf

Put this in that file:

1
2
3
4
5
6
   LoadModule authz_svn_module modules/mod_authz_svn.so
   LoadModule dav_svn_module modules/mod_dav_svn.so
   <location /svn/repos>
     DAV svn
     SVNPath c:/svn/repos
   </location>

Stop and start the Apache service, either using the command line or the XAMPP Control Panel Application. Fire up a web browser and go to http://localhost/svn/repos.

Adding Security

In httpd-subversion.conf, add this to the Location directive:

1
2
3
4
   AuthType Basic
   AuthName "Subversion Repository"
   AuthUserFile c:/svn/passwords
   Require valid-user

Now create a password file and add a user, note: xamp htpasswd doesn't like drive letters.

1
2
3
   C:\svn>c:\xampp\apache\bin\htpasswd -cb \svn\passwords myusername mypassword
   Automatically using MD5 format.
   Adding password for user myusername

Then restart Apache again. You will now need to use the user name and password to access your repository.

If you're not familliar with the svn command line or you find it to hard to use, just download TortoiseSVN. You'll love it.

20Feb/0910

How To – get Cross Browser Compatibility Every Time

Working with Internet Explorer can be a pain for the everyday web designer. But it doesn't have to be. Many, if not all, of the bugs can be fixed quickly and easily by understanding how the occur. I've put together a list of the major problems beginners have with cross browser compatibility.

I'm only going to be concerned with the major browsers - Firefox 2+, Safari 3+ and Internet Explorer 6+. IE6 is slowly declining.  If you know the IE6 bugs you can generally know if your site will break before you even check it in a browser. This isn't an article for the super-experienced web designer, but hopefully will give some insight to some people who don't understand the mysteries of IE6 and cross browser compatibility.

Summary

Here is a quick summary for those of you who don't want to read the whole article:

  • Always use strict doctype and standards-compliant HTML/CSS
  • Always use a reset at the start of your css
  • Use -moz-opacity:0.99 on text elements to clean up rendering in Firefox, and text-shadow: #000 0 0 0 in Safari
  • Never resize images in the CSS or HTML
  • Check font rendering in every browser. Don't use Lucida
  • Size text as a % in the body, and as em's throughout
  • All layout divs that are floated should include display:inline and overflow:hidden
  • Containers should have overflow:auto and trigger hasLayout via a width or height
  • Don't use any fancy CSS3 selectors
  • Don't use transparent PNG's unless you have loaded the alpha

Element Inconsistencies

Every browser renders particular elements differently - different amounts of padding, margins, borders etc. This means your site can look different in every browser if you use default styles.

Solution

The first thing you should do, which most people most likely know about, is to reset your styles. A reset is some css you place at the start of your styles that removes the padding, margin, border and other inconsistencies from elements, and rebuilds them in a standard way.

Download Eric Meyer's reset.css and place the code at the start of your styles. Bam! Clean, cross browser styles.

Image Rendering

IE6 and IE7 both render resized images extremely badly. When you change the size of an image with CSS or in the HTML, it appears blocky and edgy.
Solution

Don't do it. Always size your images to your desired size before you use them on your site

Font Rendering

I told you not all issues were with IE. Safari 3+ has an issue with the way it renders light type on a dark background. Some would argue whether this is good or bad, but there's a way to make it appear lighter. Here's an example of standard white on black text rendering in Safari 3.1:

safari-before

Solution
Easy fix. You need to add this to your code.

p {
   text-shadow: #000 0 0 0;
}

Where #000 is your background colour. You will probably have to be more specific with the elements you select. I wouldn't suggest using this fix on the body tag. Other elements you might need to fix are the li, dt, dd, blockquote etc. Use this on any text element you want to appear 'thinner'

To make this fix in Firefox, you use the opacity fix:

p {
    -moz-opacity: 0.99;
}

You need to be careful with this fix, as it will break any Flash element that it touches in Firefox. There appears to be no workaround for it.

The type will now be rendered like this:

safari-after

Font Selection

There are common web fonts that we use - Arial, Georgia, Verdana etc. But there are some fonts that are common to both PC and Mac and can be used - Century Gothic, Arial Narrow etc. However, different browsers and OS's render type different, and you need to be aware of these differences, as your site could look dam ugly if you use the wrong font.

Solution

The font you choose is ultimately up to you. As long as it's a safe font you will be fine. However you should be aware of these rendering issues. One font you should probably not use is Lucida Grande/Sans. It renders awful in IE. Take a look at its rendering in Safari(Mac):

safari-lucida

Looks nice doesn't it? Too bad it looks like this in Internet Explorer(PC):

ie6-lucida

Some people have stated that Lucida Sans will look fine in IE with ClearType, and others have said that it still looks bad. A smart alternative is to just not use Lucida Sans as your 'fallback font', and instead use Arial or another san-serif font.

Font Sizing

The ability to resize text differs amongst browsers and OS's. IE won't resize text thats set in pixels. If we set all text in em's, IE will exaggerate the text sizes when resized.

Solution

The best reference for font sizing is the article How to Size Type in CSS by Richard Rutter. The results - You need to specify the size as a percentage in the body element, and then size it in em's through the rest of the sheet. For line height, you need to define it in em's, rather than pixels, for consistent rendering.
One thing to remember is that the default font size is 16px. So to resize our type to 12px we use:

body {
   font-size: 75%;
   line-height: 1.5em;
}

Now you can size your type in em's like so:

h1{
   font-size: 3em;
}

Another suggested technique is to resize it down to 10px, which makes it easier to size upwards in em's. For example.

body {
     font-size: 62.5%;
     line-height: 1.5em;
}
 
h1 {
      font-size: 1.8em; /* 18px */
}
 
p {
      font-size: 1.2em; /* 12px */
}

here is an issue with this however, if people use small font option in Internet Explorer, it could be so small that it's unreadable. It's only a small chance. But worth noting.

Double Margins on Floats

We create CSS layouts by floating div's up against each other, like some form of horizontal tetris. When it reaches the end of a row, it drops down to the next. The common method for creating a grid is this:

#content {
     float:right;
     width: 300px;
     margin-right: 10px;
}
 
#sidebar {
     float:right;
     width: 100px;
}

This is what it should look like in a browser:

doublemargin-ff

This is what IE does to it:

doublemargin-ie

The margin width is doubled. Any margin that is on the same side as the float will be doubled. Don't ask why. It's just IE. This means the element on the left will have that margin stretched out to 20px, which will probably break the layout.

Solution

To fix it, all you need to do is put display:inline on your layout divs.

#content {
     float:right;
     width: 300px;
     margin-right: 10px;
     display:inline;
}
 
#sidebar {
     float:right;
     width: 100px;
     display:inline;
}

Now that margin bug is all fixed. Even though it only effects margins on the same side as the float, it can still be useful to include this fix. You never know when you might use a margin on the float side. It won't effect any other browser, so you can use it safely.

Expanding Box

The expanding box problem is a big issue with many css layouts. When you have a standard layout, with floats sitting next to each other, with set widths, but an image or long string of text is longer than this width, the layout will break in IE6. Take a look at this example:

#content {
     float:left;
     width: 300px;
     margin-right: 10px;
     display:inline;
}
 
#sidebar {
     float:left;
     width: 100px;
     display:inline;
}

This will render like in this most browsers:

expandingbox

However, in IE6, it will break like so:

expandingbox-ie

Solution

The solution is to use the overflow property. If you place overflow:hidden; into the layout divs, the layout won't break in IE6.

#content {
     float:left;
     width: 300px;
     margin-right: 10px;
     display:inline;
     overflow:hidden;
}
 
#sidebar {
     float:left;
     width: 100px;
     display:inline;
     overflow:hidden;
}

This could, however, cause some issues with layouts depending on how complex they are. It also won't cause the text to wrap, and it will just remain hidden. It's unlikely you'll have a string long enough to break a layout, but it could happen. Another option is to use word-wrap: break-word; in an IE specific stylesheet. This won't effect images though, so you'll have to make a choice about with method is appropriate for your situation.

Clearing Floats

What we mean when we talk about clearing floats, is when a container or wrapper div doesn't correctly wrap around the containing divs. Take a look at this example:

clearing

See how the container is correctly containing the div's? This is what should happen. However, sometimes it does not clear correctly, like so:

noclearing

The container isn't correctly wrapping around it. You probably won't notice this until you try and put a background on your container.

Solution

There are a few different solutions for clearing. The best solution however, is a simple overflow:auto or overflow:hidden in your container

#container {
     width: 966px;
     margin: 0 auto;
     overflow:auto;
}

You need to keep in mind that overflow:auto might cause some issues in Firefox. If you do have any issues, use overflow:hidden instead. If this is still causing issues, take a look at some other forms of clearing floats. Apart from just adding this, you'll need to make sure hasLayout is triggered in IE6. You can do this by specifying a width or height. If you don't have a width in your container, you can use height:1% to trigger it, or zoom:1; if you can't afford to give it a height.

CSS Selectors

Although we would like to use all the brand spanking new CSS3 selectors, IE6 doesn't support all of the major ones. There are also still some CSS2 child and sibling selectors you simply shouldn't use if you want to support IE6:

  • E > F
  • E + F
  • E ~ F
  • :root
  • :last-child
  • :only-child
  • :nth-child()
  • :nth-last-child()
  • :first-of-type
  • :last-of-type
  • :only-of-type
  • :nth-of-type()
  • :nth-last-of-type()
  • :empty
  • :not()
  • :target
  • :enable
  • :disabled
  • :checked
  • Any of the E[attribute] Selectors
  • :first-child
  • :lang()
  • :before
  • ::before
  • :after
  • ::after

f course, a lot of these selectors aren't supported by even Firefox 3. For a full list of supported selectors, check out evotech.net's post on browser css selector support

Solution

Stick to your standard selectors. Nothing fancy. Only use E + F, E > F, E ~ F when it won't make a huge difference in IE. If you really need to use these selectors, you should look at using IE8.js which gives IE6 better selector support. However this will slow down your site. But we don't really care about IE6 users do we?

PNG Transparency

IE6 doesn't support alpha transparency in PNG's. This is possibly the most annoying bug/issue with IE.

Solution

There are a few solutions for this problem. You can either use AlphaImageLoader in an IE specific stylesheet, link to a behaviour file in an IE specific stylesheet or use JS to fix the issue. Not matter which way you choose, there is no way to have transparent repeating background images.
To use AlphaImageLoader, it's a little bit tricky. Add these properties to any png image you want to have transparency. (You need to put this code in an IE specific stylesheet if you want your CSS to validate)

.trans {
     background-image: none;
     filter: progid:DXImageTransform.Microsoft.AlphaImageLoader(src='/images/transparent.png', sizingMethod='image/scale/crop');
}

Let's say you've given all your png image tags a class "trans", you select them with your css and use the filter property. You need to create a 1x1 transparent png file and link to it in the src attribute.

An even better way to do this is via a behaviour. It's similar to the AlphaImageLoader, except that you link to a behaviour script that triggers the transparency.

The third method is to use IE8.js which I mentioned earlier. It's even safer than the previous method, and you are very unlikely to run into any problems. Link to the script in your HTML, and it will make any png ending in -trans alpha-capable. eg. myimage-trans.png.

With all this methods, you need to be aware that you might still run into problems with transparent pngs. Make sure you test it in IE6 extensively