Sudoku solver example written in Jalog and Java
This example demonstrates how to use Jalog and Java language together. In this example a Sudoku solving algorithm is implemented using Jalog. Java is used to specify the Sudoku problem and to display the solution.
Mikko Levanto, Ari Okkonen
It is simplest to download these to the same folder.
javac -cp jalog.jar SolveSudoku.java
This sould create SolveSudoku.class.
java -cp "jalog.jar;." SolveSudoku
This should display something like
SolveSudoku 0.1 by Ari Okkonen & Mikko Levanto 2019-09-17
Problem
-------------------------
| 8 | 2 | 3 |
| 9 4 | 6 | 1 2 |
| 5 | 7 1 | 6 |
-------------------------
| | | 7 |
| 6 2 | 3 | 8 |
| 4 8 | 1 9 | 6 5 |
-------------------------
| 6 8 | 7 5 | 9 4 |
| 1 2 | 4 | 7 |
| | 1 8 | 6 |
-------------------------
Solution
-------------------------
| 8 1 6 | 9 2 5 | 4 3 7 |
| 9 7 4 | 6 8 3 | 5 1 2 |
| 2 5 3 | 4 7 1 | 8 9 6 |
-------------------------
| 5 3 1 | 8 4 6 | 2 7 9 |
| 6 9 2 | 5 3 7 | 1 8 4 |
| 4 8 7 | 2 1 9 | 3 6 5 |
-------------------------
| 3 6 8 | 7 5 2 | 9 4 1 |
| 1 2 9 | 3 6 4 | 7 5 8 |
| 7 4 5 | 1 9 8 | 6 2 3 |
-------------------------
SolveSudoku.java.
The Jalog part is in the file sudoku_solver_component.pro.
myJalog. The main
method loads the Jalog program, prints the problem, solves the problem using
Jalog code, and prints the result. Finally the Jalog program is purged from
memory.
The method print_sudoku formats the Sudoku data to display.
solve_sudoku converts the problem data to
Jalog.Term data structure suitable for processing by Jalog.
In nested loops the the two dimensional Java array of integers is converted to
a Jalog list of lists of integers. Each Jalog integer is created with
the Jalog.integer method. The Jalog.open method is
used to create empty positions that are later filled by the solution
algorithm. The lists are created using the Jalog.list method.
The prepared problem is in the variable board.
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
value = sudoku_problem[i][j];
if(value == 0) {
line[j] = Jalog.open();
} else {
line[j] = Jalog.integer(sudoku_problem[i][j]);
}
}
matrix[i] = Jalog.list(line);
}
board = Jalog.list(matrix);
call method returns true. In case of failure the
call method returns false. In case of exception the
call method throws Jalog.Exit.
try {
if (myJalog.call("sudoku", board))
{
Getting the solution
} else { // fail
Report solution not found
}
} catch (Jalog.Exit e) {
Report exception
}
The call of the solution algorithm in the if clause. The call method of the instantiated engine is called with the predicate name sudoku and the prepared parameter board.
true branch of the if statement the result is transferred
from board to Java variable sudoku_solution in nested
loops. The lists are converted to Java arrays using getElements
method. The type of elements is checked using getType method.
Integers are converted to Java long values using the
getIntegerValue method and then typecasted to int.
matrix = board.getElements();
for (i = 0; i < 9; i++) {
line = matrix[i].getElements();
for (j = 0; j < 9; j++) {
element = line[j];
if (element.getType() == Jalog.INTEGER) {
sudoku_solution[i][j] = (int)element.getIntegerValue();
} else {
sudoku_solution[i][j] = 0; // error in algorithm
}
}
}
If the solution contains zeros, there is an apparent error in the algorithm.
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
sudoku_solution[i][j] = sudoku_problem[i][j];
}
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
sudoku_solution[i][j] = 0;
}
}
The main predicate sudoku is called from Java code. The actual parameter board is received to the formal paremeter rows.
The diagram below shows the calling hiearchy of the predicates. In addition some predicates are recursive.
sudoku(Rows):- make_links(Rows, Cols, SubSquares), solve(Rows, Cols, SubSquares, 1, 1, 1, 0).
/* make_links:
Create matrices for columns and sub-squares of the original matrix for
easy access */
make_links(Rows, Cols, SubSquares) :-
make_open_matrix(Cols, 9, 9),
make_open_matrix(SubSquares, 9, 9),
make_link(Rows, Cols, SubSquares, 1, 1).
make_open_matrix([],0,_) :- !. make_open_matrix([List|Matrix], NRow, NCol) :- make_open_list(List, NCol), N1Row = NRow - 1, make_open_matrix(Matrix, N1Row, NCol).
make_open_list([],0) :- !. make_open_list([_Item|List], NCol) :- N1Col = NCol - 1, make_open_list(List,N1Col).
/* make_link: Unify corresponding variables of row, column, and sub-square
matrices. */
make_link(_, _, _, 10, _) :- !.
make_link(Rows, Cols, SubSquares, IRow, 10) :-
!,
IRow_1 = IRow + 1,
make_link(Rows, Cols, SubSquares, IRow_1, 1).
make_link(Rows, Cols, SubSquares, IRow, ICol) :-
element_at(Rows, IRow, Row),
element_at(Row, ICol, TheElement),
element_at(Cols, ICol, Col),
element_at(Col, IRow, TheElement),
sub_square_index(IRow, ICol, ISSRow),
sub_square_elem_index(IRow, ICol, ISSCol),
element_at(SubSquares, ISSRow, SubSquare),
element_at(SubSquare, ISSCol, TheElement),
ICol_1 = ICol + 1,
make_link(Rows, Cols, SubSquares, IRow, ICol_1).
/* Find the index within the sub-square for element IRow, ICol */ sub_square_elem_index(IRow, ICol, ISSE) :- ISSE = 1 + ((IRow - 1) mod 3) * 3 + (ICol - 1) mod 3 .
solve(Rows, _Cols, _SubSquares, 10, _ICol, _IChoices, 0) :- matrix_all_bound(Rows), !. % Solution found! solve(_Rows, _Cols, _SubSquares, 10, _ICol, _IChoices, 0) :- !, fail. solve(_Rows, _Cols, _SubSquares, 10, _ICol, IChoices, IChoices) :- !, % No solution for this branch fail. solve(Rows, Cols, SubSquares, IRow, _ICol, IChoices, Max) :- IRow > 9, IChoices_1 = IChoices + 1, !, solve(Rows, Cols, SubSquares, 1, 1, IChoices_1, Max). solve(Rows, Cols, SubSquares, IRow, ICol, IChoices, Max) :- ICol > 9, !, IRow_1 = IRow + 1, !, solve(Rows, Cols, SubSquares, IRow_1, 1, IChoices, Max). solve(Rows, Cols, SubSquares, IRow, ICol, IChoices, Max) :- element_at(Rows, IRow, Row), element_at(Row, ICol, ThisElement), not(bound(ThisElement)), element_at(Cols, ICol, Col), sub_square_index(IRow, ICol, ISubSquare), element_at(SubSquares, ISubSquare, SubSquare), find_choices(Row, Col, SubSquare, Choices), len(Choices, IChoicesActual), !, solve_1(Rows, Cols, SubSquares, IRow, ICol, IChoices, Max, Choices, IChoicesActual, ThisElement). solve(Rows, Cols, SubSquares, IRow, ICol, IChoices, Max) :- ICol_1 = ICol + 1, !, solve(Rows, Cols, SubSquares, IRow, ICol_1, IChoices, Max).
/* Solve ThisElement */ solve_1(Rows, Cols, SubSquares, _IRow, _ICol, IChoices, _Max, Choices, IChoicesActual, ThisElement) :- IChoicesActual = Ichoices, !, pick_one(Choices, Choice), ThisElement = Choice, solve(Rows, Cols, SubSquares, 1, 1, 1, 0), !. solve_1(Rows, Cols, SubSquares, IRow, ICol, IChoices, Max, _Choices, IChoicesActual, _) :- ICol_1 = ICol + 1, max(Max, IChoicesActual, MaxNew), !, solve(Rows, Cols, SubSquares, IRow, ICol_1, IChoices, MaxNew).
max(A, B, A) :- A > B, !. max(_, B, B).
pick_one([I|_], I). pick_one([_|Rest], I) :- pick_one(Rest, I).
element_at([Elem|_], 1, Elem) :- !. element_at([_|Rest], N, Elem) :- Nm1 = N - 1, element_at(Rest, Nm1, Elem).
/* Find the sub-square for element IRow, ICol */ sub_square_index(IRow, ICol, ISubSquare) :- ISubSquare = 1 + ((IRow - 1) div 3) * 3 + (ICol - 1) div 3 .
/* find_choices: Find the possible choices for this location */
find_choices(Row, Col, SubSquare, Choices) :-
find_rest_choices(Row, Col, SubSquare, 1, Choices).
find_rest_choices(_, _, _, I, []) :- I > 9, !. find_rest_choices(Row, Col, SubSquare, I, [I|Rest]) :- not(bound_member(I, Row)), not(bound_member(I, Col)), not(bound_member(I, SubSquare)), !, I1 = I + 1, find_rest_choices(Row, Col, SubSquare, I1, Rest). find_rest_choices(Row, Col, SubSquare, I, Rest) :- !, I1 = I + 1, find_rest_choices(Row, Col, SubSquare, I1, Rest).
/* Does the list contain this number already? */ bound_member(I, [I1|_]) :- bound(I1), I = I1, !. bound_member(I, [_|Rest]) :- bound_member(I, Rest).
len([], 0) :- !. len([_|Rest], I1) :- len(Rest, I), I1 = I + 1.
matrix_all_bound([]) :- !. matrix_all_bound([List|More]) :- list_all_bound(List), matrix_all_bound(More).
list_all_bound([]) :- !. list_all_bound([H|T]) :- bound(H), list_all_bound(T).