Wednesday, June 27, 2007

Why Wubi is important for Linux

I have read a few comments of people being concerned about the role of Wubi. I'd like to address those concerns and explain why I think that Wubi is important for Linux and how I think it will affect the installers arena. Caveat: I am Wubi author (see the credits section for a full list of Wubi developers), hence my views on Wubi are heavily biased and highly optimistic.

If you do not know what Wubi is, have a look at http://wubi-installer.org/. In short, Wubi is a Windows installer that tries to make it as simple as possible to install and use Ubuntu. How simple? 1-click simple... No ISO to burn, no change of partitions required, and no change of bootlader, just 1-click.



But there is more...

Wubi is a disruptive technology and as such it does not fit well with traditional schemes (and sometimes people get confused). Wubi fills the gap between a pure demo (LiveCD or VM) and a real installation. Until today, demo mode and real installation have always been two completely separate setups (even if they come on the same medium), Wubi blurs the difference, like a demo it is very easy and safe to try/install/uninstall. Like a real installation it gives you a dual boot setup with full HW access (read 3D desktop), almost full speed and persistent storage. If you like what you see, and find yourself using Ubuntu a lot, you can "upgrade" to a dedicated partition via LVPM (still in early beta). If you do not like what you see, you can uninstall cleanly and revert the system to its previous state.

Wubi promotes an install-then-try approach which is more captivating than the try-then-install approach of the live CD or VM. The partitioning/bootloader hurdle becomes an optional step and it is deferred until the user has accumulated enough goodwill. Without a dedicated partition the user gives up a bit of performance, some robustness and the ability to hibernate, but he still gets a fully usable set-up, and the transition becomes gradual and smooth.

Also some people do not seem to digest too well that Wubi "requires" Windows. They fear that you might end up needing Windows in order to install and use Linux. Not quite. Our "dependency" on Windows is only for the installer front-end. Once installed, you end up with a dual boot installation that is completely independent of the host OS. The installation simply "sits" inside the host filesystem. Do you know what happens to a Wubi installation if you delete C:\WINDOWS? Absolutely nothing. You can still boot and use Ubuntu. So much for dependency...

As for the Windows front-end (Wubi), that happens to be the most popular one for obvious reasons, but we also have a front-end for Linux (Lubi), and we plan to create a Mac front-end called "Mubi". So what does this "dependency" really boils down to? Simple: we aknowledge that most people already have an OS installed, and we try to leverage that to improve the installation experience.

To begin with we do not have to explain how to change BIOS settings to boot from a CD. Nor to explain what to do with an ISO file. With an executable there is absolutely nothing to explain, but if you want to run an executable, you need an OS.

Second, since we run the installer from a working OS we can detect the settings from a live and working system, therefore we can spare the user several pointless questions and make fairly good guesses. Yes you already have migration-assistant to import the settings (and in fact we do use that), but observing an online system is always better than observing an offline system.

Third, since Wubi sits inside another OS, it can also be uninstalled cleanly. There is no ominous message such as "once you press this button, there is no turning back". We just install. If the user has seconds thoughts, s/he can always restore the system to its previous state.

Well, all that puts us in a fairly unique position. What is the result? The result is that Wubi is probably the first 1-click OS installer ever: enter the password, click "install" and reboot. It does not get any easier than that. First impressions are important, and sporting what can possibly be considered one of the easiest OS installer around does help a lot if you have to fight the stigma of being a "difficult" OS.

Will Wubi replace traditional installers? No. If you already know that you want to use Ubuntu and/or are confident about ISO burning and partitioning, there is not much point in using Wubi at all. Wubi helps when you do not know whether you will end up using Ubuntu and/or you are not confident about ISO burning and partitioning. It's a "niche" market, but one that includes the vast majority of users out there.

So will it change things for Linux? I really hope so. Wubi might end up disrupting the Linux installer scenario, like the introduction of LiveCD did a few years ago'. I would not be too surprised (and quite pleased indeed) if we ended up with Wubi clones popping up in other distros (debian-based distros are already supported by the way). In fact Wubi will be incorporated within Ubuntu in the 8.04 release cycle.

Thursday, January 25, 2007

No Blobs By Default Petition

I have started a petition in order to ask Mark and the Ubuntu developers to reconsider their decision to add binary drivers by default and opt for easy-installation as opposed to pre-installation of closed software. The issue has been discussed at length and I see no point in reiterating the arguments in favor and against the decision, suffice to say the proposed change should hopefully accomodate the views of those who oppose preinstallation of closed drivers, without compromosing ease of use and availability of features.

https://wiki.ubuntu.com/NoBlobsByDefaultPetition

If you agree with the above proposal, please consider 1) visiting the wiki and signing the petition, 2) making the petition known to others. I know that Mark and the other developers are well aware of the issues at stake, but I believe that a "formal" petition might be more effective to influence their decision process. I also believe that Ubuntu is a community distro, which means that the community does not passively accepts the choices made, but it forges such choices. This is one chance to influence the direction of your favorite distribution, I hope you will take advantage of it.

Thanks

Friday, November 24, 2006

Are Google and Mozilla waiting for a baby?

We all know the two are having an affair, but might the story "evolve"? The integration of Mozilla and Google may go well beyond the use of Google as default search engine... And in case you are wondering, yes, I am talking about Google "OS"...

Let's have a look at the parent genes. On the the desktop side, we have... ...Mozilla:

  1. XPCOM/XULRunner
  2. A local web-server (doubling up as application server providing XUL)
  3. A web-framework (something like RoR but fine-tuned for XUL and better integrated with XPCOM)
  4. A side-bar similar to google-desktop used as task-oriented panel + taskbar + notification + systray (ever wondered why google called their side-bar: google-DESKTOP?)
  5. Firefox
  6. Flash player (manage a trois?)

On the server side, running from Google HQ:

  1. A remote web-server (doubling up as application server providing XUL)
  2. A remote "hard-disk"

Put the two (or three) together and you have quite a nice combination. Let me explain.

This is not strictly an OS but more like an application framework that can run on any platform where Firefox (3) runs. It can easily be turned into a full OS by bundling it with Linux/BSD, but that is another story... Applications are essentially XUL files running locally, and they are provided by the local web-server and/or the remote web-server (and cached locally). They can optionally embed flash/html/svg components. Data (docs, emails, bookmarks) is stored on the remote hard-disk and is downloaded and synced locally so that it can be used offline. All data can optionally be shared.

Why is this baby so special?

  • Native speed, but with web-os flexibility. Like a USB-key OS without the USB-Key.
  • Cross platform
  • It can be downloaded and it should weight about 20-30 MB
  • One click installation
  • It can run on top of an existing OS (no partitioning)
  • It can replace a desktop environoment or coexist with it, managing its own applications
  • It can be bundled with Linux and a window manager (even Beryl ) to create a full blown OS, with a fairly small footprint
  • All Mozilla apps are supported by default
  • Seamless integration of local/remote apps, local/remote data, traditional GUI/web GUI.
  • Not all the functionality of an application needs to be installed/downloaded beforehand, so applications can be downloaded on-the-fly depending on user interaction
  • It should still be possible to install an application in a more traditional way in order to accomodate for offline workflow.

Even if Google is not interested, it might be a nice FOSS project, possibly using a distributed web-server and a "remote hard-disk" based on a p2p grid... In fact it might be a nice FOSS project even if Google is interested, to give the same flexibility to those that have privacy concerns...

Friday, September 15, 2006

Is Linux.org hurting Linux? Part 2

This is a follow up to my previous blog entry: Is Linux.org Hurting Linux? Since the article was published I have exchanged some emails with the webmaster. I prefer the discussion to be in the open, and therefore, with the permission of Linux.org webmaster, I will use this blog to attach relevant bits.

Sent by Ago, 5th of September

Dear sirs,

I have major complaints about the website, while I appreciate the initial efforts and the original contribution, I do not think that the website as it is today is helping Linux image. Quite the opposite. I expressed my thoughts in my blog http://agolb.blogspot.com/2006/09/is-linuxorg-hurting-linux.html . I was harsh, but I am not a political person. I honestly hope that the resulting debate will help improve the website and make it state of the art, as it deserves. Linux.org is the flag, and the flag has to fly high. The people who maintain Linux.org bear a great
responsibility.


Sent by Webmaster, 6th of September
Thanks for your mail. I saw your blog page. We take all suggestions seriously, though, pesonally, I don't think it's a good idea to respond to questions about how the website is financed.

Sent by Webmaster, 14th of September

I saw that you posted to Digg yesterday. First of all, I want to clarify a few things for you so that there aren't any misunderstandings.

If you want to add what I am going to say to your blog, that's fine.
(If you misquote me, I'll let you know real fast! :) - Also, I am not the Michael that posted on your blog to defend the site, nor is it Michael McLagan the owner of Linux.org. People have commented that it's me (or McLagan) and it isn't.

First of all, I started working for Linux.org in March of 2000 and assumed the 'webmaster' position shortly thereafter. I am responsible for updating the content on the site (where this content can be updated - I'll get into that shortly).

We redesigned the website in August of 2000 and as it has been pointed out, there hasn't been a redesign. Honestly, we don't get too many complaints about it. However, I am the first to say that it needs a redesign and that is something we have been working on. I personally have worked on a couple of prototypes but both Michael and I felt that these weren't professional looking enough. I have made my opinion clear that either we get a pro to redesign the site (like Slashdot did) or we go with a design of mine. Since I don't make the final decisions on this, I can't tell you when it's going to get done. Just like you, I hope it's soon.

As far as my job goes, I am pretty much free to post content to the site as I see fit and I also write reviews, op-eds and I am the author of the three Linux courses you see. Currently, I am re-writing the basic Linux course. I think there is a wealth of information behind what you call our out-of-date exterior (and rightfully so, as I mentioned). Some people have defended the site on the Digg post have also pointed that out.

As far as revenue goes, I don't handle that so I can't really comment too much on it. That's not out of secrecy - it's out of ignorance. I don't discuss it with Michael. There's honestly no reason for that other than I consider myself like the editor of a newspaper. The circulation people are in charge of bringing in the money and the editor is in charge of getting the stories out. Any good newspaper works that way.

I saw many people mention Linux.com as being 'better' than Linux.org.
Well, Linux.com is part of the whole VA Linux website company (Slashdot, Newsforge, etc.) and they have had no problems running *Microsoft* ads, as has Linuxtoday.com. Michael has told me on many occasions that he will *never* run Microsoft ads and I suspect that he has been offered that opportunity on a few occasions. And this could be very lucrative, but we won't do it. I can also personally tell you that the day a Microsoft ad appears on the site, is the last day I work for linux.org. I don't like seeing paid links to gambling and medicines either, but at least we're not making deals with Microsoft like VA Linux.

When I started out in 2000 here, there were seven of us. Now there are just two of us, Michael and myself. Until last year we had a guy named Magnus maintaining the Perl backend to the site. He left and stuff gets broken and I end up having to do magic acts to keep some content maintained. Some of it is just so broken that it doesn't work. I end up doing MySQL inserts by hand.

Again, I don't know anything about the actual state of the finances, but I suspect that if we had the money, we'd have hired a guy to *at least* take Magnus' place. So that should be told to the people who are out there saying that we're making a fortune in advertising. We're not.

If we were, you'd have a nice professional looking site and I wouldn't be making MySQL inserts on the command line. Michael runs the servers himself and that takes, I assume, most of his time. We have to pay for the bandwidth (2 T1s) and the electricity which, I assume, takes up a large portion of the budget.

I would also like to mention the personal attacks on Michael McLagan that I saw. It just proves that some people know how to use Google and that's about it. Repeating hearsay that's almost 10 years old is not much of an argument. One may think the present look of Linux.org hurts the Linux community, but they should be thankful that Linux.org is in the hands of who it is. I have been told of six-figure offers for the domain from a lot of companies. Many of these you wouldn't want to have it - people who would *really* hurt Linux. Michael has constantly said that Linux needs an independent voice and that's what we are. That's why he's held on to the site.

You're in your rights to publish your opinion because I think it's good for the community to debate whether one of its flagship sites is not presenting the best face of Linux to the public. I personally think that we can do a lot better, though we try very hard. If some ambitious web developer out there wants to submit a design to us, we'd be honored to consider it and I personally would do my best to lobby in favor of the best one. If there are any perl hackers out there who want to send me their opinions on how to best handle maintenance of our list of Linux applications, Linux user groups, Linux companies and other parts of the site, I would welcome that input. After all, we want this to be a site for and by the Linux community. That's all we've ever pretended to do.


Sent by Webmaster (includes Ago's reply to previous email), 16th of September

> Why don't you simply ask for some cooperation? I am absolutely sure
> that you will find literally dozens of talented people willing to
> collaborate. All you have to do is create some sort of project. You
> have to understand that many people would like to give something back
> to the Linux community and for many there simply is no better chance
> than this one. But you also need to realize what are the implications
> of managing the website in the spirit of an open source project.

I think you're confusing open source software with an internet site.Everything that we publish on the site is 'open' to the public.But the management of the site isn't 'open source'. Not even Linus Torvalds accepts code from just anyone. He's also in control of the kernel and the final decisions are his. We've accepted volunteer work in the past. In our experience, however, this hasn't worked out too well.For example, I have started working with people to translate the courses into other languages and on every occasion people have gotten tired of it and you're left with unfinished work. There are other instances that Michael can give - before I got here - where a sort of 'open' approach to maintaining the site just went nowhere.

Again, that's not to say that we can't accept redesign ideas or other things like that, like I mentioned before. We *always* accept ideas and we try to implement the feasible ones.

> More technically inclined people tend to like the website, and
> particularly the lessons. But these days Linux is entering the desktop
> market and people that hardly know what a partition is are turning
> their eyes to Linux. The demographic of Linux users has changed,
> Linux.org has not, and it should catch up.

I'll say it again (for the nth time), that I think the website needs a new look and certain features of its navigation need revamping. But I don't think it turns off new Linux users. Unless you have scientific polling to back up your claims that it does, then my opinion is just as valid as yours. You also have to remember that I see and respond to all of the email sent here and most of it is overwhelmingly positive and a lot of this is from newcomers to Linux.

> Try to put yourself in the shoes of someone that has just heard of
> Linux and wants to learn more. He has to decide what OS to use. He
> opens the Apple website, the MS one, and then Linux.org.
> Honestly, what will be his reaction based on those 3 websites?

I don't visit the MS or Apple sites, so I honestly can't say. I think it's more valid to compare it to other Linux sites. Besides, I don't think people use Windows because they've visited the Microsoft website, so I think you're argument is pretty weak.

> Please do not take it personally. It is a fact that you are competing
> with the best web designers in the world. You are alone, they have
> full teams exclusively dedicated to the job. This is not 1994, the
> audience is not the same, and we need to level the field. The way OSS
> is competing successfully against giants in the software world is via
> the cooperation of thousands of users, I do not see why it should be
> any different for the main Linux website.

>> As far as revenue goes, I don't handle that so I can't really
>> comment too much on it. That's not out of secrecy - it's out of
>> ignorance. I don't discuss it with Michael.
> Unfortunately I think this is an issue.
> Do not misunderstand me, I have nothing against advertising and making
> money out of a domain. But there must be a limit to what you can do,
> and to me Michael went over that limit. I do not think anybody can
> deny that the ads are excessive and some of them are even
> inappropriate. It would be certainly possible to make money from the
> website in more discrete ways and nobody would object to that. Add to
> it that it would not be a problem to find donated hosting. If hosting
> and bandwidth are your main expenses, why don't you take care of them
> directly instead of polluting the website?

We are totally open to suggestions on how to better finance the website. As far as being hosted or our handling it on our own, it's not my call. I don't care one way or the other. I assume that we are doing the hosting ourselves because it's the best way to do it in our cirucumstances. It's not my department. It's like asking the editor of a newspaper which paper company he prefers.

> You cannot justify your behaviour by claiming that others have done
> worse (and I would object that having MS ads is worse than having
> casinos ones). The ads of casinos and pills are an abuse of the Linux
> trademark and an abuse of the original spirit of the .org top-domain,
> and they are certainly affecting negatively the Linux image and that
> of the whole community. Such behaviour makes me question the real
> objective of the website.

I don't share your opinion that running Microsoft ads on a Linux website is better than running the paid links for casinos. These casinos have never publicly stated that their aim is to destroy Linux.Is it the best way to finance a website? Probably not. I told you that in my last email. And if you believe that they represent an abuse of the Linux trademark, then I would suggest you file a complaint with the Linux Mark Institute. When you say that advertisements are negatively effecting the Linux image, remember that it's just your opinion -unless you have done scientific polling to back it up. The objective of the website is to present information about the Linux operative system in an independent way. There's no hidden or other *real* objective that I know of. If there is, it's been hidden even from me.

To sum up with couple of bullet points:

* Casino gambling links seem to be the only alternative at this point.Microsoft ads will never run. We are seeking better adverts and open to suggestions. Some kind of adverts need to run. There's no other way to pay the bills.

* Googling 'Michael McLagan' and cutting and pasting the opinion of somebody who had an argument with him in 1998 is not a constructive way of improving the linux.org website.

* We are very aware that the website needs a new look. Navigation could also be improved. I have personally worked on this and I am awaiting a green light to go ahead with changes. But there's a wealth of information here under a scruffy exterior.

* I disagree with the conclusion that linux.org hurts Linux. There are a lot of things that *really* hurt Linux. There are a few wolves in sheep's clothing in the Linux community. They deserve more discussion than Linux.org's out-of-date looking website.

I am giving you my permission to publish what you see fit from these emails. I think the gist of what I'm trying to say is in these final bullet points. I would appreciate you getting the gist of these on your blog if you're planning on posting more about it.


Sent by Ago, 18th of September
> I think you're confusing open source software with an internet site.

I am not. I said "in the _spirit_ of an open source project". There
are several examples of websites maintained by community efforts. If
you find it difficult to get people involved in THE Linux website,
maybe you should ask yourself why that is the case.

> But I don't think it turns off new Linux users.
> Unless you have scientific polling to back up your
> claims that it does, then my opinion is just as valid as yours.

It is not "just my opinion". Several people have confirmed my
impressions, in fact the vast majority of those who posted on Digg, on
Ubuntu forum and on my blog share my opinion. It may not be a
"scientific" poll, but pretending those voices do not exist is not
going to do you any good...

> Besides, I don't think people use Windows
> because they've visited the Microsoft website,
> so I think you're argument is pretty weak.

As we all know, for many people buying a new PC the question will not
even arise since Windows will be preinstalled. But there are many
others wondering whether they should by a boxed Vista to replace XP,
or whether they should install Linux on their old machine and replace
Windows 98/ME/2000/XP/OSX, or whether it is worth to free-up a second
partition, or whether they should spend some time to find a new PC
with Linux preistalled. All those people will look for some
information on Linux before making their choice. Isn't your website
going to be the most likely place they will stumble upon? Will your
website foster them to try Linux? What do you think?

> * Casino gambling links seem to be the only alternative at this point.

You seem to imply that the only sources of revenues can be either MS
or Casinos. Quite hard to believe. Not to mention that it is hard to
believe that donated hosting was such an impossible proposition, that
the "best" way out was to accept Casinos and Pills as sponsors. And it
is hard to believe that the bandwidth costs so much that you need to
pollute every page with several ads, particularly considering your
page rank.

Monday, September 04, 2006

Is Linux.org hurting Linux?

Exercise: try doing a google search for "Linux" and check out the first website that comes out in the results page. It is Linux.org. It is not the official Linux website (there is no such a thing, save maybe kernel.org), but in practice, millions of people believe it is, and for most it represents the very first face of Linux they will have the pleasure to meet.

Is it a nice, modern, exciting page fostering Linux adoption?

Hardly so. Even worse, far too many energies seem to be dedicated to raising money, which would not be not a negative fact per se, if the money bit did not look like the main purpose of the website:

  • Banner on the top
  • Banner on the left
  • Banner on the right
  • Banner on the bottom
  • ContentLinks in the middle (with all those lovely pop-ups)
  • Another banner on the left
  • Bookstore
  • Hardware manufacturers
  • Vendors
  • Subscriptions
  • Donations
  • Advertise with us
The bottom banner deserves a special mention. It contains a table of "sponsored links". Guess who is sponsoring Linux:
  • River Belle Casino
  • Lucky Nugget Casino
  • Jackpot City Casino
  • Gaming Club Casino
  • weight loss pills
  • online casino
  • online poker
  • Best online casino
  • Health and Fitness Forum
  • #1 Best Web Hosting Messenger
  • Linux Gifts for all occasions!
  • Buy Vitamin Supplements
  • Online bingo UK
  • Online Casinos
  • Online Slots
  • Online casino
  • Online Backgammon: Linux
  • Online Casinos
  • myblog.typepad.com
  • Casino Software
  • Online Casino Offers
Screenshot as of 4-Sep-06:


Take your pick. All in the main page of the main Linux website. And remember that we are talking about a website that is #1 in the google search for "Linux", something they are well aware of and monetizing upon:

Advertising: Media Kit

Linux Online, the primary online resource for the Linux Operating System since 1994, has earned the respect of the Linux community and the media. Our site is featured regularly on television and radio, and in newspaper and magazine stories about the success and popularity of Linux. The major search engines list Linux Online as the first destination when searching for the term "Linux". In addition, both Netscape Communicator and Internet Explorer refer their users to Linux Online when "Linux" is entered in the location field.

The Obvious Way

Linux Online provides an ideal starting point for current and future user's journey into the Linux Operating System. Network administrators, IT managers, and the average user come to Linux Online to find out about the operating system as well as to learn about the latest products and services available for use with this innovative and well-proven OS. With over one million unique visitors per month, Linux Online will give your advertising campaign a much wider audience than any other Linux website available today. Simply put, there is no better opportunity for your company to promote its Linux product or service than Linux Online!

Very Desirable Audience

Linux Online can bring to your company or organization a slice of the most sought after marketing and advertising audience in the industry. Based on a recent survey, we found that the typical Linux Online visitor is male, 31 years old, earns $42,000 US per year, has a post-secondary degree and uses Linux on his home PC. 73% of our Linux Online visitors are responsible for purchasing computer equipment, software, and services for PCs for end-use or for their company. With over 58% of those buyer's responsible for a department or entire company, we've got your market's attention! Additionally, 29% put Linux to use in their work environment.

Benefits

Linux Online is a popular gathering place for the Linux community where current and potential Linux users can find the latest news and information about Linux and Open Source. You will reap the benefits of our experience with launching successful advertising campaigns by our commitment to making your campaign as effective as possible. Among the benefits you receive by advertising with Linux Online:
  • Your advertisements appear on a site designed to connect consumers with valuable Linux resources, products, services, and applications.
  • Exposure to over one million unique visitors and five million total hits per month to make sure your product or service is seen.
  • Priority listing in the vendors area of Linux Online. Vendors are normally sorted by country and then alphabetically. As an advertiser on Linux Online, you will be placed at the top of your respective country/area ahead of the alphabetical list.
  • Free impressions on the Linux Online ad directory. Directly below banner advertisements is a link to a page showing all the current ads on the site at http://www.linux.org/advert/bin/directory.
  • ...

The official objective is to promote Linux, but is it the only objective?

"You will reap the benefits of our experience with launching successful advertising campaigns by our commitment to making your campaign as effective as possible".

And all this is needed to support the website?

Well apparently it is not enough. Donations are also welcome: "Linux Online is a community supported web site. We need the help of visitors, like you, to pay the day to day costs of operating this site."

Really? Did anybody even bother to look for donated hosting instead of donated money? I have seen far lesser Linux websites hosted for free, would it be so problematic to find a real sponsor for a change?

Moreover, it does not look to me that much has been invested back into the website in the past 12 years. The page looks and feels like a site straight out of the early 90's which is what it basically is, even the information is a bit dated and sometimes even confusing, hardly something to encourage users to try Linux.

How is the image of Linux going to be affected by having casinos and pills advertised on its main page? If an enquiring soul stumbles upon this website when investigating whether to use Linux on his desktop, is the 90's revival feast going to convince him? How many users have already been turned off?

So is Linux.org helping Linux or not?

Friday, January 13, 2006

Scite html export function

After looking for some code-to-html converter to post the code of my previous blog, I discovered that I had it just under my nose... Scite, one of my favourite editors, has a nice Export as Html function... All I had to do was add the css part to my template and insert the rest of the text in the post. I also used a div tag with attributes ( div class="alt2" style="border: 1px inset ; margin: 0px; padding: 6px; overflow: auto; width: 640px; height: 498px;") to make the code appear in its own window.

Sudoku Solver in Python

A few months ago, my wife gave me a book with sudoku puzzles. After solving a couple by hand, I decided that it was much more fun to try and write a solver...

My first implementation was a quick hack, the code was brief and ugly with lots of index operations in a bad functional programming style, but it worked well. It used only solution-reduction algorithms, no brute force. As such not all sudoku puzzles could be solved, but the ones that could, were solved pretty fast. Satisfied with my little achievement I soon forgot about it...

Then, recently, I read this article on LinuxJournal. The program in article was unfinished (the third part has still to be published), but the code was much tidier than mine. I took some inspiration to rewrite my solver in a more pythonic way. After that I stumbled on the ASPN recipe, which gave me the idea of adding a brute force solver.

The result is a combination of analytic and brute force solvers that performs 2 or 3 orders of magnitude better than the ASPN code.

Enough talk, here it is:

#!/usr/bin/env python
#
# sudoku-solver version 3
#
# Some ideas ripped-off from:
# http://www.linuxjournal.com/article/8729
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440542
# Pavol solver in
#    http://groups.google.com/group/comp.lang.python/browse_thread/thread/5087890f4c5e770d
#
# Copyright 2005 Ago,
# But you are free to copy, reuse, modify and distribute the code as you see fit

from copy import deepcopy
class DeadEnd(Exception): pass


class Matrix:
    def __init__(self, input):
        self.rows = [[] for i in range(9)]
        self.cols  = [[] for i in range(9)]
        self.submatrices = [[] for i in range(9)]
        self.cells = [Cell(i,self) for i in range(81)]
        self.subdiagonals = [self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
        input = [s not in '-*' and int(s) or 0 for s in input if s in '0123456789-*']
        for cell,val in zip(self.cells, input):
            if val: cell.setSolution(val)

    def solve(self): #Brute-force solver
        self.solveByReduction()
        lensols=[(len(c.solutions),c.index) for c in self.cells if not c.solved]
        if not lensols: return True
        unsolved = min(lensols)[1]
        solutions = list(self.cells[unsolved].solutions)
        for s in solutions:
            tmpmatrix = deepcopy(self)
            try:
                tmpmatrix.cells[unsolved].setSolution(s)
                if tmpmatrix.solve():
                    self.update(tmpmatrix)
                    return True
            except DeadEnd: pass

    def solveByReduction(self):
        while True:
            self.changed = False
            for c in self.cells: c.solve()
            for c in self.subdiagonals: c.skim()
            if not self.changed: break

    def update(self, m):
        self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\
            m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals

    def __str__(self):
        return "\n".join(str([c for c in row ])[1:-1] for row in self.rows)


class Cell:
    def __init__(self, index, matrix):
        self.solved = False
        self.matrix = matrix
        self.index = index
        self.row = matrix.rows[index/9]
        self.col = matrix.cols[index%9]
        self.submatrix = matrix.submatrices[((index/9)/3)*3+(index%9)/3]
        self.row.append(self)
        self.col.append(self)
        self.submatrix.append(self)
        self.solutions = set(range(1,10))

    def solve(self):
        if self.solved: return
        if len(self.solutions) == 1:
            self.setSolution(self.solutions.pop())
        else:
            sol = set()
            for cells in [self.row, self.col, self.submatrix]:
                otherSolutions = self.cells2sols(cells, self)
                sol |= (self.solutions - otherSolutions)
            if len(sol) > 1: raise DeadEnd()
            if sol: self.setSolution(sol.pop())
    
    def skim(self):
        submatrix = set(self.submatrix)
        for r in  (set(self.row), set(self.col)):
            subset1 = submatrix - r
            subset2 = r - submatrix
            solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2)
            solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1)
            for c in subset1: c.delSolutions(solsNotIn1)
            for c in subset2: c.delSolutions(solsNotIn2)
    
    def setSolution(self, val):
        self.solved = True
        self.solutions = set((val,))
        self.matrix.changed = True
        for other in self.row+self.col+self.submatrix:
            if other is self: continue
            if other.solutions == self.solutions: raise DeadEnd()
            other.delSolutions(self.solutions)
    
    def delSolutions(self, val):
        if not self.solved and val & self.solutions:
            self.solutions -= val
            self.matrix.changed = True
            if not self.solutions: raise DeadEnd()
                
    def __repr__(self):
        return str(self.solved and list(self.solutions)[0] or list(self.solutions))

    @staticmethod
    def cells2sols(cells, exclude=None):
        return set(s for c in cells for s in c.solutions if c is not exclude)


if __name__ == "__main__":
    input ='''
0,0,0,0,9,6,8,0,0
0,0,1,0,0,0,0,7,0
0,2,0,0,0,0,0,0,3
0,3,0,0,0,8,0,0,6
0,0,4,0,2,0,3,0,0
6,0,0,5,0,0,0,8,0
9,0,0,0,0,0,0,5,0
0,7,0,0,0,0,1,0,0
0,0,5,9,4,0,0,0,0
'''
    matrix = Matrix(input)
    matrix.solve()
    print matrix