% % ECLiPSe sample code - Sudoku problem % % This is a puzzle, originating from Japan, where you have a % 9x9 grid, consisting of 9 3x3 sub-grids. The challenge is % to fill the grid with numbers from 1 to 9 such that every row, % every column, and every 3x3 sub-grid contains the digits 1 to 9. % Some of these numbers are given, which is the way different % instances of the problem are made. The solution is usually unique. % % Compile this file with ECLiPSe and call e.g. % :- solve(1). % % Author: Joachim Schimpf, IC-Parc % :- lib(ic). :- import alldifferent/1 from ic_global. solve(ProblemName) :- problem(ProblemName, Board), print_board(Board), sudoku(Board), labeling(Board), print_board(Board). sudoku(Board) :- dim(Board, [N,N]), Board :: 1..N, ( for(I,1,N), param(Board) do alldifferent(Board[I,*]), alldifferent(Board[*,I]) ), NN is integer(sqrt(N)), ( multifor([I,J],1,N,NN), param(Board,NN) do alldifferent(concat(Board[I..I+NN-1, J..J+NN-1])) ). print_board(Board) :- dim(Board, [N,N]), ( for(I,1,N), param(Board,N) do ( for(J,1,N), param(Board,I) do X is Board[I,J], ( var(X) -> write(" _") ; printf(" %2d", [X]) ) ), nl ), nl. %---------------------------------------------------------------------- % Sample data %---------------------------------------------------------------------- problem(1, []( [](_, _, 2, _, _, 5, _, 7, 9), [](1, _, 5, _, _, 3, _, _, _), [](_, _, _, _, _, _, 6, _, _), [](_, 1, _, 4, _, _, 9, _, _), [](_, 9, _, _, _, _, _, 8, _), [](_, _, 4, _, _, 9, _, 1, _), [](_, _, 9, _, _, _, _, _, _), [](_, _, _, 1, _, _, 3, _, 6), [](6, 8, _, 3, _, _, 4, _, _))). problem(2, []( [](_, _, 3, _, _, 8, _, _, 6), [](_, _, _, 4, 6, _, _, _, _), [](_, _, _, 1, _, _, 5, 9, _), [](_, 9, 8, _, _, _, 6, 4, _), [](_, _, _, _, 7, _, _, _, _), [](_, 1, 7, _, _, _, 9, 5, _), [](_, 2, 4, _, _, 1, _, _, _), [](_, _, _, _, 4, 6, _, _, _), [](6, _, _, 5, _, _, 8, _, _))). problem(3, []( [](_, _, _, 9, _, _, _, _, _), [](_, _, 7, _, 6, _, 5, _, _), [](_, _, 3, 5, _, _, _, 7, 9), [](4, _, 5, _, _, 9, _, _, 1), [](8, _, _, _, _, _, _, _, 7), [](1, _, _, 6, _, _, 9, _, 8), [](6, 4, _, _, _, 8, 7, _, _), [](_, _, 9, _, 1, _, 2, _, _), [](_, _, _, _, _, 7, _, _, _))). problem(4, []( [](_, 5, _, _, _, 1, 4, _, _), [](2, _, 3, _, _, _, 7, _, _), [](_, 7, _, 3, _, _, 1, 8, 2), [](_, _, 4, _, 5, _, _, _, 7), [](_, _, _, 1, _, 3, _, _, _), [](8, _, _, _, 2, _, 6, _, _), [](1, 8, 5, _, _, 6, _, 9, _), [](_, _, 2, _, _, _, 8, _, 3), [](_, _, 6, 4, _, _, _, 7, _))). % Problems 5-8 are harder, taken from % http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html problem(5, []( [](_, 9, 8, _, _, _, _, _, _), [](_, _, _, _, 7, _, _, _, _), [](_, _, _, _, 1, 5, _, _, _), [](1, _, _, _, _, _, _, _, _), [](_, _, _, 2, _, _, _, _, 9), [](_, _, _, 9, _, 6, _, 8, 2), [](_, _, _, _, _, _, _, 3, _), [](5, _, 1, _, _, _, _, _, _), [](_, _, _, 4, _, _, _, 2, _))). problem(6, []( [](_, _, 1, _, 2, _, 7, _, _), [](_, 5, _, _, _, _, _, 9, _), [](_, _, _, 4, _, _, _, _, _), [](_, 8, _, _, _, 5, _, _, _), [](_, 9, _, _, _, _, _, _, _), [](_, _, _, _, 6, _, _, _, 2), [](_, _, 2, _, _, _, _, _, _), [](_, _, 6, _, _, _, _, _, 5), [](_, _, _, _, _, 9, _, 8, 3))). problem(7, []( [](1, _, _, _, _, _, _, _, _), [](_, _, 2, 7, 4, _, _, _, _), [](_, _, _, 5, _, _, _, _, 4), [](_, 3, _, _, _, _, _, _, _), [](7, 5, _, _, _, _, _, _, _), [](_, _, _, _, _, 9, 6, _, _), [](_, 4, _, _, _, 6, _, _, _), [](_, _, _, _, _, _, _, 7, 1), [](_, _, _, _, _, 1, _, 3, _))). problem(8, []( [](1, _, 4, _, _, _, _, _, _), [](_, _, 2, 7, 4, _, _, _, _), [](_, _, _, 5, _, _, _, _, _), [](_, 3, _, _, _, _, _, _, _), [](7, 5, _, _, _, _, _, _, _), [](_, _, _, _, _, 9, 6, _, _), [](_, 4, _, _, _, 6, _, _, _), [](_, _, _, _, _, _, _, 7, 1), [](_, _, _, _, _, 1, _, 3, _))). % this one is from http://www.skyone.co.uk/programme/pgefeature.aspx?pid=48&fid=129 problem(9, []( [](5, _, 6, _, 2, _, 9, _, 3), [](_, _, 8, _, _, _, 5, _, _), [](_, _, _, _, _, _, _, _, _), [](6, _, _, 2, 8, 5, _, _, 9), [](_, _, _, 9, _, 3, _, _, _), [](8, _, _, 7, 6, 1, _, _, 4), [](_, _, _, _, _, _, _, _, _), [](_, _, 4, _, _, _, 3, _, _), [](2, _, 1, _, 5, _, 6, _, 7))). % BBC Focus magazine October 2005 problem(10, []( [](_, 6, _, 3, 2, _, _, 7, _), [](4, 7, _, _, _, _, _, 3, 2), [](_, _, _, 9, _, _, 1, 4, 6), [](2, 4, _, 8, _, _, _, _, _), [](_, _, 8, _, _, _, 2, _, 1), [](1, _, _, _, _, 2, _, _, _), [](_, _, 2, 4, 7, 6, 8, _, _), [](6, 8, 9, _, _, _, _, 5, 4), [](_, _, _, _, 8, _, _, _, _))). problem(11, []( [](1, 8, 2, 7, 5, _, 3, _, 9), [](9, 5, 6, _, 3, _, _, 8, _), [](3, 4, 7, _, _, 9, _, 5, _), [](2, _, 3, _, 4, _, _, 9, 8), [](4, _, 8, 9, _, 2, 5, _, 3), [](5, 7, 9, 3, 6, 8, 1, 2, 4), [](_, 2, _, 4, 9, _, 8, 3, _), [](_, 3, _, _, 2, _, 9, _, 5), [](_, 9, _, _, _, 3, _, 1, _))). problem(20, []( [](7, _, 6, _, _, 8, _, _, _), [](_, _, _, 7, _, _, 5, 3, _), [](4, _, 3, _, _, 6, _, 7, _), [](_, 1, _, _, _, _, 4, _, 9), [](_, _, _, _, _, _, _, _, _), [](5, _, 2, _, _, _, _, 8, _), [](_, 6, _, 9, _, _, 1, _, 4), [](_, 8, 1, _, _, 5, _, _, _), [](_, _, _, 2, _, _, 3, _, 8))).