Sunday 6 May 2007

Matchpeg Sudoku

We're often asked, "Why does Matchpeg have a Sudoku solver?" And also, though not usually by the same people, "How does it work?"

Important information for non-Brits: it is compulsory for every British newspaper to print at least one Sudoku puzzle daily. The freesheets for London commuters typically have three (which gives you an insight into the average journey time of a commuter into London, and the fact that these freesheets are only distantly related to "newspapers", and have rather more in common with the puzzle compendiums which you can buy in any airport before undertaking a seventeen hour flight in steerage).

More useful background information: British newspapers are well known for their bouts of collective mania. Their peerless executives reach a more-or-less simultaneous decision to fill them with spot-the-ball competitions, bingo, vouchers for free flights and meals in restaurants, free DVDs. Sudoku was the last-but-one or -two of these crazes.

The creation of Matcheg Sudoku was prompted by The Guardian printing one of these witless puzzles on every single page of its G2 supplement. This spoiled a perfectly nice breakfast, and writing a tool to solve them provided a handy little intellectual challenge to kick off the working day.

We stuck the solver on the site because we feel it chimes quite nicely with Matchpeg's aim of solving business frustrations.


How it works.

From a programming perspective, solving a Sudoku puzzle is mainly a simple exercise in recursion. The best method seems to be to keep track of all the values which a particular cell can't be. For example, if the cell in the top-left corner is known to contain 5, then the twenty other cells in the first row, first column, and first block can't contain 5.

Each time you set a known value, you record these 20 knock-on values. And each time you record a value which a cell can't be, you do two checks:

  • Does the cell now have eight values which it can't be? If so, it must be the ninth.
  • Is it now known that eight of the cells in a row, column, or block can't be a particular value? If so, then the ninth cell must contain that value.

When you discover a new value as a result of either of the above, you fill it in and process the 20 new implications of that. So, setting a single cell triggers recursive calls setting the values of other cells.

This method by itself solves the vast majority of Sudoku puzzles - typically, everything other than those rated as "very hard".

The next step involves looking for cells in a row, column, or block where only two of the cells can contain a pair of values: for example, there are only two cells which can contain 4, and the same two cells are also the only ones which can contain 8. If so, then you know that those two cells must contain either 4 or 8, and you can eliminate anything else on their can't-be list.

We've never seen a puzzle where this extra step actually gives a solution rather than just narrowing things down a bit. You could apply further subtle logic to the solution, but that's more computationally expensive than simply brute-forcing the puzzle from this point onwards. In fact, the check for pairs usually takes longer than its benefits merit: it's quicker to skip this check, and just brute-force the solution without first looking for pairs.

So, if the Matchpeg solver can't work out the puzzle through simple logic, it starts guessing. This falls into two parts: trying out guesses for single cells in isolation, and and then trying out a combination of guesses for multiple cells if necessary.

The first part simply consists of going down the grid, taking every value which each individual unknown cell could still be, and seeing what happens if that value is filled in. There are three possible results from trying out each one of these isolated hypotheses:

  • The value can't be right. Its knock-on effects are that the grid must be invalid (i.e. duplicate values in a row, column, or block).
  • Filling in that one value solves the puzzle. In other words, the hypothesis becomes a lucky guess.
  • It makes no difference. Filling in the value neither solves the puzzle nor is impossible.

Recording the hypotheses which can't be right (and their knock-on effects) usually means that you then hit a "lucky guess" very quickly. You typically only need to try out about 10 hypotheses before you get a solution.

In a very, very small number of cases, no single cell by itself gives the solution. You have to try out a combination of guesses for multiple cells at once.

The Matchpeg solver builds a list of the hardest remaining cells, and then tries all the possible combinations of the two hardest cells. If that doesn't work, it tries all the permuations of the three hardest. And then four, and then five.

However, we've never seen a puzzle which requires guessing four or five cells at once. The "world's hardest Sudoku puzzle" gets solved from the combination of guesses for only three cells.

Wednesday 2 May 2007

NEW feature - central list of RSS feeds

As we hope you already know, Matchpeg makes a very large number of RSS feeds available. For example:
  • Feed of all your pending meetings
  • Feed of all your incomplete action points
  • Feed of all your pending brainstorming sessions
  • Feed of all your current workflow items
  • ...Plus individual feeds for each meeting, workflow item, and brainstorming session
However, no web browser has quite cracked the issue of advertising feed-availability to people. Therefore, in order to make them more prominent and better-known, we've added a central list of the main feeds. This is accessible using the new "RSS feeds" link on the right of the Dashboard.

(If you have no idea what RSS is what are you doing reading a blog? we suggest that you read a generic introduction to the subject, such as the one published by the BBC. All Matchpeg's feeds can be added to places such as a Google home page.)

Tuesday 1 May 2007

NEW feature - full help file

Matchpeg's context-sensitive help file is now complete - i.e. full documentation of the system in addition to the Getting Started guides, the brief help text displayed on each screen (e.g. at the top of boxes), and all the various tooltips.

Now that the help file is complete, help on each page can be viewed in either or two ways:

  • Click on the new help icon in the top right of each page

  • Or just press F1

The "Help" link in the "Help and support" section on the Dashboard continues to link to the first page of the help file.

We recommend that everyone - though particularly new users - reads the "hints and tips" section of the help file. Almost everyone will already know 80% of the information in this, but it will be a different 80% for each person, and the remaining 20% may well turn out to be valuable information.

Introducing the Matchpeg Introducer scheme

Big drum roll for the launch of... the Matchpeg Introducer scheme.

The basis for this is simple, and it's worked really well in our previous ventures: word-of-mouth recommendations are much more effective and much cheaper than any other form of marketing, and anyone who recommends us to their friends and colleagues deserves a share of the proceeds.
  • You sign up as an introducer.
  • You put a link to Matchpeg on your website/blog.
  • People sign up with Matchpeg after coming to us via your link.
  • We pay you commission whenever your referrals spend money with us.

We also provide other kinds of marketing support such as e-mail templates which you can use when contacting your friends and colleagues about Matchpeg.

You can even introduce other introducers: if someone becomes an introducer themselves after coming to Matchpeg via you, then you can earn extra commission on their referrals. (No, this is not a Ponzi scheme. Payments to introducers don't come from payments by other introducers. Registration as an introducer is free.)

Thursday 26 April 2007

Welcome to Matchpeg

Welcome to Matchpeg, the site for relieving business frustrations and delivering results.