Monthly Archives: August 2006

The Incredible power of ALS

I cannot resist posting a few words about ALS (Almost Locked Sets), a very advanced solving technique with a lot of solving power. As I stated earlier, I just missed the deadline for 1.5.1 with these new solving techniques. They are now released in 1.5.1.1

One of them, long overdue, is Empty Rectanges. It does not solve anything new, but it is an easy to use alternative for multi-coloring and sometimes even for Nishio. Many other sudoku programs already supported ER, but having the most powerful techniques already implemented makes you lazy, I guess. The templates catch any single digit elimination, so I was not encouraged to implement lower-level single digit techniques. However, after the overwhelming success of my finned-fish implementation, it seemed the right time to do Empty Rectangles as well. Having restructured the solver in such a way that it is now very easy to add new techniques does also help.

The real thing I wanted to talk about is ALS. It is a bad acronym, but commonly known in the sudoku community. An Almost Locked Set is a situation where N cells have N+1 digits as their candidates. The simplest ALS is a single cell with only 2 candidates. Consider the following grid:

ALS-infested grid

How many Almost Locked Set does this grid contain? 10? 20?

No, there are almost 200 ALS’s in this grid, with only 96 candidates left. Most of them are harmless, but when you can pick the right combinations, they can become incredible solving tools. My list of 50,000 sudokus that require tabling steps is reduced to half its size, now ALS can be used. There is no single technique that had such a tremendous impact.

I will expand my solving guide to tell more about the power of ALS.

Size Matters

It has cost me a night sleep, but I have rewritten parts of SudokuGo, my batch generator. It now can generate any Sudoku with boxes of size 2×2, 2×3, 3×3 (duuh), 3×4 and 4×4, including the main variants, Jigsaw, X and DG.

If have also generalized the Windoku concept. A 4×4 sudoku can contain 1 extra 2×2 box in the center, with 3 implied extra groups. No Windows for the irregular formats, but 16×16 can have 9 extra 4×4 boxes, with 7 implied groups. I’m not sure this format will ever work, because the program chokes on generating a valid grid. Too bad if it turns out to be an impossible format, because it looks great. I’ve tested generation of the Windoku groups without box constraints, and that works. The combination may prove to be too much. Just to many conflicting constraints.

Also released SudoCue version 1.5.1. Redid the optimizer as many requested it should work, and also added a menu option to fetch the daily competition puzzle from www.sudoku.org.uk. Undo and redo work on candidates too.

I am now trying to implement Almost Locked Sets. Considering every possibility, the program now found 228 sets in a single grid. Needs some work to filter out the sets that are actually useful. I think I start sorting out the sets that do not overlap, but have a restricted common digit x. It must be possible to find ALS-xz patterns amongst these pairs of sets. I’ll write some more if I made some progress. Would be nice to be the first program that supports ALS, after being the first (and still the only) that supports finned fish.

Logic Discussions

I have started a thread on the Sudoku Discussions forum about the use of logic in Sudoku. The discussion started off pretty good, but it now seems to be stalling at logic notation. Good links were placed and I’m trying to catch up on lots of the material. The question remains: how do we use logic in sudoku?

Here is an example:

Take a bivalue cell C. It has 2 candidates, C1 and C2. One of them must be true, the other one false. We can write this as: (C1 v C2), ~(C1 & C2). This works fine with 2 candidates, but how about 3, or 9?

First daily Sudoku-X on the WWW

Since I implemented Sudoku-X in SudoCue, I was wondering where people would be able to find these puzzles on a regular basis. To my surprise: nowhere! Only websudoku.com has a weekly feature of variants, and Inertia only pretends to have them, leading you to their desktop program.

So I decided to run my batch generator for a while, and it came up with a wonderful series of puzzles, with various symmetries and a wide range in difficulty levels. I decided to focus on 2 difficulty levels, one for the beginners and one for the advanced players, keeping them both happy on my site.

Since all my puzzles are themed, I needed one for this new feature. X-Rays, X-Wings, X-Men and X-Files were amongst the candidates. Combining the puzzles with an archive made me choose X-Files, which happened to be problems that needed to be solved. I’m still probing the theme, but there will be more wordplay in this arena. I’m full of ideas.

On a side note: The addition of regular puzzles and the rewriting of all the on-site documentation has resulted in a steady growth in visitors. This seems to have a snowball effect, because more and more people discover my site. It must have good pageranks in Google. Quality does pay off in the end.

Crossword Killers

These puzzles have been posted by MikeJapan and h3lix on DJ-Ape’s forum.

They are an interesting variation which combine a zero-killer with crosswords in the empty regions. I adapted SumoCue to handle these puzzles. In “letter” mode, the program shows the placed digits and candidates as letters in the “zero” regions. In stead of cage combinations, there is a new tool that shows all remaining valid words for each region. This tool can be set to “horizontal” and “vertical” mode, because a single cell can belong to 2 words.

I have already implemented a new solving technique that eliminates candidates that do not occur in any valid word. There is a background interface with the Internet Anagram Server at Wordsmith to retrieve all valid words for the given letters. The SumoCue V2 save format can save the letter table.

I’m not sure what techniques to implement next. It’s easy to build the word lists into DLX and verify a unique solution, but it is nicer to have more human executable solving techniques. The next target could be invalid word combinations, where the combination violates the sudoku rule by placing repeating digits in a box. This could lead to words being eliminated from the list, because they cannot be used in any combination, which in turn could cause letter eliminations.

It looks like a pretty far-fetched technique, but it is still logical.

Another technique that I’ve been thinking about is a variation on the killer pair/triple/quad. When a word, when placed, would eliminate all candidates from a cell, or all combinations from a cage, the word cannot be placed. All cells of the cage must “see” the word, so this is not a technique that can be used on a large scale.

I’ll see what comes next.