%=============================================================================================
% pocitani matice moznych prvku
%=============================================================================================

% seznamyMoznosti(+Sudoku, -Seznamy moznosti pro kazde pole).
% budu potrebovat transpozici matice
% ten rozdil inicialni udelam pro kazdy radek jen jednou
seznamyMoznosti(I,M):- transpozice(I,T),radkySloupce(I,T,M0),zmensiMat(I,B),odectiBloky(M0,B,M).

% radkySloupce(+Sudoku, +Transpozice, -Seznamy moznosti co nejsou v radku ani ve sloupci).
radkySloupce([],_,[]).
radkySloupce([R|Rs],T,[O|Os]):-X0=[1,2,3,4,5,6,7,8,9],subtract(X0,R,X1),seznamyRadky(X1,T,O),radkySloupce(Rs,T,Os).
seznamyRadky(_,[],[]).
seznamyRadky(M,[S|Ss],[O|Os]):- subtract(M,S,O), seznamyRadky(M,Ss,Os).

% odectiBloky(+Moznosti jen bez radku a sloupcu, +SumaBloku, -Moznosti i s odectenymi bloky).
odectiBloky([],_,[]).
odectiBloky([I0,I1,I2|Is],[B|Bs],[M0,M1,M2|Ms]):-odectiRadky(I0,B,M0),odectiRadky(I1,B,M1),odectiRadky(I2,B,M2),
    odectiBloky(Is,Bs,Ms).
odectiRadky([],_,[]).
odectiRadky([R0,R1,R2|Rs],[B|Bs],[V0,V1,V2|Vs]):-subtract(R0,B,V0),subtract(R1,B,V1),subtract(R2,B,V2),
    odectiRadky(Rs,Bs,Vs).

% transpozice(+M, -TM):-TM je transpozice matice M
transpozice(M, []):-vsePrazdne(M).
transpozice(M, [H|TM]):-hlavyZbytky(M, H, Z), transpozice(Z, TM).
% vsePrazdne(+SeznamSeznamu):-vsechny seznamy v SeznamSeznamu jsou prazdne
vsePrazdne([]).
vsePrazdne([[]|Z]):-vsePrazdne(Z).
% hlavyZbytky(+SeznamSeznamu, -Hlavy, -Zbytky):-rozdeli vsechny seznamu v SeznamSeznamu na Hlavy a Zbytky
hlavyZbytky([], [], []).
hlavyZbytky([[H|T] | Z], [H|PP], [T|ZB]):-hlavyZbytky(Z, PP, ZB).

% zmensi matici, vzdy cely blok strci do jednoho prvku
zmensiMat([],[]).
zmensiMat([A,B,C|Xs],[[Y0,Y1,Y2]|Ys]):-zmensiRad(A,[A0,A1,A2]),zmensiRad(B,[B0,B1,B2]),zmensiRad(C,[C0,C1,C2]),
    append(A0,B0,X0),append(X0,C0,Y0),
    append(A1,B1,X1),append(X1,C1,Y1),
    append(A2,B2,X2),append(X2,C2,Y2),zmensiMat(Xs,Ys).
zmensiRad([],[]).
zmensiRad([A,B,C|Xs],[[A,B,C]|Ys]):-zmensiRad(Xs,Ys).

%=============================================================================================
% funkce pro selekci prvku na radku
%=============================================================================================

% jenjiste(+Radek, +SeznamMoznosti, -NovyRadek).
% asi by se to dalo delat iterativne, ale ted se mi nechce
jenjiste([.|Rs],[[X]|_],[X|Rs]).
jenjiste([R|Rs],[_|Ms],[R|Xs]):- jenjiste(Rs,Ms,Xs).
tip2([.|Rs],[[A,B]|_],[X|Rs]):- X = A; X = B.
tip2([R|Rs],[_|Ms],[R|Xs]):- tip2(Rs,Ms,Xs).
tip3([.|Rs],[[A,B,C]|_],[X|Rs]):- X = A; X = B; X = C.
tip3([R|Rs],[_|Ms],[R|Xs]):- tip3(Rs,Ms,Xs).
tipN([.|Rs],[M|_],[X|Rs]):- member(X,M).
tipN([R|Rs],[_|Ms],[R|Xs]):- tipN(Rs,Ms,Xs).

% podobne jako tipN, ale dosazuje konkretni, cislo o kterem uz vim ze je tam jen jednou
dosadCislo(N,[.|Rs],[M|_],[N|Rs]):- member(N,M).
dosadCislo(N,[R|Rs],[_|Ms],[R|Xs]):- dosadCislo(N,Rs,Ms,Xs).

% jedinevradku(+Radek, +SeznamMoznosti, -NovyRadek).
jedinevradku(I,M,O):- jedinevradku(1,I,M,O).
jedinevradku(N,I,M,O):- najdiJedineCislo(N,M), dosadCislo(N,I,M,O).
jedinevradku(N,I,M,O):- N1=N+1, N1<10, jedinevradku(N1,I,M,O).

% uspeje, pokud se cislo vyskytuje jen jednou na radku moznosti
najdiJedineCislo(N,[M|Ms]):- (member(N,M), \+najdiCislo(N,Ms)); najdiJedineCislo(N,Ms).
% uspeje, pokud se tam vyskytuje cislo libovolnekrat
najdiCislo(N,[M|Ms]):- member(N,M); najdiCislo(N,Ms).

%=============================================================================================
% rizeni programu, centralni cast kodu
%=============================================================================================

% zjisti jestli je sudoku vyplnene
vyplnene([]).
vyplnene([X|Xs]):- \+member(.,X), vyplnene(Xs).

% doplni jedno cislo, prvni zkusi jen jiste a kdyztak zkusi vsechny
krok(I,O):- seznamyMoznosti(I,M),(vyzkousejPoRadcich(jenjiste,I,M,O);
                                  vyzkousejPoRadcich(jedinevradku,I,M,O);
                                  vyzkousejPoSloupcich(jedinevradku,I,M,O);
                                  vyzkousejPoRadcich(tip2,I,M,O);
                                  vyzkousejPoRadcich(tip3,I,M,O);
                                  vyzkousejPoRadcich(tipN,I,M,O)).

% vyzkousejPoRadcich(+Funkce, +In, +Moznosti, -Out)
% vyzkousejPoRadcich(_,[],_,[]). chci aby to selhalo pokud se nic nenajde
vyzkousejPoRadcich(F,[I|Is],[M|_],[O|Is]):- call(F,I,M,O). % mozna ! ale jen u jistych
vyzkousejPoRadcich(F,[I|Is],[_|Ms],[I|Os]):- vyzkousejPoRadcich(F,Is,Ms,Os).

vyzkousejPoSloupcich(F,I,M,O):- transpozice(I,TI), transpozice(M,TM), vyzkousejPoRadcich(F,TI,TM,TO), transpozice(TO,O).

%============================================================================================================
% vstup do programu a testovaci metody
%============================================================================================================

% vypln(+Sudoku, -Reseni).
vypln(S,S):-vyplnene(S),!.
vypln(A,C):-krok(A,B), vypln(B,C).

% primitivni
test1(X):- vypln(
[[3,6,4,7,8,5,.,.,9],
 [.,8,2,4,3,9,6,5,7],
 [7,9,5,2,.,6,8,3,4],
 [4,7,1,5,9,2,3,6,8],
 [9,5,.,3,7,8,4,1,2],
 [8,2,3,6,4,1,7,9,5],
 [2,1,8,.,6,4,5,7,3],
 [6,3,9,8,5,7,.,4,1],
 [5,4,7,1,2,3,9,8,6]],X),!.

test2(X):- vypln(
[[3,6,4,7,8,5,.,.,9],
 [.,8,2,4,3,9,6,5,7],
 [7,9,5,2,.,6,8,3,4],
 [4,7,1,5,9,2,3,6,8],
 [9,5,.,3,7,8,4,1,2],
 [8,2,3,6,4,1,7,9,5],
 [.,.,.,.,6,4,5,7,3],
 [.,.,.,8,5,7,.,4,1],
 [.,.,.,1,2,3,9,8,6]],X),!.

% lehke
test3(X):- vypln(
[[1,.,.,.,8,.,6,7,3],
 [.,.,.,.,.,7,4,.,5],
 [5,.,.,.,.,.,2,.,.],
 [6,.,3,.,.,9,.,.,1],
 [7,4,.,5,.,6,.,3,2],
 [9,.,.,4,.,.,8,.,7],
 [.,.,9,.,.,.,.,.,4],
 [4,.,7,6,.,.,.,.,.],
 [8,3,1,.,4,.,.,.,6]],X),!.

% stredni
test4(X):- vypln(
[[.,.,2,8,7,1,9,.,4],
 [.,.,4,9,.,.,.,5,.],
 [.,.,3,.,.,.,6,1,8],
 [.,.,6,1,8,.,.,.,.],
 [9,.,.,2,.,4,.,.,1],
 [.,.,.,.,6,7,8,.,.],
 [6,8,7,.,.,.,4,.,.],
 [.,4,.,.,.,3,7,.,.],
 [3,.,9,7,4,8,1,.,.]],X),!.

% tezke
test5(X):- vypln(
[[.,.,9,.,5,.,.,.,3],
 [.,8,.,.,9,2,.,7,.],
 [.,4,.,.,3,.,.,.,8],
 [.,9,7,.,.,4,.,8,2],
 [8,.,.,3,.,9,.,.,1],
 [4,2,.,5,.,.,3,9,.],
 [7,.,.,.,4,.,.,5,.],
 [.,3,.,8,1,.,.,2,.],
 [2,.,.,.,7,.,1,.,.]],X),!.

% zapeklite
test6(X):- vypln(
[[.,9,.,.,.,4,5,.,.],
 [.,.,.,.,.,.,4,1,8],
 [6,.,.,.,.,5,.,2,.],
 [8,.,.,9,4,.,.,.,6],
 [.,4,6,.,3,.,2,8,.],
 [3,.,.,.,8,6,.,.,5],
 [.,5,.,6,.,.,.,.,2],
 [2,8,9,.,.,.,.,.,.],
 [.,.,3,2,.,.,.,9,.]],X),!.