以下作成したプログラムの全文です。生成方法の種類により、一部書き換える必要があります。また、html出力部は坂本教授よりご提供頂きました。ありがとうございます。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define N 9
#define B 3 //square root of N
#define swap(a,b) a^=b^=a^=b
#define R 1000 //反復回数
//#define DEBUG
void header(std::ostream& os){
os <<
"<!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01//EN\">"
"<html lang=\"ja\">"
"<head>"
"<meta http-equiv=\"content-type\" content=\"text/html; charset=Shift_JIS\">"
"<title>数独</title>"
"<style>"
"td td{width: 3em; height:3em;text-align: center}"
"</style>"
"</head>"
"<body>"
<< std::endl;
}
void footer(std::ostream& os){
os <<
"</body>"
"</html>"
<< std::endl;
}
void inner(std::ostream&os, int top, const int * x){
os << "<table border=\"1\">" << std::endl;
for(int i=0; i<3; ++i){
os << "<tr>" << std::endl;
for(int j=0; j<3; ++j){
os << "<td>";
int value=x[top+i*9+j];
#ifndef DEBUG
if(value>0 ){
#endif
os<< value;
#ifndef DEBUG
}
#endif
os <<"</td>" << std::endl;
}
os << "</tr>" << std::endl;
}
os << "</table>" << std::endl;
}
std::ostream& operator<<(std::ostream& os, const int* x){
header(os);
os << "<table border=\"1\">" << std::endl;
for(int i=0; i<3; ++i){
os << "<tr>" << std::endl;
for(int j=0; j<3; ++j){
os << "<td>" ;
inner(os,i*27+j*3,x);
os << "</td>" << std::endl;
}
os << "</tr>" << std::endl;
}
os << "</table>" << std::endl;
footer(os);
return os;
}
void printResult(int board[]){//結果出力
int i,n=0;
for (i=0; i<N*N; ++i) {
if (N>9 && board[i]<10) printf(" ");//２桁整列用
printf("%d ", board[i]);
if (i%N==N-1) printf("\n");
}
printf("\n");
return;
}
int canBePlaced(int board[], int pos, int x)//check関数で仮に入れられた値が、縦・横・その値の所属の3×3マス（太枠）にあれば0を返す（なければ1を返す)
{
int row=pos/N;//row=行
int col=pos%N;//col=列
int i, j, topLeft;
for (i=0; i<N; ++i) {
if (board[row*N+i]==x) return 0;
if (board[col+i*N]==x) return 0;
}
topLeft=N*(row/B)*B+(col/B)*B;
for (i=0; i<B; ++i) {
for (j=0; j<B; ++j) {
if (board[topLeft+i*N+j]==x) return 0;
}
}
return 1;
}
int count0(int board[]){//配列内０の数を数える
int c=0;
for (int i=0; i<N*N; i++) {
if(board[i]==0)c++;
}
return c;
}
void cloneBoard(int boardOriginal[],int boardCopy[]){//前の配列を後ろのにコピペ
for (int i=0; i<N*N; i++) {
boardCopy[i]=boardOriginal[i];
}
}
void rand9(int randamboard[], int n){//１〜９の値をランダムに並び替える
srand((unsigned)time(NULL)+n);
for (int x=0; x<N; x++)randamboard[x]=x+1;
// numbersをランダムに並び替える
for(int i=0; i<N; i++){
int j =rand()%N;
if (i!=j)swap(randamboard[i], randamboard[j]);
}
return;
}
void rand81(int randBoard[],int n){//0〜80の値をランダムに並び替える
srand((unsigned)time(NULL)+n);
for (int x=0; x<N*N; x++)randBoard[x]=x;
// numbersをランダムに並び替える
for(int i=0; i<N*N; i++){
int j =rand()%N*N;
if (i!=j)swap(randBoard[i], randBoard[j]);
}
return;
}
void check(int board[], int pos, int n)//完成形を作成
{
int i, x, newPos, j=0;
//Solution is found.
if (pos==N*N) throw j;//メイン関数へ戻る
//Find a blank.
for (newPos=pos; newPos<N*N; ++newPos) {
if (board[newPos]==0) break;
}
//Check recursively.
for (x=0; x<N; ++x) {
int randBoard9[N];
rand9(randBoard9, n);//randBoard9＝１〜９の値がランダムに入った配列。nはsrandのシード値を変えるのに使用。
int y=randBoard9[x];
if (canBePlaced(board, newPos, y)) {//if （boardのnewPosにrand9(x)が入れられるなら）
board[newPos]=y;
check(board, newPos+1,n+1);
board[newPos]=0;//backtracking
}
}
return;
}
void maker1(int board[], int n){//問題作成１ ランダム
int randBoard81[N*N];
rand81(randBoard81, n);
for (int x=0; x<N*N; x++){
int c=0;
int tmp=board[randBoard81[x]];
board[randBoard81[x]]=0;
for (int i=1; i<=N; i++){
if (canBePlaced(board, randBoard81[x], i))c++;
}
if(c!=1)board[randBoard81[x]]=tmp;
}
return;
}
void maker2(int board[], int n){//問題作成 順番指定
int cntBoard[]={
46,47,48,10,11,12,55,56,57,
49,50,51,13,14,15,58,59,60,
52,53,54,16,17,18,61,62,63,
19,20,21, 1, 2, 3,28,29,30,
22,23,24, 4, 5, 6,31,32,33,
25,26,27, 7, 8, 9,34,35,36,
64,65,66,37,38,39,73,74,75,
67,68,69,40,41,42,76,77,78,
70,71,72,43,44,45,79,80,81};
for (int x=0; x<N*N; x++){
int c=0;
int tmp=board[cntBoard[x]-1];
board[cntBoard[x]-1]=0;
for (int i=1; i<=N; i++){
if (canBePlaced(board, cntBoard[x]-1, i))c++;
}
if(c!=1)board[cntBoard[x]-1]=tmp;
}
return;
}
int main(){
clock_t start, end;
start = clock();
int board[N*N],boardDef[N*N],ave[5]={0,0,0,0,0};
int boardMax1[N*N],boardMax2[N*N];
int c=0, max1=0,max2=0, tmp;
for (int j=0; j<R; j++) {//反復回数
c++;//ループ毎のランダムシード変更用
for (int i=0; i<N*N; i++) {//配列内の要素を全て０で初期化
board[i]=0;
}
try {check(board, 0, c);}
catch (int b){/*printResult(board);*/}
cloneBoard(board,boardDef);
//printf( "パターン1\n\n");
maker1(board, 0);
//printResult(board);
tmp=count0(board);
//printf( "0の個数:%d[個]\n", tmp);
ave[0]+=tmp;
if(tmp>max1){//最大値測定用
cloneBoard(board,boardMax1);
max1=tmp;
}
cloneBoard(boardDef,board);
/*
//printf( "パターン2\n\n");
maker2(board, 0);
//printResult(board);
tmp=count0(board);
//printf( "0の個数:%d[個]\n", tmp);
ave[4]+=tmp;
if(tmp>max2){//最大値測定用
cloneBoard(board,boardMax2);
max2=tmp;
}*/
}
/*printf( "------------------------------\n");
printf( "パターン１\n平均：%d[個]\n", ave[0]/R);
printf( "最大：%d[個]\n", max1);
printResult(boardMax1);
printf( "パターン２\n平均：%d[個]\n", ave[1]/R);
printf( "最大：%d[個]\n", max2);
printResult(boardMax2);*/
end = clock();
printf( "処理時間:%d[ms]\n", end - start );
std::cout << boardMax1;
return 0;
}