生成数独

来源:互联网 时间:1970-01-01

通过随机生成中间九宫格的数字之后,通过行变换和列变化产生其他八个九宫格的数字,最后通过随机“挖洞”产生一个合法的数独。

基本上只是把《编程之美》里面说的东西实现了一遍,能产生9!个不同的数独,比较简单,但是方法不错。

#include <ctime>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 9;
vector<int> src;
int table[N][N] = {};

void ouput()
{
for (int i = 0; i < 9; ++i)
{
for (int j = 0; j < 9; ++j)
{
cout << table[i][j] << " ";
}
cout << endl;
}
}

void centerInit()
{
for (int i = 0; i < N; ++i)
src.push_back(i + 1);
random_shuffle(src.begin(), src.end());

int k = 0;
for (int i = 3; i < 6; ++i)
for (int j = 3; j < 6; ++j)
table[i][j] = src[k++];
}

void crossInit()
{
for (int i = 3; i < 6; ++i)
{
int l = 0;
for (int j = 3; j < 6; ++j)
{
if (i == 3)
{
table[i + 1][l] = table[i][j];
table[i + 2][l + 6] = table[i][j];
++l;
}
else if (i == 4)
{
table[i + 1][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
else if (i == 5)
{
table[i - 2][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
}
}
for (int j = 3; j < 6; ++j)
{
int l = 0;
for (int i = 3; i < 6; ++i)
{
if (j == 3)
{
table[l][j + 1] = table[i][j];
table[l + 6][j + 2] = table[i][j];
++l;
}
else if (j == 4)
{
table[l][j + 1] = table[i][j];
table[l + 6][j - 1] = table[i][j];
++l;
}
else if (j == 5)
{
table[l][j - 2] = table[i][j];
table[l + 6][j - 1] = table[i][j];
++l;
}
}
}
}

void cornerInit()
{
for (int i = 0; i < 3; ++i)
{
int l = 0;
for (int j = 3; j < 6; ++j)
{
if (i == 0)
{
table[i + 1][l] = table[i][j];
table[i + 2][l + 6] = table[i][j];
++l;
}
else if (i == 1)
{
table[i + 1][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
else if (i == 2)
{
table[i - 2][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
}
}
for (int i = 6; i < 9; ++i)
{
int l = 0;
for (int j = 3; j < 6; ++j)
{
if (i == 6)
{
table[i + 1][l] = table[i][j];
table[i + 2][l + 6] = table[i][j];
++l;
}
else if (i == 7)
{
table[i + 1][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
else if (i == 8)
{
table[i - 2][l] = table[i][j];
table[i - 1][l + 6] = table[i][j];
++l;
}
}
}
}

void init()
{
srand(time(NULL));
memset(table, 0, sizeof(table));
centerInit();
crossInit();
cornerInit();
}

void generateSudoku(int difficulty)
{
difficulty *= 20;
while (difficulty--)
{
table[rand() % 9][rand() % 9] = 0;
}
}

int main()
{
init();
int d;
cout << "Please select the difficulty(1~4): ";
cin >> d;
generateSudoku(d);
ouput();
cout << endl;
system("pause");
return 0;
}


相关阅读:
Top