New Su Doku puzzles in The Times

The boxes don't have to be 3x3; these puzzles can be composed based on any partition of the square into 9 sections of 9 cells each. Games magazine has printed a set of these puzzles from time to time in the last while, and each set has used a number of different partition layouts. (I don't remember what they called them, but it wasn't 'number place' or anything in Japanese.)

For that matter, the choice of 9 for the number of symbols and the number of cells on a side is also arbitrary, although a more convenient choice than some, since it allows for the 3x3 partitioning.

First, a couple of variants, which can be combined: (a) larger grid (16x16 made of 4x4 proves to be quite challenging); (b) the long diagonals also contain each number from 1 to N exactly once.

Personally, I tend to get good results by applying the pigeonhole principle, and coming up with 'the 7s must go in these squares'.

XXX XXX XXX XXX XXX XXX XXX XXX XXX

... ... ... ... ... ... ... ... ...

... ... ... ... ... ... ... ... ...

The squares marked with X must contain exactly three 7s, each in a different row, and each in a different 3x3 box.

YYY ... ... YYY ... ... YYY ... ...

YYY ... ... YYY ... ... YYY ... ...

YYY ... ... YYY ... ... YYY ... ...

Similarly, the squares marked with Y must contain exactly three 7s, each in a different column, and each in a different 3x3 box.

Any comments on the solver at http://act365.com/sudoku would be welcome. Currently, it only handles the vanilla Su Doku (is it one word or two?) problems that appear daily in The Times, not the exotic variants described elsewhere on the thread.

Well, it works on at least one example, which is good enough for my typical test regime What's your method, iterated application of 'this must be X' / 'these can't be Y' rules?

This comment of yours raised an eyebrow though:

Although the problem will be far from straightforward for most readers to solve, an average home computer will be able find the solution in little more than a second. The code that drives the Su Doku solver that appears on this page is very brief - and far from optimal - but it is still able to make problems The Times categorizes as 'Very Hard' seem trivial. In my humble opinion, this shows that the Su Doku problem is not a worthy companion to the chess and crossword puzzles that appear in the same supplement.

and set me to wondering about the various *types* of puzzles we see here and elsewhere.

I suspect that these days a typical chess *problem* can easily be bruteforced by a home computer in a matter of seconds, seeing as this problem space is a very different one from the more general and much harder 'play a game of chess', so I don't know that that makes a good counterpoint.

As for a quality cryptic crossword - I count these as the acme of the puzzling world; it seems to me that getting a program to reliably solve these would be as hard or even harder than beating the Turing Test - seeing as there are humans who can convince humans they are human but yet cannot solve cryptic crosswords! (On the flip side, we have tasks that would not be regarded as puzzles at all - recognising one's grandmother, for example - but which computers still struggle with, neural networks &c notwithstanding)

In the final analysus, both chess problems and crosswords are accepted as puzzles worthy of human endeavour, and it's surely for this reason - they are hard *for people*. We do see support for the idea that brute-force-able problems are less worthy - I believe we've seen in this group that the 'can't solve with Excel' Enigma reposts from New Scientist are preferred to those susceptible of such solution - but more generally, anything that provides a challenge for the solver armed with nothing more than 'a pencil, lots of paper, and a clear head' is good enough, isn't it?

The bottom row and buttons are cut off when I try it. (Red Hat 9, Firefox 1.0, Java 1.4.2)

Sorry - I'd only tested it on Windows XP with Internet Explorer 6.0. I'll post to the forum again as soon as I've fixed the problem. The issue is that the display size embedded within the APPLET tag is interpreted differently by different browsers.

I've tried to explain the algorithm on the FAQ page http://act365.com/sudoku/faq.htm - please let me know if the explanation is inadequate. The source code is available. Look at the Grid.solve() method if you're a Java programmer.

Perhaps my comment is a little harsh - I wrote it in a state of disillusionment after I'd found that my very basic solver appeared to crack even the hardest Su Doku problems.

Agreed, but the algorithms within chess software have been refined over many years. I'm particularly dismissive of Su Doku because the solver took me less than an evening to write.

Crosswords probably represent the acme of the puzzle world but I couldn't comment - the only crossword in The Times that I regularly complete is the one in the Sports section - and I couldn't do that today!

Certainly, the Su Doku problem has provided me with an interesting challenge over the last couple of evenings - however, I feel that the ease to which the problem has fallen to the computer has firmly established the hierarchy: Crossword puzzle > Chess puzzle > Su Doku puzzle. Even when the human solves Su Doku with 'human-style' logic, he essentially uses elimination as his main tool, i.e. he knows that there are only nine possible values for each square, so he has to discount eight of them. Surely, this simple process of elimination is an inferior form of mental activity to the verbal creativity one must employ in order to solve a good crossword puzzle. I concede that the Su Doku puzzle is sufficiently taxing to be afforded the status of a source of pleasure, however, I feel that the inferior form of reasoning employed in its solution means that, unlike a crossword, it could not be afforded the status of an activity that usefully trains the mind.

Anyway, it's gone midnight, so it's time to come down off my soapbox.

Goodnight all,

I debated with a friend (over a decade ago, now that I think about it) about whether a computer could solve a cryptic crossword. He made the case that a computer could, using the following method:

1. Search for every possible combination of words that could fill the grid, then 2. Search for matches between the words' definitions and words in the clues given.

At the time, I argued against the idea, but now it looks pretty plausible, as long as the words in the finished puzzle are contained within the computer's word list.

A plausible step 3 might also be to keep an eye out for words in the grid whose anagrams can be found in consecutive words in the clues.

The current development branch contains a rudimentary Su Doku composer. However, I'll have to improve it quite a bit before it's ready to see the light of day (which it will as part of Release 1.2). So far, its best puzzle has 24 cells:

*** *** 7*9 4*6 7** *2* *8* *** ***

*1* *65 *9* 3** *** **4 *9* 21* *6*

*** *** *7* *4* **8 5*1 9*8 *** ***

I think the symmetry is pleasing, though the solver makes short work of it.

This is not surprising, since it's trivial to do by hand. Filling in the first 20 gaps with the most obvious guess: 123 456 789 456 789 123 789 123 456 causes the rest to follow in about 25 seconds of light effort.

Maybe you should tell the composer to use the recommended password selection strategy of avoiding obvious keyboard patterns!

You're right - perhaps it would have been clearer if I'd said that you'd find it difficult to prove the uniqueness of any solution to the puzzle.

The current version of the solver will, when there's nothing blatantly better to do, start at the top-left corner and fill empty squares with the values 1, 2, etc. in sequence. Since the puzzle composer is closely related to the solver, the composer tends to create puzzles with solutions that correspond to this pattern. Although the human will say that such problems are easy to solve, the mathematician (I assume there's an intersection somewhere) will argue that your decision to fill the grid 1, 2, etc. is entirely arbitrary and had the puzzle been translated by a random mapping, say {1,2,3,4,5,6,7,8,9} to {3,6,1,2,9,4,7,5,8}, the human would have found the problem much more difficult to solve, though, to the mathematician, the problem would have been essentially unaltered.

In summary, the current version of the composer generates problems that are difficult for mathematicians but not for humans!