一、游戏介绍:
「数独sudoku」来自日文,但概念源自「拉丁方块」,是十八世纪瑞士数学家欧拉发明的。游戏规则很简单:在九个九宫格里,填入1到9的数字,让每个数字在每个行、列及九宫格里都只出现一次。
二、数独算法主要步骤
1、出题
(1)静态数组,数值固定,或采用由用户输入方式
(2)电脑出题算法
将一行或者一列随机填上1-9,生成一个数独题目
根据第一步生成的数独题目调用解题函数求解
从解出来的题目中随机挖空若干个数字(在一定的范围内,挖空的数字越多,难度越大)
通过以上几步,就可以生成一个数独题目了,但有一点需要注意一下,由于题目需要一定随机性,除了第一步的填充数字外,数独求解算法也要求具有一定的随机性。即对于有多个解的数独程序,不同的时候运行得出来的解也不同。
2、验证
验证每行、每列、每个九宫格里的数字是否唯一
3、解题:简单的算法一般采用穷举+回溯算法
针对为0的位置尝试填入1-9数字,同时调用验证函数
成功则继续填下一个空位
否则,还原为0,回溯调用解题函数
当所有空格填完,返回
算法改进:可以采用预先判断可填值范围,缩小填值范围
4、显示
就是输出一个二维数组
三、代码
C#控制台代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace solve
{
class Program
{
//出题,采用静态数组
static int[,] pu = new int[9, 9]
{
{0,0,0,7,2,8,0,0,0},
{0,9,0,0,5,1,6,0,0},
{0,0,0,0,6,0,0,8,2},
{3,0,0,8,0,2,7,0,4},
{1,7,4,0,3,0,0,2,0},
{2,8,0,5,0,0,0,3,0},
{0,1,0,3,0,0,2,0,0},
{0,0,7,0,4,6,0,0,5},
{0,0,6,1,0,0,0,4,9} };
static void Main(string[] args)
{
Show();
GetAnswer(0);
Console.ReadLine();
}
/// <summary>
/// 验证函数
/// </summary>
/// <param name="i"></param>
/// <param name="j"></param>
/// <returns></returns>
static bool IsValid(int i, int j)
{
int n = pu[i, j];
int[] query = new int[9] { 0, 0, 0, 3, 3, 3, 6, 6, 6 };
int t, u;
//每一行每一列是否重复
for (t = 0; t < 9; t++)
{
if ((t != i && pu[t, j] == n) || (t != j && pu[i, t] == n))
return false;
}
//每个九宫格是否重复
for (t = query[i]; t < query[i] + 3; t++)
{
for (u = query[j]; u < query[j] + 3; u++)
{
if ((t != i || u != j) && pu[t, u] == n)
return false;
}
}
return true;
}
/// <summary>
/// 显示函数
/// </summary>
static void Show()
{
for (var i = 0; i < 9; i++)
{
for (var j = 0; j < 9; j++)
{
Console.Write(pu[i, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine("----------------------------------------------");
}
/// <summary>
/// 使用回溯算法求解
/// </summary>
/// <param name="n"></param>
static void GetAnswer(int n)
{
if (n == 81)
{//是否已经是最后一个格子
Show();
return;
}
int i = n / 9, j = n % 9;
if (pu[i, j] != 0)
{//如果当前格子不需要填数字,就跳到下一个格子
GetAnswer(n + 1);
return;
}
for (int k = 0; k < 9; k++)
{
pu[i, j]++;//当前格子进行尝试所有解
if (IsValid(i, j))
GetAnswer(n + 1);//验证通过,就继续下一个
}
pu[i, j] = 0; //如果上面的单元无解,还原,就回溯
return ;
}
}
}
大家可以参考由飞多网络技术中心提供的更详细的C#版WINFORM源程序
/software/application/05/08-1193.html