2

祝大家好日子，

我一直在研究 C# Sudoku Solver 应用程序，但我真诚地低估了解决数独算法的难度。我一直在网上搜索我可以实现的可能算法，但是我没有找到一个我可以理解的简单算法。

我找到了一个可能在我的应用程序中工作的算法，但是这个人正在使用一维数组来解决它。我试图对其进行更改以使其与多维数组一起使用，但我无法使其正常工作。

谁能给我建议或告诉我如何更改代码以使其与多维数组（int [，]）一起使用？我似乎无法自己找到它。代码在这里找到：http: //blah.winsmarts.com/2007-1-sudoku_solver_in_c-.aspx

如果您有另一种可以与 int[,] 一起使用的算法，那当然也很棒。

由于我已经搜索了很长时间，因此将不胜感激。提前致谢！

4

2 回答 2

1

您链接的代码已经在逻辑上使用二维数组，它只是使用一维数组作为支持。改变这个：

private int[] vals = new int[81];
public int this[int row, int column]
{
    get { return vals[FindIndex(row, column)]; }
    set
    {
        vals[FindIndex(row, column)] = value;
    }
}

private int FindIndex(int row, int column)
{
    return (((column - 1) * 9) + row - 1);
}

到：

private int[,] vals = new int[9,9];
public int this[int row, int column]
{
    get { return vals[row - 1, column - 1]; }
    set
    {
        vals[row - 1, column - 1] = value;
    }
}

（- 1在当前代码的其余部分中， 's 是必需的，因为rowandcolumn从 1 而不是 0 开始。）

于 2013-05-21T13:59:53.373 回答
0

递归回溯，蛮力，算法。

public class SudokoSolver
{
    private readonly Grid _grid;

    public SudokoSolver(Grid grid)
    {
        _grid = grid;
        _grid.Validate();
    }

    public int?[,] SolvePuzzle()
    {
        Solve();
        Console.WriteLine(_grid.Assigns + " tries total.");
        return _grid.Data;
    }

    private bool Solve()
    {
        int row, col;
        if (!_grid.FindUnassignedLoc(out row, out col))
        {
            return true;
        }

        for (int num = 1; num <= 9; num++)
        {
            if (_grid.NoConflicts(row, col, num))
            {
                _grid.Assign(row, col, num);

                if (Solve())
                {
                    return true;
                }
                _grid.Unassign(row, col);
            }
        }

        return false;
    }

    public int?[,] Data
    {
        get { return _grid.Data; }
    }
}

public class Grid
{
    public int?[,] Data { get; private set; }
    private int _curC = 0;
    private int _curR = 0;
    private int _assigns = 0;

    public Grid(int?[,] data)
    {
        Data = data ?? new int?[9,9];
    }
    public bool FindUnassignedLoc(out int row, out int col)
    {
        while (Data[_curR, _curC].HasValue)
        {
            _curC++;

            if (_curC == 9)
            {
                _curR++;
                _curC = 0;
            }

            if (_curR == 9)
            {
                row = -1;
                col = -1;
                return false;
            }
        }

        row = _curR;
        col = _curC;

        return true;
    }

    public bool NoConflicts(int row, int col, int num)
    {
        for (int r = 0; r < 9; ++r)
        {
            if (Data[r, col] == num)
            {
                return false;
            }
        }

        for (int c = 0; c < 9; c++)
        {
            if (Data[row, c] == num)
            {
                return false;
            }
        }

        int fromC = 3 * (col/3);
        int fromR = 3 * (row / 3);

        for (int c = fromC; c < fromC + 3; c++)
        {
            for (int r = fromR; r < fromR + 3; r++)
            {
                if (Data[r, c] == num)
                {
                    return false;
                }
            }
        }

        return true;
    }

    public void Assign(int row, int col, int num)
    {
        _assigns++;
        Data[row, col] = num;
    }

    public void Unassign(int row, int col)
    {
        Data[row, col] = null;
        _curC = col;
        _curR = row;
    }

    public int Assigns
    {
        get { return _assigns; }
    }

    public void Validate()
    {
        if (Data.Length != 81)
        {
            throw new Exception("Invalid dimentions!");
        }

        if (!IsLegal())
        {
            throw new Exception("Illigal numbers populated!");
        }
    }

    public bool IsLegal()
    {
        var container = new HashSet<int>();
        //vertical check 
        for (int c = 0; c < 9; ++c)
        {
            container.Clear();
            for (int r = 0; r < 9; ++r)
            {
                if (Data[r, c].HasValue)  
                {
                    if (container.Contains(Data[r, c].Value))
                    {
                        return false;
                    }
                    container.Add(Data[r, c].Value);
                }
            }
        }
        // horizontal check
        for (int r = 0; r < 9; ++r)
        {
            container.Clear();
            for (int c = 0; c < 9; ++c)
            {
                if (Data[r, c].HasValue)
                {
                    if (container.Contains(Data[r, c].Value))
                    {
                        return false;
                    }
                    container.Add(Data[r, c].Value);
                }
            }
        }

        // square check
        var topLeftCorners = new List<Tuple<int, int>>
        {
            new Tuple<int, int>(0,0),
            new Tuple<int, int>(0,3),
            new Tuple<int, int>(0,6),
            new Tuple<int, int>(3,0),
            new Tuple<int, int>(3,3),
            new Tuple<int, int>(3,6),
            new Tuple<int, int>(6,0),
            new Tuple<int, int>(6,3),
            new Tuple<int, int>(6,6)
        };

        foreach (var topLeftCorner in topLeftCorners)
        {
            int fromC = topLeftCorner.Item2;
            int fromR = topLeftCorner.Item1;

            container.Clear();

            for (int c = fromC; c < fromC + 3; c++)
            {
                for (int r = fromR; r < fromR + 3; r++)
                {
                    if (Data[r, c].HasValue)
                    {
                        if (container.Contains(Data[r, c].Value))
                        {
                            return false;
                        }
                        container.Add(Data[r, c].Value);
                    }
                }
            }
        }

        return true;
    }
}
于 2017-04-14T08:48:08.210 回答