Решение SudokuSharp Solver с расширенными функциями

Несмотря на то, что в первый раз я пишу что-то такое «большое», мне кажется, что я хорошо знаю C # (в конце концов, он очень похож на Java). Приятно было также изучить LINQ, и я очень впечатлен функциями (которые похожи на Steams в Java 8), и, возможно, я использовал их здесь (если это возможно).

Обзор класса

  • SudokuFactory: содержит статические методы для создания некоторых вариантов судоку.
  • SudokuBoard: содержит коллекцию SudokuRule и SudokuTile
  • SudokuRule: Является ли это коробкой, строкой, строкой или чем-то совершенно другим, не имеет значения. Содержит набор SudokuTile, который должен быть уникальным.
  • SudokuTile: Каждая плитка в головоломке. Может быть «заблокирован» (как дыра в головоломке), помнит, что это possibleValues, а также содержит значение (0 используется для фрагментов без значения)
  • SudokuProgress: используется для того, чтобы знать, каков был прогресс решающего шага.
  • Программа: Основная отправная точка. Содержит тесты для семи разных судоку. Все были проверены на правильность решения.

Так как это первый раз, когда я использую C # и LINQ, скажите мне что-нибудь. Все предложения приветствуются. За исключением того факта, что поле box следует называть Box. Меня особенно интересовали бы случаи, когда я мог бы упростить некоторые из использования LINQ (поверьте мне, их много). Надеюсь, вы сможете следить за всеми запросами LINQ. Я попытался дать некоторые короткие комментарии, когда это необходимо, чтобы объяснить, что происходит. Если вы хотите объяснить какую-то часть, опубликуйте комментарий, и я объясню.

Как обычно, у меня есть склонность превращать вызов во что-то сверхгибкое, поддерживая все более или менее ненужные вещи. Некоторые из возможных головоломок, которые может решить этот код:

  • Твердый классический 9x9 Судоку с 3х3-ящиками , который требует больше передовые методы (или, в моем случае, более или менее «грубой силы» путем проб и ошибок)
  • Nonomino
  • HyperSudoku
  • Самурайский судоку
  • Классический судоку любого размера с любым количеством ящиков и размером ящиков (только полностью протестирован на 9x9 с коробками 3x3 и 4x4 с 2x2 ящиками, но любые размеры должны быть возможны)

Эти изображения являются головоломками, которые проверены и решены в приведенном ниже коде:

Weekend Challenge Sudoku Самурай Судоку

Одна известная проблема с реализацией заключается в том, что если вы введете пустую головоломку, тогда она будет работать годами, чтобы найти все возможные комбинации для нее.

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;
    }
}

Программа:

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();
        }
    }
}
69 голосов | спросил Simon Forsberg 16 MonEurope/Moscow2013-12-16T02:22:52+04:00Europe/Moscow12bEurope/MoscowMon, 16 Dec 2013 02:22:52 +0400 2013, 02:22:52

5 ответов


15

Это потрясающе. Специально для человека, который не использует C # каждый день в течение многих лет.


Мои основные проблемы:

  • слишком много вещей, которые public, которые должны быть internal, иногда internal могут быть обращены в private , Используйте наиболее ограничительный уровень доступа, который имеет смысл для определенного члена.
  • метод с ошибкой AddRow of SudokuBoard. Я бы предпочел, чтобы один строковый массив передавался в конструктор SudokuFactory вместо нескольких вызовов AddRow. Этот метод слишком просто вызвать слишком много или слишком мало, чтобы получить исключение во время выполнения.
  • Отсутствие некоторого строкового представления результата решения, которое может быть использовано в модульных тестах.
  • метод вывода консоли, например Output и OutputRules в основных классах. Они должны находиться в Program, потому что они просто используются для вывода консоли, не более того.
  • отсутствие единичных тестов. Я переместил вашу логику, чтобы разделить библиотеку и добавить проект модульного тестирования. Это первое, что я сделал, когда я начал реорганизовывать ваш код, чтобы убедиться, что мой рефакторинг ничего не сломает.
    Также я бы использовал тип библиотеки .NET Standard. Это позволит повторно использовать ту же логику для веб-сайтов, мобильных (Xamarin) и настольных приложений.

Единичные тесты

Чтобы добавить модульные тесты, я добавил параметр string[] tileDefinitions в конструкторы SudokuBoard (также они должны быть 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)
{
}

Также я удалил поле _rowAddIndex и заменил метод AddRow с помощью 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]);
        }
    }
}

Теперь я добавил string[] tileDefinitions ко всем методам SudokuFactory.

Чтобы получить простое строковое представление решения sudoku, которое можно было бы легко использовать в модульных тестах и, возможно, в других проектах, я добавил string[] TileDefinitions общедоступное свойство в 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();

Теперь код наших модульных тестов (я повторно использовал ваш код из вывода консоли для тестовых случаев). Я использую XUnit здесь:

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);
    }
}

Рефакторинг

Я применил уже упомянутые идеи рефакторинга из других ответов, поэтому я не буду упоминать их отдельно.

Также я использую выражения-члены, строковые интерполяции и локальные функции из более новых версий C #, которые не были доступны при написании вашего сообщения.

SudokuTile

Свойства могут быть сгруппированы по readonly /const и изменены:

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 должен начинаться с подчеркивания, чтобы он соответствовал вашему соглашению об именах. Тип _possibleValues можно безопасно заменить на ISet<int> на более примитивный IEnumerable<int>. ResetPossibles должен быть упрощен:

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

Линия

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

в RemovePossibles можно легко заменить, используя метод Except LINQ

_possibleValues = _possibleValues.Except(existingNumbers);

Также вы можете заменить double if на оператор switch в методе RemovePossibles. Результат:

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

Здесь мы должны изменить тип поля _tiles с ISet<SudokuTile> на IEnumerable<SudokuTile>, потому что вы не будете использовать какую-либо модификацию коллекции методы, такие как Add, Remove или Clear. Коллекция используется только для чтения. Но вы можете сохранить строку

_tiles = new HashSet<SudokuTile>(tiles);

в конструкторе, потому что методы LINQ имеют отложенное выполнение, и здесь коллекция должна быть рассчитана немедленно. Но я заменил это на

_tiles = tiles.ToArray();

только потому, что это короче.

Также ваши поля должны быть readonly

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

Линия в RemovePossibles

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

имеет много избыточности:

  • HashSet<int> здесь не имеет смысла, поскольку вы получаете материализованную коллекцию, используя метод ToList call
  • но даже ToList здесь избыточно, потому что этот набор номеров передается в SudokuTile.RemovePossibles, который немедленно изменяет коллекцию _possibleValues. li>
  • Вызов

    Distinct также избыточен здесь, потому что вы проверили все свои правила перед использованием метода SudokuBoard.Simplify, используя строку

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

    , поэтому все ваши значения плитки уже различны.

Таким образом, эту строку можно сократить до

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

Также строка в CheckForOnlyOnePossibility

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

имеет проблемы

  • Вы используете existingNumbers как сборник только для чтения с использованием метода Contains, поэтому IList<int> можно безопасно заменить с помощью IEnumerable<int>.

  • ToList здесь избыточно, потому что метод Contains не использует отложенное выполнение.

  • Вызов

    Distinct также избыточен здесь, потому что вы проверили все свои правила перед использованием метода SudokuBoard.Simplify, используя строку

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

    , поэтому все ваши значения плитки уже различны.

Таким образом, эту строку можно сократить до

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

SudokuBoard

Я думаю, что лучше переместить все определения полей в начало класса с помощью модификатора readonly. Кроме того, я добавляю подчеркивание к именам полей для обеспечения согласованности согласования именования.

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

Также я изменил тип _rules на List<SudokuRule>, потому что он более дружелюбен с LINQ (поскольку LINQ имеет метод ToList, но не ToSet).


Двойной цикл в конструкторе копирования кода SudokuBoard может быть упрощен с помощью одного оператора LINQ (кстати, я изменил SudokuFactory.Box тип возврата из безликой Tuple в более значимый 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();
}

Эта большая часть кода

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];
    }
}

можно заменить на пару строк:

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 может быть заменен индексатором для доступа к плиткам платы через синтаксис массива:

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

Simplify можно упростить, используя метод Aggregate LINQ и переменную inline:

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()));
}

Все короткие и простые одноразовые используемые вещи, такие как CheckValid, TileBox, ResetSolutions, Simplify, SetupLineRules должен быть встроен или использоваться как локальная функция. Файл результатов будет указан ниже.

SudokuFactory

Реализованный метод SetupLineRules, используя советы из нескольких других ответов:

Box

Заменен этот код из 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); }

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(); } Метод LINQ:

SelectMany

Также есть несколько мест в этом файле, где синтаксис метода LINQ короче и легко читается, а затем синтаксис запроса.

Файлы результатов

SudokuProgress

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();

SudokuTile

internal enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }

SudokuRule

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();
}

SudokuBoard

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;
}

SudokuFactory

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));
    }
}

Исходный код

Весь исходный код доступен на Github .

ответил Vadim Ovchinnikov 23 MarpmFri, 23 Mar 2018 23:54:15 +03002018-03-23T23:54:15+03:0011 2018, 23:54:15
47

Впечатляет. Я имею в виду.

Пара наблюдений:

Ваши перечисления ...

public enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }

Должно быть:

public enum SudokuProgress { Failed, NoProgress, Progress }

Когда первое, что вы видите, это следующее:

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

вы задаетесь вопросом, откуда берутся _maxValue и tiles, и почему _maxValue (соглашение об именах которого принадлежит частному полю) можно получить доступ например, я бы выставил его как свойство get-only. Доступ к закрытым полям из другого объекта не кажется мне инстинктивно.

Говоря о дьяволе:

private int _maxValue;

Эта строка принадлежит только над конструктором, который использует его (это 30-некоторые строки ниже его первого использования).

Этот box метод , который должен быть назван Box (на самом деле box), является плохим именем, потому что это имя из инструкции CIL , которую компилирует ваш C #), возвращает не очень красивый Tuple <T1, T2> - структура имеет тип, называемый Tuple<T1,T2>, который имеет свойства Point и X; если это не подходит, я не знаю, что это такое. Боковое примечание, Y - это тип значения , поэтому нет бокса , если вы используете его поверх Point, который является ссылочным типом (берет на себя бокс). В нижней строке используйте Tuple и вызовите этот метод что-то еще:

Point

Вы хотите злоупотреблять LINQ? Как насчет этого:

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);
        }
    }
}

И превращая это в это:

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);
    }
}

Требуется 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); } , возвращаемый модифицированным методом IEnumerable<Point>, выбирает каждую точку в Box ключа Key и новый KeyValuePair в качестве vale, а затем SudokuTile выбирает Enumerable в словаре, который присваивается ToDictionary. ( C #: 1, Java: 0 ) Строки кода: 1.


В tiles ваши личные поля могут быть помечены как SudokuRule.

Это лишь частичный обзор, я напишу больше после того, как я внедрил свое собственное решение - я специально не посмотрел ваш код головоломки:)

В целом выглядит неплохо (за исключением всего этого readonly, который не нужен ), но это мне говорить, не делает его хуже , но тестирование может быть более приятным с нестатическими зависимостями) Замечательно, что вы дали C # немного любви на этой неделе. Я знаю, что Visual Studio не Eclipse, но я могу заверить вас, что VS с ReSharper сделал бы подобный опыт (и мог бы показать вам некоторые трюки LINQ!), По крайней мере, с точки зрения проверки кода (R # делает VS фактически лучше, чем Eclipse ... но я предвзятый и дрейфующий, поэтому я сохраню это!) ...


Мне нравится, как ваш метод static Solve() возвращает все найденные решения.

Тем не менее, если весь ваш проект скомпилирован в единую сборку (.exe /.dll), использование модификатора доступа yield эквивалентно internal - public в основном означает «область сборки», поэтому тип или метод internal не могут быть доступны из другой сборки ; если нет другой сборки, все в проекте может «видеть» ее, поэтому я не вижу смысла для internal здесь.

Нечего сказать, кроме, может быть, методаinternal может быть лучше, чем IsValuePossible, но это просто nitpicking. Очень аккуратно, я ревную.

Последнее: этот фрагмент кода инициализации списка:

IsPossibleValue

Можно использовать инициализатор и писать так:

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));

Каждый элемент в инициализаторе фактически вызывает метод 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)) } }; , так что он полностью эквивалентен. Кроме того, сейчас одна инструкция.

ответил Mathieu Guindon 16 MonEurope/Moscow2013-12-16T09:59:30+04:00Europe/Moscow12bEurope/MoscowMon, 16 Dec 2013 09:59:30 +0400 2013, 09:59:30
22

Не могу прочитать весь этот код на моем телефоне, хотя он выглядит довольно хорошо структурированным для меня! Хорошая работа!

Я видел это. Разве сообщение об исключении не противоречит предложению if?

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

CLEARED установлен в 0, а if проверяет значение «меньше 0», поэтому значение может быть установлено на 0.

Кроме того, не запустив код, почему toString() имеет четыре параметра в String.Format, только используя три?

У меня будет более пристальный взгляд, когда я нахожусь на компьютере, но приятно работать!

ответил Niclas Lindqvist 16 MonEurope/Moscow2013-12-16T11:35:27+04:00Europe/Moscow12bEurope/MoscowMon, 16 Dec 2013 11:35:27 +0400 2013, 11:35:27
18

Я знаю рядом с zilch о C #, поэтому я не буду очень помогать в этом обзоре, но могу сказать, что он выглядит хорошо продуманным и реализует некоторые интересные функции. И, подобно розничному кодеру, я все еще работаю над своей версией (надеясь минимизировать часть грубой силы) с помощью Ruby.

Если C # позволяет перечислениям внедрять методы, я бы переместил CombineSolvedState в SudokuProgress. Простите мой синтаксис Java, но если это разрешено, я ожидаю, что его будет легко перевести.

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
}

Я думаю, этот вопрос SO устраняет проблему, и один ответ говорит, что это невозможно напрямую без использования класса, а не для перечисления, а другое означает, что это можно сделать с помощью расширений.

Кроме того, вы не можете использовать перечисления в выражении switch вместо серии if s?

ответил David Harkness 16 MonEurope/Moscow2013-12-16T11:48:54+04:00Europe/Moscow12bEurope/MoscowMon, 16 Dec 2013 11:48:54 +0400 2013, 11:48:54
16

Вы можете написать свой метод Box без циклов foreach или 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);
}

или эквивалентно:

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)));
}

Стандартный и менее подробный способ создания Tuple s Tuple.Create.

Если вы сделали свой Tile, Rule и Board неизменяемыми, как они есть; разделение между ними не было бы проблемой. Например, две головоломки Samurai Sudoku действительно разделяют .

Ваша модель не различает пустую доску и частичное назначение; Позиция платы и присвоение этой позиции вы вызываете как Tile. Вы вызываете Tuple<int,int> position в местах.

  • _rowAddIndex выглядит как сирота. Он явно не принадлежит этому классу.

  • AddRow следует называть точным числом раз.

  • Прежде чем позвонить кому-нибудь еще. Мне кажется конструктором.

Также нет различия между головоломкой и ее методом решения. Головоломка - непреложная структура. Каждый, кто пытается решить головоломку в газете, пытается решить ту же самую головоломку . Они используют разные методы и используют разные временные структуры данных.

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);

Здесь вы агрегируете.

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

можно более четко переписать как:

return withoutNumber.Aggregate(
    SudokuProgress.NO_PROGRESS,
    (result, tile) => SudokuTile.CombineSolvedState(
                         result, 
                         tile.RemovePossibles(existingNumbers)));
ответил abuzittin gillifirca 16 MonEurope/Moscow2013-12-16T18:58:10+04:00Europe/Moscow12bEurope/MoscowMon, 16 Dec 2013 18:58:10 +0400 2013, 18:58:10

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132