数独解算器不工作

Question

我首先尝试创建一个数独解算器

计算可以放入正方形的可能值。
然后使用这些约束回溯

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sudoku_Solver
{
    static class Program
    {


    private static int[,] grid = new int[,]{
            { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
            { 5, 2, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 8, 7, 0, 0, 0, 0, 3, 1 },
            { 0, 0, 3, 0, 1, 0, 0, 8, 0 },
            { 9, 0, 0, 8, 6, 3, 0, 0, 5 },
            { 0, 5, 0, 0, 9, 0, 0, 6, 0 },
            { 1, 3, 0, 0, 0, 0, 2, 5, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 7, 4 },
            { 0, 0, 5, 2, 0, 6, 3, 0, 0 }
        };

    private static List<int>[,] constraints;
    static void Main(string[] args)
    {
        GetConstraints();

        SolveSudokuGrid();

        PrintGrid();
        Console.Read();

    }

    static bool SolveSudokuGrid()
    {
        int row = -1 , col = -1;

        if (IsGameOver(ref row, ref col) == true)
            return true;

        //Get constraint
        List<int> constraint = constraints[row, col];

        for (int i = 0; i < constraint.Count; i++)
        {
            //Assume correct number by adding a constraint
            grid[row, col] = constraint[i];

            if (SolveSudokuGrid() == true)
                return true;

            //Cant solve. Backtrack
            grid[row, col] = 0;
        }

        return false;
    }

    static void PrintGrid()
    {
        for (int row = 0; row < 9; row++)
        {
            for (int col = 0; col < 9; col++)
                    Console.Write(grid[row,col]);
            Console.WriteLine();
        }
    }
    static bool IsGameOver(ref int row, ref int col)
    {
        for(int r = 0; r < 9; r++)
        {
            for(int c = 0; c < 9; c++)
            {
                if (grid[r, c] == 0)
                {
                    row = r;
                    col = c;
                    return false;
                }
            }
        }

        return true;
    }
    static void GetConstraints()
    {
        constraints = new List<int>[9, 9];

        for(int row = 0; row < 9; row++)
        {
            for(int col = 0; col < 9; col++)
            {
                if(grid[row,col] == 0)
                {
                    constraints[row, col] = ComputeConstraint(row, col);
                    continue;
                }

                constraints[row, col] = null;
            }
        }
    }

    static List<int> ComputeConstraint(int row, int col)
    {
        List<int> constraint = new List<int>();

        for (int i = 1; i <= 9; i++)
            if (HasConflicts(row, col, i) == false)
                constraint.Add(i);

        return constraint;
    }
    static bool usedInRow(int row, int num)
    {
        /*
        * Scans through that "row" till a match is found.
        * So "row" will be the same, but "col" will keep changing as we scan
        */
        for (int col = 0; col < 9; col++)
        {
            if (grid[row,col] == num)
            {
                return true;
            }

        }
        return false;
    }

    static bool usedInCol(int col, int num)
    {
        /*
        * Scans through that "col" till a match is found.
        * So "col" will be the same, but "row" will keep changing as we scan
        */
        for (int row = 0; row < 9; row++)
        {
            if (grid[row,col] == num)
            {
                return true;
            }

        }
        return false;
    }

    static bool usedInBox(int boxStartRow, int boxStartCol, int num)
    {
        /*
        * Scans through the mini 3x3 box, looking for a duplicate number
        */
        for (int row = boxStartRow; row < boxStartRow + 3; row++)
        {
            for (int col = boxStartCol; col < boxStartCol + 3; col++)
            {
                if (grid[row,col] == num)
                    return true;
            }
        }
        return false;
    }

    static bool HasConflicts(int row, int col, int num)
    {
        bool isInRow, isInCol, isInBox, hasConflicts = false;

        isInRow = usedInRow(row, num);
        isInCol = usedInCol(col, num);


        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        isInBox = usedInBox(startRow, startCol, num);

        if (isInRow)
        {

            hasConflicts = true;
        }

        if (isInCol)
        {

            hasConflicts = true;
        }

        if (isInBox)
        {

            hasConflicts = true;
        }

        return hasConflicts;
    }
}
}

Answer 1

如果您想假设某个号码是正确的，则必须重新检查是否有重复号码。如果之前添加了数字并且存在于当前列或行或框中，则转到下一个约束。

你得到错误的答案是因为你在将数字输入 table 之前没有重新检查。

因此您可以在将数字输入 table 之前再次使用您自己的方法简单地修复它。

你在 SolveSudokuGrid 方法中的 for 循环就像

        for (int i = 0; i < constraint.Count; i++)
        {
            //Assume correct number by adding a constraint
            // But lets do a check if we already added in current column or row or box.
            if (usedInRow(row, constraint[i])) continue;
            if(usedInCol(col, constraint[i])) continue;

            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            if (usedInBox(startRow, startCol, constraint[i])) continue;

            grid[row, col] = constraint[i];

            if (SolveSudokuGrid() == true)
                return true;

            //Cant solve. Backtrack
            grid[row, col] = 0;
        }

并不是说这不会解决您当前的数独问题，因为给定的 table 无法解决。所以它将 return 和 table 保持不变。您还可以仅使用 SolveSudokuGrid:

的最终结果来检查 table 是否可解

    static void Main(string[] args)
    {
        GetConstraints();

        bool solvable = SolveSudokuGrid();

        if(!solvable) Console.WriteLine("Cannot solve!");
        else  PrintGrid();
        Console.Read();
    }

然而有时你可能会因为错误的table和算法的设计（如果你输入重复的数字）而陷入死循环。但如果 table 本身不包含重复数字，它应该可以正常工作。

更新：为了加快算法速度而不是按顺序分配数字，您必须将数字分配给不太正确的元素。

这将大大提高算法的速度。这也是解决数独的常用方法。

你的IsGameOver方法就像

    static bool IsGameOver(ref int row, ref int col)
    {
        for (int r = 0; r < 9; r++)
        {
            for (int c = 0; c < 9; c++)
            {
                if (grid[r, c] == 0)
                {
                    // set the row and col.
                    row = r;
                    col = c;

                    // but Lets check for the element with least possibilities in constraints.
                    // and prefer it against current row and col
                    int min = constraints[r, c].Count;
                    for (int i = 0; i < 9; i++)
                    {
                        for (int j = 0; j < 9; j++)
                        {
                            if (constraints[i, j] != null && // if the constraint is available
                                constraints[i, j].Count < min && // if found less possibilities
                                grid[i, j] == 0) // if the element of the table is 0 (its not assigned yet)
                            {
                                // set the row and col with less possibilities
                                row = i;
                                col = j;

                                min = constraints[i, j].Count;
                            }
                        }
                    }

                    return false;
                }
            }
        }

        return true;
    }

数独解算器不工作

Sudoku solver not working

c#

algorithm

sudoku