Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- outputFile('./neighbours_solved.txt').
- inputFile('./neighbours_unsolved.txt').
- /********************* dummy solution algorithms -> fill your correct algorithm here */
- :- use_module(library(clpfd)).
- valid_neighbors([_]).
- % If two numbers are neighbors, they must be within +1 of each other
- valid_neighbors([A, N, B|T]):-
- N #= 1,
- abs(A-B) #= 1, A #\= B,
- valid_neighbors([B|T]).
- % If two numbers are not neighbors, they cannot be within +1 of each other
- valid_neighbors([A, N, B|T]):-
- N #= 0,
- abs(A-B) #\= 1, A #\= B,
- valid_neighbors([B|T]).
- % Numbers have to be between 1 and the size of the board
- valid_numbers(Size, [H]):-
- H in 1..Size.
- valid_numbers(Size, [H, _|T]):-
- H in 1..Size,
- valid_numbers(Size, T).
- % Remove every other element of a list.
- r([], []).
- r([X], [X]).
- r([X,_|Xs], [X|Ys]):- r(Xs, Ys).
- % Use constraint propagation in order to solve boards
- % Inspired by the techniques used at https://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku
- solve(Size, Grid):-
- % A board with size 4 needs three extra lines for the neighbor rows.
- % A board of size N needs N * 2 - 1 lines to accommodate for the neighbor rows.
- N #= Size * 2 - 1, length(Grid, N),
- maplist(same_length(Grid), Grid),
- % The final solution is presented without neighbor symbols
- removeNeighbors(Grid, Solution),
- % Transpose the grid in order to apply the same rules to the columns
- transpose(Grid, Transposed),
- % Every other line of the grid is a value row
- removeNeighborLines(Grid, VRows),
- % The rules of the neighbor relations need to be upheld for the rows
- maplist(valid_neighbors, VRows),
- % Every other element of the value rows are values
- maplist(r, VRows, RowValues),
- % Each value can only appear once on every row
- maplist(all_distinct, RowValues),
- % Ensure all numbers on a line are valid.
- maplist(valid_numbers(Size), VRows),
- % Every other row of the columns is a value column
- removeNeighborLines(Transposed, VColumns),
- % The rules of the neighbor relations need to be upheld for the columns
- maplist(valid_neighbors, VColumns),
- % Ensure all numbers on a line are valid.
- maplist(valid_numbers(Size), VColumns),
- % Every other element of a value column is a value
- maplist(r, VColumns, Columns),
- % Each value can only appear once on every column
- maplist(all_distinct, Columns),
- % Assign a value from the available ones to each element of the rows
- maplist(label, Solution).
- doSolve(neighbors(size(Size),grid(Problem)),neighbors(size(Size),grid(Solution))):-
- solve(Size, Problem),
- removeNeighbors(Problem, Solution).
- removeNeighbors([P],[S]):- removeNeighborLines(P,S).
- removeNeighbors([P,_|PT],[S|ST]):- removeNeighborLines(P,S), removeNeighbors(PT,ST).
- removeNeighborLines([P],[P]).
- removeNeighborLines([P,_|PT],[P|ST]):- removeNeighborLines(PT,ST).
- /********************* writing the result */
- writeFullOutput(neighbors(size(N),grid(Grid))):-
- write('size '), write(N), write('x'), write(N), nl, writeGrid(Grid).
- writeGrid([]).
- writeGrid([E|R]):- writeGridLine(E), writeGrid(R).
- writeGridLine([]):- nl.
- writeGridLine([E|R]):- E=0, !, write(E), write(' '), writeGridLine(R).
- writeGridLine([E|R]):- write(E), write(' '), writeGridLine(R).
- /********************** reading the input */
- readProblem(neighbors(size(N),grid(Grid))):-
- findKW(size), readInt(N), readInt(M), M=N, GridLength is N*2-1, length(Grid,GridLength),
- readGridLines(GridLength,Grid).
- findKW(KW):- string_codes(KW,[H|T]), peek_code(H), readKW([H|T]), !.
- findKW(_):- peek_code(-1), !, fail.
- findKW(KW):- get_code(_), findKW(KW).
- readKW([]):- get_code(_).
- readKW([H|T]):- get_code(H), readKW(T).
- readGridLines(N,[A]):- length(A,N), readGridLine(A).
- readGridLines(N,[A,B|T]):- length(A,N), readGridLine(A), length(B,N), readNeighborLine(B), readGridLines(N,T).
- readGridLine([N]):- readInt(I), makeHint(I,N).
- readGridLine([N,X|T]):- readInt(I), makeHint(I,N), get_code(M), translate(M,X), !, readGridLine(T).
- readNeighborLine([X]):- get_code(M), translate(M,X), !.
- readNeighborLine([X,0|T]):- get_code(M), translate(M,X), get_code(_), get_code(_), get_code(_), !, readNeighborLine(T).
- makeHint(X,X):- X>0.
- makeHint(0,_).
- translate(-1,'ERROR: EOF').
- translate(120,1).
- translate(32,0).
- translate(X,X).
- translate(X,E):- whitespace(X), get_code(Y), translate(Y,E).
- translate(X,E):- string_codes(E,[X]).
- whitespace(10). whitespace(12). whitespace(32).
- readInt(N):- get_code(M), handleCode(M,N).
- handleCode(M,N):- is_number_code(M,N1), !, continueInt(N1,N).
- handleCode(-1,_):- !, fail. /* EOF */
- handleCode(_,N):- readInt(N).
- continueInt(O,N):- get_code(M), is_number_code(M,M1), !, H is 10*O+M1, continueInt(H,N).
- continueInt(N,N).
- is_number_code(N, N1):- N>=48, N<58, N1 is N-48.
- is_number_code(95,0).
- /*********************** global control: starting the algorithm and the reading */
- run:- inputFile(IF), see(IF), outputFile(F), tell(F), findKW(puzzles), readInt(N), write('puzzles '), write(N), nl, solveProblems(N), told, seen, !.
- run:- told, seen. /* close the files */
- solveProblems(0).
- solveProblems(N):- N>0, readProblem(P), doSolve(P, S), writeFullOutput(S), !, N1 is N-1, solveProblems(N1).
- :- nl,nl,write(' try running "?- run."'), nl,nl,nl.
- :- run.
- :- halt.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement