% ------------------------------------------------------------------------------ % Helpers % kommt X mindestens einmal in Liste vor? mitglied(X, [X|_]). mitglied(X, [_|L]) :- mitglied(X, L). % loesche X genau 1x aus Liste loesche(X, [X|S], S, 1). loesche(X, [Y|S], [Y|S1], Pos) :- loesche(X,S,S1, Posneu), Pos is Posneu +1. zahl(X) :- between(1, 9, X). % alle Zahlen zwischen 1 und 9 % ------------------------------------------------------------------------------ % Bearbeiten des Brettes setzeelement(1, [_|Liste], X, [X|Liste]) :- !. setzeelement(Pos, [X|Liste], Element, [X|Liste2]) :- !, Posneu is Pos-1, setzeelement(Posneu, Liste, Element, Liste2). getfirstfree([u|_], 1) :- !. getfirstfree([_|Liste], Position) :- getfirstfree(Liste, Pos), Position is Pos+1. singleton(L, Pos) :- loesche(u, L, Lneu, Pos), not(mitglied(u, Lneu)). getsingleposition([X11, X12, X13, X14, X15, X16, X17, X18, X19, X21, X22, X23, X24, X25, X26, X27, X28, X29, X31, X32, X33, X34, X35, X36, X37, X38, X39, X41, X42, X43, X44, X45, X46, X47, X48, X49, X51, X52, X53, X54, X55, X56, X57, X58, X59, X61, X62, X63, X64, X65, X66, X67, X68, X69, X71, X72, X73, X74, X75, X76, X77, X78, X79, X81, X82, X83, X84, X85, X86, X87, X88, X89, X91, X92, X93, X94, X95, X96, X97, X98, X99], Posneu) :- % Zeilen prüfen singleton([X11, X12, X13, X14, X15, X16, X17, X18, X19], Pos), Posneu is Pos + 0; singleton([X21, X22, X23, X24, X25, X26, X27, X28, X29], Pos), Posneu is Pos + 9; singleton([X31, X32, X33, X34, X35, X36, X37, X38, X39], Pos), Posneu is Pos + 18; singleton([X41, X42, X43, X44, X45, X46, X47, X48, X49], Pos), Posneu is Pos + 27; singleton([X51, X52, X53, X54, X55, X56, X57, X58, X59], Pos), Posneu is Pos + 36; singleton([X61, X62, X63, X64, X65, X66, X67, X68, X69], Pos), Posneu is Pos + 45; singleton([X71, X72, X73, X74, X75, X76, X77, X78, X79], Pos), Posneu is Pos + 54; singleton([X81, X82, X83, X84, X85, X86, X87, X88, X89], Pos), Posneu is Pos + 63; singleton([X91, X92, X93, X94, X95, X96, X97, X98, X99], Pos), Posneu is Pos + 72; % Spalten prüfen singleton([X11, X21, X31, X41, X51, X61, X71, X81, X91], Pos), Posneu is (Pos-1)*9 +1; singleton([X12, X22, X32, X42, X52, X62, X72, X82, X92], Pos), Posneu is (Pos-1)*9 +2; singleton([X13, X23, X33, X43, X53, X63, X73, X83, X93], Pos), Posneu is (Pos-1)*9 +3; singleton([X14, X24, X34, X44, X54, X64, X74, X84, X94], Pos), Posneu is (Pos-1)*9 +4; singleton([X15, X25, X35, X45, X55, X65, X75, X85, X95], Pos), Posneu is (Pos-1)*9 +5; singleton([X16, X26, X36, X46, X56, X66, X76, X86, X96], Pos), Posneu is (Pos-1)*9 +6; singleton([X17, X27, X37, X47, X57, X67, X77, X87, X97], Pos), Posneu is (Pos-1)*9 +7; singleton([X18, X28, X38, X48, X58, X68, X78, X88, X98], Pos), Posneu is (Pos-1)*9 +8; singleton([X19, X29, X39, X49, X59, X69, X79, X89, X99], Pos), Posneu is (Pos-1)*9 +9; % Quadrate prüfen singleton([X11, X12, X13, X21, X22, X23, X31, X32, X33], Pos), QOffset = 0, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X14, X15, X16, X24, X25, X26, X34, X35, X36], Pos), QOffset = 3, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X17, X18, X19, X27, X28, X29, X37, X38, X39], Pos), QOffset = 6, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X41, X42, X43, X51, X52, X53, X61, X62, X63], Pos), QOffset = 27, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X44, X45, X46, X54, X55, X56, X64, X65, X66], Pos), QOffset = 30, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X47, X48, X49, X57, X58, X59, X67, X68, X69], Pos), QOffset = 33, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X71, X72, X73, X81, X82, X83, X91, X92, X93], Pos), QOffset = 54, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X74, X75, X76, X84, X85, X86, X94, X95, X96], Pos), QOffset = 57, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos; singleton([X77, X78, X79, X87, X88, X89, X97, X98, X99], Pos), QOffset = 60, Posneu is (ceiling(Pos/3)-1)*6 + QOffset + Pos. ausgabe([X1, X2, X3, X4, X5, X6, X7, X8, X9]) :- write(X1), write(X2), write(X3), write(' '), write(X4), write(X5), write(X6), write(' '), write(X7), write(X8), write(X9), !. ausgabe([X1, X2, X3, X4, X5, X6, X7, X8, X9 | Rest]) :- ausgabe([X1, X2, X3, X4, X5, X6, X7, X8, X9]), nl, ausgabe(Rest). % ------------------------------------------------------------------------------ % Tests auf korrekte Verteilung getrow(Pos, 1) :- Pos =< 9, !. getrow(Pos, Row) :- Posneu is (Pos-9), getrow(Posneu, Rowneu), Row is Rowneu+1. getcol(Pos, 1) :- (Pos mod 9) =:= 1, !. getcol(Pos, 2) :- (Pos mod 9) =:= 2, !. getcol(Pos, 3) :- (Pos mod 9) =:= 3, !. getcol(Pos, 4) :- (Pos mod 9) =:= 4, !. getcol(Pos, 5) :- (Pos mod 9) =:= 5, !. getcol(Pos, 6) :- (Pos mod 9) =:= 6, !. getcol(Pos, 7) :- (Pos mod 9) =:= 7, !. getcol(Pos, 8) :- (Pos mod 9) =:= 8, !. getcol(Pos, 9) :- (Pos mod 9) =:= 0. getsqr(Pos, 1) :- getcol(Pos, S), S<4, getrow(Pos, Z), Z<4, !. getsqr(Pos, 2) :- getcol(Pos, S), S<7, getrow(Pos, Z), Z<4, !. getsqr(Pos, 3) :- getrow(Pos, Z), Z<4, !. getsqr(Pos, 4) :- getcol(Pos, S), S<4, getrow(Pos, Z), Z<7, !. getsqr(Pos, 5) :- getcol(Pos, S), S<7, getrow(Pos, Z), Z<7, !. getsqr(Pos, 6) :- getrow(Pos, Z), Z<7, !. getsqr(Pos, 7) :- getcol(Pos, S), S<4, !. getsqr(Pos, 8) :- getcol(Pos, S), S<7, !. getsqr(_, 9). valide9(Z1, Z2, Z3, Z4, Z5, Z6, Z7, Z8, Z9) :- (Z1 == u ; (Z1 \= Z2, Z1 \= Z3, Z1 \= Z4, Z1 \= Z5, Z1 \= Z6, Z1 \= Z7, Z1 \= Z8, Z1 \= Z9)), (Z2 == u ; (Z2 \= Z3, Z2 \= Z4, Z2 \= Z5, Z2 \= Z6, Z2 \= Z7, Z2 \= Z8, Z2 \= Z9)), (Z3 == u ; (Z3 \= Z4, Z3 \= Z5, Z3 \= Z6, Z3 \= Z7, Z3 \= Z8, Z3 \= Z9)), (Z4 == u ; (Z4 \= Z5, Z4 \= Z6, Z4 \= Z7, Z4 \= Z8, Z4 \= Z9)), (Z5 == u ; (Z5 \= Z6, Z5 \= Z7, Z5 \= Z8, Z5 \= Z9)), (Z6 == u ; (Z6 \= Z7, Z6 \= Z8, Z6 \= Z9)), (Z7 == u ; (Z7 \= Z8, Z7 \= Z9)), (Z8 == u ; (Z8 \= Z9)). valide([X11, X12, X13, X14, X15, X16, X17, X18, X19, X21, X22, X23, X24, X25, X26, X27, X28, X29, X31, X32, X33, X34, X35, X36, X37, X38, X39, X41, X42, X43, X44, X45, X46, X47, X48, X49, X51, X52, X53, X54, X55, X56, X57, X58, X59, X61, X62, X63, X64, X65, X66, X67, X68, X69, X71, X72, X73, X74, X75, X76, X77, X78, X79, X81, X82, X83, X84, X85, X86, X87, X88, X89, X91, X92, X93, X94, X95, X96, X97, X98, X99]) :- % Zeilen prüfen valide9(X11, X12, X13, X14, X15, X16, X17, X18, X19), valide9(X21, X22, X23, X24, X25, X26, X27, X28, X29), valide9(X31, X32, X33, X34, X35, X36, X37, X38, X39), valide9(X41, X42, X43, X44, X45, X46, X47, X48, X49), valide9(X51, X52, X53, X54, X55, X56, X57, X58, X59), valide9(X61, X62, X63, X64, X65, X66, X67, X68, X69), valide9(X71, X72, X73, X74, X75, X76, X77, X78, X79), valide9(X81, X82, X83, X84, X85, X86, X87, X88, X89), valide9(X91, X92, X93, X94, X95, X96, X97, X98, X99), % Spalten prüfen valide9(X11, X21, X31, X41, X51, X61, X71, X81, X91), valide9(X12, X22, X32, X42, X52, X62, X72, X82, X92), valide9(X13, X23, X33, X43, X53, X63, X73, X83, X93), valide9(X14, X24, X34, X44, X54, X64, X74, X84, X94), valide9(X15, X25, X35, X45, X55, X65, X75, X85, X95), valide9(X16, X26, X36, X46, X56, X66, X76, X86, X96), valide9(X17, X27, X37, X47, X57, X67, X77, X87, X97), valide9(X18, X28, X38, X48, X58, X68, X78, X88, X98), valide9(X19, X29, X39, X49, X59, X69, X79, X89, X99), % Quadrate prüfen valide9(X11, X12, X13, X21, X22, X23, X31, X32, X33), valide9(X14, X15, X16, X24, X25, X26, X34, X35, X36), valide9(X17, X18, X19, X27, X28, X29, X37, X38, X39), valide9(X41, X42, X43, X51, X52, X53, X61, X62, X63), valide9(X44, X45, X46, X54, X55, X56, X64, X65, X66), valide9(X47, X48, X49, X57, X58, X59, X67, X68, X69), valide9(X71, X72, X73, X81, X82, X83, X91, X92, X93), valide9(X74, X75, X76, X84, X85, X86, X94, X95, X96), valide9(X77, X78, X79, X87, X88, X89, X97, X98, X99). % testet nur der geänderten Pos entsprechende Zeile/Spalte/Quadrat, ob noch konsistent validePos([X11, X12, X13, X14, X15, X16, X17, X18, X19, X21, X22, X23, X24, X25, X26, X27, X28, X29, X31, X32, X33, X34, X35, X36, X37, X38, X39, X41, X42, X43, X44, X45, X46, X47, X48, X49, X51, X52, X53, X54, X55, X56, X57, X58, X59, X61, X62, X63, X64, X65, X66, X67, X68, X69, X71, X72, X73, X74, X75, X76, X77, X78, X79, X81, X82, X83, X84, X85, X86, X87, X88, X89, X91, X92, X93, X94, X95, X96, X97, X98, X99], Position) :- getrow(Position, R), (R = 1 , valide9(X11, X12, X13, X14, X15, X16, X17, X18, X19); R = 2 , valide9(X21, X22, X23, X24, X25, X26, X27, X28, X29); R = 3 , valide9(X31, X32, X33, X34, X35, X36, X37, X38, X39); R = 4 , valide9(X41, X42, X43, X44, X45, X46, X47, X48, X49); R = 5 , valide9(X51, X52, X53, X54, X55, X56, X57, X58, X59); R = 6 , valide9(X61, X62, X63, X64, X65, X66, X67, X68, X69); R = 7 , valide9(X71, X72, X73, X74, X75, X76, X77, X78, X79); R = 8 , valide9(X81, X82, X83, X84, X85, X86, X87, X88, X89); R = 9 , valide9(X91, X92, X93, X94, X95, X96, X97, X98, X99)), getcol(Position, C), (C = 1 , valide9(X11, X21, X31, X41, X51, X61, X71, X81, X91); C = 2 , valide9(X12, X22, X32, X42, X52, X62, X72, X82, X92); C = 3 , valide9(X13, X23, X33, X43, X53, X63, X73, X83, X93); C = 4 , valide9(X14, X24, X34, X44, X54, X64, X74, X84, X94); C = 5 , valide9(X15, X25, X35, X45, X55, X65, X75, X85, X95); C = 6 , valide9(X16, X26, X36, X46, X56, X66, X76, X86, X96); C = 7 , valide9(X17, X27, X37, X47, X57, X67, X77, X87, X97); C = 8 , valide9(X18, X28, X38, X48, X58, X68, X78, X88, X98); C = 9 , valide9(X19, X29, X39, X49, X59, X69, X79, X89, X99)), getsqr(Position, Q), (Q = 1 , valide9(X11, X12, X13, X21, X22, X23, X31, X32, X33); Q = 2 , valide9(X14, X15, X16, X24, X25, X26, X34, X35, X36); Q = 3 , valide9(X17, X18, X19, X27, X28, X29, X37, X38, X39); Q = 4 , valide9(X41, X42, X43, X51, X52, X53, X61, X62, X63); Q = 5 , valide9(X44, X45, X46, X54, X55, X56, X64, X65, X66); Q = 6 , valide9(X47, X48, X49, X57, X58, X59, X67, X68, X69); Q = 7 , valide9(X71, X72, X73, X81, X82, X83, X91, X92, X93); Q = 8 , valide9(X74, X75, X76, X84, X85, X86, X94, X95, X96); Q = 9 , valide9(X77, X78, X79, X87, X88, X89, X97, X98, X99)). % ------------------------------------------------------------------------------ endbrett(L) :- not(mitglied(u, L)), valide(L). zug(Brett_alt, Position, Brett_neu) :- zahl(Element_neu), % waehle einen neuen Wert setzeelement(Position, Brett_alt, Element_neu, Brett_neu), % bilde neues Brett validePos(Brett_neu, Position). % ...wenn möglich sudoku(SolvedBrett, SolvedBrett) :- endbrett(SolvedBrett). sudoku(Brett, SolvedBrett) :- getsingleposition(Brett, Position), !, zug(Brett, Position, Gezogen), sudoku(Gezogen, SolvedBrett). sudoku(Brett, SolvedBrett) :- getfirstfree(Brett, Position), !, zug(Brett, Position, Gezogen), sudoku(Gezogen, SolvedBrett). % |1 |2 |3 |4 |5 |6 |7 |8 |9 | % ein Brett brett([u,1,5, 4,u,u, u,9,7, u,u,u, 9,u,8, 5,u,u, u,u,8, 2,5,u, u,u,6, 1,u,u, 6,9,2, u,u,u, 8,u,3, 5,u,7, u,2,u, u,7,u, u,u,u, u,6,u, 3,u,9, 8,u,u, 1,u,u, 5,u,u, 7,u,u, u,u,8, u,u,u, u,u,4, 2,u,u]). % Brett40 mit 48 vorgegebenen Zahlen brett40([8,3,4, 7,6,2, 5,9,u, 9,u,u, 3,u,4, 7,2,8, u,u,1, u,5,8, 3,u,4, u,8,2, u,9,7, 6,1,3, 7,u,3, u,u,6, u,4,u, 6,4,9, u,u,1, 8,5,7, 3,u,5, u,u,9, u,u,u, 1,9,u, u,u,3, u,7,u, 4,6,u, u,u,5, u,3,u]). % Brett79 mit 32 vorgegebenen Zahlen brett79([3,u,8, u,6,u, u,u,5, u,u,u, 5,u,u, u,u,u, 1,u,u, u,u,8, u,u,2, u,u,3, 8,7,u, 5,u,u, u,u,u, 1,3,9, 4,u,6, u,9,u, 4,u,u, 3,7,8, 7,u,u, 9,u,u, u,5,u, 8,u,u, u,u,7, u,1,u, u,1,u, u,8,4, 2,u,u]). % Brett148 mit 28 vorgegebenen Zahlen brett148([4,u,u, 2,7,u, u,u,u, 9,u,u, u,1,u, u,5,u, u,u,u, u,5,6, 8,u,u, u,2,u, 4,u,u, 3,u,u, u,8,1, u,u,u, u,2,6, u,u,u, 5,u,u, u,1,u, u,u,u, u,u,5, 7,u,1, 8,4,u, u,u,u, 6,u,2, u,u,u, 8,2,u, u,9,u]). % Anfragen % ?- brett1(X), time(sudoku(X, L)).