張德長

困難  通過率：27.56%  時間限制：1秒  空間限制：32M

 

描述

問題描述：數獨（Sudoku）是一款大眾喜愛的數字邏輯游戲。玩家需要根據9X9盤面上的已知數字，推算出所有剩余空格的數字，并且滿足每一行、每一列、每一個3X3粗線宮內的數字均含1-9，并且不重復。

例如：

輸入

輸出

 

數據范圍：輸入一個 9*9 的矩陣

輸入描述：

包含已知數字的9X9盤面數組[空缺位以數字0表示]

輸出描述：

完整的9X9盤面數組

示例1

輸入：

0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1

復制

輸出：

5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

個人感覺，這個題目出的不好，有多種答案，但是題目只給出一種答案；只要不符合標準答案，即使滿足要求，也無法通過；6個用例只通過了5個；

后面的Check函數不是為了解出答案，而是為了檢查輸出的結果；

本方法還有改進的空間，目前無法唯一確定某一個值時，都是從可能的選項中默認選擇第一個；

其實如果默認第一個的情況下無法解出答案時，可以用Check+Random的方式，也就是每試一次都是從可能的選項中隨機選擇一個，如果不行就再來一遍；

前提時要先把能唯一確定的最終狀態記錄下來，后面開始通過無限循環一直進行查找，總能找到答案；

 using System;
    using System.Collections.Generic;
    public class Program
    {
        public static void Main()
        {
            string line; List<string> lines = new List<string>();
            while ((line = System.Console.ReadLine()) != null)
            { // 注意 while 處理多個 case
                lines.Add(line);

                if (lines.Count == 9)
                {
                    string[] lineArr;
                    int[,] arr = new int[9, 9];
                    int answer = 0; bool find;
                    for (int i = 0; i < 9; i++)
                    {
                        line = lines[i];
                        lineArr = line.Split(" ");
                        for (int j = 0; j < 9; j++)
                        {
                            arr[i, j] = int.Parse(lineArr[j]);
                        }
                    }
                    //最多循環81次
                    for (int k = 0; k < 81; k++)
                    {
                        if (k == 0)
                        {
                            find = true;
                        }
                        else
                        {
                            find = false;
                        }
                        for (int i = 0; i < 9; i++)
                        {
                            for (int j = 0; j < 9; j++)
                            {

                                if (arr[i, j] == 0)
                                {
                                    answer = GetAnswer(i, j, arr, find);
                                    if (answer != 0)
                                    {
                                        arr[i, j] = answer;
                                        find = true;
                                    }

                                }
                            }
                        }
                        //如果已完成，就立即結束循環
                        if (!HasZero(arr))
                        {
                            break;
                        }
                    }
                    
                    //輸出
                    for (int i = 0; i < 9; i++)
                    {
                        line = string.Empty;
                        for (int j = 0; j < 9; j++)
                        {
                            line += arr[i, j].ToString();
                            if (j != 8)
                            {
                                line += " ";
                            }
                        }
                        Console.WriteLine(line);
                    }
                    Check(arr);
                }

            }
        }
        //獲取某個空位的答案
        static int GetAnswer(int row, int column, int[,] arr, bool find)
        {
            //使用排除法確定可以填寫的值
            //一共1-9九個，如果排除到只剩一個，那么就可以確定答案了
            List<int> left = new List<int>();
            for (int i = 1; i <= 9; i++)
            {
                left.Add(i);
            }
            //從行開始排除
            for (int i = 0; i < 9; i++)
            {
                if (i == column) continue;
                left.Remove(arr[row, i]);
            }
            if (left.Count == 1)
            {
                
                return left[0];
            }
            //再從列排除
            for (int i = 0; i < 9; i++)
            {
                if (i == row) continue;
                left.Remove(arr[i, column]);
            }
            if (left.Count == 1)
            {
                return left[0];
            }
            //從所在的九宮格排除
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (row / 3 * 3 + i == row && column / 3 * 3 + j == column)
                        continue;
                    left.Remove(arr[row / 3 * 3 + i, column / 3 * 3 + j]);
                }
            }
            if (left.Count == 1)
            {
                return left[0];
            }
            else if (!find && left.Count > 0)
            {
                return left[0];
            }
            return 0;
        }
        //判定矩陣中是否還有0，也就是判定是否已經完成
        static bool HasZero(int[,] arr)
        {
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (arr[i, j] == 0)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        static bool Check(int[,] arr)
        {
            if (HasZero(arr)) return false;
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    int answer = GetAnswer(i, j, arr, true);
                    if (answer != arr[i, j])
                    {
                        Console.WriteLine($"row={i},col={j},answer={answer},real={arr[i, j]}");
                        return false;
                    }
                }
            }
            return true;
        }
    }