HPCW2014 21 - SuDoKu

domen111

HP CodeWars 2014
AC code(C#): http://ideone.com/uDQTZC

題目概述:
給你一個標準數獨的題目，請你算出答案。
數獨規則: http://oddest.nc.hcc.edu.tw/wusu29.htm
例如:
---26-7-1
68--7--9-
19---45--
82-1---4-
--46-29--
-5---3-28
--93---74
-4--5--36
7-3-18---


解法:
基本上遞迴下去暴力解就ok了。遞迴函式中測試1~9的數字是否可以填入，如果可以就繼續遞迴，直到解出題目，若不行就return回去上一遞迴。

複雜度:
如果隨便估計最壞的時間複雜度會是: 9^81 很恐怖的天文數字，不過事實上不可能到那麼大。
以範例測資來說，Do被呼叫55次；空的題目是393次；我試過的幾題中最多的是11540次。

心得:
其實這個解數獨的程式是好幾年前就用C#寫好的視窗程式，寫了幾行輸出入就賺到17分(我們寫的其他題目大多5分左右)，心得就是寫HP Code War時，記得要把以前寫過的code存在電腦裡，基本上hpcw就是一堆會寫的題目，時間內能寫多少就得幾分，如果有以前寫過的code就直接改一改輸出入丟上去，就省了很多時間，賺到好幾分，尤其像是這種較高分的題目。

[C#] 純文本查看 復制代碼

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace prob21
{
    class Program
    {
        static string[] SuDoKu = new string[81];
        static bool[] IsOriginal = new bool[81];  //是不是題目
 
        static void Main(string[] args)
        {
            string temp;
            for (int i = 0; i < 9; i++)
            {
                temp = Console.ReadLine();
                for (int j = 0; j < temp.Length; j++)
                {
                    if (temp[j] == '-')
                        SuDoKu[i * 9 + j] = "";
                    else
                        SuDoKu[i * 9 + j] = temp[j].ToString();
                }
            }
 
            for (int i = 0; i < 81; i++)
            {
                if (SuDoKu[i].Trim() == "")
                    IsOriginal[i] = false;
                else
                    IsOriginal[i] = true;
            }
 
            Do(0);
 
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    Console.Write(SuDoKu[i * 9 + j]);
                }
                Console.Write("\n");
            }
        }
 
                //遞迴解題
        static bool Do(int i)
        {
            //檢查是不是題目
            while (i < 81 && IsOriginal[i])
                i++;
            //檢查是不是已經解題了
            if (i > 80)
                return true;
            //從1、2、3…9逐一測試直到成功
            for (int j = 1; j <= 9; j++)
            {
                //檢查可不可以在這個地方填這個數字
                if (Check(i, j.ToString()))
                {
                    SuDoKu[i] = j.ToString();
                    //呼叫自己
                    if (Do(i + 1))  //如果傳回已經解題了，就回傳已經解題了
                        return true;
                    else          //如果傳回需要倒回去，就存空白的值
                        SuDoKu[i] = "";
                }
            }
            return false;
        }
        static bool Check(int arrayNo, string data)
        {
            return CheckRow(arrayNo, data) && CheckColumn(arrayNo, data) && CheckGrid(arrayNo, data);
        }
        static bool CheckRow(int arrayNo, string data)
        {
            int rowNo = arrayNo / 9;
 
            for (int i = 0; i < 9; i++)
            {
                if (SuDoKu[i + rowNo * 9] == data && (i + rowNo * 9) != arrayNo)
                {
                    return false;
                }
            }
            return true;
        }
        static bool CheckColumn(int arrayNo, string data)
        {
            int colNo = arrayNo % 9;
 
            for (int i = 0; i < 9; i++)
            {
                if (SuDoKu[i * 9 + colNo] == data && (i * 9 + colNo) != arrayNo)
                {
                    return false;
                }
            }
            return true;
        }
        static bool CheckGrid(int arrayNo, string data)
        {
            int gridNo = arrayNo / 27 * 27 + arrayNo % 9 / 3 * 3;
 
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (SuDoKu[gridNo + i * 9 + j] == data && (gridNo + i * 9 + j) != arrayNo)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}