Game Programming With Prolog: Ia Gaming (sudoku)

Anduril

Dec 29 2005, 02:21 PM

That's an almost finished code for a sudoku solver in prolog, just missing some backtracking fixes...

CODE

diferents(_,[]).
diferents(0,[A|B]):-diferents(A,.
diferents(A,[C|D]):-A\=C,A\=0,diferents(A,D).

repetit([]).
repetit([A|B]):-diferents(A,,repetit(.

fer_ll(N,L):-fer_ll(N,[],L).
fer_ll(0,L,L).
fer_ll(N,LI,L):-N>0,N1 is N-1,fer_ll(N1,[N|LI],L).

comptapos([],0).
comptapos([A|B],N):-comptapos(B,N1),N is N1+1.

ele_correctes([],_).
ele_correctes(L):-comptapos(L,N),fer_ll(N,LP),append([0],LP,LP2),ele_correctes(L,LP2).
ele_correctes([A|B],LP):-member(A,LP),ele_correctes(B,LP).

verificasubllista([]).
%verificasubllista(L):-ele_correctes(L),repetit(L).
verificasubllista([A|B]):-ele_correctes(A),repetit(A),verificasubllista(.

verificasudoku(L,N):-files(L,N,LF),columnes(L,N,LC),reg(L,N,LR),verificasubllista(LF),verificasubllis
ta(LC),verificasubllista(LR).

%verficasudoku([]).
%verificasudoku([A|B]):-verificasubllista(A),verificasudoku(.

files([],_,[]).
files(LI,N,[X|Y]):-ll(LI,N,X,RX),files(RX,N,Y).
ll([LI|RF],1,[LI],RF).
ll([LI|RLI],N,[LI|RF],RL):-C is N-1,ll(RLI,C,RF,RL).

columnes([],[],[]).
columnes(A,N,L):-creallistes(A,N,A2),col(A2,L).
col([A,A2|B],L):-afegirelements(A,A2,A3),col2(A3,B,L).
col2(A3,[B1|RB],L):-afegirelements(A3,B1,C),col2(C,RB,L).
col2(RES,[],RES).
afegirelements([X|RX],[Y|RY],[CY|RCY]):-append(X,Y,CY),afegirelements(RX,RY,RCY).
afegirelements([],[],[]).
creallistes([],_,[]).
creallistes(LI,N,[L|RL]):-ll(LI,N,Z,X),creasubllistes(Z,N,L),creallistes(X,N,RL).
creasubllistes(_,0,[]).
creasubllistes(LI,N,[X|Y]):-C is N-1,creasub2(LI,X,RX),creasubllistes(RX,C,Y).
creasub2([LI|RE],[LI],RE).

reg(LI,N,LF):-regions(LI,N,Z),col(Z,P),creasubreg(P,N,L),cridaappend(L,Q),aplana(Q,LF).
creasubreg([],_,[]).
creasubreg([X|Y],N,[Z|T]):-files(X,N,Z),creasubreg(Y,N,T).
regions([],_,[]).
regions(LI,N,[Z|Y]):-ll(LI,N,X,RX),sqrt(N,ARREL),files(X,ARREL,Z),regions(RX,N,Y).
cridaappend([],[]).
cridaappend([X,Y|T],[Z|F]):-append(X,Y,Z),cridaappend(T,F).
aplana([X],X).

completarLlista([],LA,LP,LR):-verificasubllista(LA),invertir(LA,LR).
completarLlista(A,:-comptapos(A,N),fer_ll(N,LP),completarLlista(A,[],LP,.
completarLlista([0|B],LA,LP,LF):-member(R,LP),completarLlista(B,[R|LA],LP,LF).
completarLlista([A|B],LA,LP,LF):-A\=0,completarLlista(B,[A|LA],LP,LF).

solucionarSudoku(A,N,LR):-files(A,N,,completaLlistes(B,LR),verificasudoku(A,N),appll(LR,R),mostraSudoku®.%!!!!!!!!!!!falta verificar sudoku

completaLlistes([],LA,LR):-invertir(LA,LR).
completaLlistes(B,LR):-completaLlistes(B,[],LR).
completaLlistes([A|B],LA,LR):-completarLlista(A,Z),completaLlistes(B,[Z|LA],LR).

mostraSudoku(S):-display('\nSOLUCIÓ CORRECTA\n\n'),mostraSudoku(S,3,3,3).
mostraSudoku([X|RX],0,_,_):-display('\n'),mostraSudoku([X|RX],3,3,3).
mostraSudoku([X|RX],R,0,_):-display('\n'),R2 is R-1,mostraSudoku([X|RX],R2,3,3).
mostraSudoku([X|RX],R,F,0):-display('\t'),F2 is F-1,mostraSudoku([X|RX],R,F2,3).
mostraSudoku([],_,_,_).
mostraSudoku([X|RX],R,F,C):-R>0,F>0,C>0,C2 is C-1,display(X),display(' '),mostraSudoku(RX,R,F,C2).

%Sudoku de prova: [0,3,0,0,0,10,0,0,0,0,6,0,0,0,0,5,0,5,0,0,0,0,0,9,8,3,0,8,0,0,0,6,3,0,2,0,0,0,0,
5,0,0,0,0,9,0,3,8,0,0,0,6,0,7,1,4,0,0,0,0,0,9,0,2,0,0,0,0,8,0,0,0,0,0,4,0,0,0,3,
0]
%Sudoku fàcil de prova: [8,3,2,5,9,1,6,7,4,4,9,6,3,8,7,2,5,1,5,7,1,2,6,4,9,8,3,1,8,5,7,4,6,3,9,2,2,6,7,9
,5,3,4,1,8,9,4,3,8,1,2,7,6,5,7,1,4,6,3,8,5,2,9,3,2,9,1,7,5,8,4,6,6,5,8,4,2,9,1,3
,7]
% [8,3,2,5,9,1,6,0,0,4,9,6,3,8,7,2,5,0,5,7,1,2,0,0,0,8,3,1,8,0,7,4,6,0,0,2,2,6,7,9
,5,3,4,1,8,9,4,3,0,1,2,7,6,0,0,0,4,6,3,8,5,0,9,3,2,9,1,7,5,0,4,6,6,5,8,4,2,9,1,3
,7]

invertir(L,LI):-invertir(L,[],LI).
invertir([],L,L).
invertir([X|RX],L,LI):-invertir(RX,[X|L],LI).

appll(L,LF):-appll(L,[],LF).
appll([A|C],LA,LF):-append(LA,A,Z),appll(C,Z,LF).
appll([],LA,LA).

files([],_,[]).
files(LI,N,[X|Y]):-ll(LI,N,X,RX),files(RX,N,Y).
ll([LI|RF],1,[LI],RF).
ll([LI|RLI],N,[LI|RF],RL):-C is N-1,ll(RLI,C,RF,RL).

columnes([],[],[]).
columnes(A,N,L):-creallistes(A,N,A2),col(A2,L).
col([A,A2|B],L):-afegirelements(A,A2,A3),col2(A3,B,L).
col2(A3,[B1|RB],L):-afegirelements(A3,B1,C),col2(C,RB,L).
col2(RES,[],RES).
afegirelements([X|RX],[Y|RY],[CY|RCY]):-append(X,Y,CY),afegirelements(RX,RY,RCY).
afegirelements([],[],[]).
creallistes([],_,[]).
creallistes(LI,N,[L|RL]):-ll(LI,N,Z,X),creasubllistes(Z,N,L),creallistes(X,N,RL).
creasubllistes(_,0,[]).
creasubllistes(LI,N,[X|Y]):-C is N-1,creasub2(LI,X,RX),creasubllistes(RX,C,Y).
creasub2([LI|RE],[LI],RE).

reg(LI,N,LF):-regions(LI,N,Z),col(Z,P),creasubreg(P,N,L),cridaappend(L,Q),aplana(Q,LF).
creasubreg([],_,[]).
creasubreg([X|Y],N,[Z|T]):-files(X,N,Z),creasubreg(Y,N,T).
regions([],_,[]).
regions(LI,N,[Z|Y]):-ll(LI,N,X,RX),sqrt(N,ARREL),files(X,ARREL,Z),regions(RX,N,Y).
cridaappend([],[]).
cridaappend([X,Y|T],[Z|F]):-append(X,Y,Z),cridaappend(T,F).
aplana([X],X).

Maybe you'll nedd to translate predicate names from spanish to english, also some of the predicates are in Catalan... sry ^^

Notice from miCRoSCoPiC^eaRthLinG:

When you publish such large blocks of code, make sure you include them between CODE or CODEBOX tags. Failure to do so will cause your credits to be adjusted - which means you might loose all the credits for such a post.

Secondly - such a code is quite useless, unless you clearly explain at each step - what exactly is happening. That is a MUST for posts like this - coz without such explanations, again, the code alone is quite useless. It's like leaving others groping in the dark trying to figure it all by themselves - specially for newbies.

Since, you're new to this board, you'll get off without a warning this time. But our credits system is heavily dependent on proper usage of the BBCode tags. Hence, I'm forced to adjust the credits - Reducing Hosting credits worth 18 days.

Monbasstic

Apr 21 2006, 08:17 PM

Hi Anduril

I try to undestand what are you doing with the predicate "cridaappend"
It is involved inside the calcul of the regions

reg(LI,N,LF):-regions(LI,N,Z),col(Z,P),creasubreg(P,N,L),cridaappend(L,Q),aplana(Q,LF).

I have noted tha cridaappend works fine when is called whit a even number of elements
into L ...

% ?-cridaappend([[[1,2],[3,4]], [[5,6],[7,8]] ],Q)
% Q = [[[1, 2], [3, 4], [5, 6], [7, 8]]]
% ?-cridaappend([[[11,12],[13,14],[15,16]], [[21,22],[23,24]] ],Q)
% Q = [[[11, 12], [13, 14], [15, 16], [21, 22], [23, 24]]]
% ?-cridaappend([ [1],[2],[3],[4],[5],[6] ],Q)
% Q = [[1, 2], [3, 4], [5, 6]]
% ?-cridaappend([ [11,12],[21,22],[31,32],[41,42],[51,52],[61,62] ],Q)
% Q = [[11, 12, 21, 22], [31, 32, 41, 42], [51, 52, 61, 62]]

but, it fails when L is a list with a odd number of elements
% ?-cridaappend([ [1],[2],[3],[4],[5]],Q)
% Failure

also, the list returned by the previous procedure "creasubreg(P,N,L)" gives in L
a odd number of elements like (for example)..
L = [ [ [11, 12, 13, 21, 22, 23, 31, 32, 33],
[41, 42, 43, 51, 52, 53, 61, 62, 63],
[71, 72, 73, 81, 82, 83, 91, 92, 93] ],
[ [14, 15, 16, 24, 25, 26, 34, 35, 36],
[44, 45, 46, 54, 55, 56, 64, 65, 66],
[74, 75, 76, 84, 85, 86, 94, 95, 96] ],
[ [17, 18, 19, 27, 28, 29, 37, 38, 39],
[47, 48, 49, 57, 58, 59, 67, 68, 69],
[77, 78, 79, 87, 88, 89, 97, 98, 99] ] ]

Then, when we call latter "cridaappend", the algoritm fails.

Can you explain me how you implements the predicate "append" , i supose
it is implemented as:
append([],L,L).
append([X|L1],L2,[X|L12]):-
append(L1,L2,L12).

thanks in advance
Mon

ADD REPLY / Got an Opinion!	a humble request :-)	RAPID SEARCH!	Free Hosting	[X]
Express your Opinions, Thoughts or Contribute more info. to help others. Ask your Doubts & Queries to get answers, So that "Together We can help others!"	Register FREE for AD-FREE forum, Create your own topics, Ask Questions, track topics, setup subscriptions & notifications and Get a Free Website w/ Email and FTP.		500MB Space No Ads, CPanel, FTP, PHP, MySQL, EMails - 100% FREE