The Omnifarium

Sudoku #11

Category: Sudoku
Thu, 30 Jun 2005, 22:53

In #10, I discussed basic Sudoku solving techniques. But occasionally, you'll meet a puzzle that needs more. In particular, all of the puzzles you see here need at least some of these advanced techniques.

The first is an extension of a basic technique. Previously, I mentioned looking for cells with only one possible value. But you can also look for pairs of cells in a group (row, column, or square) with the exact same two possibilities. Consider how this works. Let's say you have two cells, A and B, with the two possibilities {x,y}. If cell A had value x, then x would be eliminated from cell B, leaving it with value y (and vice versa). Thus, the possibilities x and y must exist in these two cells, and so, x and y can be eliminated from all other cells of this group.

You can also extend this technique to three cells in a group with the exact same three possibilities. This case doesn't come up much. But as before, it's also a situation that's easy to spot, so it's worth being aware of.

Next time, the second advanced solving technique.

Hans

path: /Sudoku | permanent link to this entry

Same-Sex Marriage Bill Passes

Category: Politics
Wed, 29 Jun 2005, 17:09

Last night, the Canadian parliament did the right thing and passed legislation legalizing same-sex marriage. The only meaningful hurdle left is Senate approval, and then Canada will join the Netherlands and Belgium as the first progressive countries to allow gays and lesbians to marry.

As might be expected, Stephen Harper and the opposition Conservatives promise to fight the issue further. But they really don't have any grounds to oppose the bill. Already, courts in eight provinces and one territory have ruled that same-sex couples can marry. Any legislation that a possible future Conservative government might try to enact to rescind same-sex marriage rights would be immediately challenged, and likely struck down by the same courts.

The opposition never really had a chance. Quite simply, most people who oppose same-sex marriage don't really have anything to lose. The issue has only been about extending legal rights to certain people, and has never meant taking away any existing rights from anyone else. For me, I know how I'd feel if the government told me I that couldn't marry my wife. It's only fair that other loving couples also have the same legal right to marry.

Allowing same-sex marriage means that the institution of marriage can now be enjoyed by even more people. Marriage has thus been strengthened for all of us. At one time, only marriages performed in Anglican churches were legally recognized in parts of Canada. And even well into the last century, people could be arrested for just dating outside their "race". It's been a long road, but now practically all couples in Canada can legally marry, regardless of religious denomination, skin color, or sexual orientation.

Hans

path: /Politics | permanent link to this entry

Sudoku #10

Category: Sudoku
Tue, 28 Jun 2005, 21:03

One Sudoku fan asked me where she could find the answers to my puzzles. The way to find the answer, simply, is to solve the puzzle. In this note, and several future notes, I'll discuss how to solve Sudoku puzzles.

The object, of course, is to place numbers from one to nine in the blank cells such that each row, column, and 3x3 square includes each of the digits from one to nine exactly once.

To start, look at each blank cell. The possible values for that cell are the values not found in any of the 24 other cells in its associated row, column, and 3x3 square. In each blank cell, list out its possibilities using a sharp pencil. And have a good eraser handy. The general idea is to repeatedly eliminate possibilities until only one possibility remains for all 81 cells.

Step one: While working through the solution, once a value becomes known for a cell, that value can be eliminated from the sets of possible values for all other cells in its associated row, column, and square.

Step two: If you see any cell that has only one possible value, then that must be the value for that cell. Go back to step one.

Step three: Look for a row, column, or square where some number from one to nine is found only once among the sets of possibilities in that group. That must be the value of its cell. Eliminate the other possibilities for that cell and go back to step one.

Repeat these three simple steps as often as necessary.

For many puzzles, these steps are all you need. But if you want to solve any of the puzzles here (including the one below), you'll need more. Check back in a couple of days for the first of several advanced Sudoku solving techniques.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #9

Category: Sudoku
Sun, 26 Jun 2005, 08:37

Number 9, number 9, number 9, ...

To many, "Revolution 9" is their least favorite Beatles song. It's an avant garde collage of various soundbites that's not easy to appreciate. But I think most people take the song way too seriously (like many other songs on the "White" album). Although it purposely seems to try to be some sort of meaningful statement, listening right to the end of the song reveals the punchline, and you realize John Lennon has been playing with us all along. Personally, while it still may not be my favorite Beatles song, I do look forward to "Revolution 9" while listening to one of my favorite Beatles albums.

Number 9, number 9, number 9, ...

The number nine has great significance in Sudoku. We have to select digits from one to nine. Within the 9x9 grid, we have nine rows, nine columns, and nine squares.

Number 9, number 9, number 9, ...

For my 9th puzzle, I offer this challenger. Sometimes my Sudoku program takes hours to spit out a good puzzle. This time, it only took about nine minutes. And this time again, we get a puzzle with a completely blank center square.

Number 9, number 9, number 9, ...

Hans

path: /Sudoku | permanent link to this entry

Sudoku #8

Category: Sudoku
Fri, 24 Jun 2005, 21:12

Here's puzzle #8, just in time for the weekend.

I rather like Sudoku puzzles with entire groups initially empty. This one has a blank middle row, a blank middle column, and a blank middle square. As a result, it may take you a bit of time to deduce anything about the cell in the exact center of the puzzle.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #7

Category: Sudoku
Wed, 22 Jun 2005, 22:50

Yesterday, I spent 40 minutes stuck in Markham's rush hour gridlock. It was a great relief to finally get back into the sane streets of Toronto. These days, more and more businesses are relocating to Markham to take advantage of lower taxes. Of course taxes are lower there - they obviously don't spend enough on vital infrastructure improvements, like better roads and public transit!

Are you stressed out too from your rush hour drive through the town of Markham? Try relaxing with a Sudoku puzzle.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #6

Category: Sudoku
Sun, 19 Jun 2005, 16:19

My program has been spitting out lots of puzzles this weekend, so I might as well post one more for Father's Day. I hope other fathers are able to take advantage of the day and relax, possibly with a Sudoku puzzle handy. For me so far, this has been a day of yard work, basement renovation, and spending some time with my daughter. In other words, it's been a normal Sunday for me!

Hans

path: /Sudoku | permanent link to this entry

Sudoku #5

Category: Sudoku
Sat, 18 Jun 2005, 09:58

I tweaked my Sudoku program a bit, set the parameters, fed my computer a really strong cup of tea, and let it spin for a while. When I came back to my computer, I saw this delightful puzzle. All of the Sudoku solving techniques I know are needed for this puzzle, and early on. You might get discouraged, but I assure you that it is solvable.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #4

Category: Sudoku
Wed, 15 Jun 2005, 19:47

There are some Sudoku fans who argue that a "true" Sudoku puzzle should be symmetrical. I'm not sure I agree with that. What really matters is the enjoyment you get from solving it. An asymmetrial puzzle can be just as challenging as one with symmetry. But what the heck. If a puzzle has to have symmetry to be "true Sudoku", well, I can do that too. Here's #4, and it's symmetrical.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #3

Category: Sudoku
Sat, 11 Jun 2005, 16:16

The heat wave continues in southern Ontario. Unless you want to melt, there's no point in going outside. So instead, stay inside and solve a Sudoku puzzle. Here's number three. I hope it helps you forget about the scorching weather outside for a little while.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #2

Category: Sudoku
Wed, 08 Jun 2005, 21:36

This is the second of my Sudoku puzzles. I hope it's more challenging than the first.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #1

Category: Sudoku
Sun, 05 Jun 2005, 21:11

I tried solving a few Soduko puzzles. But I've found it more interesting to try and come up with new Soduko puzzles. I'll try to post a Soduko puzzle when I have the chance, hopefully, once a week. Easy puzzles aren't hard to find, so I'll try to post only more challenging ones.

Hans

path: /Sudoku | permanent link to this entry

Sudoku Has Hit Toronto!

Thu, 02 Jun 2005, 22:05

Earlier this week, the Toronto Star began including a Sudoku puzzle in its daily newspaper. Some other local rags also include a Sudoku puzzle. Apparently, these puzzles are extremely popular in other countries, especially Japan and Britain. Ever eager to try out new puzzles, I had to give this one a go. So far, I've solved about half a dozen, and I think I've already had my fill of Sudoku.

What is Sudoku? You start with a 9x9 square grid. At first, some of the squares are already filled in with numbers. Your task (should you decide to accept it) is to fill in the empty squares with numbers from one to nine. The same number can't appear more than once in any row, column, or 3x3 box.

How do you solve it? Start by considering that each empty square can possibly hold any number from one to nine. There are then two processes you can use. First, when you know a value for one square, you can eliminate that value from each associated row, column, and box. Second, try to find squares in any row, column, or box that can only hold one particular value. For most puzzles, repeating these two processes is enough. But some puzzles require additional analysis involving studying the intersections between boxes and rows or columns.

In other words, solving a Sudoku puzzle is pretty much a systematic, analytic process. Plan on about 20 to 30 minutes to complete a puzzle, longer if you have to resort to deeper analysis. Most of that time is spent listing possibilities for each square and eliminating them one by one. If you make a mistake along the way, it usually means starting over from the beginning. Of course, a pencil with a good eraser is a necessity. The main challenge is to keep at this boring task without making any mistakes.

Since solving Sudoku puzzles is a mindless, repetitive job, I figured the best approach would be to let my computer do it. So I wrote a program. Roughly 350 lines of Python code is sufficient for the task. And writing the program was more fun than I had solving Sudoku puzzles by myself.

Hans

path: /Toronto | permanent link to this entry