学步园

      数独是一个很多人都喜欢的游戏。对于这样的问题，我比较喜欢的解决方案是写一个程序来解决这些问题。不过这些问题显然是那种需要回溯需要优化的问题。游戏规则我就不罗嗦了，言归正传。
      首先是解决数独问题的算法。程序输入，一个9*9的输入矩阵，有数字的地方就是指定的数字，没有数字的地方输入为0。算法的主要思想如下：
      1、创建一个堆栈trackStack，用来保存用程序填入的格子的信息。
      2、查找所有的数字为0的地方，察看这些地方所有的可能选择的数量，找到最小数量的那个格子。
      3、如果找到的最小数量为0的话，表明没有数字可以填写了。从trackStack中弹出一项，重新填写这个格子可能的一个数据。重复2；
      4、如果找到的最小数量不是0的话，在格子中填入最小的可能数据，将填入的格子的信息压入堆栈trackStack。如果还有格子为空，重复2；
      5、结束。

下面是完整的程序：

 

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace sodoku
{
    class DataItem
    {
        public int i;
        public int j;
        public int value ;
    }
    class Program
    {
        static bool bContinue = true ;
        static Stack<DataItem> trackStack = new Stack<DataItem>();
        static void OutputResult(int[][] iData)
        {
            for(int i = 0 ; i < 9 ; i++ )
            {
                Console.WriteLine();
                for (int j = 0; j < 9; j++)
                {
                    Console.Write("{0}\t", iData[i][j]);
                }
            }
        }

        static bool CheckValidInput(int[][] iData)
        {
            return true;
        }

        static int SearchMinOptions(int[][] iData)
        {
            int iMaxCount = 0;
            int iRow = 0, iColumn = 0;
            int iMinNum = 0;

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (iData[i][j] == 0)
                    {
                        int[] iFlag = new int[10];
                        for (int m = 0; m < 10; m++)
                        {
                            iFlag[m] = 0;
                        }
                        for (int k = 0; k < 9; k++)
                        {
                            iFlag[iData[i][k]] = 1;
                            iFlag[iData[k][j]] = 1;
                            iFlag[iData[i / 3 * 3+ k / 3][j / 3 * 3+ k % 3]] = 1;
                        }

                        int iCount = 0;
                        int iCurrMinNum = 0;
                        for (int m = 1; m < 10; m++)
                        {
                            if (iFlag[m] == 1)
                                iCount++;
                            if (iFlag[m] == 0 && iCurrMinNum == 0)
                            {
                                iCurrMinNum = m;
                            }
                        }
                        if (iCount > iMaxCount)
                        {
                            iRow = i;
                            iColumn = j;
                            iMaxCount = iCount;
                            iMinNum = iCurrMinNum;
                        }
                    }
                }
            }

            if (iMinNum == 0)
            {
                //OutputResult(iData);
                //check whether finished
                if( CheckFinished(iData) )
                {
                    Console.WriteLine( "Result:" ) ;
                    OutputResult( iData) ;
                    bContinue = false ;
                    return 0 ;
                }
                else
                {
                    do 
                    {
                        if (trackStack.Count == 0)
                        {
                            Console.WriteLine("Error!");
                            bContinue = false;
                            return 0;
                        }

                        DataItem item = trackStack.Pop() ;
                        int[] iFlag = new int[10];
                        for (int m = 0; m < 10; m++)
                        {
                            iFlag[m] = 0;
                        }
                        for (int k = 0; k < 9; k++)
                        {
                            iFlag[iData[item.i][k]] = 1;
                            iFlag[iData[k][item.j]] = 1;
                            iFlag[iData[item.i / 3 * 3+ k / 3][item.j / 3 * 3+ k % 3]] = 1;
                        }
                        for (int m = item.value + 1; m < 10; m++)
                        {
                            if (iFlag[m] == 0 && m > item.value )
                            {
                                iData[item.i][item.j] = m ;
                                item.value = m ;
                                trackStack.Push( item ) ;
                                return SearchMinOptions(iData);
                            }
                        }
                    }while(true ) ;
                }
            }
            Console.WriteLine();
            Console.WriteLine("X:{0},Y:{1},Num:{2}", iRow, iColumn,iMinNum);
            DataItem item2 = new DataItem();

            item2.i = iRow;
            item2.j = iColumn;
            item2.value = iMinNum;

            trackStack.Push(item2);

            iData[iRow][iColumn] = iMinNum;
            return 0;
        }
        static bool CheckFinished(int[][] iData)
        {
            bool bFinished = true;
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (iData[i][j] == 0)
                    {
                        bFinished = false;
                        break;
                    }
                }
            }

            return bFinished;
        }
        static void Main(string[] args)
        {
            string[] strAll = System.IO.File.ReadAllLines(@"D:\Test\sodoku\example.txt");

            int[][] iData = new int[9][] ;