Hespanha

Cada vez mais na área de programação aquela história de se especializar em uma linguagem, e resolver todos os problemas com ela está sendo questionada. E realmente, como vocês verão neste post, esse questionamento faz todo sentido. Existe uma linguagem mais adequada para resolver cada problema, e por isso, é obrigação do programador conhecer diversas linguagens, no mínimo uma de cada paradigma, para poder escolher qual linguagem se encaixa melhor para determinado problema.

Considere o problema de implementar um resolvedor de Sudoku, ou seja, você deve implementar um programa que dado um tabuleiro do jogo parcialmente preenchido, seu programa deve devolver o tabuleiro totalmente preenchido.

Não sei se é a melhor que existe, mas a melhor linguagem que eu conheço pra resolver este problema é Prolog. Sim, aquela linguagem de programação que a gente vê na faculdade no curso de Inteligência Artificial. Prolog é uma linguagem de programação declarativa, baseada em lógica de primeira ordem. Em Prolog temos:

-Fatos: Uma afirmação básica. (Ex: Azalão é um cavalo; cavalo gosta de grama.)

-Regras: É uma inferência sobre um fato. (Ex: Um animal gosta de grama se ela é um cavalo.)

-Query: Uma questão (Ex: Azalão gosta de grama?)

E é isso, ou seja, bem diferente de uma linguagem de programação imperativa, como Java por exemplo.

Agora vamos definir as regras para verificar se um jogo de Sudoku é valido, e embaixo de cada regra vamos definir o código em Prolog para implementar tal regra. São elas:

Supondo que nosso problema é definido como:

sudoku(Entrada, Solucao)

Regra 1) Para um jogo resolvido, os números na entrada e na saída devem ser os mesmos.

sudoku(Entrada, Solucao) :- Solucao = Entrada.

Regra 2) Um tabuleiro de Sudoku é uma grade de 81 elementos, com valores de 1-9.

Entrada = [S11, S12, S13, S14, S15, S16, S17, S18, S19,
		  S21, S22, S23, S24, S25, S26, S27, S28, S29,
		  S31, S32, S33, S34, S35, S36, S37, S38, S39,
		  S41, S42, S43, S44, S45, S46, S47, S48, S49,
		  S51, S52, S53, S54, S55, S56, S57, S58, S59,
		  S61, S62, S63, S64, S65, S66, S67, S68, S69,
		  S71, S72, S73, S74, S75, S76, S77, S78, S79,
		  S81, S82, S83, S84, S85, S86, S87, S88, S89,
		  S91, S92, S93, S94, S95, S96, S97, S98, S99],
	fd_domain(Solucao, 1, 9).

Regra 3) Um tabuleiro tem 9 linhas, 9 colunas e 9 quadrados.

Row1 = [S11, S12, S13, S14, S15, S16, S17, S18, S19],
Row2 = [S21, S22, S23, S24, S25, S26, S27, S28, S29],
Row3 = [S31, S32, S33, S34, S35, S36, S37, S38, S39],
Row4 = [S41, S42, S43, S44, S45, S46, S47, S48, S49],
Row5 = [S51, S52, S53, S54, S55, S56, S57, S58, S59],
Row6 = [S61, S62, S63, S64, S65, S66, S67, S68, S69],
Row7 = [S71, S72, S73, S74, S75, S76, S77, S78, S79],
Row8 = [S81, S82, S83, S84, S85, S86, S87, S88, S89],
Row9 = [S91, S92, S93, S94, S95, S96, S97, S98, S99],

Col1 = [S11, S21, S31, S41, S51, S61, S71, S81, S91],
Col2 = [S12, S22, S32, S42, S52, S62, S72, S82, S92],
Col3 = [S13, S23, S33, S43, S53, S63, S73, S83, S93],
Col4 = [S14, S24, S34, S44, S54, S64, S74, S84, S94],
Col5 = [S15, S25, S35, S45, S55, S65, S75, S85, S95],
Col6 = [S16, S26, S36, S46, S56, S66, S76, S86, S96],
Col7 = [S17, S27, S37, S47, S57, S67, S77, S87, S97],
Col8 = [S18, S28, S38, S48, S58, S68, S78, S88, S98],
Col9 = [S19, S29, S39, S49, S59, S69, S79, S89, S99],

Square1 = [S11, S12, S13, S21, S22, S23, S31, S32, S33],
Square2 = [S14, S15, S16, S24, S25, S26, S34, S35, S36],
Square3 = [S17, S18, S19, S27, S28, S29, S37, S38, S39],
Square4 = [S41, S42, S43, S51, S52, S53, S61, S62, S63],
Square5 = [S44, S45, S46, S54, S55, S56, S64, S65, S66],
Square6 = [S47, S48, S49, S57, S58, S59, S67, S68, S69],
Square7 = [S71, S72, S73, S81, S82, S83, S91, S92, S93],
Square8 = [S74, S75, S76, S84, S85, S86, S94, S95, S96],
Square9 = [S77, S78, S79, S87, S88, S89, S97, S98, S99].

Regra 4) Não pode haver números repetidos nas linhas, colunas e quadrados.

valid([]).
valid([Head | Tail]) :-
	fd_all_different(Head), valid(Tail).

valid([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9,
     Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9,
     Square1, Square2, Square3, Square4, Square5, Square6, Square7, Square8, Square9]).

E pronto, acredite ou não, o problema está resolvido. Como vocês viram, a única coisa que fizemos foi definir as regras do problema e pronto, o Prolog resolve o problema pra você. Agora pense como você resolveria esse problema em Java por exemplo. Com certeza definir as regras acima seria apenas o começo.

Mas muitos devem estar se perguntando: “Tá, mas meu programa é feito em Java, o que eu vou fazer com esse código em Prolog?”. Mas é aí que entra o principal ponto, é possível integrar código em Prolog com diversas outras linguagems, por isso que hoje em dia não é mais preciso resolver todos os problemas de um sistema com a mesma linguagem.

E aí, animou a conhecer mais Prolog?

Segue abaixo o código completo do problema. Para rodar essa implementação é necessário o gprolog, já que usamos algumas funções pré-definidas existentes apenas nesta ferramenta.

valid([]).
valid([Head | Tail]) :-
	fd_all_different(Head), valid(Tail).

sodoku(Puzzle, Solution) :-
	Solution = Puzzle,
	Puzzle = [S11, S12, S13, S14, S15, S16, S17, S18, S19,
		  S21, S22, S23, S24, S25, S26, S27, S28, S29,
		  S31, S32, S33, S34, S35, S36, S37, S38, S39,
		  S41, S42, S43, S44, S45, S46, S47, S48, S49,
		  S51, S52, S53, S54, S55, S56, S57, S58, S59,
		  S61, S62, S63, S64, S65, S66, S67, S68, S69,
		  S71, S72, S73, S74, S75, S76, S77, S78, S79,
		  S81, S82, S83, S84, S85, S86, S87, S88, S89,
		  S91, S92, S93, S94, S95, S96, S97, S98, S99],
	fd_domain(Solution, 1, 9),

	Row1 = [S11, S12, S13, S14, S15, S16, S17, S18, S19],
	Row2 = [S21, S22, S23, S24, S25, S26, S27, S28, S29],
	Row3 = [S31, S32, S33, S34, S35, S36, S37, S38, S39],
	Row4 = [S41, S42, S43, S44, S45, S46, S47, S48, S49],
	Row5 = [S51, S52, S53, S54, S55, S56, S57, S58, S59],
	Row6 = [S61, S62, S63, S64, S65, S66, S67, S68, S69],
	Row7 = [S71, S72, S73, S74, S75, S76, S77, S78, S79],
	Row8 = [S81, S82, S83, S84, S85, S86, S87, S88, S89],
	Row9 = [S91, S92, S93, S94, S95, S96, S97, S98, S99],

	Col1 = [S11, S21, S31, S41, S51, S61, S71, S81, S91],
	Col2 = [S12, S22, S32, S42, S52, S62, S72, S82, S92],
	Col3 = [S13, S23, S33, S43, S53, S63, S73, S83, S93],
	Col4 = [S14, S24, S34, S44, S54, S64, S74, S84, S94],
	Col5 = [S15, S25, S35, S45, S55, S65, S75, S85, S95],
	Col6 = [S16, S26, S36, S46, S56, S66, S76, S86, S96],
	Col7 = [S17, S27, S37, S47, S57, S67, S77, S87, S97],
	Col8 = [S18, S28, S38, S48, S58, S68, S78, S88, S98],
	Col9 = [S19, S29, S39, S49, S59, S69, S79, S89, S99],

	Square1 = [S11, S12, S13, S21, S22, S23, S31, S32, S33],
	Square2 = [S14, S15, S16, S24, S25, S26, S34, S35, S36],
	Square3 = [S17, S18, S19, S27, S28, S29, S37, S38, S39],
	Square4 = [S41, S42, S43, S51, S52, S53, S61, S62, S63],
	Square5 = [S44, S45, S46, S54, S55, S56, S64, S65, S66],
	Square6 = [S47, S48, S49, S57, S58, S59, S67, S68, S69],
	Square7 = [S71, S72, S73, S81, S82, S83, S91, S92, S93],
	Square8 = [S74, S75, S76, S84, S85, S86, S94, S95, S96],
	Square9 = [S77, S78, S79, S87, S88, S89, S97, S98, S99],

	valid([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9,
	       Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9,
	       Square1, Square2, Square3, Square4, Square5, Square6, Square7, Square8, Square9]).

Segue um exemplo de entrada:

sodoku([9,4,_,1,_,2,_,5,8,
 6,_,_,_,5,_,_,_,4,
 _,_,2,4,_,3,1,_,_,
 _,2,_,_,_,_,_,6,_,
 5,_,8,_,2,_,4,_,1,
 _,6,_,_,_,_,_,8,_,
 _,_,1,6,_,8,7,_,_,
 7,_,_,_,4,_,_,_,3,
 4,3,_,5,_,9,_,1,2], Solution).

Abraços e até a próxima!

This entry was posted on Sunday, September 12th, 2010 at 11:11 pm and is filed under programação, prolog. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.