% permutations: one list is a reordering of the items in the other list
% perm(-List1, +List2)
perm([],[]).
perm(X,[Y|Z]):-select(X,Y,R),perm(R,Z).

% if L is list of items in 1..9 then p(L)) iff  L is a permuation of 1..9
p(L):-count(L, [1,1,1,1,1,1,1,1,1]).

count([], [0,0,0,0,0,0,0,0,0]):-!.
count([1 | R], [1,C2,C3,C4,C5,C6,C7,C8,C9]):- count(R,[0,C2,C3,C4,C5,C6,C7,C8,C9]),!.
count([2 | R], [C1,1,C3,C4,C5,C6,C7,C8,C9]):- count(R,[C1,0,C3,C4,C5,C6,C7,C8,C9]),!.
count([3 | R], [C1,C2,1,C4,C5,C6,C7,C8,C9]):- count(R,[C1,C2,0,C4,C5,C6,C7,C8,C9]),!.
count([4 | R], [C1,C2,C3,1,C5,C6,C7,C8,C9]):- count(R,[C1,C2,C3,0,C5,C6,C7,C8,C9]),!.
count([5 | R], [C1,C2,C3,C4,1,C6,C7,C8,C9]):- count(R,[C1,C2,C3,C4,0,C6,C7,C8,C9]),!.
count([6 | R], [C1,C2,C3,C4,C5,1,C7,C8,C9]):- count(R,[C1,C2,C3,C4,C5,0,C7,C8,C9]),!.
count([7 | R], [C1,C2,C3,C4,C5,C6,1,C8,C9]):- count(R,[C1,C2,C3,C4,C5,C6,0,C8,C9]),!.
count([8 | R], [C1,C2,C3,C4,C5,C6,C7,1,C9]):- count(R,[C1,C2,C3,C4,C5,C6,C7,0,C9]),!.
count([9 | R], [C1,C2,C3,C4,C5,C6,C7,C8,1]):- count(R,[C1,C2,C3,C4,C5,C6,C7,C8,0]),!.

% diff(L1,L2) is true when no item in L1 equals the same numebered item in L2
diff([X],[Y]):-X\=Y, !.
diff([X|R1], [Y|R2]):-X\=Y, diff(R1,R2), !.

nonmember(_,[]):- !.
nonmember(X,[Y|Z]):-X\=Y, nonmember(X,Z), !.

% find perm with items not in columns perm(-Digits,+Row,-OldCols,+NewCols)
perm([],[],Cols, Cols).
perm(X,[Y|Z], [C|D], [[Y|C]|E]):-select(X,Y,R),nonmember(Y, C), perm(R,Z,D,E).

sudoku(Board):-Board=[R1,R2,R3,R4,R5,R6,R7,R8,R9],
     
	R1=[X11,X12,X13, X14,X15,X16, X17,X18,X19],
	R2=[X21,X22,X23, X24,X25,X26, X27,X28,X29],
	R3=[X31,X32,X33, X34,X35,X36, X37,X38,X39],

	R4=[X41,X42,X43, X44,X45,X46, X47,X48,X49],
	R5=[X51,X52,X53, X54,X55,X56, X57,X58,X59],
	R6=[X61,X62,X63, X64,X65,X66, X67,X68,X69],

	R7=[X71,X72,X73, X74,X75,X76, X77,X78,X79],
	R8=[X81,X82,X83, X84,X85,X86, X87,X88,X89],
	R9=[X91,X92,X93, X94,X95,X96, X97,X98,X99],

      D=[1,2,3,4,5,6,7,8,9], %the digits
      % D=[9,8,7,6,5,4,3,2,1], %the digits

% the givens LA Times Sunday Sep 25 2005 
	R1=[6,_,_, 9,_,7, _,_,3],
	R2=[_,_,_, 6,_,3, _,_,_],
	R3=[7,_,1, _,_,_, 9,_,6],

	R4=[_,_,7, 3,_,1, 4,_,_],
	R5=[4,_,_, _,_,_, _,_,8],
	R6=[_,_,5, 7,_,2, 6,_,_],

	R7=[2,_,9, _,_,_, 8,_,7],
	R8=[_,_,_, 2,_,6, _,_,_],
	R9=[3,_,_, 4,_,8, _,_,1],

 
  % the rules of Sudoku
     C0=[[],[],[],[],[],[],[],[],[]], % upside down columns
   %Rows
     perm(D,R1,C0, C1),
     write('R1'), write_ln(R1), %status report
     perm(D,R2,C1, C2),
     perm(D,R3,C2, C3),
   % Top 3 Boxes
     p([X11,X12,X13,X21,X22,X23,X31,X32,X33]),
	write('1'), % progress report
     p([X14,X15,X16,X24,X25,X26,X34,X35,X36]),
	write('2'),
     p([X17,X18,X19,X27,X28,X29,X37,X38,X39]),
	write_ln('3'),

     perm(D,R4,C3,C4),
     perm(D,R5,C4,C5),
     perm(D,R6,C5,C6),
   % Middle 3 Boxes
     p([X41,X42,X43,X51,X52,X53,X61,X62,X63]), 
	write('4'),
     p([X44,X45,X46,X54,X55,X56,X64,X65,X66]),  
	write_ln('5'),
     p([X47,X48,X49,X57,X58,X59,X67,X68,X69]),
	 write_ln('6'),

     perm(D,R7,C6,C7),
    perm(D,R8,C7,C8),
     perm(D,R9,C8,_),
   % Bottom 3 Boxes
     p([X71,X72,X73,X81,X82,X83,X91,X92,X93]),  
	write('7'),
     p([X74,X75,X76,X84,X85,X86,X94,X95,X96]),  
	write('8'),
     p([X77,X78,X79,X87,X88,X89,X97,X98,X99]),
	write_ln('9'),
   %Columns
    write_ln('---'),
%     write_ln(C9),
     write_ln('---'),
     write_ln(R1),
     write_ln(R2),
     write_ln(R3),
     write_ln(R4),
     write_ln(R5),
     write_ln(R6),
     write_ln(R7),
     write_ln(R8),
     write_ln(R9).