Recursividade
Canal do Youtube do "Professor Carlos Menezes": lá há três aulas gravadas sobre recursividade.
Recursividade é quando uma função chama a ela mesma.
É uma técnica para resolver problemas que envolve o uso de soluções dos mesmos problemas, só que em versões menores; exemplificando:
Como faço para calcular o fatorial do número 4? Ora, é 1*2*3*4 ou 4*3*2*1
E o fatorial do número 3? É 1*2*3.
E o fatorial do número 2? É 1*2.
E o fatorial do número 1? É 1.
E o fatorial do número 0? É 1.
Reparem que o fatorial do número 3 é parte do cálculo do fatorial do número 4? Ou seja, fatorial de 4 é igual a 4 vezes o fatorial do 3, ou:
4! = 4 * 3!
Genericamente definimos (recursivamente) o fatorial de N como:
N! = N * (N-1)!
Percebem como uso a solução do próprio fatorial em versão menor (fatorial de N-1) para o cálculo do problema original (fatorial de N)?
Mas este raciocínio tem de parar em algum momento, pois senão seria uma repetição infinita: para calcular o fatorial do 2 precisaria do fatorial do 1, para calcular o fatorial do 1 precisaria do fatorial do 0, para calcular o fatorial do 0 precisaria do fatorial do -1, e do fatorial do -2, -3, -4, ... Este ponto de parada é chamado de base da recursão; consiste na versão mais simples possível do problema, cuja solução é óbvia.
Para o problema do fatorial, a base é o fatorial de 0, que é definido como valendo 1:
0! = 1
Ao programarmos um algoritmo recursivo precisamos tomar um cuidado: testarmos a base da recursão antes de fazermos a chamada recursiva, para evitarmos a criação de um laço infinito. Vejamos como isso se aplica na implementação da função fatorial:
int fatorial (int N)
{
if(N==0) return 1; //esta é a base da recursao
else return N * fatorial (N-1); //a chamada recursiva
}
Executando passo-a-passo o algoritmo do fatorial (recursivo):
fatorial(4)
|----4*fatorial(3)-----> fatorial(3)
|----3*fatorial(2)-----> fatorial(2)
|----2*fatorial(1)-----> fatorial(1)
|----1*fatorial(0)-----> fatorial(0)
|
v
fatorial(1) = 1*1 <---- 1
|
v
fatorial(2) = 2*1 <---- 1
|
v
fatorial(3) = 3*2 <---- 2
|
v
fatorial(4) = 4*6 <---- 6
|
v
24
Uma implementação cheia de printfs para ajudar o entendimento:
#include <stdio.h>
int fatorial (int N)
{ if(N==0)
{ printf("Cheguei finalmente na base... 0! = 1\n");
return 1;
}
else
{ printf("Para calcular o fatorial de %d preciso calcular o de %d\n",
N, N-1);
int aux = fatorial (N-1);
printf("Calculei o fatorial de %d que dá %d\n", N-1, aux);
return N * aux;
}
}
int main()
{ int x;
printf("Entre com um número:");
scanf("%d", &x);
printf("O fatorial de %d é %d\n", x, fatorial(x));
return 0;
}
Exercícios
1) Faça o teste de mesa para os algoritmos abaixo. Você pode usar o modo de depuração (debug) do ambiente de desenvolvimento C para lhe ajudar:
a)
int alg1 (int n)
{ if (n == 0) return 2;
else return 2 * alg1 (n - 1) + 3;
}
Suponha que alg1 é invocado p/ n = 4.
RESOLUÇÃO:
n alg1(n)
4 2 * alg1(3) + 3 (else)
3 2 * alg1(2) + 3 (else)
2 2 * alg1(1) + 3 (else)
1 2 * alg1(0) + 3 (else)
0 2 ( Base de retorno de alg1(n) ) (if)
1 2 * alg1(0) + 3 => 2 * 2 + 3 = 7
2 2 * alg1(1) + 3 => 2 * 7 + 3 = 17
3 2 * alg1(2) + 3 => 2 * 17 + 3 = 37
4 2 * alg1(3) + 3 => 2 * 37 + 3 = 77
b)
int alg2(int n)
{
if (n == 0) return 1;
else return 3 * alg2 (n / 2) + 1;
}
Suponha que alg2 é invocado com n = 10.
n alg2(n)
10 =3*alg2(5) + 1 (else)
5 =3*alg2(2) + 1 (else)
2 =3*alg2(1) + 1 (else)
1 =3*alg2(0) + 1 (else)
0 =1 (if)
1 =3*1+1 = 4
2 =3*4+1 = 13
5 =3*13+1 = 40
10 =3*40+1 = 121
121 (resposta final)
//Código para ajudar no entendimento:
#include <stdio.h>
int alg2(int n)
{
if (n == 0)
{ printf("Cheguei na base. alg2(0) = 1\n");
return 1;
}
else
{ printf("Para calcular o valor de alg2(%d) precisarei do valor de alg2(%d)\n",
n, n/2);
int aux = alg2(n/2);
printf("Estou calculando o valor de alg2(%d) = %d\n",
n/2, aux);
printf("Logo, o valor de alg2(%d) = %d\n",
n, 3 * aux + 1);
return 3 * aux + 1;
}
}
int main()
{
printf("O valor de alg2(10) é %d\n", alg2(10));
return 0;
}
c)
int alg3(int n)
{
if (n < 0) return 2;
else return 2 * alg3(n - 2) + 1;
}
Suponha que alg3 é invocado com n = 7.
47 (resposta final)
d)
int alg4(int n)
{
if (n <= 0) return 2;
else return alg4(n - 1) * alg4(n - 2);
}
Suponha que alg4 foi invocado com n = 4.
n alg4(n)
4 =alg4(3) * alg4(2) = 32*8 = 256 (else)
3 =alg4(2) * alg4(1) = 8*4 = 32 (else)
2 =alg4(1) * alg4(0) = 4*2 = 8 (else)
1 =alg4(0) * alg4(-1) = 2*2 = 4 (else)
0 =2 (if)
-1 =2 (if)
256 (resposta final)
e)
int alg5(int n, int k)
{
if(n == 0) return 0;
else return alg5(n - 1, k) + k;
}
Invoquemos alg5 com n=4 e k=5.
Resposta = 20
n k alg5(n, k)
4 5 =alg5(3, 5) + 5 (else)
3 5 =alg5(2, 5) + 5 (else)
2 5 =alg5(1, 5) + 5 (else)
1 5 =alg5(0, 5) + 5 (else)
0 5 =0 (if)
1 5 =0+5 = 5
2 5 =5+5 = 10
3 5 =10+5 = 15
4 5 =15+5 = 20
f)
int alg6(int n, int k)
{
if(n < k) return 0;
else return alg6 (n-k, k) + 1;
}
Suponha que alg6 é invocado p/ n = 32 e k = 5. O que faz esse algoritmo?
6 (resposta final)
g)
int alg7(int n, int k)
{
if(n < k) return 0;
else return alg7(n / k, k) + 1;
}
Suponha que alg7 é invocado para n = 32 e k = 2.
Resposta = 5
h)
int alg8(int n, int k)
{
if(n <= 1) return 0;
else return alg8(n - 1, k + 1) + n*k;
}
Suponha que alg8 é invocado p/ n = 4 e k = 1.
Resposta = 16
Dicas para os próximos exercícios:
Para resolvermos um algoritmo por recursividade, tente responder às 3 perguntas abaixo. Cada uma fornecerá uma parte da solução:
1) Qual é a instância mais simples do problema?
-> Isso fornecerá a base da recursão!!
2) O que é só um pouco mais simples que resolver o problema original?
-> Usaremos para escrever o caso geral da recursão
3) Se lhe fornecêssemos a solução do problema mais simples (o da pergunta 2), você conseguiria resolver o problema original? Como?
-> Isso é suficiente para escrever o caso geral da recursividade
Exemplo: quero calcular o fatorial de N
1) Qual é a instância mais simples do problema?
-> Fatorial de 0, que é 1.
2) O que é só um pouco mais simples que resolver o problema original?
-> Resolver o fatorial de N-1.
3) Se lhe fornecêssemos a solução do problema um pouco mais simples (o da pergunta 2), você conseguiria resolver o problema original? Como?
-> O fatorial de N é igual a N * Fatorial de (N-1).
Assim, o código fica:
int fatorial (int N)
{
if(N==0) return 1;
else return N * fatorial(N-1);
}
Outro exemplo:
--------------------
Calcular a soma dos inteiros positivos até N, ou seja, 0 + 1 + 2 + 3 + 4 + ... + (N-1) + N, usando uma função recursiva.
1) Qual é a instância mais simples do problema?
-> A soma dos inteiros até 0, que resulta 0.
2) O que é só um pouco mais simples que resolver o problema original?
-> Achar a soma até (N-1): 0 + 1 + 2 + 3 + 4 + ... + (N-1)
3) Se lhe fornecêssemos a solução do problema mais simples (o da pergunta 2), você conseguiria resolver o problema original? Como?
-> Sabendo a soma até (N-1), basta somar N para achar a soma até N.
Assim, o código fica:
int soma (int N)
{
if(N==0) return 0;
else return N + soma(N-1);
}
Outro exemplo:
--------------------
Calcular a expressão: 0/1 + 1/2 + 2/3 + 3/4 + .... + (N-1)/N + N/(N+1)
1) Qual é a instância mais simples do problema?
-> A soma das frações até que N seja 0, o que resulta em 0.0.
2) O que é só um pouco mais simples que resolver o problema original?
-> Achar a expressão até (N-1): 0/1 + 1/2 + 2/3 + 3/4 + .... + (N-1)/(N)
3) Se lhe fornecêssemos a solução do problema mais simples (o da pergunta 2), você conseguiria resolver o problema original? Como?
-> Sabendo a soma até (N-1), basta somar N/(N+1) para achar a soma até N.
Assim, o código fica:
float expressao(int N)
{
if(N==0) return 0.0;
else return (float)N/(N+1) + expressao(N-1);
}
Voltando aos exercícios:
2) Crie uma função recursiva que calcule potenciações através de multiplicações sucessivas:
x^y = x * x * x * x ......* x --> y vezes
Matematicamente, x^0 = 1 e x^y = x * x^(y-1)
a) Base: expoente == 0 -> resultado = 1
b) x^(y-1) é um pouco mais simples que x^y
c) x^y = x * x^(y-1)
Simulando potenciacao(2, 5):
potenciacao(2, 4) * 2
(potenciacao(2, 3) * 2) * 2
((potenciacao(2, 2) * 2) * 2) * 2
(((potenciacao(2, 1) * 2) * 2) * 2) * 2
((((potenciacao(2, 0) * 2) * 2) * 2) * 2) * 2
(((((1)* 2) * 2) * 2) * 2) * 2
((((2) * 2) * 2) * 2) * 2
(((4) * 2) * 2) * 2
((8) * 2) * 2
(16) * 2
32
Link da solução:
https://onlinegdb.com/SJ_TslVdd
#include <stdio.h>
int potenciacao(int base, int expoente)
{ if(expoente == 0) return 1;
else return potenciacao(base, expoente-1) * base;
}
int main()
{
printf("2 elevado a 5 resulta %d\n", potenciacao(2,5));
return 0;
}
3) Crie uma função recursiva que calcule multiplicações através de somas sucessivas:
x*y = x + x + x + x ...... + x -> y vezes
Matematicamente, x*0 = 0 e x*y = x + x*(y-1)
a) Base: y == 0 -> resultado = 0
b) x*(y-1) é um pouco mais simples que x*y
c) x*y = x + x*(y-1)
Link da solução:
https://onlinegdb.com/rkxRoXWNu_
#include <stdio.h>
int multiplicacao(int x, int y)
{ if(x == 0) return 0;
else return multiplicacao(x-1, y) + y;
}
int main()
{
printf("7 vezes 5 resulta %d\n", multiplicacao(7,5));
return 0;
}
4) Calcule recursivamente o valor da expressão: expressao(n) = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ...+ 1/(n-1) + 1/n
a) n=1 -> expressao(1) = 1/1
n=2 -> expressao(2) = 1/1 + 1/2
n=3 -> expressao(3) = 1/1 + 1/2 + 1/3
n=4 -> expressao(4) = 1/1 + 1/2 + 1/3 + 1/4
Situação (instância) mais simples: n=1 -> expressao(1) = 1.0
b) expressao(n) = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ...+ 1/(n-1) + 1/n
A um pouco mais simples: expressao(n-1) = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ...+ 1/(n-1)
c) expressao(n) = expressao(n-1) + 1/n
Link da solução:
https://onlinegdb.com/By3CmMEdu
#include <stdio.h>
float expressao(int n)
{ if(n == 1) return 1.0;
else return expressao(n-1) + 1.0/n;
}
int main()
{
printf("expressao(100) vale %f\n", expressao(100));
return 0;
}
5) Crie uma função recursiva que calcule divisões através de subtrações sucessivas:
x/y = número de vezes que consigo subtrair y de x (x - y - y - y - y ...... >= 0)
Matematicamente, se x < y --> resposta = 0
caso contrário, x / y = ((x-y)/y) + 1
a) Mais simples de todos: x < y -------> 0
b) Um pouco mais simples: (x-y)/y
c) x / y=((x-y)/y)+1
#include <stdio.h>
int divisao(int x, int y)
{ if(x < y) return 0;
else return divisao(x-y, y) + 1;
}
int main()
{
printf("25 dividido por 10 vale %d\n", divisao(25, 10));
return 0;
}
6) Ache recursivamente a soma dos números ímpares positivos até n:
1 + 3 + 5 + 7 + 9 + 11 + .... n (n ímpar)
ou
1 + 3 + 5 + 7 + 9 + 11 + .... n-1 (n par)
7) Crie uma função recursiva que calcule logaritmos através de divisões sucessivas:
logaritmo x na base y = número de vezes que consigo dividir x por y
Matematicamente, se x < y --> resposta = 0
caso contrário, log x na base y = (log de (x/y) na base y) + 1
Resolução:
Qual é o logaritmo de 1000 na base 10? De outra maneira, qual é o expoente que eu coloco na base 10 para virar 1000?
Resposta = 3
Qual é o logaritmo de 32 na base 2? De outra maneira, qual é o expoente que eu coloco na base 2 para virar 32?
Resposta = 5
#include <stdio.h>
int logaritmo(int n, int base)
{ if(n < base) return 0;
else return logaritmo(n/base, base) + 1;
}
int main()
{
printf("logaritmo de 1024 na base 2 vale %d\n", logaritmo(1024, 2));
return 0;
}
8) Crie uma função recursiva que converta um número binário em decimal.
#include <stdio.h>
int bindec(int n)
{ if(n==0 || n==1) return n;
else return bindec(n/10) * 2 + n%10;
}
int main()
{ int x;
printf("Entre com um número binário: ");
scanf("%d", &x);
printf("O correspondente de %d em decimal é %d", x, bindec(x));
return 0;
}
9) Crie uma função recursiva que converta um número decimal em binário.
#include <stdio.h>
void decbin(int n)
{ if(n==0 || n==1) printf("%d", n);
else
{ decbin(n/2);
printf("%d", n%2);
}
}
int main()
{ int x;
printf("Entre com um número inteiro: ");
scanf("%d", &x);
printf("O correspondente de %d em binário é ", x);
decbin(x);
return 0;
}
10) Crie uma função recursiva que procure um número dentro de um vetor, a partir de um dado índice. Se achar o mesmo, o método retorna o índice onde ele se encontra, senão, retorna -1 (busca linear recursiva).
-> Só para entendermos melhor o problema, a versão iterativa (não-recursiva) seria assim:
int busca(int vet[ ], int N, int indiceInicio, int procurado)
{ int i;
for(i=indiceInicio; i < N; i++)
{ if(procurado == vet[i])
{ return i;
}
}
return -1;
}
Agora vamos pensar na versão recursiva....
int buscaRecursiva(int vet[ ], int N, int indiceInicio, int procurado)
{ if(indiceInicio >= N) return -1; //não existe no vetor
if(vet[ indiceInicio ] == procurado) return indiceInicio; //achei!!!
return buscaRecursiva(vet, N, indiceInicio+1, procurado);
}
Com o main....
#include <stdio.h>
int busca(int vet[ ], int N, int indiceInicio, int procurado)
{ int i;
for(i=indiceInicio; i < N; i++)
{ if(procurado == vet[i])
{ return i;
}
}
return -1;
}
int buscaRecursiva(int vet[ ], int N, int indiceInicio, int procurado)
{ if(indiceInicio >= N) return -1; //não existe no vetor
if(vet[ indiceInicio ] == procurado) return indiceInicio; //achei!!!
return buscaRecursiva(vet, N, indiceInicio+1, procurado);
}
int main()
{ int vet[] = {4, 8, 1, 7, 3, 12, 34, 97, -1, 2};
printf("Procurando o elemento 12 (iterativa) => %d\n",
busca(vet, 10, 0, 12));
printf("Procurando o elemento 72 (iterativa) => %d\n",
busca(vet, 10, 0, 72));
printf("Procurando o elemento 12 (recursiva) => %d\n",
buscaRecursiva(vet, 10, 0, 12));
printf("Procurando o elemento 72 (recursiva) => %d\n",
buscaRecursiva(vet, 10, 0, 72));
return 0;
}
11) Crie um método recursivo que retorne o maior elemento de um vetor.
#include <stdio.h>
int maior(int N, int vet[])
{ int m = vet[0];
int i;
for(i=1; i<N; i++)
{ if(vet[i] > m)
m = vet[i];
}
return m;
}
int maiorRec(int N, int vet[])
{ if(N==1) return vet[0];
else
{ int m = maiorRec(N-1, vet);
if(m > vet[N-1]) return m;
else return vet[N-1];
}
}
int main()
{ int vet[]={5, 2, 6, 1, 8, 3, 9, 4, -1, 12, 7};
printf("O maior elemento é %d\n", maior(11, vet));
printf("O maior (rec.) elemento é %d\n", maiorRec(11, vet));
return 0;
}
12) Crie uma função recursiva para calcular o máximo divisor comum (MDC) entre dois números inteiros, usando o algoritmo de Euclides.
#include <stdio.h>
int mdc(int x, int y)
{ if(x%y == 0) return y;
else return mdc(y, x%y);
}
int main()
{
printf("mdc(105, 70) => %d\n", mdc(105, 70));
return 0;
}
13) Torre de Hanói
"Édouard Lucas teve inspiração de uma lenda para construir o jogo das Torres de Hanói em 1883[1]. Já seu nome foi inspirado na torre símbolo da cidade de Hanói, no Vietnã[2]. Existem várias lendas a respeito da origem do jogo, a mais conhecida diz respeito a um templo Hindu, situado no centro do universo. Diz-se que Fuças supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre uma plataforma. Fuças ordenara-lhes que movessem todos os discos de uma estaca para outra segundo as suas instruções. As regras eram simples: apenas um disco poderia ser movido por vez e nunca um disco maior deveria ficar por cima de um disco menor. Segundo a lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o templo desmoronar-se-ia e o mundo desapareceria. Dessa forma criaria-se um novo mundo, o mundo de Hanói." (Wikipedia)
É possível fazer uma solução recursiva para o problema de um jeito bem simples:
Base da Recursão: resolver o quebra-cabeças com um disco é trivial, bastando fazer um movimento e pronto!
Caso Geral: se sei resolver o quebra-cabeças para N-1 discos fica fácil resolvê-lo para N discos. Transporto N-1 discos para o pino auxiliar (eu disse que sabia resolver para N-1 discos!), transporto o disco maior que sobrou para o pino destino e, finalmente, transporto os N-1 discos do pino auxiliar para o pino destino (novamente eu disse que sabia resolver para N-1 discos!).
Veja como fica a implementação:
#include<stdio.h>
void hanoi (int n, char origem, char destino, char auxiliar)
{
if(n==1) printf("Mova o disco do pino %c para o pino %c\n", origem, destino);
else{
hanoi(n-1, origem, auxiliar, destino); //transporto N-1 discos da origem para o auxiliar
printf("Mova o disco do pino %c para o pino %c\n", origem, destino);
hanoi(n-1, auxiliar, destino, origem); //transporto N-1 discos do auxiliar para o destino
}
}
int main ()
{
printf("Resolvendo a Torre de Hanoi para 3 discos:\n");
hanoi(3, 'A', 'C', 'B');
printf("Resolvendo a Torre de Hanoi para 4 discos:\n");
hanoi(4, 'A', 'C', 'B');
return 0;
}
EXTRAS:
------------
1) Calcule uma aproximação para o PI (3.14159..) usando a série de Leibniz (veja: https://pt.wikipedia.org/wiki/F%C3%B3rmula_de_Leibniz_para_%CF%80 ).
PI = 4.0/1 - 4.0/3 + 4.0/5 - 4.0/7 + 4.0/9 - 4.0/11 + 4.0/13 ....
3,14159265358979323846
#include <stdio.h>
#include <math.h>
float pi(int N)
{ int i;
float soma = 0;
for(i=0; i<=N; i++)
{ soma = soma + (4*pow(-1,i))/(2*i+1);
}
return soma;
}
float pirec(int N)
{ if(N==0) return 4.0;
else return pirec(N-1) + (4*pow(-1,N))/(2*N+1);
}
int main()
{ printf("PI = %f\n", pi(100000));
printf("PI = %f\n", pirec(100000));
return 0;
}
2) Dizemos que um número natural n com pelo menos dois algarismos é palíndrome se o 1º algarismo de n é igual ao seu último algarismo, o 2º algarismo de n é igual ao penúltimo algarismo, e assim sucessivamente.
Exemplos:
567765 e 32423 são palíndromes.
567675 não e palíndrome.
Dado um inteiro n, n > 10, verificar se é palíndrome.
1) Pergunta: qual é a instância mais simples desse problema?
Resposta: qualquer número n com apenas 1 dígito é palíndrome; com dois dígitos iguais também.
2) 567765 -> 6776 -> 77
32423 -> 242 -> 4
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool palindrome(char n[ ], int inicio, int fim)
{ if(inicio == fim) return true; //um dígito
else if(fim - inicio == 1) //dois dígitos
{ if(n[inicio] == n[fim]) return true; //dois dígitos iguais
else return false; //dois dígitos diferentes
}
else return (n[inicio] == n[fim] && palindrome(n, inicio+1, fim-1));
}
int main()
{ char numero[30];
printf("Entre com um número: ");
scanf("%s", numero);
if(palindrome(numero, 0, strlen(numero)-1)) printf("É palíndrome");
else printf("Não é palíndrome");
return 0;
}
3) "Sudoku, por vezes escrito Su Doku (数独 'sūdoku'?) é um jogo baseado na colocação lógica de números. O objetivo do jogo é a colocação de números de 1 a 9 em cada uma das células vazias numa grade de 9x9, constituída por 3x3 subgrades chamadas regiões. O quebra-cabeça contém algumas pistas iniciais, que são números inseridos em algumas células, de maneira a permitir uma indução ou dedução dos números em células que estejam vazias. Cada coluna, linha e região só pode ter um número de cada um dos 1 a 9. Resolver o problema requer apenas raciocínio lógico e algum tempo. Os problemas são normalmente classificados em relação à sua realização. O aspecto do sudoku lembra outros quebra-cabeças de jornal. " (https://pt.wikipedia.org/wiki/Sudoku)
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
Faça um programa que resolva um sudoku.
https://onlinegdb.com/BJJfFFQ8u
#include <stdio.h>
#include <stdbool.h>
int grid[9][9] = {{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}};
void imprime()
{ int x, y;
for(x=0; x<9; x++)
{ for(y=0; y<9; y++)
printf("%3d", grid[x][y]);
printf("\n");
}
}
bool possivel(int x, int y, int n)
{ int i, j, x0, y0;
for(i=0; i<9; i++)
if(grid[i][y] == n)
return false;
for(j=0; j<9; j++)
if(grid[x][j] == n)
return false;
x0 = (x/3)*3;
y0 = (y/3)*3;
for(i=0; i<3; i++)
for(j=0; j<3; j++)
if(grid[x0+i][y0+j] == n)
return false;
return true;
}
void resolva()
{ int x, y, n;
char entrada[50];
for(x=0; x<9; x++)
for(y=0; y<9; y++)
if(grid[x][y] == 0) //vazio
{ for(n=1; n<=9; n++) //testo as 9 possibilidades
if(possivel(x, y, n))
{ grid[x][y] = n;
resolva();
grid[x][y] = 0;
}
return; //fracasso: não consegui resolver
}
imprime();
printf("Mais alguma resposta? ");
gets(entrada);
}
int main()
{
printf("Sudoku\n\n");
resolva();
return 0;
}
Comentários
Postar um comentário