8-8 数独

問題

数独を解きます。

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] Ban = {{0,8,0,7,0,1,0,5,0},  //0
                      {0,0,2,0,4,0,9,0,0},  //1
                      {9,3,0,0,0,0,0,7,4},  //2
                      {8,0,0,1,0,4,0,0,6},  //3
                      {0,0,6,0,0,0,1,0,0},  //4
                      {7,0,0,9,0,3,0,0,8},  //5
                      {2,4,0,0,0,0,0,1,5},  //6
                      {0,0,7,0,5,0,3,0,0},  //7
                      {0,5,0,8,0,7,0,4,0}}; //8

        var stk = new Stack<int[,]>();
        stk.Push((int[,])Ban.Clone());

        while (stk.Count != 0) {
            Ban = stk.Pop();

            int targetX = 0, targetY = 0;
            while (targetX != 9) {
                if (Ban[targetX, targetY] == 0) {
                    break;
                }
                if (++targetY == 9) {
                    targetX++;
                    targetY = 0;
                }
            }

            if (targetX == 9) {
                Console.WriteLine("答え");
                PrintBan(Ban);
            }
            else {
                for (int N = 1; N <= 9; N++) {
                    if (IsValid(Ban, targetX, targetY, N)) {
                        Ban[targetX, targetY] = N;
                        stk.Push((int[,])Ban.Clone());
                    }
                }
            }
        }
    }

    static void PrintBan(int[,] pBan)
    {
        Console.WriteLine("-----------------------");
        for (int X = 0; X <= 8; X++) {
            for (int Y = 0; Y <= 8; Y++) {
                Console.Write(pBan[X, Y].ToString() + ",");
            }
            Console.WriteLine();
        }
    }

    static bool IsValid(int[,] pBan, int targetX, int targetY, int N)
    {
        for (int X = 0; X <= 8; X++) if (pBan[X, targetY] == N) return false;
        for (int Y = 0; Y <= 8; Y++) if (pBan[targetX, Y] == N) return false;

        for (int X = targetX / 3 * 3; X <= targetX / 3 * 3 + 2; X++) {
            for (int Y = targetY / 3 * 3; Y <= targetY / 3 * 3 + 2; Y++) {
                if (pBan[X, Y] == N) return false;
            }
        }
        return true;
    }
}

実行結果

答え
-----------------------
6,8,4,7,9,1,2,5,3,
5,7,2,3,4,8,9,6,1,
9,3,1,5,2,6,8,7,4,
8,2,3,1,7,4,5,9,6,
4,9,6,2,8,5,1,3,7,
7,1,5,9,6,3,4,2,8,
2,4,8,6,3,9,7,1,5,
1,6,7,4,5,2,3,8,9,
3,5,9,8,1,7,6,4,2,

解説

Stackジェネリックは強力ですねぇ

Javaアルゴリズムパズル 3-7 数独
PostgreSQLパズル 再帰with句10 数独を解く
DB2 SQLパズル 再帰with句10 数独を解く