Project Euler Problem 96

問題概要

Problem 96 - PukiWiki
を参照．

解法

全てのマスについて現在置くことが出来るもの，と置かれているものを記録してバックトラック法．

実装(C++)

入力データーの最初に50と書いた行を追加し，gridから始まる行を取り除く必要がある．

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int popcount(int x){
	int res=0;
	while(x){
		x&=x-1;
		res++;
	}
	return res;
}
short MAP[9][9]; //現状
short canput[9][9];//何が置けるか
void clear(){
	for(int x=0;x<9;x++)for(int y=0;y<9;y++)
		MAP[x][y]=0,canput[x][y]=((1<<9)-1)<<1;
}
void put(int x,int y,int c){
	MAP[x][y]=c;
	int val=~(1<<c);
	for(int i=0;i<9;i++){
		canput[x][i]&=val;
		canput[i][y]&=val;
	}
	for(int i=0;i<3;i++)for(int j=0;j<3;j++){
		canput[(x/3)*3+i][(y/3)*3+j]&=val;
	}
}
bool dfs(){
	//まず選べる種類が最も少ないマスを全探索
	int minbits=100,sx,sy;
	int count=0;
	for(int x=0;x<9;x++){
		for(int y=0;y<9;y++){
			if(MAP[x][y]){
				count++;
				continue;
			}
			if(popcount(canput[x][y])<minbits){
				sx=x;sy=y;
				minbits=popcount(canput[x][y]);
			}
		}
	}
	if(count==81){
		for(int y=0;y<9;y++){
			for(int x=0;x<9;x++){
				cout<<MAP[x][y];
			}
			cout<<endl;
		}
		return true;
	}else{
		//sx,syに対しておけるものを全て試す
		short backup[9][9];
		memcpy(backup,canput,sizeof(canput));
		for(int i=1;i<=9;i++){
			if((canput[sx][sy]>>i)&1){
				put(sx,sy,i);
				if(dfs())return true;
				MAP[sx][sy]=0;
				memcpy(canput,backup,sizeof(canput));
			}
		}
	}
	return false;
}
int main() {
	int T;
	cin>>T;

	int eulerans=0;

	for(;T--;){
		clear();
		vector<string> in(9);
		for(int i=0;i<9;i++){
			cin>>in[i];
		}
		for(int y=0;y<9;y++){
			for(int x=0;x<9;x++){
				if(in[y][x]-'0')put(x,y,in[y][x]-'0');
			}
		}
		dfs();
		eulerans+=MAP[0][0]*100+MAP[1][0]*10+MAP[2][0];
	}
	cout<<eulerans<<endl;
	return 0;
}