C#实现数独解法

2022-11-13 10:11:45 解法 数独

数独简介

数独（shù dú）是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 [1]  。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

实现方式

今天晚上抽空把数独的计算机求解也给实现了一下，由于时间有限，我这里追求的是简洁而有效的解法，故用的是最原始而直观的回溯算法。速度也还可以接受，解网上最难的数独也大概就0.0X秒的样子。最开始是一个面向过程的实现，考虑到用的是C#的实现，便把这个算法给OO化了一下。

class Sudoku
{
    public int[,] Numbers { get; set; }
    int x;
    int y;

    public Sudoku(int[,] num)
    {
        Numbers = num;

        for (x = 0; x < 9; x++)
        {
            for (y = 0; y < 9; y++)
            {
                if (Numbers[x, y] == 0)
                    return;
            }
        }
    }

    public bool IsCompleted { get { return x == 9 && y == 9; } }

    //计算数独，返回null表示无法计算
    public Sudoku CaluSudoKu()
    {
        if (IsCompleted)
            return this;

        foreach (var num in GetAvaibleNumbers())
        {
            var tmpData = Numbers.Clone() as int[,];
            tmpData[x, y] = num;

            var sudouku = new Sudoku(tmpData);
            var ret = sudouku.CaluSudoKu();

            if (ret != null)
                return ret;
        }

        return null;
    }

    int[] GetAvaibleNumbers()
    {
        var set = new HashSet<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
        for (int i = 0; i < 9; i++)
        {
            set.Remove(Numbers[x, i]);
            set.Remove(Numbers[i, y]);
        }

        int xStart = x - x % 3;
        int yStart = y - y % 3;

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                set.Remove(Numbers[i + xStart, j + yStart]);
            }
        }

        return set.ToArray();
    }
}

算法非常简单，大概就五六十行的样子，这种简单的算法自然谈不上高效，那些讨论数独算法的时间复杂度和空间复杂度的话题不在本文讨论范围之列。

到此这篇关于C#实现数独解法的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持。

相关文章