# Sudoku

## Introduction

Sudoku is a popular puzzle where you place digits from 1 to 9 within a 9×9 grid according to certain rules. In each row, column, and 3×3 square, each digit must be represented exactly once. The following is a sample puzzle:

The following represents the solution to this puzzle:

## The 150,000 Puzzles

At first, I offered some of my puzzles on my blog. Unfortunately, after a while, that got to be a bit unwieldy. After about 50 postings, I started running out of things to say. And most of my comments had nothing to do with Sudoku anyways, and really belonged elsewhere on my blog.

And so I decided to present the puzzles in a slightly different format, within the permanent pages of my web site. Check the index at the top for my collections of puzzles, 20,000 per page. The first volume of “Advanced” puzzles includes almost all of the puzzles previously posted to my blog.

Here, you can find all the Sudoku puzzles you could ever want, all in printable form. If you are new to Sudoku, you may want to start with the Beginner Puzzles. These all have 30 seed values and 2-fold rotation symmetry. Once these get too easy for you, you can move up to the Standard Puzzles, which have fewer seed values. For both the Beginner and Standard puzzles, you don’t need to use any of the “advanced” solving techniques. However, some of the advanced techniques may help you out with those puzzles.

In the Hard Puzzles and Advanced Puzzles, use of the advanced techniques is definitely needed to solve the puzzles. The Advanced puzzles may be some of the hardest Sudoku puzzles you’ll find on the internet.

The last section of normal Sudoku puzzles are the Blackjack Puzzles, so named because they all have only 21 seed values. Are they any easier or more difficult than the others? Try them and find out!

If you want something a little bit different, the Nonomino Puzzles provide a twist to the game. Instead of nine 3×3 regions, the puzzle is tiled with irregularly shaped nonominos. Use of an advanced technique may or may not be required for these puzzles.

The Diagonal Sudoku Puzzles offer yet another challenging variation on the puzzle. In this game, the two diagonals must also have the digits from 1 to 9 represented just once.

Finally, the Challenge Puzzles provide some miscellaneous challenging puzzles. The first group of puzzles have just 20 initial values. The other puzzles are more Nonomino puzzles, but with 21 or fewer initial values. The latter puzzles of this group have just 14 initial values.

## The Program

When I first saw a Sudoku puzzle on the pages of the Toronto Star, of course, I had to try it out. Right away, I could see that the puzzle was quite amenable to being solved by computer program. I wrote my first program in Python, which is an excellent language for rapid development. I had a program working in no time.

There are a couple of approaches to solving Sudoku puzzles programmatically. The obvious one is the brute-force back-tracking method. All possibilities are tried, and when an impasse is reached, guesses are backed out, and the next possibility is tried.

For my program, I took the analytical approach. I wrote the program simulating how a person would solve the puzzle, applying various analytical techniques until a solution was reached. This is a more complex approach, but is faster. This approach has another advantage. The same program used to solve puzzles can also be used to randomly generate puzzles.

At this point, the Python program was getting a bit slow, especially when generating more difficult puzzles. And so next, I rewrote the program in C. This increased the generation speed tremendously. Further tweaking of the algorithms sped up the program further.

## FAQ

The best way to find the answer to a puzzle is to solve it. After all, if you look up the answer, it really doesn’t help you learn how to solve Sudoku puzzles. But the answers are available here.