Pongeponge

Codingame『Mini sudoku solver』

「数独」を数学する -世界中を魅了するパズルの奥深い世界-


4 x 4数独を解け

 縦、横、2x2ドメインで数字が被らないようにすればいいんだから、
それぞれをスキャンして数字を調べていけばいい。


n x n数独

 これはn x n (n = m^2)数独でも対応可能なんだろうか?
100x100でも時間さえかければ今のコードで解けるものなのか?


コード
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        MiniSudokuSolver mss = new MiniSudokuSolver();

        mss.Solve();

        mss.Draw();
    }
}

class MiniSudokuSolver
{
    private List<int>[,] map;

    public MiniSudokuSolver()
    {
        map = new List<int>[4, 4];

        for (int y = 0; y < 4; y++)
        {
            string line = Console.ReadLine();
            for (int x = 0; x < 4; x++)
            {
                map[x, y] = new List<int>();

                int num = int.Parse(line[x].ToString());

                if (num == 0)
                {
                    map[x, y] = new List<int>() { 1, 2, 3, 4 };
                }
                else
                {
                    map[x, y] = new List<int>() { num };
                }
            }
        }
    }

    public void Solve()
    {
        bool f = false;

        while(!f)
        {
            f = true;

            for (int y = 0; y < 4; y++)
            {
                for (int x = 0; x < 4; x++)
                {
                    if(map[x,y].Count != 1)
                    {
                        for (int line = 0; line < 4; line++)
                        {
                            //横
                            if (line != x & map[line, y].Count == 1 & map[x, y].Contains(map[line, y][0]) == true)
                                map[x, y].Remove(map[line, y][0]);

                            //縦
                            if (line != y & map[x, line].Count == 1 & map[x, y].Contains(map[x, line][0]) == true)
                                map[x, y].Remove(map[x, line][0]);
                        }

                        //2x2ドメイン
                        for (int dy = y/2*2; dy < y/2*2+1; dy++)
                        {
                            for (int dx = x/2*2; dx < x/2*2+1; dx++)
                            {
                                if (dx != x & dy != y)
                                {
                                    if (map[dx, dy].Count == 1 & map[x, y].Contains(map[dx, dy][0]) == true)
                                    {
                                        map[x, y].Remove(map[dx, dy][0]);
                                    }
                                }
                            }
                        }
                    }

                    //要素数2以上があれば再ループ
                    if (map[x, y].Count != 1) f = false;
                }
            }
        }
    }


    public void Draw()
    {
        for (int y = 0; y < 4; y++)
        {
            for (int x = 0; x < 4; x++)
            {
                Console.Write(map[x, y].Count == 1 ? map[x, y][0] : 0);
            }
            Console.WriteLine("");
        }
    }
}