Project Euler 96: Devise an algorithm for solving Su Doku puzzles

I was all excited when I first saw the headline of Problem 96 of Project Euler  since I love solving SuDoku puzzles. And I wasn’t disappointed when I saw the problem description which reads

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

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

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ “guess and test” methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and ‘Save Link/Target As…’), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

Ok, I have cheated a bit since I dabbled into making a solver for Sudoku puzzles a while ago, so I decided to reuse it for this solution. I have implemented a brute force solver as well as implemented logic limit the number of solutions.

One of the best places I have found for reading about solving strategies is here. He lists several advanced solving strategies though he misses some of the basic ones which I will use here.  But let’s jump right into the Brute force solution.

The code

I wont show the code here, as it is pretty long. But I want to give you a short primer to the files, so you can find your way around it.  You can download the source code here.

Grid.cs – Just a simple 9×9 grid of integers which will be used to give the solution

PossibleGrid.cs – A class I have made which makes a 9×9 grid where each cell can hold all the numbers 1-9. There are methods in the file to fix one cell and remove that number as a possible solution for other cells. So if I fix the upper left corner to 3 that is not a possible solution for the first row, column or box so those are removed as possible solutions. This file is mainly good for logic solutions, but speeds up the back tracking algorithm by keeping track of possible solutions.

Backtrack.cs – This contains the algorithm for backtrakcing as described earlier.

Run.cs – This contains the main method which reads the input file, does the timing and so on.

LogicSover.cs – contains one method for solving a sudoku by logic. It wont solve all Sudokus but it does reduce the number of possible solutions for most. You could implement more strategies in this file if you like.

Brute force solution

Creating a brute force solver for Sudoku is a pretty easy thing. It is usually called the back tracking algorithm. You start at the first cell and fill in the smallest valid number for the first cell. Then move to the next cell and repeat. You do this until you reach a cell with no valid entries.

When you encounter a cell with no valid solution you move back and increase the previous cell to the next lowest valid number. If such a number does not exist you move back until you encounter a cell you can change and then start moving forward again. It is a simple strategy, and often more than fast enough.

I have seen an example where the first row has the solution 9 8 7…. and that means we need to check almost all solutions before finding the correct one. For the average solution this is pretty okay though.

Running the code with only the backtracking algorithm gives us

The sum of 3 leftmost digits are 24702
Solution took 301,5991 ms

So it is fairly okay, but not as good as it could be.

Adding a bit of logic

I am pretty sure you will laugh when you hear the strategy I have employed to speed up the Sudoku solving. It is really very simple.

The strategy is as follows. I will go through a row to see if a number can only be placed in one cell in that row. There might be multiple valid solutions for each cell, but we can encounter a row where one of the cells has the valid solutions 1,2,3 and 5. But since 5 is not a valid solution for any other cell then we can fix this cell to 5. Once we fix a cell we should remove that option as a possible solution for the box and column.  This can be repeated for columns and boxes.

I told you it was simple, but is is effective. Adding this solution strategy gives us an execution time of

The sum of 3 leftmost digits are 24702
Solution took 32,6672 ms

Or about 10% of the brute force solution. In fact there are  40 of the given Sudokus which are completely solved by this method.

Wrapping up

The code for this was a reuse of some old code I had, and therefore somewhat longer than the usual solutions. You can download it right here.

The blog image is from Andreas Marx who solved a sudoku while drinking tea and decided to share that under the Creative Commons license.

Posted by Kristian

7 comments

Bjarki Ágúst

Your code is longer than mine, but also much faster (and cleaner).
Mine runs in about 1.5 seconds:

private class Sudoku
{
    public int[,] Board { get; set; }

    public Sudoku(int[,] board)
    {
        this.Board = board;
    }

    private static int[] Numbers = 1.To(9).ToArray();

    public void Solve()
    {
        bool anySolved, anyFound;

        do
        {
            anySolved = anyFound = false;

            for (int x = 0; x < 9; x++)
            {
                for (int y = 0; y < 9; y++)
                {
                    if (this.Board[x, y] != 0) continue;
                    anyFound = true;
                    IEnumerable<int> remaining = this.Remaining(x, y);

                    int fst = remaining.FirstOrDefault();
                    if (fst == 0) return;

                    if (!remaining.Skip(1).Any())
                    {
                        this.Board[x, y] = fst;
                        anySolved = true;
                    }
                }
            }
        } while (anyFound && anySolved);

        if (anyFound)
        {
            this.SolveBruteForce();
        }
    }

    public IEnumerable<int> Horizontal(int x)
    {
        for (int y = 0; y < 9; y++) if (this.Board[x, y] != 0) yield return this.Board[x, y];
    }

    public IEnumerable<int> Vertical(int y)
    {
        for (int x = 0; x < 9; x++) if (this.Board[x, y] != 0) yield return this.Board[x, y];
    }

    public IEnumerable<int> Box(int x, int y)
    {
        x = (x / 3) * 3;
        y = (y / 3) * 3;

        for (int xd = 0; xd < 3; xd++)
        {
            for (int yd = 0; yd < 3; yd++)
            {
                if (this.Board[x + xd, y + yd] != 0) yield return this.Board[x + xd, y + yd];
            }
        }
    }

    public bool Solved
    {
        get
        {
            for (int x = 0; x < 9; x++)
            {
                for (int y = 0; y < 9; y++)
                {
                    if (this.Board[x, y] == 0) return false;
                }
            }

            return true;
        }
    }

    public IEnumerable<int> Remaining(int x, int y)
    {
        return Numbers.Except(this.Horizontal(x).Concat(this.Vertical(y)).Concat(this.Box(x, y)));
    }

    public void SolveBruteForce()
    {
        int min = -1, minX = 0, minY = 0;

        for (int x = 0; x < 9; x++)
        {
            for (int y = 0; y < 9; y++)
            {
                if (this.Board[x, y] != 0) continue;

                var cur = Remaining(x, y);
                int count = cur.Count();
                if (min == -1 || count < min)
                {
                    minX = x;
                    minY = y;
                    min = count;
                }

                if (min == 2) break;
            }

            if (min == 2) break;
        }

        foreach (int rem in Remaining(minX, minY))
        {
            int[,] cur = (int[,])this.Board.Clone();
            this.Board[minX, minY] = rem;
            this.Solve();
            if (this.Solved) return;
            this.Board = cur;
        }
    }
}

[Problem("96", Description = "Devise an algorithm for solving Su Doku puzzles.")]
public void P96()
{
    var lines = File.ReadAllLines("Problem96.txt").Where(l => l[0] != 'G').Skip(0 * 9);
    int sum = 0;

    while (lines.Any())
    {
        Sudoku s = new Sudoku(lines.Take(9).Select(l => l.Select(c => c - '0').ToArray()).ToArray().ToMultidimensional());
        s.Solve();
        sum += s.Board[0, 0] * 100 + s.Board[0, 1] * 10 + s.Board[0, 2];
        lines = lines.Skip(9);
    }

    this.WriteLine(sum);
}

Yep, as I mentioned the main part of the code was written prior to solving this problem. So basically I just reused the code which I had not written with the intention of being small.

Jean-Marie Hachey

Hard to find …

A sudoku that cannot be solved with this application:
http://www.solution-sudoku.com/Default.aspx

One optimization that worked quite well in my implementation was to order the positions by how many possible digits they allow and backtrack over that (the list is recomputed at each backtracking step, when moving forward to the next position to tackle).

A further optimization: we are only asked for the first 3 digits (top-left) of the solution. You do not need to solve the entire puzzle, only enough so that you are certain of those three squares.

Carl J Appellof

Once again, I’m late to the game on commenting. I’ve been enjoying playing sudoku for a long time, and have several favorite strategies, which I coded up. Then ran into a paper by J. F. Crook on the topic of using “preemptive sets” to solve more difficult puzzles. http://www.ams.org/notices/200904/rtx090400460p.pdf
Actually, pretty simple to implement once I figured it out. That, combined with a backtracking method and my original methods resulted in a very fast solution:
Took 2.031425 ms
50 wins and 0 losses
Sum = 24702

I think my code does some extra work that’s unnecessary, so the solution might be sped up a little. I only found 4 of the puzzles needed backtracking at all!

Leave a Reply