8-8 数独

問題

数独を解きます。

ソース

#include <valarray>
#include <vector>
#include <stack>
#include <stdio.h>

void PrintBan(std::vector<std::valarray<int> > &pBan);
bool IsValid(std::vector<std::valarray<int> > &pBan, int targetX, int targetY, int N);

void main()
{
    int BanNijigenArr[9][9] = {{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
    const int UBX = sizeof(BanNijigenArr)/sizeof(BanNijigenArr[0])-1;
    const int UBY = sizeof(BanNijigenArr[0])/sizeof(int)-1;

    std::vector<std::valarray<int> > BanArrVect(9);
    for(int X=0;X<=UBX;X++){
        std::valarray<int> wkArr(BanNijigenArr[X],UBY+1);
        BanArrVect.at(X) = wkArr;
    }

    std::stack<std::vector<std::valarray<int> > > stk;
    stk.push(BanArrVect);

    while (stk.empty() == false) {
        BanArrVect = stk.top(); stk.pop();

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

        if (targetX == 9) {
            puts("答え");
            PrintBan(BanArrVect);
        }
        else{
            for (int N = 1; N <= 9; N++) {
                if (IsValid(BanArrVect, targetX, targetY, N)) {
                    BanArrVect.at(targetX)[targetY] = N;
                    stk.push(BanArrVect);
                }
            }
        }
    }
}

void PrintBan(std::vector<std::valarray<int> > &pBan)
{
    puts("-----------------------");
    for (int X = 0; X <= (int)pBan.size()-1; X++) {
        for (int Y = 0; Y <= (int)pBan.at(X).size()-1; Y++) {
            printf("%d,",pBan.at(X)[Y]);
        }
        puts("");
    }
}

bool IsValid(std::vector<std::valarray<int> > &pBan, int targetX, int targetY, int N)
{
    for (int X = 0; X <= 8; X++) if (pBan.at(X)[targetY] == N) return false;
    for (int Y = 0; Y <= 8; Y++) if (pBan.at(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.at(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,

解説

第1引数にビルトイン配列の変数名 (C言語の配列名なので実質はポインタ)
第2引数に要素数
を取る、ValArrayクラスのコンストラクタを使ってます。