 Game Programming With Prolog: Ia Gaming (sudoku) |
Free Web Hosting > Computers & Tech > Programming > Programming General > Lisp & Prolog (AI Languages)|
|
|
|
  |
 Dec 29 2005, 02:21 PM
Post
#1
|
|
|
Newbie [ Level 1 ]  Group: Members Posts: 9 Joined: 29-December 05 Member No.: 10,345  |
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 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. This post has been edited by miCRoSCoPiC^eaRthLinG: Dec 29 2005, 06:10 PM |
 |
 
|
|
Apr 21 2006, 08:17 PM
Post
#2
|
|
|
Newbie [ Level 1 ] Group: Members Posts: 1 Joined: 11-April 06 Member No.: 12,659 |
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 |
|
|
|
|
Similar Topics
| Topics | Topics | |
|---|---|---|
|
|
|
|
Lo-Fi Version | Time is now: 14th October 2008 - 01:47 AM |