终于调通了。数独的C#求解程序！

HimeTale 2008-06-03 10:42:30

关于数独的简介看这个http://baike.baidu.com/view/961.htm
form上很简单，9*9的DataGridView用来添已知数字,
一个运行，一个清空。
所有结果依次控制台输出。

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;



namespace WindowsApplication12

{

    public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();

        }



        private void Form1_Load(object sender, EventArgs e)

        {

            ClearDv();

        }



        private void btnClear_Click(object sender, EventArgs e)

        {

            ClearDv();

        }



        //清空DataGridView

        private void ClearDv()

        {

            while (dvData.Rows.Count > 0)

            {

                dvData.Rows.Remove(dvData.Rows[0]);

            }

            dvData.Rows.Add(9);

            for (int i = 0; i < 9; i++)

                for (int j = 0; j < 9; j++)

                    dvData.Rows[i].Cells[j].Value = string.Empty;

        }



        private void btnStart_Click(object sender, EventArgs e)

        {

            getSol();

        }



        private void getSol()

        {

            if (isComplete())

            {

                //控制台输出结果

                for (int i = 0; i < 9; i++)

                {

                    for (int j = 0; j < 9; j++)

                        Console.Write(dvData.Rows[i].Cells[j].Value.ToString() + " ");

                    Console.WriteLine();

                }

                Console.WriteLine("****************");

                return;

            }

            int intX, intY;  //单元格坐标

            List<int> listCan = GetWeakPoint(out intX, out intY);  //listCan:单元格的所有可能值

            if (listCan.Count == 0)

                return;



            for (int i = 0; i < listCan.Count; i++)

            {

                //纪录回溯前状态

                string temp = dvData.Rows[intX].Cells[intY].Value.ToString();

                dvData.Rows[intX].Cells[intY].Value = listCan[i];

                //回溯尝试下一个位置

                getSol();

                //还原到回溯前的状态

                dvData.Rows[intX].Cells[intY].Value = temp;

            }

        }



        //寻找可能性最少的格

        private List<int> GetWeakPoint(out int intX, out int intY)

        {

            intX = 0;

            intY = 0;

            List<int> listCan=new List<int>();

            List<int> listTemp=new List<int>();

            for (int i=1; i <= 9; i++)

                listCan.Add(i);

            for (int i = 0; i < 9; i++)

            {

                for (int j = 0; j < 9; j++)

                    {

                        listTemp.Clear();

                        for (int k = 1; k <= 9; k++)

                            listTemp.Add(k);

                        //只对非空单元格操作

                        if (dvData.Rows[i].Cells[j].Value.ToString() == string.Empty)

                        {

                            //行排除可能性

                            for (int k = 0; k < 9; k++)

                                if (dvData.Rows[i].Cells[k].Value.ToString() != string.Empty)

                                    listTemp.Remove(Convert.ToInt32(dvData.Rows[i].Cells[k].Value));

                            //列排除可能性

                            for (int k = 0; k < 9; k++)

                                if (dvData.Rows[k].Cells[j].Value.ToString() != string.Empty)

                                    listTemp.Remove(Convert.ToInt32(dvData.Rows[k].Cells[j].Value));

                            for (int m = 0; m < 9; m++)

                                for (int n = 0; n < 9; n++)

                                    if (m / 3 == i / 3 && j / 3 == n / 3)

                                        if (dvData.Rows[m].Cells[n].Value.ToString() != string.Empty)

                                            listTemp.Remove(Convert.ToInt32(dvData.Rows[m].Cells[n].Value));

                            if (listTemp.Count < listCan.Count)

                            {

                                listCan.Clear();

                                for (int p = 0; p < listTemp.Count; p++)

                                    listCan.Add(listTemp[p]);

                                intX = i;

                                intY = j;

                            }

                        }

                    }

            }

            return listCan;

        }



        //判断是否解决

        private bool isComplete()

        {

            for (int i = 0; i < 9; i++)

                for (int j = 0; j < 9; j++)

                    if (dvData.Rows[i].Cells[j].Value == null || dvData.Rows[i].Cells[j].Value.ToString() == string.Empty)

                        return false;

            return true;

        }

    }

}