我要招人

去企业版

首页 > 试题广场 >

Sudoku

[编程题]Sudoku

热度指数：92380 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

例如：

输入

输出

数据范围：输入一个 9*9 的矩阵

输入描述:

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述:

完整的9X9盘面数组

示例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

算法知识视频讲解

牛客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)

牛客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)

牛客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)