Game Programming With Prolog: Ia Gaming (sudoku)

[Anduril 0]

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

 

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),verificasubllista(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 sudokucompletaLlistes([],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.

Edited December 29, 2005 by miCRoSCoPiC^eaRthLinG (see edit history)

[Monbasstic 0]

Hi Anduril I try to undestand what are you doing with the predicate "cridaappend"It is involved inside the calcul of the regionsreg(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 elementsinto 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)% Failurealso, the list returned by the previous procedure "creasubreg(P,N,L)" gives in La 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 suposeit is implemented as: append([],L,L). append([X|L1],L2,[X|L12]):- append(L1,L2,L12).thanks in advanceMon