Sudoku #37

Category: Sudoku
Sun, 31 Jul 2005, 14:13

What's the minimum number of seed values needed for a Sudoku puzzle with a unique solution? I will go out on a limb and say that no fewer than 24 seed values are needed.

I don't have a mathematical proof for my assertion, but my Sudoku program has now been running for almost one full day now looking for a puzzle with no more than 23 start values. And it still hasn't produced a puzzle. I'll let it run a little longer, but my gut tells me it won't find anything.

Todays puzzle, like most that I post, has 24 starting values.

Hans

    7
     
  3 5
    4
  1  
     
     
    2
  4  
     
2    
7 8  
4    
9   7
    5
  3 6
    1
     
  9  
3    
     
     
  4  
8    
2 8  
     
9    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #36

Category: Sudoku
Sat, 30 Jul 2005, 15:42

Astronomers recently announced the discovery of a new Kuiper Belt Object (KBO), orbiting beyond Pluto. Tentatively named "2003 EL61", it is interesting because it may be the first KBO discovered that's bigger than Pluto. This would then add more fuel to the argument that Pluto should not be considered a planet.

As one astronomer describes, the solar system contains six types of objects: a star, rocky planets, asteroids, gas giant planets, Kuiper belt objects, and the Oort cloud. Each class of object has its own unique characteristics. Although most people like to call Pluto a planet, it has much more in common with KBO's. In fact, there's no useful classification system that puts Pluto in the same class as other planets without also including some asteroids and other KBO's.

Already, at least one major planetarium omits Pluto from its list of planets. And so now with the discovery of a KBO that's likely bigger than Pluto, it may well be time for people to start getting used to the idea of a solar system with just eight planets. Even if it turns out that 2003 EL61 is not bigger than Pluto, astronomers believe it's just a matter of time anyways before such a KBO is discovered.

The puzzle I had first intended to be #36 turned out to be too easy after I fed it to a more recent version of my Sudoku solver. So I'm posting something else. Todays Sudoku puzzle might be the toughest I've posted yet!

Hans

  9  
     
    7
     
7   8
    5
  6  
     
4    
  6  
  4 3
  8  
5    
     
    2
  8  
1 9  
  4  
    9
     
  2  
4    
9   1
     
3    
     
  1  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #35

Category: Sudoku
Fri, 29 Jul 2005, 16:21

Well, it looks like the Space Shuttle fleet is grounded again. During the launch of Discovery earlier this week, cameras detected a piece of foam insulation falling off its external tank. NASA engineers want to study the problem further before letting another shuttle fly.

This only confirms my paranoid suspicions about NASA's manned spaceflight program. NASA and its aerospace contractors have little interest in putting men into space. The aerospace industry is quite happy to accept government contracts to study, design, and even build prototypes. But when it comes to actually putting people into space, they run the risk of astronauts getting killed. And nothing affects access to the pork barrel as much as bad press from crashes.

By any credible quantitative measure, NASA's shuttle program has been a big failure. It was supposed to bring the cost of spaceflight down substantially. However, with a cost of at least half a billion dollars a flight, it's been anything but affordable. Sure, it's given us some spectacular images, but for cost-effective access to space, nothing beats unmanned rockets and satellites. Consider the Hubble telescope. For the cost of the five shuttle missions devoted to Hubble, NASA could have built and launched at least two replacement telescopes!

Now then, I'm not against the idea of men in space. I just think NASA needs to better define its role in that endeavor. Is NASA a research and development organization? Or is its goal putting men and cargo into space? These two goals are contradictory. If NASA is to be an R&D company, that's fine. We need an organization that's willing to invest in research, pushing technology to its limits. But a space transportation company has other needs. If the goal is to put things and people into space, a company needs to do so in the most reliable and cost-effective manner possible. And that often means staying away from bleeding-edge technology.

Back on Earth, as I promised a couple of days ago, here's another puzzle with mirror symmetry. In this one, there are three blank groups intersecting at the lower right.

Hans

     
    2
  3  
3   1
    8
  2  
    7
5    
9    
9    
    4
3 5  
    3
     
9    
7   8
6    
     
  4 9
     
1    
5 6  
     
2    
     
     
     

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #34

Category: Sudoku
Thu, 28 Jul 2005, 08:53

Previously, I talked about rewriting my Sudoku program from Python to C to improve its run-time performance. Not content to leave well enough alone, I decided to try to improve performance a bit more by tweaking the algorithm.

(The following discussion is probably of interest only to computer programmers. For others, feel free to skip ahead to todays puzzle.)

First, let me summarise how I first implemented the basic Sudoku solving methods. Function set_cell() is called to set the value of a cell. Function eliminate() is used to eliminate a possibility from a cell. And function resolve() locates a cell in a group with a unique possibility within the group. The three functions were mutually recursive. For example, function set_cell() would call eliminate(), which might then call set_cell() if the number of possibilities for a cell dropped down to 1.

The performance enhancement I wanted to try was to just consider the unknown cells within a group, rather than all of them. The idea was that each group would be partitioned into two areas. When a cell gets set a specific value, the cell would be then be moved into the bottom half of the group, and further analysis would then consider just the unknown cells at the top of the group.

Unfortunately, the recursion of the three basic functions meant that cells would get set and unique possibilities searched for before certain possibilities were eliminated from all of the cells of a group. Which meant that function resolve() could see a unique possibility in the unknown portion of a group where the possibility was already set in the known portion. This caused the program to blow up real good.

The answer was to implement another performance improvement, changing the recursive algorithm into an iterative one. Function eliminate() would now eliminate possibilities from all cells of the group before proceeding. If new cell values get discovered, they would get added to a list, to be processed on a subsequent iteration of the loop. One reason this would help performance is that function resolve() would not get called multiple times as the recursive calls wound back down the call stack.

What kind of improvement did I get from these two changes? My old program could generate about six puzzles per minute. The new one could now produce about 28 puzzles per minute. That's more than a four times improvement!

With this one application, I've now demonstrated three ways you can improve performance in your code: First, use a compiled language; second, find a better algorithm; and third, convert a recursive algorithm into an iterative algorithm.

And now, on to todays Sudoku puzzle.

Hans

1    
    3
2    
  8  
4    
     
     
     
5 8 3
  9  
5   7
     
1    
     
    7
     
6   4
  9  
4 1 6
     
     
     
    2
  9  
    5
7    
    8

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #33

Category: Sudoku
Wed, 27 Jul 2005, 08:44

For a change, here's a puzzle with mirror symmetry instead of rotational symmetry.

This begs the question: What makes up a good Sudoku puzzle? One aspect is the puzzles appearance. Symmetry may not be essential to a good puzzle, but it makes the puzzle more pleasing to the eye. There are several types of symmetry, with rotational symmetry the most common in published puzzles. But there's no reason you can't have mirror symmetry, with the axis of reflection diagonal, vertical, or horizontal. And some published puzzles have more than one degree of symmetry.

Puzzles can also vary in the number of cells with initial seed values. Some equate the number of starting values with the level of difficulty. But although a greater number of start values may make a puzzle easier, you can still have an easy puzzle with as few as 24 start values. (A related question is: Is there a minimum number of start values required for a puzzle to have a unique solution?)

Another way to look at a Sudoku puzzle is the distribution of start values. When solving a puzzle manually, I generally start with the groups with the most start values. But sometimes a puzzle has a very even distribution, with all groups having either two or three starting values. This can sometimes result in a more challenging puzzle, but perhaps an esthetically less interesting one.

On the other hand, puzzles with a wide variance in the number of start values can be interesting too. A group with a lot of start values may give you a bit of a head start, but the groups with few or even no seed values might give you some headaches. I tend to like posting puzzles with one or two empty groups. For standard puzzles with rotational symmetry, usually it's a middle group that ends up empty.

Anyways, have a go at todays puzzle. As I mentioned, it features mirror symmetry about a diagonal. It also features two empty groups, and no more than four seed values per group. If this puzzle is too easy for you, check back in a couple of days for a harder puzzle with mirror symmetry.

Hans

     
     
     
    9
  7  
2 6  
  2 1
5   3
     
    2
  4 9
6    
     
     
     
  4 7
8    
     
  1  
3    
7 8  
  2  
7    
4    
     
    5
  9  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #32

Category: Sudoku
Tue, 26 Jul 2005, 09:45

Today in history, 202 years ago, the first public railway started operation south of London, England. The Surrey Iron Railway was used to haul bulk freight between the Thames and the industrial area along the River Wandle to the south. The trains were not pulled by locomotives, but rather by horses. Steam locomotives would come into common use only a few short years later.

Over the subsequent two centuries, the railways revolutionized the world. Trains would be used not just for freight, but also by passengers. It was the railroads that opened up western North America to settlers. In particular, Canada ended up the way it did largely because of the railways.

Today, the railways are still an important part of daily life in many parts of the world. In my home city, Toronto, tens of thousands of commuters ride to work on either TTC subway trains or on GO commuter trains.

If you're taking a train to work and you're looking for something to do, why not solve a Sudoku puzzle?

Hans

     
1    
     
6    
  7 5
2    
3 1  
2    
    6
  7 2
5    
     
     
     
     
     
    1
4 8  
3    
    1
  4 5
    1
7 5  
    3
     
    2
     

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #31

Category: Sudoku
Mon, 25 Jul 2005, 10:28

I'd like to take this opportunity to congratulate the winners of the recent World Stupidity Awards. The awards are given out by the Academy Recognizing Stupidity Everywhere (ARSE), and this years gala was held in Montréal on Friday. Here are some of the highlights:

The award for Stupidest Woman of the Year went to Paris Hilton. Stupidest Man was awarded to columnist Ann Coulter.

The award for Stupidest Statement of the Year went to repeat award winner George W Bush for his observation: "They never stop thinking of ways of harming America, and neither do we."

Fox News won the award for Media Outlet Which Has Best Furthered Ignorance.

If you're a nominee for one of these awards, you're probably not interested in trying to solve a Sudoku puzzle. For the rest of you, here's today's challenge.

Hans

    5
    4
8    
     
9   6
  2  
    9
  3  
     
     
    2
  8  
1    
8   9
    3
  7  
5    
     
     
  1  
3    
  8  
5   4
     
    4
3    
7    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #30

Category: Sudoku
Fri, 22 Jul 2005, 10:03

What's special about the number 30? It's the product of the first three prime numbers. That is, 30=2x3x5. Products of prime numbers are called "primorials". The first ten primorials are: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, and 6469693230.

What's special about July 22? July 22, also written as "22/7", is known as "Pi Approximation Day", in honor of a commonly used approximation to the value of π. (Pi Day is celebrated on March 14.)

What's special about today's Sudoku puzzle? Nothing much, really. Like the other puzzles I post, this one requires the usual assortment of advanced solving techniques.

Hans

  5  
7    
4    
     
9   8
     
  3  
     
     
    1
2    
  9 6
2    
6   7
    5
4 5  
    9
2    
     
     
  1  
     
3   2
     
    8
    7
  9  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #29

Category: Sudoku
Thu, 21 Jul 2005, 09:00

Yesterday, the US government announced plans to extend daylight savings time by two months in the Spring and Fall. It would seem that the US will do anything to conserve energy. Anything, that is, except any measure that would involve any significant sacrifice on the part of its citizens.

It is estimated that extending daylight savings time would result in a whopping 1% to 2% savings in energy during those two months. But if the US really wanted to save energy, there are other more effective measures. They could increase the taxes on gasoline and increase the taxes on gas-guzzling motor vehicles. They could increase investment in alternative energy sources like solar and wind power. These are things that will need to be done anyways as the non-renewable resources dry up. Now is as good a time as any to prepare for the inevitable.

And now for a problem that's easier to solve - todays Sudoku puzzle.

Hans

    5
  1 4
6    
9    
  7  
5    
  8  
     
  2  
  6  
    8
3    
     
     
     
    1
5    
  9  
  8  
     
  9  
    7
  4  
    1
    4
8 6  
3    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #28

Category: Sudoku
Wed, 20 Jul 2005, 08:34

On this day, 36 years ago, two men from Earth landed on another celestial body, the Moon. In doing so, Neil Armstrong and Buzz Aldrin were well on their way to successfully completing a challenge made by President Kennedy eight years earlier.

The primary goal of Apollo was political - to beat the Russians to the Moon. If it weren't for the early successes of the Soviet Union in launching first satellites and later men into orbit, the United States wouldn't have been in such a hurry to showcase its own technological prowess.

Since 1972, there have been no manned space flights to the Moon, or any other planet. Why not? There simply haven't been any good political reasons to do so. One might argue that scientific curiousity is a good reason, but good science can be done much more effectively with unmanned space probes. Just look at what's happening now on Mars. There are two automated rovers crawling on its surface, and a number of satellites are busy doing remote sensing from orbit. The amount of scientific information about obtained from unmanned probes dwarfs the amount of science done by NASA's manned programs, at a fraction of the cost.

What about the so-called "spinoff benefits" from the manned spaceflight programs? First, studies have shown that the spinoff benefits are greatly exaggerated. Second, if you want advances in specific areas, like cancer research, the best approach is to fund those areas directly, and not to count on the rare possible spinoff from spaceflight research.

And now with my rant out of the way, here's todays challenge.

Hans

     
9   1
     
     
    8
9 3  
    7
     
    2
     
  8 7
  4  
7    
6   2
    3
  8  
5 4  
     
2    
     
1    
  1 6
4    
     
     
9   3
     

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #27

Category: Sudoku
Tue, 19 Jul 2005, 09:35

In my previous Sudoku blog entry (#26), I described a conundrum where taking a different path on the way to solving one particular solvable puzzle led to a roadblock. I mused that I must be missing some analytical technique. Thanks to Bryan Wolf, I now know what I missed!

In #11, I described the "elimination" technique. That is, if you have two cells in a group with the same two possibilities, the two can be eliminated from the other cells of the group. What I missed was that when you go to three or more cells, not all possibilities need to be represented in those cells.

For example, if you have three cells with the possibilities {1,2,3}, {1,2,3}, and {2,3}, the technique still applies, and the three possibilities can be eliminated from the other cells of the group. I had incorrectly assumed that all three cells had to have the exact same three possibilities.

This now begs the question: If you know all possible analytical techniques for solving Sudoku, can you actually get into a dead-end situation if you choose the wrong order of applying the analytical techniques? My intuition now tells me that the answer is probably no.

And now, todays puzzle. My program tells me that two different analytical techniques are needed for this. But that was the program with the less than perfect elimination technique. After I fix my program, you might find some tougher puzzles.

Hans

5    
2 7  
    9
     
    8
7    
  3  
     
     
3    
6    
  8  
8   1
     
5   6
  5  
    7
    2
     
     
  6  
    4
3    
     
2    
  7 4
    9

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #26

Category: Sudoku
Mon, 18 Jul 2005, 06:58

I ran into an interesting conundrum yesterday with one of my Sudoku puzzles. It was solvable by my original Sudoku program written in Python. But my new program written in C couldn't solve it, even though it included a couple of additional advanced solving techniques!

Here's how my old program handled one particular step, as shown by the following diagram. It noticed the three cells in one column with the three possibilities {123}. Since those possibilities must occur in those three cells, these possibilities can be eliminated from the other cells in the group, indicated by the underlining. The program could then apply other techiques and proceed to the solution. (Right away, you can see that the entire middle row can be resolved easily.)

5 2379 37
1 8 4
269
 
2369 36
189 6 149
3 7 2
189 5 149
1248
 
123 1348
6 59 59
7 123 1348
3 679 167
48 47 2
489 5 18
4 12 19
5 38 6
129 38 7
125 8 157
9 137 1347
124 123 6
268 236 9
7 1 5
2468
 
2346 368
127 4 35
6 9 8
127
 
12 35
158
 
1567 1578
3 4 2
158
 
156
79
157
89

But with the additional advanced methods added to my new program, it applied a different method, as illustrated by the following diagram. With this technique, the intersections of four groups is considered: one column, one 4x4 square in the middle of the board, and two rows. In this case, posssibility 1 must occur in either the upper-left and lower-right indicated cells, or in the lower-left and one of the two upper-right cells. Possibility 1 can therefore be eliminated from the other cells of the two rows, again, indicated by the underlining. (See #16 for further explanation of this technique.)

At this point, my program reached a roadblock, and couldn't proceed without resorting to backtracking. Clearly, the technique used previously no longer applies since we no longer have the three groups with possibilities {123}.

5 2379 37
1 8 4
269
 
2369 36
189 6 149
3 7 2
189 5 149
1248
 
123 1348
6 59 59
7 123 1348
3 679 167
48 47 2
489 5 18
4 12 19
5 38 6
129 38 7
125 8 157
9 137 1347
124 123 6
268 236 9
7 1 5
2468
 
2346 368
127 4 35
6 9 8
127
 
12 35
158
 
1567 1578
3 4 2
158
 
156
79
157
89

The lesson is that sometimes when you reach an impasse and don't know how to proceed, you have to start over and make different choices along the way to the solution. It's frustrating - you haven't made any mistakes, but still you need to go back to the beginning and try again.

How will I address this in my program? I'm not sure yet. One alternative is to try solving the puzzle again varying the order in which the advanced methods are invoked. But that feels like a kludge solution. There are lots of ways to change the order, which would increase the time needed to solve or generate puzzles. On the other hand, that might be a good way to produce more difficult puzzles!

I still can't shake the feeling, though, that I'm missing some other analytical technique. I need to keep looking for it.

Anyways, in todays puzzle, you can't avoid one particular advanced solving technique. But I'm not telling you which technique it is!

Hans

5 9  
  6 3
    8
  6  
     
1    
     
  9  
     
     
1    
    2
  8  
5   4
  3  
1    
    8
     
     
  5  
     
    5
     
  7  
9    
8 3  
  4 6

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #25

Category: Sudoku
Sun, 17 Jul 2005, 09:39

The heat wave rages on in southern Ontario. Yesterday, I took my daughter to Morningside Mall (or rather, what's left of it). The air was stifling. But it wasn't the heat. Nor was the humidity a problem. What made breathing difficult was the smog. I had never breathed such disgustingly dirty air.

Now more than ever we need to find alternative energy sources. Coal may still be plentiful and cheap, but the burning of coal is still one of the biggest sources of air pollution. If we keep the coal plants open, the problem will only get worse over time, and that will continue to kill people.

As with solving Sudoku puzzles, the problems with energy and pollution must be looked at logically. Hoping and praying for a solution can never work. We need to apply intelligent thought to these serious problems facing us.

Hans

2    
     
5    
     
8 3  
  1 4
3   7
     
     
  9  
    8
    3
  6  
     
  7  
1    
9    
  6  
     
     
1   5
1 8  
  9 6
     
    5
     
    6

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #24

Category: Sudoku
Sat, 16 Jul 2005, 10:26

24 hours in the day, 24 beers in a case. Coincidence?

The two-four is a long-time Canadian tradition. At one time in Ontario, the beer stores were called "Brewers Retail". You would take your case of empty stubbies back to the store for the deposit. You'd put your empty case on a roller conveyor on one side of the store, order your favorite Labatt's or Molson's, then go to the other side of the store. After a short wait, your new two-four would come clattering down the rollers.

These days, you go to the "Beer Store", where you can find a a much greater variety of domestic brands. The stubbies are long gone, and most stores are now largely self-serve. The beer is also better, with many breweries eschewing preservatives and other artificial ingredients.

Does beer help you in solving Sudoku puzzles? Probably not. You need to keep your mind sharply focused on the task. Todays puzzle, especially, needs your full attention.

Hans

     
2   7
6    
     
    8
  5 2
    6
     
  3  
5    
    6
  4  
     
9   1
     
  6  
3    
    8
  8  
     
7    
6 1  
8    
     
    5
4   9
     

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #23

Category: Sudoku
Fri, 15 Jul 2005, 19:10

What's special about the number 23? If you have a room full of 23 people, chances are better than 50:50 that two of them will have the same birthday. This might seem surprising, but sometimes intuition fails us.

Consider a room with two people. There's just one way to have a pair of people with a common birthday. But with three people, there are three ways. With four people, there are six possible pairs, and with five people, there are ten possible pairings. As you add more people to the party, the possible ways to have a common birthday rises at a much faster rate. I won't show the math here since someone else does a better job explaining the probabilities involved.

But solving Sudoku has nothing to do with probabilities. There's just no point in trying to use probability theory when solving a Sudoku puzzle. All possibilities for a cell must be considered equally valid until eliminated through ruthless logic.

Todays puzzle, like all others here, can be solved analytically. It might not seem like it, though, if you get stuck. If you're not aware of all the solving techniques I use, you may well get stuck with this tricky one!

Hans

  3  
  5  
2    
    1
     
  7  
     
3    
    9
    9
3   2
     
6    
9   5
    8
     
6   7
4    
7    
    6
     
  2  
     
5    
    4
  8  
  2  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #22

Category: Sudoku
Thu, 14 Jul 2005, 21:56

I know how much everyone likes listening to phone messages left by telemarketers. Yesterday, some local company left an interesting message. It went something like: "I'm from the XYZ Dating Service. I'm calling to follow up on some information we mailed to you...". Although the information previously sent was junk mail addressed to "occupant", I can imagine someone listening to the message, and then suspecting his or her spouse of playing games!

Is this some devious new marketing strategy for the dating services? Are they so desparate for business that they're willing to try to break up otherwise healthy relationships in the hope that some of them might eventually use their services? Why else would they try to drum up business in a family-friendly, middle-class neighborhood of single-family homes? Wouldn't they get more business in areas popular with singles, like Eglinton Avenue at Yonge or Mount Pleasant?

Anyways, if you have no need of a dating service, why not print out two copies of todays puzzle so both you and your partner can have some quiet Sudoku time together.

Hans

  8 1
     
9   2
  7  
     
     
5 6  
    3
     
8    
    4
     
4    
3   5
    1
     
6    
    9
     
2    
  7 6
     
     
  2  
3   5
     
8 4  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #21

Category: Sudoku
Wed, 13 Jul 2005, 22:43

One local radio station recently changed formats yet again. JACK-FM 92.5, initially a "new country" station, now advertizes itself with the slogan "Playing what we want". Well, I thought, I don't want to listen to what someone else wants, I want to listen to what I want!

But curiousity got the better of me, and I checked out this station. And guess what? What they want to play sounds pretty good to my ears. Their format is rather different. They play songs from a much wider playlist than other stations, with a much more eclectic mix. They even play late 1970's new wave material that you never hear any more on any other station!

Another aspect of their format is that they run fewer ads, which again is much appreciated. For people living outside the Toronto area, the "Jack" format has also been adopted by other radio stations too. Flip across the FM dial, and you might be surprised by what you hear.

Anyways, while you're enjoying the music on the radio and trying to stay cool during the heat wave, you might as well try solving todays challenging Sudoku puzzle.

Hans

9    
1   4
     
8 1  
     
    2
     
    7
     
  8  
  6  
7   5
  7  
     
  6  
3   5
  2  
  1  
     
3    
     
5    
     
  9 7
     
9   1
    4

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #20

Category: Sudoku
Tue, 12 Jul 2005, 09:22

Yesterday, I was surfing around some of the other Sudoku web sites, and I came across one that offered some puzzles described as "devious". Well, of course, I had to try them out. The first puzzle turned out to have no solution. It simply had an invalid starting arrangement. The second was easy to solve, needing just the basic solving methods. The third was a bit more interesting.

When I fed the third "devious" puzzle to my solving program, it had to resort to a trial and error, backtracking method to find a solution. Backtracking means either one of two things. First, it could mean that my program doesn't know about some particular analytical solving technique. Second, it could mean that the puzzle has multiple solutions. A bit more analysis revealed multiple solutions for the puzzle.

Are multiple solutions acceptable in a proper Sudoku puzzle? I would argue that they're not. Every puzzle should have one distinct solution discoverable through a series of analytical steps. Otherwise, you can drive yourself crazy trying all sorts of analytical approaches.

As for the puzzles I post here, as far as I know, they are all solvable analytically. Some of the steps may be tricky, but you shouldn't have to resort to trial and error to solve any of them. If you don't think that's true about any of these puzzles, send me an e-mail.

Hans

    8
     
  6 9
     
    6
4 8 7
     
    7
     
  1  
    5
    3
  6  
     
  9  
4    
6    
  5  
     
2    
     
8 4 3
5    
     
9 1  
     
3    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #19

Category: Sudoku
Mon, 11 Jul 2005, 10:24

I got a bit impatient with the performance of my first Sudoku program written in Python. It often took hours for that program to output a good challenging puzzle. And so, looking for something to keep my mind off an upcoming visit to the hospital, I decided to rewrite the program in C.

(If you're not interested in computer programming, just skip ahead to todays puzzle.)

Python is a fabulous language, and perhaps my favorite programming tool. Using Python, I can crank out working code a lot faster than in any other programming language. But since it's an interpreted language, it's not necessarily the best choice for compute-intensive applications, like generating Sudoku puzzles.

Up until a year ago, most of my professional computer programming was done in C. It too is a fine programming language, ideal for systems programming, or for any compute-intensive application. Although I hadn't written any C code in the past 12 months, and although the Sudoku program ended up twice as big in C as the Python original, I had my new, much faster program up and running in no time.

This brings up an advantage of Python. It was very easy to get my original program running using Python. When it came time to rewrite into C, I already had the algorithms worked out and debugged. Debugging the C program turned out to be a lot easier than if I had started in C.

I'd like to bring up just one more point in todays rant. Some programmers like to think that they're able to do any programming task using just one programming language. While it certainly is possible to program almost any task using practically any language, in most cases there are languages better suited to particular tasks than others. For all programmers, it is vitally important to know multiple programming languages. For the case of Sudoku programming, although Python was a great choice as a prototyping language, the compute-bound nature of the problem made C the better choice for the final, production program.

With my new program, I can churn out Sudoku puzzles about 50 times faster than before. This means I can choose from more puzzles, and post the toughest of the tough. Todays puzzle is from the first batch of puzzles from my new program. It may well be the most challenging puzzle I've posted so far.

Hans

    7
     
9   5
    6
7 1  
    2
     
5    
    8
2   1
3    
     
     
     
     
     
    6
7   9
5    
    9
     
6    
  2 1
5    
9   4
     
3    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #18

Category: Sudoku
Sun, 10 Jul 2005, 07:31

Today is the 80th anniversary of the start of the trial of John Scopes in Dayton, Tennessee, for the "crime" of teaching evolution. Scopes was found guilty 11 days later. It wasn't until 1968 that laws outlawing the teaching of evolution were overturned by the US Supreme Court.

But even now, there are still groups opposed to the teaching of evolution, blaming it for all sorts of evils in the modern world. Some try to diminish it by calling it "just a theory". But that reflects a profound lack of understanding of what evolution is.

What many people don't realize about evolution is that it's not a theory. Theories involving evolution include Darwin's natural selection and more recent theories like punctuated equilibrium. But evolution is not a theory, it's the observation. Scientists ever since Darwin have observed that species change. They change over time and over distance. Evolution has been observed in nature, in the laboratory, and in the fossil record. It is simply one of the most important principles underlying the biological sciences today.

Science works through a process of logical analysis. Likewise, when solving a Sudoku puzzle, you must proceed in a systematic manner from what you already know, eliminating possibilities that cannot possibly be true, to get closer and closer to the ultimate truth.

Hans

6 9  
4   7
  1  
8    
     
  5  
4    
  6  
     
     
  3  
5    
9    
6   8
    3
    2
  7  
     
     
  8  
    9
  8  
     
    2
  5  
2   7
  3 4

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #17

Category: Sudoku
Sat, 09 Jul 2005, 10:14

Seventeen is very clearly a magical number. I'm sure most people instantly recognize it as the first sum of distinct fourth powers. But further proof of the magic of this number can easily be discerned with a little study.

Many people are familiar with Dan Brown's popular book The Da Vinci Code, and know that it's a source of great wisdom. Let's dive into it further. Let's apply the power of 17, and let's look at the 17th words on each of the first 17 pages: "for a into fumbled had intriguing man profoundly brownstone legendary he south I tuiles. five referred Bezu".

Scary, huh? But there's more. Let's go on for another 17 pages: "his 70,000-square-foot opportunity his found exhaled like Lexington 1934 been do. Grand his yet Saunière pagan official".

Clearly, we're on to something here. Should we push our luck and go straight to the 17th such grouping? Starting on page 285: "have we while them rang. foreign goddess said the felt aptly despondent. some box he in write".

Although cleverly hidden and somewhat jumbled, the message is clear. But what exactly does it mean? Why is the foreign goddess despondent? Is this some fabulous esoteric message from Dan Brown? Or perhaps from the mysterious Priory of Sion? Perhaps some hint can be gleaned from the 17th sentence of Chapter 17: "Fache shook his head."

But why bother yourself which such deep thinking. Why not just relax with todays Sudoku puzzle.

Hans

     
  6 7
     
     
  5  
9    
8    
3 4  
2    
     
6    
9    
  8 2
     
6 4  
    5
    8
     
    2
  4 5
    6
    7
  3  
     
     
6 1  
     

path: /Sudoku | permanent link to this entry

triangle
 

The Book of Signs

Category: Books
Fri, 08 Jul 2005, 18:30

Dover Publications is well known for affordable reprints of some marvellous old books. The Book of Signs (by Rudolf Koch) is an example of a Dover book that's a terrific source of clip art suitable for web sites, since Dover explicitly allows the use of a certain number of illustrations from the book without permission. This note serves to provide the requested credit.

The following describes the meanings of the symbols used in this blog:

Notes in the Books section get this profound symbol. The The Book of Signs describes it thusly: "An oriental symbol of the soul's pilgrimage through life: the soul climbs up through the four belts of the world, or elements, to its purification, and wins through from darkness into light."
The Bowling section gets the triquetrum, which conveys the sense of rolling. The circle is divided into three sections, representing the three throws per frame you are allowed in five-pin bowling.
Politics gets this unlikely choice, which represents friendship between people. Many Canadians may remember this symbol. A ring of eight of these symbols was used as a logo for Expo 67, the world's fair held in Montréal.
Religion is represented by this ancient pagan symbol representing the sun. Later, it was appropriated by Christians as a Chrismon, or monogram of Christ.
Three straight horizontal lines represent "passive intellect". Three straight vertical lines represent "active intellect". Three wavy horizontal lines mean "intellect in action". Three lines arranged in a triangle symbolize "creative intellect". Finally, when the lines cut through each other, order dissolves. The symbol used for Sudoku is called "disordered intellect", suggesting an activity for those who might just have too much time on their hands. (Hmmm, that could well apply to blogging too!)
The symbol used for the Television section is a holding mark called "the manure heap".
For Toronto I use this symbol called simply "the city". Inverted, it indicates the destruction of the city.
Finally, the symbol for the Trains section is, appropriately, an old chemical symbol for iron. The arrow represents forward motion and the two parallel lines represent the two iron rails. Thus, this medieval symbol foresees the use of iron in the railroad industry a thousand years in advance!

Hans

path: /Books | permanent link to this entry

pilgrimage
 

Sudoku #16

Category: Sudoku
Thu, 07 Jul 2005, 14:15

In #11, #12, and #14, I discussed some advanced Sudoku solving techniques. These three techniques are sufficient for most of the puzzles I've seen. However, one puzzle had me stumped for a while. Obviously, I needed something more. My Sudoku program could solve it, but it had to resort to a trial and error, backtracking algorithm. There just had to be some analytical technique that I was missing.

I finally found another technique. However, this is a bit more complicated than the previous techniques. The best way to describe it is to provide a concrete example. The following shows how far I got with that puzzle with just the previous techniques:

17 4 3
6 789 1789
2 578 578
9 8 67
4 2 5
37 36 1
2 5 167
138
 
38 178
68 9 4
9 568 2568
3 57 257
4 1 5678
13 135 4
6 157 8
2 57 9
1568 7 1268
49
 
24 129
568 68 3
8 2 17
17
 
69 69
5 3 4
5 16 367
17 4 23
8 9 26
49
 
346 69
38 238 5
7 1 26

To break the impasse, we need to look at two rows and two columns at the same time. In this diagram, look at the four cells where the marked rows and columns intersect. Note that the possibility "6" occurs in all four cells. Note also that in the marked rows, possibility "6" occurs only in the intersecting cells. Thus, the value "6" must appear either in the top right and bottom left cells, or in the top left and bottom right cells. Either way, "6" cannot appear in any other cell in the two marked columns, and can therefore be eliminated from those other cells. In this case, the three underlined sixes can be eliminated.

Theoretically, I suppose you could extend this technique to three rows intersecting with three columns. But I doubt you'll ever have to resort to that.

Now that my Sudoku program knows about this technique, does that mean I will now post even more challenging puzzles? To answer this question, you'll just have to wait and see. For today, though, another relatively easy puzzle, with a blank middle group.

Hans

4    
     
    6
  1 9
6    
2    
3 5  
  8  
7    
  5  
     
8    
     
     
     
    9
     
  2  
    2
  1  
  6 3
    6
    5
7 9  
9    
     
    2

path: /Sudoku | permanent link to this entry

triangle
 

Jesus Forgot to Bring the Pork Chops

Category: Books
Wed, 06 Jul 2005, 09:47

With a provocative title like When Will Jesus Bring the Pork Chops?, you might expect George Carlin to be more down on religion in his latest book. He does have some choice words about religion, but overall, religion has a minor place in the book. Most of his rants discuss our fascination with and overuse of euphemisms. Other rants seem purposely provocative. And many comments are bluntly insightful.

This is not really the kind of book to read from start to finish. The best way to read it is to flip through the book reading random pages when you have a spare minute or two. The best bits are the short bits and pieces. Try to imagine Carlin doing a stand-up routine when reading bits like "I was reading a fitness magazine that had an article about cross-training, and I realized this would have been a good idea for Jesus."

Regarding euphemisms, one great bit called "God Help Us" discusses the term faith-based. He argues convincingly that the term is used, mainly by Bush Republicans, since it's more acceptable to the general public than the term religious. He has these choice words on the subject: "The term faith-based is nothing more than an attempt to slip religion past you when you're not thinking; which is the way religion is always slipped past you."

In case you might think Carlin is picking sides, conservatives (political or religious) aren't the only targets in this book. The left doesn't survive his barbs unscathed either. For example, liberals use the terms investing or funding, whereas others would call it spending money. Conservatives say gun control while liberals call it gun safety.

In another more serious section, he discusses the issue of land mines, pointing out that mines cost three dollars to make and install, but cost a hundred dollars to remove. He wonders how many Cambodians who lost one leg already lose the other by stepping on a second land mine.

Finally, here's Carlin's take on America's lost innocence. No commentary is necessary on this:

"I keep hearing that America lost its innocence on 9/11. I thought that happened when JFK was shot. Or was it Vietnam? Pearl Harbor? How many times can America lose its innocence? Maybe we keep finding it again. Doubtful. Because, actually, if you look at the record, you'll find that America has had very little innocence from the beginning."

Because of the authors reputation as a stand-up comic, you might expect more humor in this book. The dust covers whimsical take-off of Leonardo's "Last Supper" certainly suggests more comedy. Sure, there are some lighter moments in this book. But most of it is a dark, no-nonsense observation of the world as it really is, railing against the ways most people want the world to be.

Hans

path: /Books | permanent link to this entry

pilgrimage
 

Sudoku #15

Category: Sudoku
Tue, 05 Jul 2005, 16:27

If you're new to this blog, you might be wondering what it's all about. First, a blog is a great way to expose your ideas, wonderful or crazy, to the wider world.

Why Sudoku? A couple of weeks ago, the Toronto Star started including a daily Sudoku puzzle. Being a puzzle fan, of course I had to try it. Although I got bored with it quickly, I did get interested in solving Sudoku by computer. Using Python, I had a working program done pretty quickly.

I then realized that the program could also be used to create Sudoku puzzles. All I had to do was randomly add values to an initially empty 9x9 grid, and then try to solve it. It was also easy to keep track of which specific solving methods were needed to solve a puzzle. These metrics could be used to determine the relative difficulty of a particular puzzle.

With these tools in place, I decided to take the most difficult puzzles produced by my program, and offer them up to the Sudoku world. Every so often, perhaps a couple of times a week, I'll upload a new puzzle, along with some commentary. I may comment on the particular puzzle, or on Sudoku in general. Or I may comment on something else entirely. It's my blog, and I'll do what I want.

Anyways, I do hope you find these puzzles either a source of enjoyment, or an exercise in frustration.

Todays puzzle should be a bit easier. Next time, I'll discuss another advanced solving technique.

Hans

    6
4    
1 9  
8    
6    
4    
     
     
3   7
3 8  
    2
     
     
     
     
     
1    
  7 5
7   4
     
     
    1
    8
    5
  5 9
    1
4    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #14

Category: Sudoku
Mon, 04 Jul 2005, 09:15

In #10, #11, and #12 I discussed some basic and advanced Sudoku solving techniques. Here is one more advanced method. Unlike the others, this one requires looking at two groups at once.

Look at the intersection of a 3x3 square (call it set A) and either a row or a column (call it set B). There are three cells in the intersection, which we'll call set C. (That is, C=A∩B.) For this method to work, there must be at least two unknown cells in the intersection.

Now then, if some possibility x exists in set C but not in A-C, then that possibility also cannot exist in B-C. That is, possibility x can then be eliminated from the cells of B not part of the intersection. And of course, vice versa.

Are there any other easy analytical methods? So far, I've only found one published puzzle that can't be solved by some combination of these basic and advanced techniques. I've found one more advanced techique, but I won't discuss it until I can come up with an easy way to describe it. For now though, none of the puzzles I've posted so far need that particular technique.

Anyways, for today, you get a slightly easier puzzle.

Hans

    6
1 8  
     
     
    2
1   4
  8  
4    
     
     
    7
6   5
6    
     
    1
5   9
6    
     
     
    9
  7  
2   8
7    
     
     
  6 1
3    

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #13

Category: Sudoku
Sun, 03 Jul 2005, 14:19

When I was young, I was told that something bad often happens to kids when they're 13. For instance, some kids break a leg. Whatever it was, it was because 13 was such an unlucky number.

One friend of mine, a rabid spaceflight fan, celebrated his 13th birthday on April 13, 1970. Doubly unlucky, you might think. But even more so if you remember what else happened on that date. The Apollo 13 spacecraft carrying three astronauts was about 330,000km from Earth, rapidly approaching the Moon, when an oxygen tank exploded, crippling the spacecraft. Can you get any more unlucky than that?

Through a lot of hard work by the three astronauts, as well as hundreds of people in Mission Control, the three managed a safe return to Earth using their Lunar Module as a "lifeboat".

But the number 13 is also considered "lucky". "Lucky numbers" are constructed using a method similar to the Sieve of Erastosthenes, which can be used to construct prime numbers. First, from the sequence of positive integers, strike out every second number, leaving the sequence of odd numbers: 1, 3, 5, 7, 9, ...

After 2, the next number left in the sequence is 3, so strike out every third number, resulting in the sequence: 1, 3, 7, 9, 13, 15, 19, ...

The next number remaining is 7, and so strike out every seventh number. And so on.

You are then left with the "Lucky Numbers": 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, ...

Anyways, I hope you feel lucky with today's challenging Sudoku puzzle.

Hans

  9  
  8  
6    
     
  9  
3   4
    2
     
     
     
  3 5
1    
6 4  
     
  3 5
    8
1 7  
     
     
     
9    
2   6
  7  
     
    3
  5  
  1  

path: /Sudoku | permanent link to this entry

triangle
 

Sudoku #12

Category: Sudoku
Sat, 02 Jul 2005, 10:01

In #10 and #11 I discussed some basic and advanced Sudoku solving techniques. Here is the second advanced technique. Unlike the previous one, the situation described here isn't quite as easy to spot. And you might not be able to eliminate quite as many possibilities as before. But any progress is still progress, so this technique is still worth knowing.

In this technique, look in any group (row, column, or square) for two possibilities (say, x and y) that occur in only two cells. Since these two possibilities must occur in either of these two cells, all other possibilities other than x and y can be eliminated from those two cells.

As with the previous advanced techique, this can also be extended to three possibilities occuring only in three cells of a group. But this situation rarely crops up.

Next time, I'll have a short discussion on the number 13. I'll get to the final advanced technique with puzzle #14.

Hans

    3
5    
7 2  
  2 7
     
8    
     
     
  6  
    2
  9  
  1  
    9
     
2    
  4  
  2  
8    
  6  
     
     
    4
     
1 9  
  7 2
    1
5    

path: /Sudoku | permanent link to this entry

triangle
 

The Mobility Express?

Fri, 01 Jul 2005, 15:07

Urban planners have known for decades that building new roads is often not the best way to solve traffic problems. In fact, in many cases, it has been shown that new roads can make existing traffic problems worse.

A couple of days ago, the mailman delivered a glossy brochure published by the CAA called "The Mobility Express 2005 post-survey report". In it, they continue to advocate certain improvements to roads and public transit within the city of Toronto. While some of the improvements make a lot of sense, such as extending the Spadina subway line north to York University, extending the Bloor line westward into Mississauga, and extending the use of synchronized traffic signals (SCOOT), the majority of the proposals are just plain silly. The most goofy and, not surprisingly, the least popular are those dealing with new expressways.

The least popular proposal of them all, especially among people living near the Humber Bay, is a bridge over the Humber Bay just off the Western Beaches. The report argues that it would create a more direct route into the city. But how much time would it save drivers? Maybe 30 seconds? Sure, the city could alleviate congestion in that one area, but only to move it further downtown.

The next goofy proposal is to replace Eglinton Avenue West in Etobicoke with an expressway. It may help shorten the drive to the airport for some people living in Etobicoke, by a few minutes. But otherwise, the estimated $610,000,000 cost would certainly be better spent on other more important local traffic solutions, such as the Eglinton West subway line (abandoned shortly after construction started).

The Scarborough Highlands Expressway is another goofy idea. This expressway would occupy a hydro corridor running from Highway 401 at Morningside Avenue across to the Don Valley Parkway south of Eglinton. It would never be further than 6km away from the 401! The report claims that it would divert a significant number of cars from the crowded northern section of the DVP. Maybe so, but it would then dump all those cars into the crowded southern section of the DVP!

But the grand prize for goofiness goes to the proposal for the "Gardiner Offshore Extension". Get this, they actually propose a 2 billion dollar, ~24km long bridge located offshore about a kilometer south of the Scarborough Bluffs! Savvy commuters living in the bedroom communities east of Toronto already know that the best way to get to their jobs downtown is the Lakeshore East GO train. What's the point in improving the drive into the downtown only to face gridlock and skyhigh parking prices once you get there!

Quite simply, the CAA proposals for Toronto are just too ludicrous for words. The two or three good ideas are just overwhelmed by the really silly ones.

Hans

path: /Toronto | permanent link to this entry

the city