76
\$\begingroup\$

Even though it's the first time I'm writing something this "big", it feels like I know C# quite well (it is very similar to Java after all). It's been nice to learn LINQ also and I am very impressed by the features (which is just like Steams in Java 8), and perhaps I have overused it here (if it's possible to do that).

Class summary

  • SudokuFactory: Contains static methods to create some Sudoku variations
  • SudokuBoard: Contains collection of SudokuRule and of SudokuTile
  • SudokuRule: Whether it's a box, a line, a row, or something entirely different doesn't matter. Contains a collection of SudokuTile that must be unique.
  • SudokuTile: Each tile in the puzzle. Can be "blocked" (like a hole in the puzzle), remembers it's possibleValues, and also contains a value (0 is used for tiles without a value)
  • SudokuProgress: Used to know what the progress of a solving step was.
  • Program: Main starting point. Contains tests for seven different Sudokus. All have been verified to be solved correctly.

Since this is the first time I'm using C# and LINQ, please tell me anything. All suggestions welcome. Except for the fact that the method box should be called Box. I'd be especially interested in cases where I could simplify some of the LINQ usage (trust me, there is a lot). I hope you are able to follow all the LINQ queries. I have tried to put some short comments where needed to explain what is happening. If you want an explanation for some part, post a comment and I will explain.

As usual, I have a tendency to make the challenge into something super-flexible with support for a whole lot of more or less unnecessary things. Some of the possible puzzles that this code can solve is:

  • A hard classic 9x9 Sudoku with 3x3 boxes that requires more advanced techniques (or in my case, more or less "brute force" by trial and error)
  • Nonomino
  • HyperSudoku
  • Samurai Sudoku
  • A classic Sudoku of any size with any number of boxes and size of boxes (only completely tested on 9x9 with 3x3 boxes and 4x4 with 2x2 boxes but any sizes should be possible)

These images are puzzles that are tested and solved in the below code:

The Weekend Challenge Sudoku Sudoku with "weird" boxes Sudoku with additional boxes Samurai Sudoku

One known issue with the implementation is if you would input an empty puzzle, then it would work for years to find all the possible combinations for it.

SudokuProgress

public enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }

SudokuTile

public class SudokuTile
{
    internal static SudokuProgress CombineSolvedState(SudokuProgress a, SudokuProgress b)
    {
        if (a == SudokuProgress.FAILED)
            return a;
        if (a == SudokuProgress.NO_PROGRESS)
            return b;
        if (a == SudokuProgress.PROGRESS)
            return b == SudokuProgress.FAILED ? b : a;
        throw new InvalidOperationException("Invalid value for a");
    }

    public const int CLEARED = 0;
    private int _maxValue;
    private int _value;
    private int _x;
    private int _y;
    private ISet<int> possibleValues;
    private bool _blocked;

    public SudokuTile(int x, int y, int maxValue)
    {
        _x = x;
        _y = y;
        _blocked = false;
        _maxValue = maxValue;
        possibleValues = new HashSet<int>();
        _value = 0;
    }

    public int Value
    {
        get { return _value; }
        set
        {
            if (value > _maxValue)
                throw new ArgumentOutOfRangeException("SudokuTile Value cannot be greater than " + _maxValue.ToString() + ". Was " + value);
            if (value < CLEARED)
                throw new ArgumentOutOfRangeException("SudokuTile Value cannot be zero or smaller. Was " + value);
            _value = value;
        }
    }

    public bool HasValue 
    {
        get { return Value != CLEARED; }
    }

    public string ToStringSimple()
    {
        return Value.ToString();
    }

    public override string ToString()
    {
        return String.Format("Value {0} at pos {1}, {2}. ", Value, _x, _y, possibleValues.Count);
    }

    internal void ResetPossibles()
    {
        possibleValues.Clear();
        foreach (int i in Enumerable.Range(1, _maxValue))
        {
            if (!HasValue || Value == i)
                possibleValues.Add(i);
        }
    }

    public void Block()
    {
        _blocked = true;
    }
    internal void Fix(int value, string reason) 
    {
        Console.WriteLine("Fixing {0} on pos {1}, {2}: {3}", value, _x, _y, reason);
        Value = value;
        ResetPossibles();
    }
    internal SudokuProgress RemovePossibles(IEnumerable<int> existingNumbers)
    {
        if (_blocked)
            return SudokuProgress.NO_PROGRESS;
        // Takes the current possible values and removes the ones existing in `existingNumbers`
        possibleValues = new HashSet<int>(possibleValues.Where(x => !existingNumbers.Contains(x)));
        SudokuProgress result = SudokuProgress.NO_PROGRESS;
        if (possibleValues.Count == 1)
        {
            Fix(possibleValues.First(), "Only one possibility");
            result = SudokuProgress.PROGRESS;
        }
        if (possibleValues.Count == 0)
            return SudokuProgress.FAILED;
        return result;
    }

    public bool IsValuePossible(int i) 
    {
        return possibleValues.Contains(i);
    }

    public int X { get { return _x; } }
    public int Y { get { return _y; } }
    public bool IsBlocked { get { return _blocked; } } // A blocked field can not contain a value -- used for creating 'holes' in the map
    public int PossibleCount 
    {
        get {
            return IsBlocked ? 1 : possibleValues.Count; 
        } 
    }
}

SudokuRule

public class SudokuRule : IEnumerable<SudokuTile>
{
    internal SudokuRule(IEnumerable<SudokuTile> tiles, string description)
    {
        _tiles = new HashSet<SudokuTile>(tiles);
        _description = description;
    }

    private ISet<SudokuTile> _tiles;
    private string _description;

    public bool CheckValid()
    {
        var filtered = _tiles.Where(tile => tile.HasValue);
        var groupedByValue = filtered.GroupBy(tile => tile.Value);
        return groupedByValue.All(group => group.Count() == 1);
    }
    public bool CheckComplete()
    {
        return _tiles.All(tile => tile.HasValue) && CheckValid();
    }

    internal SudokuProgress RemovePossibles()
    {
        // Tiles that has a number already
        IEnumerable<SudokuTile> withNumber = _tiles.Where(tile => tile.HasValue);

        // Tiles without a number
        IEnumerable<SudokuTile> withoutNumber = _tiles.Where(tile => !tile.HasValue);

        // The existing numbers in this rule
        IEnumerable<int> existingNumbers = new HashSet<int>(withNumber.Select(tile => tile.Value).Distinct().ToList());

        SudokuProgress result = SudokuProgress.NO_PROGRESS;
        foreach (SudokuTile tile in withoutNumber)
            result = SudokuTile.CombineSolvedState(result, tile.RemovePossibles(existingNumbers));
        return result;
    }
    internal SudokuProgress CheckForOnlyOnePossibility() 
    {
        // Check if there is only one number within this rule that can have a specific value
        IList<int> existingNumbers = _tiles.Select(tile => tile.Value).Distinct().ToList();
        SudokuProgress result = SudokuProgress.NO_PROGRESS;

        foreach (int value in Enumerable.Range(1, _tiles.Count))
        {
            if (existingNumbers.Contains(value)) // this rule already has the value, skip checking for it
                continue;
            var possibles = _tiles.Where(tile => !tile.HasValue && tile.IsValuePossible(value)).ToList();
            if (possibles.Count == 0)
                return SudokuProgress.FAILED;
            if (possibles.Count == 1)
            {
                possibles.First().Fix(value, "Only possible in rule " + ToString());
                result = SudokuProgress.PROGRESS;
            }
        }
        return result;
    }

    internal SudokuProgress Solve()
    {
        // If both are null, return null (indicating no change). If one is null, return the other. Else return result1 && result2
        SudokuProgress result1 = RemovePossibles();
        SudokuProgress result2 = CheckForOnlyOnePossibility();
        return SudokuTile.CombineSolvedState(result1, result2);
    }

    public override string ToString()
    {
        return _description;
    }

    public IEnumerator<SudokuTile> GetEnumerator()
    {
        return _tiles.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public string Description { get { return _description; } }
}

SudokuBoard:

public class SudokuBoard
{
    public SudokuBoard(SudokuBoard copy)
    {
        _maxValue = copy._maxValue;
        tiles = new SudokuTile[copy.Width, copy.Height];
        CreateTiles();
        // Copy the tile values
        foreach (var pos in SudokuFactory.box(Width, Height))
        {
            tiles[pos.Item1, pos.Item2] = new SudokuTile(pos.Item1, pos.Item2, _maxValue);
            tiles[pos.Item1, pos.Item2].Value = copy.tiles[pos.Item1, pos.Item2].Value;
        }

        // Copy the rules
        foreach (SudokuRule rule in copy.rules) 
        {
            var ruleTiles = new HashSet<SudokuTile>();
            foreach (SudokuTile tile in rule) 
            {
                ruleTiles.Add(tiles[tile.X, tile.Y]);
            }
            rules.Add(new SudokuRule(ruleTiles, rule.Description));
        }
    }

    public SudokuBoard(int width, int height, int maxValue)
    {
        _maxValue = maxValue;
        tiles = new SudokuTile[width, height];
        CreateTiles();
        if (_maxValue == width || _maxValue == height) // If maxValue is not width or height, then adding line rules would be stupid
            SetupLineRules();
    }

    public SudokuBoard(int width, int height) : this(width, height, Math.Max(width, height)) {}

    private int _maxValue;

    private void CreateTiles()
    {
        foreach (var pos in SudokuFactory.box(tiles.GetLength(0), tiles.GetLength(1)))
        {
            tiles[pos.Item1, pos.Item2] = new SudokuTile(pos.Item1, pos.Item2, _maxValue);
        }
    }

    private void SetupLineRules()
    {
        // Create rules for rows and columns
        for (int x = 0; x < Width; x++)
        {
            IEnumerable<SudokuTile> row = GetCol(x);
            rules.Add(new SudokuRule(row, "Row " + x.ToString()));
        }
        for (int y = 0; y < Height; y++)
        {
            IEnumerable<SudokuTile> col = GetRow(y);
            rules.Add(new SudokuRule(col, "Col " + y.ToString()));
        }
    }

    internal IEnumerable<SudokuTile> TileBox(int startX, int startY, int sizeX, int sizeY)
    {
        return from pos in SudokuFactory.box(sizeX, sizeY) select tiles[startX + pos.Item1, startY + pos.Item2];
    }

    private IEnumerable<SudokuTile> GetRow(int row)
    {
        for (int i = 0; i < tiles.GetLength(0); i++)
        {
            yield return tiles[i, row];
        }
    }
    private IEnumerable<SudokuTile> GetCol(int col)
    {
        for (int i = 0; i < tiles.GetLength(1); i++)
        {
            yield return tiles[col, i];
        }
    }

    private ISet<SudokuRule> rules = new HashSet<SudokuRule>();
    private SudokuTile[,] tiles;

    public int Width
    {
        get { return tiles.GetLength(0); }
    }

    public int Height {
        get { return tiles.GetLength(1); }
    }

    public void CreateRule(string description, params SudokuTile[] tiles)
    {
        rules.Add(new SudokuRule(tiles, description));
    }
    public void CreateRule(string description, IEnumerable<SudokuTile> tiles)
    {
        rules.Add(new SudokuRule(tiles, description));
    }

    public bool CheckValid()
    {
        return rules.All(rule => rule.CheckValid());
    }

    public IEnumerable<SudokuBoard> Solve()
    {
        ResetSolutions();
        SudokuProgress simplify = SudokuProgress.PROGRESS;
        while (simplify == SudokuProgress.PROGRESS) simplify = Simplify();

        if (simplify == SudokuProgress.FAILED)
            yield break;

        // Find one of the values with the least number of alternatives, but that still has at least 2 alternatives
        var query = from rule in rules
                    from tile in rule
                    where tile.PossibleCount > 1
                    orderby tile.PossibleCount ascending
                    select tile;

        SudokuTile chosen = query.FirstOrDefault();
        if (chosen == null)
        {
            // The board has been completed, we're done!
            yield return this;
            yield break;
        }

        Console.WriteLine("SudokuTile: " + chosen.ToString());

        foreach (var value in Enumerable.Range(1, _maxValue))
        {
            // Iterate through all the valid possibles on the chosen square and pick a number for it
            if (!chosen.IsValuePossible(value))
                continue;
            var copy = new SudokuBoard(this);
            copy.Tile(chosen.X, chosen.Y).Fix(value, "Trial and error");
            foreach (var innerSolution in copy.Solve()) 
                yield return innerSolution;
        }
        yield break;
    }

    public void Output()
    {
        for (int y = 0; y < tiles.GetLength(1); y++)
        {
            for (int x = 0; x < tiles.GetLength(0); x++)
            {
                Console.Write(tiles[x, y].ToStringSimple());
            }
            Console.WriteLine();
        }
    }

    public SudokuTile Tile(int x, int y)
    {
        return tiles[x, y];
    }

    private int _rowAddIndex;

    public void AddRow(string s)
    {
        // Method for initializing a board from string
        for (int i = 0; i < s.Length; i++)
        {
            var tile = tiles[i, _rowAddIndex];
            if (s[i] == '/')
            {
                tile.Block();
                continue;
            }
            int value = s[i] == '.' ? 0 : (int)Char.GetNumericValue(s[i]);
            tile.Value = value;
        }
        _rowAddIndex++;
    }

    internal void ResetSolutions()
    {
        foreach (SudokuTile tile in tiles)
            tile.ResetPossibles();
    }
    internal SudokuProgress Simplify()
    {
        SudokuProgress result = SudokuProgress.NO_PROGRESS;
        bool valid = CheckValid();
        if (!valid)
            return SudokuProgress.FAILED;

        foreach (SudokuRule rule in rules)
            result = SudokuTile.CombineSolvedState(result, rule.Solve());

        return result;
    }

    internal void AddBoxesCount(int boxesX, int boxesY)
    {
        int sizeX = Width / boxesX;
        int sizeY = Height / boxesY;

        var boxes = SudokuFactory.box(sizeX, sizeY);
        foreach (var pos in boxes)
        {
            IEnumerable<SudokuTile> boxTiles = TileBox(pos.Item1 * sizeX, pos.Item2 * sizeY, sizeX, sizeY);
            CreateRule("Box at (" + pos.Item1.ToString() + ", " + pos.Item2.ToString() + ")", boxTiles);
        }
    }

    internal void OutputRules()
    {
        foreach (var rule in rules)
        {
            Console.WriteLine(String.Join(",", rule) + " - " + rule.ToString());
        }
    }
}

SudokuFactory:

public class SudokuFactory
{
    private const int DefaultSize = 9;
    private const int SamuraiAreas = 7;
    private const int BoxSize = 3;
    private const int HyperMargin = 1;

    public static IEnumerable<Tuple<int, int>> box(int sizeX, int sizeY)
    {
        foreach (int x in Enumerable.Range(0, sizeX))
        {
            foreach (int y in Enumerable.Range(0, sizeY))
            {
                yield return new Tuple<int, int>(x, y);
            }
        }
    }

    public static SudokuBoard Samurai()
    {
        SudokuBoard board = new SudokuBoard(SamuraiAreas*BoxSize, SamuraiAreas*BoxSize, DefaultSize);
        // Removed the empty areas where there are no tiles
        var queriesForBlocked = new List<IEnumerable<SudokuTile>>();
        queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2                            ));
        queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2 + DefaultSize * 2 - BoxSize));
        queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1                            , pos.Item2 + DefaultSize));
        queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1 + DefaultSize * 2 - BoxSize, pos.Item2 + DefaultSize));
        foreach (var query in queriesForBlocked) 
        {
            foreach (var tile in query) tile.Block();
        }

        // Select the tiles in the 3 x 3 area (area.X, area.Y) and create rules for them
        foreach (var area in box(SamuraiAreas, SamuraiAreas)) 
        {
            var tilesInArea = from pos in box(BoxSize, BoxSize) select board.Tile(area.Item1 * BoxSize + pos.Item1, area.Item2 * BoxSize + pos.Item2);
            if (tilesInArea.First().IsBlocked)
                continue;
            board.CreateRule("Area " + area.Item1.ToString() + ", " + area.Item2.ToString(), tilesInArea);
        }

        // Select all rows and create columns for them
        var cols = from pos in box(board.Width,  1) select new { X = pos.Item1, Y = pos.Item2 };
        var rows = from pos in box(1, board.Height) select new { X = pos.Item1, Y = pos.Item2 };
        foreach (var posSet in Enumerable.Range(0, board.Width))
        {
            board.CreateRule("Column Upper " + posSet, from pos in box(1, DefaultSize) select board.Tile(posSet, pos.Item2));
            board.CreateRule("Column Lower " + posSet, from pos in box(1, DefaultSize) select board.Tile(posSet, pos.Item2 + DefaultSize + BoxSize));

            board.CreateRule("Row Left "  + posSet, from pos in box(DefaultSize, 1) select board.Tile(pos.Item1, posSet));
            board.CreateRule("Row Right " + posSet, from pos in box(DefaultSize, 1) select board.Tile(pos.Item1 + DefaultSize + BoxSize, posSet));

            if (posSet >= BoxSize*2 && posSet < BoxSize*2 + DefaultSize)
            {
                // Create rules for the middle sudoku
                board.CreateRule("Column Middle " + posSet, from pos in box(1, 9) select board.Tile(posSet, pos.Item2 + BoxSize*2));
                board.CreateRule("Row Middle "    + posSet, from pos in box(9, 1) select board.Tile(pos.Item1 + BoxSize*2, posSet));
            }
        }
        return board;
    }

    public static SudokuBoard SizeAndBoxes(int width, int height, int boxCountX, int boxCountY)
    {
        SudokuBoard board = new SudokuBoard(width, height);
        board.AddBoxesCount(boxCountX, boxCountY);
        return board;
    }

    public static SudokuBoard ClassicWith3x3Boxes()
    {
        return SizeAndBoxes(DefaultSize, DefaultSize, DefaultSize / BoxSize, DefaultSize / BoxSize);
    }

    public static SudokuBoard ClassicWith3x3BoxesAndHyperRegions()
    {
        SudokuBoard board = ClassicWith3x3Boxes();
        const int HyperSecond = HyperMargin + BoxSize + HyperMargin;
        // Create the four extra hyper regions
        board.CreateRule("HyperA", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperMargin, pos.Item2 + HyperMargin));
        board.CreateRule("HyperB", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperSecond, pos.Item2 + HyperMargin));
        board.CreateRule("HyperC", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperMargin, pos.Item2 + HyperSecond));
        board.CreateRule("HyperD", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperSecond, pos.Item2 + HyperSecond));
        return board;
    }

    public static SudokuBoard ClassicWithSpecialBoxes(string[] areas)
    {
        int sizeX = areas[0].Length;
        int sizeY = areas.Length;
        SudokuBoard board = new SudokuBoard(sizeX, sizeY);
        var joinedString = String.Join("", areas);
        var grouped = joinedString.Distinct();

        // Loop through all the unique characters
        foreach (var ch in grouped)
        {
            // Select the rule tiles based on the index of the character
            var ruleTiles = from i in Enumerable.Range(0, joinedString.Length)
                    where joinedString[i] == ch // filter out any non-matching characters
                    select board.Tile(i % sizeX, i / sizeY);
            board.CreateRule("Area " + ch.ToString(), ruleTiles);
        }

        return board;
    }
}

Program:

static class Program
{
    [STAThread]
    static void Main()
    {
        SolveFail();
        SolveClassic();
        SolveSmall();
        SolveExtraZones();
        SolveHyper();
        SolveSamurai();
        SolveIncompleteClassic();
    }
    private static void SolveFail()
    {
        SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2);
        board.AddRow("0003");
        board.AddRow("0204"); // the 2 must be a 1 on this row to be solvable
        board.AddRow("1000");
        board.AddRow("4000");
        CompleteSolve(board);
    }
    private static void SolveExtraZones()
    {
        // http://en.wikipedia.org/wiki/File:Oceans_Hypersudoku18_Puzzle.svg
        SudokuBoard board = SudokuFactory.ClassicWith3x3BoxesAndHyperRegions();
        board.AddRow(".......1.");
        board.AddRow("..2....34");
        board.AddRow("....51...");
        board.AddRow(".....65..");
        board.AddRow(".7.3...8.");
        board.AddRow("..3......");
        board.AddRow("....8....");
        board.AddRow("58....9..");
        board.AddRow("69.......");
        CompleteSolve(board);
    }
    private static void SolveSmall()
    {
        SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2);
        board.AddRow("0003");
        board.AddRow("0004");
        board.AddRow("1000");
        board.AddRow("4000");
        CompleteSolve(board);
    }
    private static void SolveHyper()
    {
        // http://en.wikipedia.org/wiki/File:A_nonomino_sudoku.svg
        string[] areas = new string[]{
           "111233333",
           "111222333",
           "144442223",
           "114555522",
           "444456666",
           "775555688",
           "977766668",
           "999777888",
           "999997888"
        };
        SudokuBoard board = SudokuFactory.ClassicWithSpecialBoxes(areas);
        board.AddRow("3.......4");
        board.AddRow("..2.6.1..");
        board.AddRow(".1.9.8.2.");
        board.AddRow("..5...6..");
        board.AddRow(".2.....1.");
        board.AddRow("..9...8..");
        board.AddRow(".8.3.4.6.");
        board.AddRow("..4.1.9..");
        board.AddRow("5.......7");
        CompleteSolve(board);

    }
    private static void SolveSamurai()
    {
        // http://www.freesamuraisudoku.com/1001HardSamuraiSudokus.aspx?puzzle=42
        SudokuBoard board = SudokuFactory.Samurai();
        board.AddRow("6..8..9..///.....38..");
        board.AddRow("...79....///89..2.3..");
        board.AddRow("..2..64.5///...1...7.");
        board.AddRow(".57.1.2..///..5....3.");
        board.AddRow(".....731.///.1.3..2..");
        board.AddRow("...3...9.///.7..429.5");
        board.AddRow("4..5..1...5....5.....");
        board.AddRow("8.1...7...8.2..768...");
        board.AddRow(".......8.23...4...6..");
        board.AddRow("//////.12.4..9.//////");
        board.AddRow("//////......82.//////");
        board.AddRow("//////.6.....1.//////");
        board.AddRow(".4...1....76...36..9.");
        board.AddRow("2.....9..8..5.34...81");
        board.AddRow(".5.873......9.8..23..");
        board.AddRow("...2....9///.25.4....");
        board.AddRow("..3.64...///31.8.....");
        board.AddRow("..75.8.12///...6.14..");
        board.AddRow(".......2.///.31...9..");
        board.AddRow("..17.....///..7......");
        board.AddRow(".7.6...84///8...7..5.");
        CompleteSolve(board);
    }

    private static void SolveClassic()
    {
        var board = SudokuFactory.ClassicWith3x3Boxes();
        board.AddRow("...84...9");
        board.AddRow("..1.....5");
        board.AddRow("8...2146.");
        board.AddRow("7.8....9.");
        board.AddRow(".........");
        board.AddRow(".5....3.1");
        board.AddRow(".2491...7");
        board.AddRow("9.....5..");
        board.AddRow("3...84...");
        CompleteSolve(board);
    }

    private static void SolveIncompleteClassic()
    {
        var board = SudokuFactory.ClassicWith3x3Boxes();
        board.AddRow("...84...9");
        board.AddRow("..1.....5");
        board.AddRow("8...2.46."); // Removed a "1" on this line
        board.AddRow("7.8....9.");
        board.AddRow(".........");
        board.AddRow(".5....3.1");
        board.AddRow(".2491...7");
        board.AddRow("9.....5..");
        board.AddRow("3...84...");
        CompleteSolve(board);
    }

    private static void CompleteSolve(SudokuBoard board)
    {
        Console.WriteLine("Rules:");
        board.OutputRules();
        Console.WriteLine("Board:");
        board.Output();
        var solutions = board.Solve().ToList();
        Console.WriteLine("Base Board Progress:");
        board.Output();
        Console.WriteLine("--");
        Console.WriteLine("--");
        Console.WriteLine("All " + solutions.Count + " solutions:");
        var i = 1;
        foreach (var solution in solutions)
        {
            Console.WriteLine("----------------");
            Console.WriteLine("Solution " + i++.ToString() + " / " + solutions.Count + ":");
            solution.Output();
        }
    }
}
\$\endgroup\$
  • 14
    \$\begingroup\$ Simon-André "Extra Mile" Forsberg is the name! \$\endgroup\$ – Mathieu Guindon Dec 15 '13 at 22:25
20
+500
\$\begingroup\$

This is amazing. Especially for person who is not using C# every day for years.


My main concerns are

  • too many thing that are public that should be internal, sometimes internal members can be turned to private. Use the most restrictive access level that makes sense for a particular member.
  • error-prone method AddRow of SudokuBoard. I'd prefer single string array passing to SudokuFactory constructor instead of multiple AddRow calls. It's easy to call this method too many or too few times to get a runtime exception.
  • absence of some string representation of solution result that could be used in unit tests.
  • console output method like Output and OutputRules in core classes. They should reside in Program because they are just used for console output, nothing more.
  • absence of unit tests. I've moved your logic to separate library and added unit test project. This is the first thing I did when I started to refactor your code to be sure that my refactoring won't break anything.
    Also I'd use .NET Standard library type. This will allow to reuse the same logic for website, mobile (Xamarin) and desktop applications.

Unit tests

To add unit tests I've added string[] tileDefinitions parameter to SudokuBoard constructors (also they should be internal):

internal SudokuBoard(int width, int height, int maxValue, string[] tileDefinitions)
{
    _maxValue = maxValue;
    tiles = new SudokuTile[width, height];
    CreateTiles();
    if (_maxValue == width || _maxValue == height) // If maxValue is not width or height, then adding line rules would be stupid
        SetupLineRules();

    Populate(tileDefinitions);
}

internal SudokuBoard(int width, int height, string[] tileDefinitions) : this(width, height, Math.Max(width, height), tileDefinitions)
{
}

Also I've removed _rowAddIndex field and replaced AddRow method with PopulateTiles:

private void PopulateTiles(string[] tileDefinitions)
{
    for (int row = 0; row < tileDefinitions.Length; row++)
    {
        string tileDefinition = tileDefinitions[row];

        for (int column = 0; column < tileDefinition.Length; column++)
        {
            SudokuTile tile = _tiles[column, row];
            if (tileDefinition[column] == '/')
            {
                tile.Block();
                continue;
            }
            tile.Value = tileDefinition[column] == '.' ? SudokuTile.CLEARED : (int)char.GetNumericValue(tileDefinition[column]);
        }
    }
}

Now I've added string[] tileDefinitions to all SudokuFactory methods.

To get simple string representation of sudoku solution that could be easily used in unit tests and maybe in other projects I've added string[] TileDefinitions public property to SudokuBoard:

public string[] TileDefinitions => tiles
    .Cast<SudokuTile>()
    .OrderBy(t => t.X)
    .ThenBy(t => t.Y)
    .GroupBy(t => t.Y)
    .Select(g => string.Join(string.Empty, g.Select(t => t.Value)))
    .ToArray();

Now code of our unit tests (I've reused your code from console output for test cases). I'm using XUnit here:

public class SudokuSolverTests
{
    [Fact]
    public void SudokuBoard_Solve_NoSolutionFound()
    {
        // Arrange
        SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2, new[]
        {
            "0003",
            "0204", // the 2 must be a 1 on this row to be solvable
            "1000",
            "4000"
        });

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.False(solutions.Any());
    }

    [Fact]
    public void SudokuBoard_Solve_ClassicWithSolution()
    {
        // Arrange
        SudokuBoard board = SudokuFactory.ClassicWith3x3Boxes(new[]
        {
            "...84...9",
            "..1.....5",
            "8...2146.",
            "7.8....9.",
            ".........",
            ".5....3.1",
            ".2491...7",
            "9.....5..",
            "3...84..."
        });

        string[] tileDefinitions = new[]
        {
            "632845179",
            "471369285",
            "895721463",
            "748153692",
            "163492758",
            "259678341",
            "524916837",
            "986237514",
            "317584926",
        };

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Single(solutions);
        Assert.Equal(tileDefinitions, solutions.First().TileDefinitions);
    }

    [Fact]
    public void SudokoBoard_Solve_ClassicWithMultipleSolutions()
    {
        // Arrange
        SudokuBoard board = SudokuFactory.ClassicWith3x3Boxes(new[]
        {
            "...84...9",
            "..1.....5",
            "8...2.46.", // Removed a "1" on this line
            "7.8....9.",
            ".........",
            ".5....3.1",
            ".2491...7",
            "9.....5..",
            "3...84..."
        });

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Equal(20, solutions.Count());
    }

    [Fact]
    public void SudukoBoard_Solve_SmallWithSolution()
    {
        // Arrange
        SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2, new[]
        {
            "0003",
            "0004",
            "1000",
            "4000"
        });

        string[] tileDefinitions = new[]
        {
            "2413",
            "3124",
            "1342",
            "4231"
        };

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Single(solutions);
        Assert.Equal(tileDefinitions, solutions.Single().TileDefinitions);
    }

    [Fact]
    public void SudokoBoard_Solve_ExtraZonesWithSolution()
    {
        // Arrange
        // http://en.wikipedia.org/wiki/File:Oceans_Hypersudoku18_Puzzle.svg
        SudokuBoard board = SudokuFactory.ClassicWith3x3BoxesAndHyperRegions(new[]
        {
            ".......1.",
            "..2....34",
            "....51...",
            ".....65..",
            ".7.3...8.",
            "..3......",
            "....8....",
            "58....9..",
            "69......."
        });

        string[] tileDefinitions = new[]
        {
            "946832715",
            "152697834",
            "738451296",
            "819726543",
            "475319682",
            "263548179",
            "327985461",
            "584163927",
            "691274358"
        };

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Single(solutions);
        Assert.Equal(tileDefinitions, solutions.First().TileDefinitions);
    }

    [Fact]
    public void SudokoBoard_Solve_HyperWithSolution()
    {
        // Arrange
        // http://en.wikipedia.org/wiki/File:A_nonomino_sudoku.svg
        string[] areas = new string[]
        {
            "111233333",
            "111222333",
            "144442223",
            "114555522",
            "444456666",
            "775555688",
            "977766668",
            "999777888",
            "999997888"
        };
        SudokuBoard board = SudokuFactory.ClassicWithSpecialBoxes(areas, new[]
        {
            "3.......4",
            "..2.6.1..",
            ".1.9.8.2.",
            "..5...6..",
            ".2.....1.",
            "..9...8..",
            ".8.3.4.6.",
            "..4.1.9..",
            "5.......7"
        });

        string[] tileDefinitions = new[]
        {
            "358196274",
            "492567138",
            "613978425",
            "175842693",
            "826453719",
            "249731856",
            "987324561",
            "734615982",
            "561289347"
        };

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Single(solutions);
        Assert.Equal(tileDefinitions, solutions.First().TileDefinitions);
    }

    [Fact]
    public void SudokoBoard_Solve_SamuraiWithSolution()
    {
        // Arrange
        // http://www.freesamuraisudoku.com/1001HardSamuraiSudokus.aspx?puzzle=42
        SudokuBoard board = SudokuFactory.Samurai(new[]
        {
            "6..8..9..///.....38..",
            "...79....///89..2.3..",
            "..2..64.5///...1...7.",
            ".57.1.2..///..5....3.",
            ".....731.///.1.3..2..",
            "...3...9.///.7..429.5",
            "4..5..1...5....5.....",
            "8.1...7...8.2..768...",
            ".......8.23...4...6..",
            "//////.12.4..9.//////",
            "//////......82.//////",
            "//////.6.....1.//////",
            ".4...1....76...36..9.",
            "2.....9..8..5.34...81",
            ".5.873......9.8..23..",
            "...2....9///.25.4....",
            "..3.64...///31.8.....",
            "..75.8.12///...6.14..",
            ".......2.///.31...9..",
            "..17.....///..7......",
            ".7.6...84///8...7..5."
        });

        string[] tileDefinitions = new[]
        {
            "674825931000142673859",
            "513794862000897425361",
            "982136475000563189472",
            "357619248000425916738",
            "298457316000918357246",
            "146382597000376842915",
            "469578123457689534127",
            "821963754689231768594",
            "735241689231754291683",
            "000000512748396000000",
            "000000497163825000000",
            "000000368592417000000",
            "746921835976142368597",
            "238456971824563497281",
            "159873246315978152346",
            "815237469000625749813",
            "923164758000314825769",
            "467598312000789631425",
            "694385127000431586972",
            "581742693000257914638",
            "372619584000896273154"
        };

        // Act
        IEnumerable<SudokuBoard> solutions = board.Solve();

        // Assert
        Assert.Single(solutions);
        Assert.Equal(tileDefinitions, solutions.First().TileDefinitions);
    }
}

Refactoring

I've applied already mentioned refactoring ideas from other answers so I won't mention them separately.

Also I'm using expression-bodied members, string interpolations and local functions from newer versions of C# which weren't available when you wrote your post.

SudokuTile

Properties can be grouped by readonly/const and mutable:

internal const int CLEARED = 0;
private readonly int _maxValue;
private readonly int _x;
private readonly int _y;

private IEnumerable<int> _possibleValues = Enumerable.Empty<int>();
private int _value = 0;
private bool _blocked = false;

_possibleValues should begin with underscore to be consistent with your naming convention. Type of _possibleValues can be safely replaced from ISet<int> to more primitive IEnumerable<int>. ResetPossibles method should be simplified:

internal void ResetPossibles()
{
    if (HasValue)
        _possibleValues = Enumerable.Repeat(Value, 1);
    else
        _possibleValues = Enumerable.Range(1, _maxValue);
}

Line

possibleValues = new HashSet<int>(possibleValues.Where(x => !existingNumbers.Contains(x)));

in RemovePossibles method can be easily replaced using Except LINQ method

_possibleValues = _possibleValues.Except(existingNumbers);

Also you can replace double if with switch statement in RemovePossibles method. Result:

internal SudokuProgress RemovePossibles(IEnumerable<int> existingNumbers)
{
    if (_blocked)
        return SudokuProgress.NO_PROGRESS;

    // Takes the current possible values and removes the ones existing in `existingNumbers`
    _possibleValues = _possibleValues.Except(existingNumbers);

    switch (_possibleValues.Count())
    {
        case 0:
            return SudokuProgress.FAILED;
        case 1:
            Fix(_possibleValues.First(), "Only one possibility");
            return SudokuProgress.PROGRESS;
        default:
            return SudokuProgress.NO_PROGRESS;
    }
}

SudokuRule

Here we should change _tiles field type from ISet<SudokuTile> to IEnumerable<SudokuTile> because you won't use any collection modification methods like Add, Remove or Clear. Collection is used only for reading. But you can preserve the line

_tiles = new HashSet<SudokuTile>(tiles);

in constructor because LINQ methods have deferred execution and here collection should be calculated immediately. But I've replaced this with

_tiles = tiles.ToArray();

just because this is shorter.

Also your fields should be readonly

private readonly IEnumerable<SudokuTile> _tiles;
private readonly string _description;

Line in RemovePossibles method

IEnumerable<int> existingNumbers = new HashSet<int>(withNumber.Select(tile => tile.Value).Distinct().ToList());

has a lot of redundancies:

  • HashSet<int> constructor call doesn't make sense here, because you've get materialized collection using ToList method call
  • but even ToList method call is redundant here because this number collection are passed to SudokuTile.RemovePossibles which immediately modifies _possibleValues collection.
  • Distinct call is also redundant here because you've checked all your rules before using SudokuBoard.Simplify method using line

    bool valid = _rules.All(rule => rule.CheckValid());
    

    so all your tile values are already distinct here.

So this line can be shorten to

IEnumerable<int> existingNumbers = withNumber.Select(tile => tile.Value);

Also line in CheckForOnlyOnePossibility method

IList<int> existingNumbers = _tiles.Select(tile => tile.Value).Distinct().ToList();

has issues

  • You're using existingNumbers as collection only for reading using Contains method, so IList<int> can be safely replaced with IEnumerable<int>.

  • ToList call is redundant here because Contains method is not using deferred execution.

  • Distinct call is also redundant here because you've checked all your rules before using SudokuBoard.Simplify method using line

    bool valid = _rules.All(rule => rule.CheckValid());
    

    so all your tile values are already distinct here.

So this line can be shorten to

IEnumerable<int> existingNumbers = _tiles.Select(tile => tile.Value);

SudokuBoard

I think it'll better to move all field definitions to top of the class with readonly modifier. Also I've add underscore to field names to enforce your naming convention consistency.

private readonly List<SudokuRule> _rules = new List<SudokuRule>();
private readonly SudokuTile[,] _tiles;
private readonly int _maxValue;

Also I've change _rules type to List<SudokuRule> because it's more friendly with LINQ (because LINQ has ToList method but not ToSet).


Double loop in SudokuBoard copy constructor can be simplified with single LINQ statement (by the way I've changed SudokuFactory.Box return type from faceless Tuple to more meaningful Point):

internal SudokuBoard(SudokuBoard copy)
{
    _maxValue = copy._maxValue;
    _tiles = new SudokuTile[copy.Width, copy.Height];
    CreateTiles();
    // Copy the tile values
    foreach (Point pos in SudokuFactory.Box(Width, Height))
    {
        _tiles[pos.X, pos.Y] = new SudokuTile(pos.X, pos.Y, _maxValue)
        {
            Value = copy[pos.X, pos.Y].Value
        };
    }

    // Copy the rules
    _rules = copy._rules
        .Select(rule => new SudokuRule(rule.Select(tile => _tiles[tile.X, tile.Y]), rule.Description))
        .ToList();
}

This big piece of code

private void SetupLineRules()
{
    // Create rules for rows and columns
    for (int x = 0; x < Width; x++)
    {
        IEnumerable<SudokuTile> row = GetCol(x);
        rules.Add(new SudokuRule(row, "Row " + x.ToString()));
    }
    for (int y = 0; y < Height; y++)
    {
        IEnumerable<SudokuTile> col = GetRow(y);
        rules.Add(new SudokuRule(col, "Col " + y.ToString()));
    }
}

private IEnumerable<SudokuTile> GetRow(int row)
{
    for (int i = 0; i < tiles.GetLength(0); i++)
    {
        yield return tiles[i, row];
    }
}
private IEnumerable<SudokuTile> GetCol(int col)
{
    for (int i = 0; i < tiles.GetLength(1); i++)
    {
        yield return tiles[col, i];
    }
}

can be replaced with couple of lines:

private void SetupLineRules()
{
    // Create rules for rows and columns
    for (int x = 0; x < Width; x++)
        _rules.Add(new SudokuRule(Enumerable.Range(0, _tiles.GetLength(1)).Select(i => _tiles[x, i]), $"Row {x}"));

    for (int y = 0; y < Height; y++)
        _rules.Add(new SudokuRule(Enumerable.Range(0, _tiles.GetLength(0)).Select(i => _tiles[i, y]), $"Col {y}"));
}

Tile method can be replaced with indexer to access tiles of board via array syntax:

public SudokuTile this[int x, int y] => _tiles[x, y];

Simplify method can be simplified using Aggregate LINQ method and variable inlining:

private SudokuProgress Simplify()
{
    bool valid = _rules.All(rule => rule.CheckValid());
    if (!valid)
        return SudokuProgress.FAILED;

    return _rules.Aggregate(SudokuProgress.NO_PROGRESS,
        (progress, rule) => SudokuTile.CombineSolvedState(progress, rule.Solve()));
}

All short and simple one-time used stuff like CheckValid, TileBox, ResetSolutions, Simplify, SetupLineRules should be inlined or used as local function. Result file will be listed below.

SudokuFactory

Refactored Box method using advices from several other answers:

internal static IEnumerable<Point> Box(int sizeX, int sizeY)
{
    return
        from x in Enumerable.Range(0, sizeX)
        from y in Enumerable.Range(0, sizeY)
        select new Point(x, y);
}

Replaced this code from Samurai method

SudokuBoard board = new SudokuBoard(SamuraiAreas*BoxSize, SamuraiAreas*BoxSize, DefaultSize);
// Removed the empty areas where there are no tiles
var queriesForBlocked = new List<IEnumerable<SudokuTile>>();
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2                            ));
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2 + DefaultSize * 2 - BoxSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1                            , pos.Item2 + DefaultSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1 + DefaultSize * 2 - BoxSize, pos.Item2 + DefaultSize));
foreach (var query in queriesForBlocked) 
{
    foreach (var tile in query) tile.Block();
}

with collection initializer and SelectMany LINQ method:

SudokuBoard board = new SudokuBoard(SamuraiAreas * BoxSize, SamuraiAreas * BoxSize, DefaultSize, tileDefinitions);
// Removed the empty areas where there are no tiles
IEnumerable<SudokuTile> tiles = new[]
{
    Box(BoxSize, BoxSize * 2).Select(pos => board[pos.X + DefaultSize, pos.Y]),
    Box(BoxSize, BoxSize * 2).Select(pos => board[pos.X + DefaultSize, pos.Y + DefaultSize * 2 - BoxSize]),
    Box(BoxSize * 2, BoxSize).Select(pos => board[pos.X, pos.Y + DefaultSize]),
    Box(BoxSize * 2, BoxSize).Select(pos => board[pos.X + DefaultSize * 2 - BoxSize, pos.Y + DefaultSize])
}.SelectMany(t => t);

foreach (SudokuTile tile in tiles) tile.Block();

Also there are multiple places in this file where LINQ method syntax is shorter and much readable then query syntax.

Result files

SudokuProgress

internal enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }

SudokuTile

public class SudokuTile
{
    internal const int CLEARED = 0;
    private readonly int _maxValue;
    private readonly int _x;
    private readonly int _y;

    private IEnumerable<int> _possibleValues = Enumerable.Empty<int>();
    private int _value = 0;
    private bool _blocked = false;

    internal static SudokuProgress CombineSolvedState(SudokuProgress a, SudokuProgress b)
    {
        switch (a)
        {
            case SudokuProgress.FAILED:
                return a;

            case SudokuProgress.NO_PROGRESS:
                return b;

            case SudokuProgress.PROGRESS:
                return b == SudokuProgress.FAILED ? b : a;
        }
        throw new InvalidOperationException($"Invalid value for {nameof(a)}");
    }

    public SudokuTile(int x, int y, int maxValue)
    {
        _x = x;
        _y = y;
        _maxValue = maxValue;
    }

    public int Value
    {
        get => _value;
        internal set
        {
            if (value > _maxValue)
                throw new ArgumentOutOfRangeException($"SudokuTile Value cannot be greater than {_maxValue}. Was {value}");
            if (value < CLEARED)
                throw new ArgumentOutOfRangeException($"SudokuTile Value cannot be smaller than zero. Was {value}");
            _value = value;
        }
    }

    public bool HasValue => Value != CLEARED;

    public string ToStringSimple() => Value.ToString();

    public override string ToString() => $"Value {Value} at pos {_x}, {_y}. ";

    internal void ResetPossibles()
    {
        if (HasValue)
            _possibleValues = Enumerable.Repeat(Value, 1);
        else
            _possibleValues = Enumerable.Range(1, _maxValue);
    }

    internal void Block() => _blocked = true;

    internal void Fix(int value, string reason)
    {
        Value = value;
        ResetPossibles();
    }

    internal SudokuProgress RemovePossibles(IEnumerable<int> existingNumbers)
    {
        if (_blocked)
            return SudokuProgress.NO_PROGRESS;

        // Takes the current possible values and removes the ones existing in `existingNumbers`
        _possibleValues = _possibleValues.Except(existingNumbers);

        switch (_possibleValues.Count())
        {
            case 0:
                return SudokuProgress.FAILED;
            case 1:
                Fix(_possibleValues.First(), "Only one possibility");
                return SudokuProgress.PROGRESS;
            default:
                return SudokuProgress.NO_PROGRESS;
        }
    }

    internal bool IsValuePossible(int i) => _possibleValues.Contains(i);

    public int X => _x;
    public int Y => _y;
    public bool IsBlocked => _blocked;  // A blocked field can not contain a value — used for creating 'holes' in the map

    internal int PossibleCount => IsBlocked ? 1 : _possibleValues.Count();
}

SudokuRule

public class SudokuRule : IEnumerable<SudokuTile>
{
    private readonly IEnumerable<SudokuTile> _tiles;
    private readonly string _description;

    internal SudokuRule(IEnumerable<SudokuTile> tiles, string description)
    {
        _tiles = tiles.ToArray();
        _description = description;
    }

    internal bool CheckValid()
    {
        IEnumerable<SudokuTile> filtered = _tiles.Where(tile => tile.HasValue);
        IEnumerable<IGrouping<int, SudokuTile>> groupedByValue = filtered.GroupBy(tile => tile.Value);
        return groupedByValue.All(group => group.Count() == 1);
    }

    internal SudokuProgress RemovePossibles()
    {
        // Tiles that has a number already
        IEnumerable<SudokuTile> withNumber = _tiles.Where(tile => tile.HasValue);

        // Tiles without a number
        IEnumerable<SudokuTile> withoutNumber = _tiles.Where(tile => !tile.HasValue);

        // The existing numbers in this rule
        IEnumerable<int> existingNumbers = withNumber.Select(tile => tile.Value);

        return withoutNumber.Aggregate(
            SudokuProgress.NO_PROGRESS,
            (result, tile) => SudokuTile.CombineSolvedState(result, tile.RemovePossibles(existingNumbers)));
    }

    internal SudokuProgress CheckForOnlyOnePossibility()
    {
        // Check if there is only one number within this rule that can have a specific value
        IEnumerable<int> existingNumbers = _tiles.Select(tile => tile.Value);
        SudokuProgress result = SudokuProgress.NO_PROGRESS;

        foreach (int value in Enumerable.Range(1, _tiles.Count()))
        {
            if (existingNumbers.Contains(value)) // this rule already has the value, skip checking for it
                continue;
            List<SudokuTile> possibles = _tiles.Where(tile => !tile.HasValue && tile.IsValuePossible(value)).ToList();
            if (possibles.Count == 0)
                return SudokuProgress.FAILED;
            if (possibles.Count == 1)
            {
                possibles.First().Fix(value, $"Only possible in rule {ToString()}");
                result = SudokuProgress.PROGRESS;
            }
        }
        return result;
    }

    internal SudokuProgress Solve()
    {
        // If both are null, return null (indicating no change). If one is null, return the other. Else return result1 && result2
        SudokuProgress result1 = RemovePossibles();
        SudokuProgress result2 = CheckForOnlyOnePossibility();
        return SudokuTile.CombineSolvedState(result1, result2);
    }

    public override string ToString() => _description;

    public IEnumerator<SudokuTile> GetEnumerator() => _tiles.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public string Description => _description;
}

SudokuBoard

public class SudokuBoard
{
    private readonly List<SudokuRule> _rules = new List<SudokuRule>();
    private readonly SudokuTile[,] _tiles;
    private readonly int _maxValue;

    internal SudokuBoard(SudokuBoard copy)
    {
        _maxValue = copy._maxValue;
        _tiles = new SudokuTile[copy.Width, copy.Height];
        CreateTiles();
        // Copy the tile values
        foreach (Point pos in SudokuFactory.Box(Width, Height))
        {
            _tiles[pos.X, pos.Y] = new SudokuTile(pos.X, pos.Y, _maxValue)
            {
                Value = copy[pos.X, pos.Y].Value
            };
        }

        // Copy the rules
        _rules = copy._rules
            .Select(rule => new SudokuRule(rule.Select(tile => _tiles[tile.X, tile.Y]), rule.Description))
            .ToList();
    }

    internal SudokuBoard(int width, int height, int maxValue, string[] tileDefinitions)
    {
        _maxValue = maxValue;
        _tiles = new SudokuTile[width, height];
        CreateTiles();
        if (_maxValue == width || _maxValue == height) // If maxValue is not width or height, then adding line rules would be stupid
        {
            // Create rules for rows and columns
            for (int x = 0; x < Width; x++)
                _rules.Add(new SudokuRule(Enumerable.Range(0, _tiles.GetLength(1)).Select(i => _tiles[x, i]), $"Row {x}"));

            for (int y = 0; y < Height; y++)
                _rules.Add(new SudokuRule(Enumerable.Range(0, _tiles.GetLength(0)).Select(i => _tiles[i, y]), $"Col {y}"));
        }

        PopulateTiles(tileDefinitions);
    }

    internal SudokuBoard(int width, int height, string[] tileDefinitions) : this(width, height, Math.Max(width, height), tileDefinitions)
    {
    }

    private void PopulateTiles(string[] tileDefinitions)
    {
        for (int row = 0; row < tileDefinitions.Length; row++)
        {
            string tileDefinition = tileDefinitions[row];

            for (int column = 0; column < tileDefinition.Length; column++)
            {
                SudokuTile tile = _tiles[column, row];
                if (tileDefinition[column] == '/')
                {
                    tile.Block();
                    continue;
                }
                tile.Value = tileDefinition[column] == '.' ? SudokuTile.CLEARED : (int)char.GetNumericValue(tileDefinition[column]);
            }
        }
    }

    private void CreateTiles()
    {
        foreach (Point pos in SudokuFactory.Box(_tiles.GetLength(0), _tiles.GetLength(1)))
        {
            _tiles[pos.X, pos.Y] = new SudokuTile(pos.X, pos.Y, _maxValue);
        }
    }

    public SudokuTile this[int x, int y] => _tiles[x, y];

    public int Width => _tiles.GetLength(0);

    public int Height => _tiles.GetLength(1);

    internal void CreateRule(string description, IEnumerable<SudokuTile> tiles) => _rules.Add(new SudokuRule(tiles, description));

    public string[] TileDefinitions => _tiles
        .Cast<SudokuTile>()
        .OrderBy(t => t.X)
        .ThenBy(t => t.Y)
        .GroupBy(t => t.Y)
        .Select(g => string.Join(string.Empty, g.Select(t => t.Value)))
        .ToArray();

    public IEnumerable<SudokuBoard> Solve()
    {
        SudokuProgress Simplify()
        {
            bool valid = _rules.All(rule => rule.CheckValid());
            if (!valid)
                return SudokuProgress.FAILED;

            return _rules.Aggregate(SudokuProgress.NO_PROGRESS,
                (progress, rule) => SudokuTile.CombineSolvedState(progress, rule.Solve()));
        }

        // reset solution
        foreach (SudokuTile tile in _tiles)
            tile.ResetPossibles();

        SudokuProgress simplify = SudokuProgress.PROGRESS;
        while (simplify == SudokuProgress.PROGRESS) simplify = Simplify();

        if (simplify == SudokuProgress.FAILED)
            yield break;

        // Find one of the values with the least number of alternatives, but that still has at least 2 alternatives
        IEnumerable<SudokuTile> query = from rule in _rules
                                        from tile in rule
                                        where tile.PossibleCount > 1
                                        orderby tile.PossibleCount ascending
                                        select tile;

        SudokuTile chosen = query.FirstOrDefault();
        if (chosen == null)
        {
            // The board has been completed, we're done!
            yield return this;
            yield break;
        }

        foreach (int value in Enumerable.Range(1, _maxValue))
        {
            // Iterate through all the valid possibles on the chosen square and pick a number for it
            if (!chosen.IsValuePossible(value))
                continue;
            SudokuBoard copy = new SudokuBoard(this);
            copy[chosen.X, chosen.Y].Fix(value, "Trial and error");
            foreach (SudokuBoard innerSolution in copy.Solve())
                yield return innerSolution;
        }
        yield break;
    }

    internal void AddBoxesCount(int boxesX, int boxesY)
    {
        int sizeX = Width / boxesX;
        int sizeY = Height / boxesY;

        IEnumerable<SudokuTile> TileBox(int startX, int startY) =>
            SudokuFactory.Box(sizeX, sizeY).Select(pos => _tiles[startX + pos.X, startY + pos.Y]);

        IEnumerable<Point> boxes = SudokuFactory.Box(sizeX, sizeY);
        foreach (Point pos in boxes)
            CreateRule($"Box at ({pos.X}, {pos.Y})", TileBox(pos.X * sizeX, pos.Y * sizeY));
    }
}

SudokuFactory

public class SudokuFactory
{
    private const int DefaultSize = 9;
    private const int SamuraiAreas = 7;
    private const int BoxSize = 3;
    private const int HyperMargin = 1;

    internal static IEnumerable<Point> Box(int sizeX, int sizeY)
    {
        return
            from x in Enumerable.Range(0, sizeX)
            from y in Enumerable.Range(0, sizeY)
            select new Point(x, y);
    }

    public static SudokuBoard Samurai(string[] tileDefinitions)
    {
        SudokuBoard board = new SudokuBoard(SamuraiAreas * BoxSize, SamuraiAreas * BoxSize, DefaultSize, tileDefinitions);
        // Removed the empty areas where there are no tiles
        IEnumerable<SudokuTile> tiles = new[]
        {
            Box(BoxSize, BoxSize * 2).Select(pos => board[pos.X + DefaultSize, pos.Y]),
            Box(BoxSize, BoxSize * 2).Select(pos => board[pos.X + DefaultSize, pos.Y + DefaultSize * 2 - BoxSize]),
            Box(BoxSize * 2, BoxSize).Select(pos => board[pos.X, pos.Y + DefaultSize]),
            Box(BoxSize * 2, BoxSize).Select(pos => board[pos.X + DefaultSize * 2 - BoxSize, pos.Y + DefaultSize])
        }.SelectMany(t => t);

        foreach (SudokuTile tile in tiles) tile.Block();

        // Select the tiles in the 3 x 3 area (area.X, area.Y) and create rules for them
        foreach (Point area in Box(SamuraiAreas, SamuraiAreas))
        {
            IEnumerable<SudokuTile> tilesInArea = Box(BoxSize, BoxSize)
                .Select(pos => board[area.X * BoxSize + pos.X, area.Y * BoxSize + pos.Y]);
            if (tilesInArea.First().IsBlocked)
                continue;
            board.CreateRule($"Area {area.X}, {area.Y}", tilesInArea);
        }

        // Select all rows and create columns for them
        foreach (int posSet in Enumerable.Range(0, board.Width))
        {
            board.CreateRule($"Column Upper {posSet}", Box(1, DefaultSize).Select(pos => board[posSet, pos.Y]));
            board.CreateRule($"Column Lower {posSet}", Box(1, DefaultSize).Select(pos => board[posSet, pos.Y + DefaultSize + BoxSize]));

            board.CreateRule($"Row Left {posSet}", Box(DefaultSize, 1).Select(pos => board[pos.X, posSet]));
            board.CreateRule($"Row Right {posSet}", Box(DefaultSize, 1).Select(pos => board[pos.X + DefaultSize + BoxSize, posSet]));

            if (posSet >= BoxSize * 2 && posSet < BoxSize * 2 + DefaultSize)
            {
                // Create rules for the middle sudoku
                board.CreateRule($"Column Middle {posSet}", Box(1, 9).Select(pos => board[posSet, pos.Y + BoxSize * 2]));
                board.CreateRule($"Row Middle {posSet}", Box(9, 1).Select(pos => board[pos.X + BoxSize * 2, posSet]));
            }
        }
        return board;
    }

    public static SudokuBoard SizeAndBoxes(int width, int height, int boxCountX, int boxCountY, string[] tileDefinitions)
    {
        SudokuBoard board = new SudokuBoard(width, height, tileDefinitions);
        board.AddBoxesCount(boxCountX, boxCountY);
        return board;
    }

    public static SudokuBoard ClassicWith3x3Boxes(string[] tileDefinitions) => SizeAndBoxes(DefaultSize, DefaultSize, DefaultSize / BoxSize, DefaultSize / BoxSize, tileDefinitions);

    public static SudokuBoard ClassicWith3x3BoxesAndHyperRegions(string[] tileDefinitions)
    {
        SudokuBoard board = ClassicWith3x3Boxes(tileDefinitions);
        const int HyperSecond = HyperMargin + BoxSize + HyperMargin;
        // Create the four extra hyper regions
        board.CreateRule("HyperA", Box(3, 3).Select(pos => board[pos.X + HyperMargin, pos.Y + HyperMargin]));
        board.CreateRule("HyperB", Box(3, 3).Select(pos => board[pos.X + HyperSecond, pos.Y + HyperMargin]));
        board.CreateRule("HyperC", Box(3, 3).Select(pos => board[pos.X + HyperMargin, pos.Y + HyperSecond]));
        board.CreateRule("HyperD", Box(3, 3).Select(pos => board[pos.X + HyperSecond, pos.Y + HyperSecond]));
        return board;
    }

    public static SudokuBoard ClassicWithSpecialBoxes(string[] areas, string[] tileDefinitions)
    {
        int sizeX = areas[0].Length;
        int sizeY = areas.Length;
        SudokuBoard board = new SudokuBoard(sizeX, sizeY, tileDefinitions);
        string joinedString = string.Join(string.Empty, areas);

        // Loop through all the unique characters
        foreach (char ch in joinedString.Distinct())
        {
            // Select the rule tiles based on the index of the character
            IEnumerable<SudokuTile> ruleTiles = from i in Enumerable.Range(0, joinedString.Length)
                                                where joinedString[i] == ch // filter out any non-matching characters
                                                select board[i % sizeX, i / sizeY];
            board.CreateRule($"Area {ch}", ruleTiles);
        }

        return board;
    }
}

Source code

All source code is available on Github.

\$\endgroup\$
48
\$\begingroup\$

Impressive. I mean it.

Couple observations:

Your enums...

public enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }

Should be:

public enum SudokuProgress { Failed, NoProgress, Progress }

When the first thing you see is this:

public class SudokuBoard
{
    public SudokuBoard(SudokuBoard copy)
    {
        _maxValue = copy._maxValue;
        tiles = new SudokuTile[copy.Width, copy.Height];
        CreateTiles();

you wonder where _maxValue and tiles come from, and why _maxValue (whose naming convention is that of a private field) can be accessed like that - I would expose it as a get-only property. Accessing private fields from another object doesn't seem instinctively right to me.

Speaking of the devil:

private int _maxValue;

This line belongs just above the constructor that's using it (it's 30-some lines below its first usage).

This box method which should be named Box (actually box is a bad name because it's the name of a CIL instruction that your C# compiles to), is returning a not-so-pretty Tuple<T1,T2> - The framework has a type called Point which has X and Y properties; if that's not appropriate, I don't know what is. Side note, Point is a value type, so there's no boxing actually going on if you use it over a Tuple, which is a reference type (incurs boxing). Bottom line, use a Point and call that method something else:

public static IEnumerable<Point> Box(int sizeX, int sizeY)
{
    foreach (int x in Enumerable.Range(0, sizeX))
    {
        foreach (int y in Enumerable.Range(0, sizeY))
        {
            yield return new Point(x, y);
        }
    }
}

You want to abuse LINQ? How about taking this:

private SudokuTile[,] tiles;
private void CreateTiles()
{
    foreach (var pos in SudokuFactory.box(tiles.GetLength(0), tiles.GetLength(1)))
    {
        tiles[pos.Item1, pos.Item2] = new SudokuTile(pos.Item1, pos.Item2, _maxValue);
    }
}

And turning it into that:

private Dictionary<Point, SudokuTile> tiles;
private void CreateTiles()
{
    tiles = SudokuFactory
                  .Box(tiles.GetLength(0), tiles.GetLength(1))
                  .Select(p => new KeyValuePair<Point, SudokuTile>{ Key = p, Value = new SudokuTile(p.X, p.Y, _maxValue)})
                  .ToDictionary(kvp => pkv.Key, kvp => kvp.Value);
}

It takes the IEnumerable<Point> returned by the modified Box method, selects each point into the Key of a KeyValuePair and a new SudokuTile as the vale, and then ToDictionary selects the Enumerable into a dictionary, which gets assigned to tiles. (C#: 1, Java: 0) Lines of code: 1.


In SudokuRule, your private fields can be marked as readonly.

This is only a partial review, I'll write more after I've implemented my own solution - I purposely haven't looked at your puzzle-resolution code :)

Overall looks quite good (except for all that static stuff that doesn't need to be, but that's me talking, doesn't make it any worse , but testing might be more enjoyable with non-static dependencies), It's great that you gave C# a bit of lovin' this week. I know Visual Studio isn't Eclipse, but I can assure you that VS with ReSharper would have made it a similar experience (and could have shown you some LINQ tricks!), at least in terms of code inspections (R# makes VS actually better than Eclipse... but I'm biased, and drifting, so I'll keep it at that!)...


I like how your Solve() method yield returns all found solutions.

That said, if your entire project is compiled into 1 single assembly (.exe/.dll), your usage of the internal access modifier is equivalent to public - internal basically means "assembly scope", so an internal type or method cannot be accessed from another assembly; if there's no other assembly, everything in the project can "see" it, so I don't see a point for internal here.

Not much left to say, except perhaps method IsValuePossible might be better off as IsPossibleValue, but that's mere nitpicking. Very neat, I'm jealous.

One last thing - this piece of list-initialization code:

var queriesForBlocked = new List<IEnumerable<SudokuTile>>();
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2                            ));
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2 + DefaultSize * 2 - BoxSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1                            , pos.Item2 + DefaultSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1 + DefaultSize * 2 - BoxSize, pos.Item2 + DefaultSize));

Could use a collection initializer and be written like this:

var queriesForBlocked = new List<IEnumerable<SudokuTile>>
    {
        { box(BoxSize, BoxSize*2).Select(pos => board.Tile(pos.Item1 + DefaultSize, pos.Item2)) },
        { box(BoxSize, BoxSize*2).Select(pos => board.Tile(pos.Item1 + DefaultSize, pos.Item2 + DefaultSize * 2 - BoxSize)) },
        { box(BoxSize*2, BoxSize).Select(pos => board.Tile(pos.Item1, pos.Item2 + DefaultSize)) },
        { box(BoxSize*2, BoxSize).Select(pos => board.Tile(pos.Item1 + DefaultSize * 2 - BoxSize, pos.Item2 + DefaultSize)) }
    };

Each item in the collection initializer actually calls the .Add method anyway, so it's completely equivalent. Except it's 1 single instruction now.

\$\endgroup\$
23
\$\begingroup\$

Can't read all this code on my phone even though it looks pretty well structured to me! Good job!

I saw this. Isn't the exception message contradicting the if clause?

if (value < CLEARED)
    throw new ArgumentOutOfRangeException("SudokuTile Value cannot be zero or smaller. Was " + value);

CLEARED is set to 0, and the if checks for 'less than 0' so the value could be set to 0.

Also, not having run the code, why does the toString() have four parameters on String.Format, only using three?

I'll have a closer look when I'm at a computer, but nice work!

\$\endgroup\$
  • \$\begingroup\$ You're right, I used to have a ClearValue method to handle clearing separately, but I realized that was useless as I was just doing if-else to check if I should set the value or call the ClearValue method. Forgot to change the exception description. Also forgot to remove that extra parameter from String.Format. \$\endgroup\$ – Simon Forsberg Dec 16 '13 at 15:16
19
\$\begingroup\$

I know next to zilch about C# so I won't be much help with this review, but I can say that it looks well thought out and implements some cool features. And like retailcoder I'm still working on my version (hoping to minimize the brute-force portion) using Ruby.

If C# allows enums to implement methods, I would move CombineSolvedState into SudokuProgress. Forgive my Java syntax, but if this is allowed I expect it will be easy to translate.

public enum SudokuProgress {
    public SudokuProgress CombineSolvedState(SudokuProgress solved) {
        if (this == SudokuProgress.FAILED)
            return this;
        if (this == SudokuProgress.NO_PROGRESS)
            return solved;
        if (this == SudokuProgress.PROGRESS)
            return solved == SudokuProgress.FAILED ? solved : this;
        throw new InvalidOperationException("Invalid value for " + this);
    }

    FAILED, NO_PROGRESS, PROGRESS
}

I think this SO question addresses the issue, and one answer says it's not directly possible without using a class instead of an enum while another implies that it can be done using extensions.

Also, can't you use enums in a switch statement instead of a series of ifs?

\$\endgroup\$
  • 5
    \$\begingroup\$ Enums in C# cannot have methods, but indeed it would be nice to have that. And Yes, you can type sw[itch], Tab (auto-expand) and then the name of a variable/parameter of the type of the enum and VS will provide case statements for all the members. \$\endgroup\$ – Rudi Dec 16 '13 at 10:12
  • \$\begingroup\$ Yeah, I wanted to use enum methods but unlike Java, C# doesn't have them. You're right about the switch-statement though. \$\endgroup\$ – Simon Forsberg Dec 16 '13 at 15:08
  • 1
    \$\begingroup\$ Enums in C# can have extension methods, which would let you achieve the same syntax. \$\endgroup\$ – breischl Dec 19 '13 at 20:30
  • \$\begingroup\$ @breischl - The second answer to the question I linked above mentioned extension methods as well, but I couldn't figure out the syntax from its example. \$\endgroup\$ – David Harkness Dec 19 '13 at 21:24
  • \$\begingroup\$ Ah, right. Sorry, I skimmed the tail end of the answer and missed that. \$\endgroup\$ – breischl Dec 19 '13 at 21:34
17
\$\begingroup\$

You can write your Box method without foreach loops or yield return:

public static IEnumerable<Tuple<int, int>> Box(int sizeX, int sizeY)
{
    return 
        from x in Enumerable.Range(0, sizeX)
        from y in Enumerable.Range(0, sizeY)
        select Tuple.Create(x,y);
}

or equivalently:

public static IEnumerable<Tuple<int, int>> Box2(int sizeX, int sizeY)
{
    return 
        Enumerable.Range(0,sizeX).SelectMany(x => 
        Enumerable.Range(0,sizeY).Select(y => 
        Tuple.Create(x,y)));
}

Standard, and less verbose, method of creating Tuples is Tuple.Create.

If you had made your Tile, Rule, and Board immutable, as they are; sharing state between them would not have been a problem. For example two Samurai Sudoku puzzles do share rules.

Your model does not differentiate between an empty board and a partial assignment; A position of a board and an assignment to that position you call both Tile. You call Tuple<int,int> position in places.

  • _rowAddIndex looks like an orphan. It clearly do not belong to that class.

  • AddRow should be called some exact number of times.

  • Before calling anything else. Seems like a constructor to me.

Also there is not differentiation between a puzzle and its solving method. A puzzle is an immutable structure. Every one trying to solve some puzzle on the newspaper is trying to solve the same puzzle. They use different methods and use different temporary data structures.

Board board = samuraiSudokuBoard.create();
PartialAssignment puzzle = new PartialAssignment(board, parse(puzzleStr));
SolutionStrategy strategy = new RecursiveStrategy(maxDepth);
var solutions = strategy.Solve(puzzle);
var solutions2 = new IterativeStrategy(maxStackSize).Solve(puzzle);
var solutions2 = new ConcurrentStrategy(maxThreads).Solve(puzzle);
var comparison = CompareSolutionTimes(puzzle, strategies);

You are aggregating here.

SudokuProgress result = SudokuProgress.NO_PROGRESS;
foreach (SudokuTile tile in withoutNumber)
    result = SudokuTile.CombineSolvedState(result, 
                 tile.RemovePossibles(existingNumbers));
return result;

can be rewritten more clearly as:

return withoutNumber.Aggregate(
    SudokuProgress.NO_PROGRESS,
    (result, tile) => SudokuTile.CombineSolvedState(
                         result, 
                         tile.RemovePossibles(existingNumbers)));
\$\endgroup\$
  • \$\begingroup\$ I'm not sure how you mean to share state between boards... If they would have been immutable, then I would have needed to make a whole lot of extra code to solve the map, as all the basic solving (the non-brute-force part) would need to create a whole new map.. \$\endgroup\$ – Simon Forsberg Dec 16 '13 at 15:19
  • \$\begingroup\$ @SimonAndréForsberg The separation would be between the classes that model 1) the layout and rules of the board, 2) the initial known cells of that particular puzzle, and 3) the mutable model used to solve that puzzle. While very cool, it would be a lot more code for something designed to run in a single-user console app. \$\endgroup\$ – David Harkness Dec 16 '13 at 17:29
  • \$\begingroup\$ You have some very good points, which will be good to think about for further projects, but for this weekly challenge it would have been even more overkill I think :) \$\endgroup\$ – Simon Forsberg Dec 16 '13 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.