数独游戏c++

问题 I: 数独游戏
时间限制: 1.000 Sec 内存限制: 128 MB

题目描述
给你一个N×N的表格(3<N<10),在表格中事先已经填入了一部分的数字,现在请你的表格中空余的格子里填入1~N范围内的数字,使得整个表格的每一行和每一列都不存在重复的数字。

数独游戏c++

 

 

测试数据保证有解,若方案不止一个,只要输出第一行数字组成的数值最小的一个方案。

输入
4
3 0 0 2
0 2 0 4
2 0 0 0
0 0 2 1

输出
3 1 4 2
1 2 3 4
2 4 1 3
4 3 2 1

代码:

#include<bits/stdc++.h>
using namespace std;
int n;
int k;
bool flag_hang[11][11];
bool flag_lie[11][11];
int kg_hang[100],kg_lie[100];
int sudujz[11][11];
bool fanganchuxian;
void shuchu(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<sudujz[i][j]<<" ";
        }
        cout<<endl;
    }
}
void dfs(int m){
    if(fanganchuxian) return ;
    if(m==k+1){
        shuchu();
        fanganchuxian=true;
        return ;
    }
    int x=kg_hang[m],y=kg_lie[m];
    for(int d=1;d<=n;d++){
        if(!flag_hang[x][d]&&!flag_lie[y][d]){
            sudujz[x][y]=d;
            flag_hang[x][d]=1;
            flag_lie[y][d]=1;
            dfs(m+1);
            flag_hang[x][d]=0;flag_lie[y][d]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int shuzi;
            cin>>shuzi;
            if(shuzi==0){
                k++;
                kg_hang[k]=i;
                kg_lie[k]=j;
            }
            else{
                flag_hang[i][shuzi]=1;
                flag_lie[j][shuzi]=1;
                sudujz[i][j]=shuzi;
            }
        }
    }
    dfs(1);
  return 0;
}

 

原文链接: https://www.cnblogs.com/bskys/p/17031512.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    数独游戏c++

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/309940

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月16日 上午11:17
下一篇 2023年2月16日 上午11:17

相关推荐