Marriage for all

This post describes my position concerning gay marriages.

Sudoku - Programming the XY-chain strategy

XY-chain is a generalisation of Y-wing. Essentially, instead of looking for a chain of three pairs, you look for longer chains in which the intersection cell of the Y-wing is expanded to a chain. The chain can be surprisingly long (one day, I might try to find out how long...), as shown in the following examples (only the relevant cells are shown).

Sudoku - Programming the Y-wing strategy

On the web there are many explanations of the Y-wing strategy, but none seems to go to the core of the issue. The only clear statement I found was that Y-wing doesn’t solve cells, but only eliminates possible candidates.

Strategy

Look for cells that contain only two candidates each. Among those cells, look for three cells that satisfy the following two conditions:

1. The arrangement of candidates in the cells is AB, AC, and BC. That is, no two cells have the same pair of candidates.

2. The cells are in two intersecting groups. This is equivalent to say that the two wing cells cannot share any group and can only happen in two ways: row+column (one of the cells shares the row with one of the other two cells and the column with the third one) and line+square, where ‘line’ stands for either ‘column’ or ‘row’ (one of the cells shares the line (row or column) with one of the other two cells and the square with the third one).

Sudoku - Programming the rectangle strategy

Every now and then I like to solve a sudoku puzzle. There are three things that interest me in sudoku: how to measure the difficulty of puzzles, how to write a program to solve puzzles, and how to write a program to create puzzles.

A program able to create puzzles must first of all be able to solve them, and to grade puzzles it is necessary to have a large number of solved puzzles. Therefore, the first step is to write a sudoku solver. There are many around, but for me part of the fun is to write the program. Years ago, I already wrote at least two sudoku-solving programs in Java. They were OO programs, but I was never particularly happy with the implementation. For this latest attempt, I have decided to ditch OO and use plain old “C” as a programming language.

In this post, I will describe a strategy that I call ‘rectangle’. It is sometimes called ‘hollow rectangle’ (you will later understand why). I intend to describe the strategy and then provide some development notes. To display the examples, I shall use snapshots of the program “Sudoku Training Software 1.1”, which runs under Windows. You can freely download it by clicking here. This is the first program I found on the Web for generating the snapshots. I use it only for that and I have no idea whether its other functions are good or bad. If you would like to suggest some other application, perhaps for the Mac, please tell me.