首页 > 试题广场 >

Sudoku

[编程题]Sudoku
  • 热度指数：97391 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据 9 \times 9 盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个 3 \times 3 粗线宫内的数字均含 1 \sim 9 这九个数字，且不重复。

\hspace{15pt}保证输入的数独是合法的，且存在唯一解。

输入描述:
\hspace{15pt}输入一个 9 \times 9 的不完整数独矩阵，矩阵中的数字为 0 \sim 9 。其中，0 表示该位置的数字尚未填入，1 \sim 9 表示该位置的数字已经填入。


输出描述:
\hspace{15pt}输出一个 9 \times 9 的完整数独矩阵。
示例1

输入

0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1

输出

5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

说明

\hspace{15pt}在这个样例中，输入的数独如下图一所示，输出的是数独的唯一解，如下图二所示。


算法知识视频讲解
添加回答
C
D1002头像 D1002
下面的输入好像不是唯一解的：
0 0 8 7 1 9 2 4 5
9 0 5 2 3 4 0 8 6
0 7 4 8 0 6 1 0 3
7 0 3 0 9 2 0 0 0
5 0 0 0 0 0 0 0 0
8 6 1 4 0 3 5 2 9
4 0 0 0 2 0 0 0 8
0 0 0 0 0 0 0 7 0
1 0 7 0 6 8 0 5 0

可能答案：
6 3 8 7 1 9 2 4 5 
9 1 5 2 3 4 7 8 6 
2 7 4 8 5 6 1 9 3 
7 4 3 5 9 2 8 6 1 
5 9 2 6 8 1 4 3 7 
8 6 1 4 7 3 5 2 9 
4 5 6 0 2 7 0 1 8 
3 8 9 1 4 5 6 7 2 
1 2 7 0 6 8 0 5 4 

index 6 3 possible num: 3,9,
index 6 6 possible num: 3,9,
index 8 3 possible num: 3,9,
index 8 6 possible num: 3,9

发表于 2025-05-22 10:14:39 回复(0)
C
野萌太君头像 野萌太君
并不需要用递归回溯，又占堆栈复杂度又高，不可能用到工程中的。 两个for循环搞定，无语的是测试例解不唯一 
#include <stdio.h>
#define N 50
#define MASK 0b111111111
int matrix[9][9],row_mask[9], col_mask[9], box_mask[9], z_row[N], z_col[N], z_box[N], n;
int count_zero(int zero_idx, int * x){
    int mask =row_mask[z_row[zero_idx]]|col_mask[z_col[zero_idx]]|box_mask[z_box[zero_idx]],result=0;
    mask ^=MASK, *x=0;
    while (mask) {
        result+= mask&1,mask>>=1,(*x)++;
    }
    return  result;
}
int main() {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            int x;
            scanf("%d", &x), matrix[row][col]=x;
            if (x) {
                row_mask[row] |= 1 << (x-1),col_mask[col]|= 1 << (x-1),box_mask[row / 3 * 3 + col / 3]|= 1 << (x-1);
            } else {
                z_row[n] = row, z_col[n] = col, z_box[n] = row / 3 * 3 + col / 3, n++;
            }
        }
    }
    int solu=1,last=0; // test case do have multiple solution, remove this for only solution
    for(int i =0;i<n;i++){
        int current =0;
        for (int j=0;j<n;j++){
            if( z_row[j]!=-1 && count_zero(j,&matrix[z_row[j]][z_col[j]])==solu){
                int mask =1<<(matrix[z_row[j]][z_col[j]]-1);
                row_mask[z_row[j]]|=mask, col_mask[z_col[j]]|=mask, box_mask[z_box[j]]|=mask;
                z_row[j]=-1;
                if (solu>1)solu=1; // test case do have multiple solution, remove this for only solution              
            }else current++; // test case do have multiple solution, remove this for only solution
        }
        if(current==last)solu++; // test case do have multiple solution, remove this for only solution
        last=current;// test case do have multiple solution, remove this for only solution
    }
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            printf("%d ", matrix[row][col]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2025-04-20 15:30:57 回复(0)
C
牛客70985078号头像 牛客70985078号
#include <stdio.h>
#include <stdbool.h>
bool iflegal(int map[9][9],int i,int j,int k);
bool op(int map[9][9]);
int map[9][9]={0};
int main() {
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            scanf("%d",&map[i][j]);
    op(map);
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            printf("%d ",map[i][j]);
        printf("\n");
    }
       
}
bool op(int map[9][9])
{
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            if(map[i][j]==0)
            {
                for(int k=1;k<=9;k++)
                {
                    if(iflegal(map,i,j,k))
                    {
                        map[i][j]=k;
                        bool a=op(map);
                        if(a==true)
                            return true;
                        else
                            map[i][j]=0;
                    }
                }
                return false;
            }
               
        }
    return true;
}
bool iflegal(int map[9][9],int i,int j,int k)
{
    int centerx=i/3*3+1,centery=j/3*3+1;
    for(int a=0;a<9;a++)
    {
        if(a==j)
            continue;
        if(map[i][a]==k)
            return false;
    }
    for(int b=0;b<9;b++)
    {
        if(b==i)
            continue;
        if(map[b][j]==k)
            return false;
    }
    for(int a=centerx-1;a<=centerx+1;a++)
        for(int b=centery-1;b<=centery+1;b++)
        {
            if(a==i&&b==j)
                continue;
            if(map[a][b]==k)
                return false;
        }
        return true;
}

   
发表于 2024-04-16 20:36:43 回复(0)
C
牛客219878930号头像 牛客219878930号
为什么我的代码在自己电脑上就能输出正确答案，在这就输出错误答案？有没有大佬帮忙看一下哪里有问题？ 
#include <stdio.h>
#include <stdlib.h>
char sd[9][9] = { 0 };
char** pdfk(int x, int y)
{
	char* res[3];
	res[0]=(char**)malloc(sizeof(char*));
	res[1] = (char**)malloc(sizeof(char*));
	res[2] = (char**)malloc(sizeof(char*));
	if (x < 3)
	{
		if (y < 3)
		{
			res[0] = &sd[0][0];
			res[1] = &sd[1][0];
			res[2] = &sd[2][0];
		}
	    else if (y < 6)
	      {
			res[0] = &sd[3][0];
			res[1] = &sd[4][0];
			res[2] = &sd[5][0];
	       }
	     else
	     {
			res[0] = &sd[6][0];
			res[1] = &sd[7][0];
			res[2] = &sd[8][0];
	      }
	}
	else if (x < 6)
	{
		if (y < 3)
		{
			res[0] = &sd[0][3];
			res[1] = &sd[1][3];
			res[2] = &sd[2][3];
		}
		else if (y < 6)
		{
			res[0] = &sd[3][3];
			res[1] = &sd[4][3];
			res[2] = &sd[5][3];
		}
		else
		{
			res[0] = &sd[6][3];
			res[1] = &sd[7][3];
			res[2] = &sd[8][3];
		}
	}
	else
	{
		if (y < 3)
		{
			res[0] = &sd[0][6];
			res[1] = &sd[1][6];
			res[2] = &sd[2][6];
		}
		else if (y < 6)
		{
			res[0] = &sd[3][6];
			res[1] = &sd[4][6];
			res[2] = &sd[5][6];
		}
		else
		{
			res[0] = &sd[6][6];
			res[1] = &sd[7][6];
			res[2] = &sd[8][6];
		}
	}
	return res;
}
char check(int x, int y, int num)
{
	for (int i = 0; i < 9; i++)
	{
		if (sd[y][i] == num && (i != x))
			return 0;
		if (sd[i][x] == num && (i != y))
			return 0;
	}
	char** fangkuai = pdfk(x, y);
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
		if (fangkuai[i][j]==num  && (i != y%3  || j!= x%3))
			return 0;
		}
	}
	return 1;
}
char place[81][3] = { 0 };
int placecnt = 0;
char result[81][3] = { 0 };
char tianchong(int ceng)
{
	if (ceng == placecnt)
	{
	//找到结果
		for (int i = 0; i < placecnt; i++)
		{
			result[i][0] = place[i][0];
			result[i][1] = place[i][1];
			result[i][2] = place[i][2];
		}
		return 1;
	}
	for (int i = 1; i < 10; i++)
	{
		if (check(place[ceng][0], place[ceng][1], i))
		{
			sd[place[ceng][1]][place[ceng][0]] = i;
			if (tianchong(ceng + 1))
				return 1;
		}
	}
	sd[place[ceng][1]][place[ceng][0]] = 0;
	return 0 ;
}
int main()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			scanf("%d", &sd[i][j]);
			if (sd[i][j] == 0)
			{
				place[placecnt][0] = j;
				place[placecnt][1] = i;
				placecnt++;
			}
		}
	}
	tianchong(0);
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			printf("%d ", sd[i][j]);
		}
		printf("\n");
	}

}
发表于 2022-07-21 22:31:30 回复(0)
C
牛客847677727号头像 牛客847677727号 
#include<stdio.h>

int mark[9][9]={0},input[9][9];
int flag=0;


int isvalue(int value,int i,int j)
{
    int m,f,l,x,y;
    for(m=0;m<9;m++)
    {
        if (input[i][m]==value)
            return 0;
    }
    for (m=0;m<9;m++)
    {
        if (input[m][j]==value)
            return 0;
    }
    x=3*(i/3);
    y=3*(j/3);
    for (f=0;f<3;f++)
    {
         for (l=0;l<3;l++)
         {
              if (input[x+f][y+l]==value)
              {
                   return 0;
               }
         }
    }
    return 1;
}


void dfs(int i,int j)
{
    if (i==9)
    {
        flag=1;
        return;
    }
    if (input[i][j]==0)
    {
        for (int n=1;n<=9;n++)
        {
            if (isvalue(n,i,j))
            {
                input[i][j]=n;
                dfs(j==8?i+1:i,j==8?0:j+1);
                if (flag)
                    return;
                input[i][j]=0;
            }
        }
    }
    else
    {
        dfs(j==8?i+1:i,j==8?0:j+1);
    }
}



int main()
{
    int i,j,n,m;
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            scanf("%d",&input[i][j]);
        }
    }
    dfs(0,0);
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
            printf("%d ",input[i][j]);
        printf("\n");
    }
    
    
 }

发表于 2021-10-18 10:13:15 回复(0)
提交观点

问题信息

搜索 思维 基础数学
难度：
7条回答 29692浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Sudoku

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号