游戏开发27课 速独算法

一、生成规则

　　1、按顺序将1~9填入宫格中；

　　2、检查所在行、列及小九宫格是否存在相同数字

　　3、若存在相同数字则将数字加1 ，重复第2步

　　这样就得到了初始的数独终盘

二、打乱顺序

　　1、随机交换某两行（只能是同一个九宫格内的两行）

　　2、随机交换某两列（只能是同一个九宫格内的两列）

       得到终盘

       

三、去掉部分数字，这样就得到了最终的数独了（可根据难度去掉不同数量的数字）

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

public class Sudu
{
    const int SIZE = 9;
    const int CELL_SIZE = 3;
    const int LEVEL_MAX = 10;
    static int[,] suduAry = new int[SIZE,SIZE];

    /**
10      * 生成数独
11      * @param level 难度级别 1~10
12      * @return
13      */
    public static int[,] generate(int level)
    {
        Random random = new Random();
        int n = random.Next(9) + 1;
        for (int i = 0; i < SIZE; i++)
        {
            for (int j = 0; j < SIZE; j++)
            {
                int p = (int)Math.Floor(i * 1.0f / CELL_SIZE);
                int q = (int)Math.Floor(j *1.0f/CELL_SIZE);
                for (int k = 0; k < SIZE; k++)
                {
                    if (checkColumn(n, j) && checkRow(n, i) && checkNineCells(n, p, q))
                    {
                        suduAry[i,j] = n;
                        break;
                    }
                    else
                    {
                        n = n % SIZE + 1;
                    }
                }
            }
            n = n % SIZE + 1;
        }
        //upset();
        //maskCells(level);

        return suduAry;
    }

    private static void maskCells(int level)
    {
        int min, max;
        level %= LEVEL_MAX;
        if (level == 0) level = LEVEL_MAX;

        if (level < 4)
        {
            min = 20;
            max = 15;
        }
        else if (level < 7)
        {
            min = 40;
            max = 10;
        }
        else if (level < 10)
        {
            min = 50;
            max = 10;
        }
        else
        {
            min = 60;
            max = 5;
        }

        Random random = new Random();
        int count = random.Next(max) + min;
        for (int i = 0; i < count; i++)
        {
            do
            {
                int n = random.Next(SIZE);
                int m = random.Next(SIZE);
                if (suduAry[n,m] > 0)
                {
                    suduAry[n,m] = 0;
                    break;
                }
            } while (true);
        }
    }

    /**
72      * 随机打乱顺序
73      */
    private static void upset()
    {
        Random random = new Random();
        //按行交换
        for (int i = 0; i < SIZE; i++)
        {
            int n = random.Next(CELL_SIZE);
            int p = random.Next(CELL_SIZE) * CELL_SIZE + n;
            for (int j = 0; j < SIZE; j++)
            {
                int tmp = suduAry[i,j];
                suduAry[i,j] = suduAry[p,j];
                suduAry[p,j] = tmp;
            }
        }
        //按列交换
        for (int i = 0; i < SIZE; i++)
        {
            int n = random.Next(CELL_SIZE);
            int p = random.Next(CELL_SIZE) * CELL_SIZE + n;
            for (int j = 0; j < SIZE; j++)
            {
                int tmp = suduAry[j,i];
                suduAry[j,i] = suduAry[j,p];
                suduAry[j,p] = tmp;
            }
        }
    }

    /**
99      * 检查某行
100      * @param n
101      * @param row
102      * @return
103      */
    private static bool checkRow(int n, int row)
    {
        bool result = true;

        for (int i = 0; i < SIZE; i++)
        {
            if (suduAry[row,i] == n)
            {
                result = false;
                break;
            }
        }

        return result;
    }
    /**
117      * 检查某列
118      * @param n
119      * @param col
120      * @return
121      */
    private static bool checkColumn(int n, int col)
    {
        bool result = true;
        for (int i = 0; i < SIZE; i++)
        {
            if (suduAry[i,col] == n)
            {
                result = false;
                break;
            }
        }
        return result;
    }

    /**
134      * 检查小九宫格
135      * @param n
136      * @param x
137      * @param y
138      * @return
139      */
    private static bool checkNineCells(int n, int x, int y)
    {
        bool result = true;
        int sx = x * 3, sy = y * 3;

        for (int i = sx; i < sx + 3; i++)
        {
            for (int j = sy; j < sy + 3; j++)
            {
                if (suduAry[i,j] == n)
                {
                    result = false;
                    break;
                }
            }
            if (!result) break;
        }

        return result;
    }

    public static void Main()
    {
        var arr = generate(1);
        for (int i = 0; i < SIZE;++i)
        {
            for(int j=0;j             {
                Console.Write(arr[i,j]+" ");
            }
            Console.WriteLine();
        }
    }
}