プロジェクトオイラー問96 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2096
数独の盤面を解く問題。

入る可能性のある数字の少ないマスから優先して全探索するだけです。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

struct E{
	int x,y;
	std::vector<char> vec;
	bool operator<(const E& e)const{
		if(vec.size()!=e.vec.size())return vec.size()<e.vec.size();
		return false; 
	} 
};
FILE *fp;
char map[9][10];

bool inOK(int x,int y,char n){
	for(int i=0;i<9;i++){
		if(map[y][i]==n)return false;
		if(map[i][x]==n)return false;
	}
	int x1=x/3*3;
	int y1=y/3*3;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(map[y1+i][x1+j]==n)return false;
		}
	}
	return true;
} 

std::vector<E> vec;
int ans=0;
bool isHit;

bool search(int p){
	if(vec.size()==p){
		ans+=(map[0][0]-'0')*100+(map[0][1]-'0')*10+(map[0][2]-'0');
		return true;
	}else{
		
		for(int i=0;i<vec[p].vec.size();i++){
			char c=vec[p].vec[i];
			int x=vec[p].x;
			int y=vec[p].y;
			if(inOK(x,y,c)==true){
				map[y][x]=c;
				if(search(p+1)==true){
					return true;	
				}
				
				map[y][x]='0';
			}
		}
	}
	return false;
}
 
void calc(){
	
	
	
	for(int i=0;i<9;i++){
		fscanf(fp,"%s",map[i]);
	}
	bool bs[9][9][10];
	memset(bs,0,sizeof(bs));
 	
while(vec.empty()==false){
 		vec.pop_back();
	}
	
	for(int y=0;y<9;y++){
		for(int x=0;x<9;x++){
			if(map[y][x]!='0')continue;
			E e1;
			e1.x=x;
 			e1.y=y;
			for(char a='1';a<='9';a++){
				if(inOK(x,y,a)==true){
 					e1.vec.push_back(a);
				}
			}
 			vec.push_back(e1);
		}
	}
 
	std::sort(vec.begin(),vec.end());
	search(0);
}


int main(){
if ((fp = fopen("sudoku.txt", "r")) == NULL) {
         	fprintf(stderr, "%s\n", "error: can't read file.");
        	return EXIT_FAILURE;
    	}
 	char top[10],top2[10];
	while(fscanf(fp,"%s %s",top,top2)!=EOF){
		calc();
 	}
	fclose(fp);
	printf("%d\n",ans);
}