Home » SudokuSharp Solver with advanced features

SudokuSharp Solver with advanced features

Solutons:


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] == "https://codereview.stackexchange.com/")
            {
                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] == "https://codereview.stackexchange.com/")
                {
                    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.

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 dependency-injection me talking, doesn’t make it any worse c#, 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 publicinternal 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.

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!

Related Solutions

Recursive to iterative using a systematic method [closed]

So, to restate the question. We have a function f, in our case fac. def fac(n): if n==0: return 1 else: return n*fac(n-1) It is implemented recursively. We want to implement a function facOpt that does the same thing but iteratively. fac is written almost in...

How can I match values in one file to ranges from another?

if the data file sizes are not huge, there is a simpler way $ join input1 input2 | awk '$5<$4 && $3<$5 {print $2, $5-$3+1}' B100002 32 B100043 15 B123465 3 This Perl code seems to solve your problem It is a common idiom: to load the entire...

Javascript difference between “=” and “===” [duplicate]

You need to use == or === for equality checking. = is the assignment operator. You can read about assignment operators here on MDN. As a quick reference as you are learning JS: = assignment operator == equal to === equal value and equal type != not equal !==...

Compiler complains about misplaced else [closed]

Your compiler complains about an misplaced else because, well, there is an else without a preceding if: // ... for (j=1; j<n-i; j++) { if(a[j]<=a[j+1]) { // ... } // END OF IF } // END OF FOR else { continue; } // ... The else in your code does not follow...

Bootstrap – custom alerts with progress bar

/* !important are just used to overide the bootstrap css in the snippet */ .alertContainer { border-radius: 0 !important; border-width: 0 !important; padding: 0 !important; height: auto !important; position: absolute !important; bottom: 15px !important; left:...

How to Garbage Collect an external Javascript load?

Yes, s.onload = null is useful and will garbage collect! As of 2019, it is not possible to explicitly or programmatically trigger garbage collection in JavaScript. That means it collects when it wants. Although there is cases where setting to null may do a GC...

Math programming with python

At first, what you are looking for is the modulo operator and the function math.floor() Modulo from wikipedia: In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus). for example: 12%12=0...

Android slide over letters to create a word [closed]

Here some advice you can use: First for each cell you can create an object that represents the state of that cell: class Cell { char mChar; int row,column; boolean isSelected; } then you can create a 2D array of your cells Cell[][] mTable = ... For views you...

Sum two integers in Java

You reused the x and y variable names (hence the variable x is already defined in method main error), and forgot to assign the ints read from the Scanner to the x and y variables. Besides, there's no need to create two Scanner objects. public static void...

Extend three classes that implements an interface in Java

Using this simplified implementation of the library, using method() instead of M(): interface IFC { void method(); } class A implements IFC { public void method() { System.out.println("method in A"); }; } As akuzminykh mentions in their comment You'd write a...

How to set the stream content in PHPExcel? [closed]

Okey, First thing first PHPExcel_Worksheet_MemoryDrawing() can't solve your problem if you insist to use stream content and pass that to your worksheet your PDF will not render your image. But you can use `PHPExcel_Worksheet_Drawing()' if you want to render...

How to remove all files from a directory?

Linux does not use extensions. It is up to the creator of the file to decide whether the name should have an extension. Linux looks at the first few bytes to figure out what kind of file it is dealing with. To remove all non-hidden files* in a directory use: rm...

Hacker used picture upload to get PHP code into my site

Client side validation The validation code you have provided is in JavaScript. That suggests it is code that you use to do the validation on the client. Rule number one of securing webapps is to never trust the client. The client is under the full control of...

First Time HTML5/CSS Site

Semantically, I would suggest using HTML5 elements more. For example, instead of... <div id="header"> <div id="logo"></div> </div> Use instead: (the ID can stay if you want it to) <header> <div id="logo"></div>...

How classes work in a CSS file? [closed]

In your first example: .container.inner_content.text_section Match any element that has all three classes .container.inner_content.text_section { color: red; } <div class="container inner_content">one class</div> <div class="container...