質問F:数独ゲーム
19740 ワード
フィンランドの数学者インカラが、世界でこれまでで最も難易度の高い数独ゲームを3ヶ月かけて設計し、答えは一つしかないという.カラは思考力が最も速く、頭が最も賢い人だけがこのゲームを解くことができると言ったからだ.これはイギリスのデイリーメールの2012年6月30日の記事です.Acmerのあなたは、プログラムを書いてすべての数独問題を解決できますか?世界でこれまでで最も難易度の高い数独ゲーム:
この問題には複数のテストが含まれています.各グループのテストでは、同じ行に隣接する2つの要素が1つのスペースで区切られた9*9のマトリクスが与えられます.そのうち1-9はその位置の記入済み数、疑問符(?)を表します.あなたが記入する数を表します.出力は各テストのセットについて、同じ行に隣接する2つの数を1つのスペースで区切った解を出力します.2組の解の間に空の行が必要です.複数の答えがあれば、いずれかを出力すればいい!サンプル入力Copy?2 6 7 ? ? 5 1 8 7 3 1 ? 5 8 6 2 4 5 4 ? 2 6 1 3 9 7 6 ? 4 3 7 ? ? 8 1 2 8 7 1 9 6 4 3 5 1 9 ? ? 8 4 7 6 2 3 7 ? 8 ? 9 1 4 6 8 ? 9 4 1 5 2 7 3 ? 1 2 6 3 7 8 5 9 ? 2 6 7 ? ? 5 1 8 7 3 1 ? 5 8 6 2 4 5 4 ? 2 6 1 3 9 7 6 ? 4 3 7 ? ? 8 1 2 8 7 1 9 6 4 3 5 1 9 ? ? 8 4 7 6 2 3 7 ? 8 ? 9 1 4 6 8 ? 9 4 1 5 2 7 3 ? 1 2 6 3 7 8 9サンプル出力Copy 9 2 6 7 4 3 5 1 8 7 3 1 9 5 8 6 2 4 4 8 6 1 3 9 7 6 5 4 4 4 4 7 2 8 8 8 8 8 8 7 7 7 7 7 7 1 8 7 1 9 6 4 4 4 4 4 5 9 3 5 5 8 4 7 6 2 9 4 6 6 6 6 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 4 4 4 4 4 4 6 3 6 3 7 5 9 9
9 2 6 7 4 3 5 1 8 7 3 1 9 5 8 6 2 4 5 4 8 2 6 1 3 9 7 6 5 4 3 7 2 9 8 1 2 8 7 1 9 6 4 3 5 1 9 3 5 8 4 7 6 2 3 7 5 8 2 9 1 4 6 8 6 9 4 1 5 2 7 3 4 1 2 6 3 7 8 5 9
この問題には複数のテストが含まれています.各グループのテストでは、同じ行に隣接する2つの要素が1つのスペースで区切られた9*9のマトリクスが与えられます.そのうち1-9はその位置の記入済み数、疑問符(?)を表します.あなたが記入する数を表します.出力は各テストのセットについて、同じ行に隣接する2つの数を1つのスペースで区切った解を出力します.2組の解の間に空の行が必要です.複数の答えがあれば、いずれかを出力すればいい!サンプル入力Copy?2 6 7 ? ? 5 1 8 7 3 1 ? 5 8 6 2 4 5 4 ? 2 6 1 3 9 7 6 ? 4 3 7 ? ? 8 1 2 8 7 1 9 6 4 3 5 1 9 ? ? 8 4 7 6 2 3 7 ? 8 ? 9 1 4 6 8 ? 9 4 1 5 2 7 3 ? 1 2 6 3 7 8 5 9 ? 2 6 7 ? ? 5 1 8 7 3 1 ? 5 8 6 2 4 5 4 ? 2 6 1 3 9 7 6 ? 4 3 7 ? ? 8 1 2 8 7 1 9 6 4 3 5 1 9 ? ? 8 4 7 6 2 3 7 ? 8 ? 9 1 4 6 8 ? 9 4 1 5 2 7 3 ? 1 2 6 3 7 8 9サンプル出力Copy 9 2 6 7 4 3 5 1 8 7 3 1 9 5 8 6 2 4 4 8 6 1 3 9 7 6 5 4 4 4 4 7 2 8 8 8 8 8 8 7 7 7 7 7 7 1 8 7 1 9 6 4 4 4 4 4 5 9 3 5 5 8 4 7 6 2 9 4 6 6 6 6 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 4 4 4 4 4 4 6 3 6 3 7 5 9 9
9 2 6 7 4 3 5 1 8 7 3 1 9 5 8 6 2 4 5 4 8 2 6 1 3 9 7 6 5 4 3 7 2 9 8 1 2 8 7 1 9 6 4 3 5 1 9 3 5 8 4 7 6 2 3 7 5 8 2 9 1 4 6 8 6 9 4 1 5 2 7 3 4 1 2 6 3 7 8 5 9
#include
using namespace std;
int mp[10][10];
char b;
int sum,flag1;
int vis[10][10];
struct s{// ?
int x,y;
}a[100];
bool check(int x,int step)
{
for(int i=0;i<9;i++)
{
if(mp[a[step].x][i]==x||mp[i][a[step].y]==x)//
return false;
}
//
int xx=a[step].x/3*3;
int yy=a[step].y/3*3;
for(int i=xx;i<xx+3;i++)
{
for(int j=yy;j<yy+3;j++)
{
if(mp[i][j]==x)
return false;
}
}
return true;
}
void dfs(int step)
{
if(step==sum)
{
flag1=1;// ! wa ,
// ,
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(j==0)
{
printf("%d",mp[i][j]);
}
else
printf(" %d",mp[i][j]);
}
printf("
");
}
}
for(int i=1;i<=9;i++)
{
if(check(i,step)&&flag1==0)
{
mp[a[step].x][a[step].y]=i;
dfs(step+1);
mp[a[step].x][a[step].y]=0;//
}
}
return ;
}
int main()
{
int flag=0;
while(cin>>b)
{
flag1=0;
sum=0;
if(b=='?')
{
a[sum].x=0;
a[sum].y=0;
sum++;
mp[0][0]=0;
}
else
{
mp[0][0]=b-'0';
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(i==0&&j==0)
{
continue;
}
cin>>b;
if(b=='?')
{
a[sum].x=i;
a[sum].y=j;
sum++;
mp[i][j]=0;
}
else
{
mp[i][j]=b-'0';
}
}
}
if(flag==0)
{
flag=1;
}
else
printf("
");
dfs(0);
}
return 0;
}
//?????????
//?????????
//?????????
//?????????
//?????????
//?????????
//?????????
//?????????
//?????????