This article is about a Prolog application that solves monograms also known as "japanese crosswords". As this programing language is quite special and follows logic programing we should think in the special way also. When it comes to solving puzzles in Prolog, it usually means that program will check all possible variants to find one that suits the goal. This time we'll do exactly the same :). Let's break our program into next pieces:
- Input
- Generation of all possible variants
- Search for solution
- Output
Source code can be found at Logic-Functional-Programming repository.
Please none!!! this is a first part of the publication. If you want to read the 2nd part, please go to "Nonogram solver in Prolog. Combinations matching." by McAngel(Ihor Mykhalevych).
All the next explanations will be made on this prototype:
11
221 5321
1222922221
——————————
1| # |
3| ### |
1 2| # ## |
1 3| # ### |
2 4| ## #### |
7| ####### |
1| # |
10|##########|
8| ######## |
——————————
Input
Input should be straight-forward. We'll accept input as two lists: data about rows, and data about columns. Each item of a list will be a sub-list that will contain numerical values that are on the side on the row/at the top of the column. For our example it will look like this:
[[1], [3], [1, 2], [1, 3], [2, 4], [7], [1], [10], [8]], %for rows
[[1], [2, 2], [1, 2, 2], [1, 1, 2], [9], [5, 2], [3, 2], [2, 2], [1, 2], [1]] %for columns.This way we also can easily find the number of rows and rolls by checking lists length.
To make a workflow even more easy we'll add next predicates as a data source:
To make a workflow even more easy we'll add next predicates as a data source:
nonogram(smile,
[[1, 1], [1, 1], [3]],
[[1], [1, 1], [1], [1, 1], [1]]).Now when we have input let's go to the next step and figure out how to get all the possible solutions.
Generation of all possible variants
Now we are going to create all possible configurations that will satisfy our row and column rules separately so later we can se if any of that match. For this step we'll use next data model:
[line(Number_of_line, List_of_configurations), line(…)]this way if we have 5th row with a numbers [2, 3] at the side, and the length (number of columns) 7 then a list element will look like this:
line(5, [[1, 2, 4, 5, 6], [1, 2, 5, 6, 7], [2, 3, 5, 6, 7]])because on the 5th row we can have 3 combinations:
1234567
1st: |## ### |
2nd: |## ###|
3rd: | ## ###|Now let's look how our request line will look by now:
length(Rows, VSize),
length(Cols, HSize),
generate(RowCombos, Rows, HSize),
generate(ColCombos, Cols, VSize).Where:
- RowCombos, ColCombos: arrays of line facts generated from Rows and Cols.
- Rows, Cols: our starting data.
- length/2: predicate that calculates the size of the list.
- HSize, VSize: horizontal and vertical sizes of our nonogram.
- generate/3: predicate that takes line(row or column) with combinations, line with starting data, and line's length.
The one thing that we do not have is generate/3, so let's think about how it should look like. As you've already guessed we'll do it with recursion, and as we need to know a number of the line that we're processing, we'll make similar operator, that will be called by generate/3, but will take one more functor with will represent the number of line. Let's call it generate_supp/4, as support for generate/3.
generate(LineCombos, Lines, Size) :- generate_supp(1, LineCombos, Lines, Size).So we'll start with 1st row.
Cool, now as we know what generate/3 is let's implement generate_supp/4 ;)
generate_supp(_, [], [], _).
generate_supp(LineNumber, [line(LineNumber,Combos)|LineCombosTail], [Line|LinesTail], Size) :-
findall(Combo, combinate(Line, Size, Combo), Combos),
NextLineNumber is LineNumber + 1,
generate_supp(NextLineNumber, LineCombosTail, LinesTail, Size).Whew… now that was tuff. The stop factor is an empty line list, this means that LineCombos list will be empty too. Else we take heads of Lines and LineCombos lists and do "magic" with them, increment LinesNumber, and do all the stuff again with list's tails. Let's look at the "magic" closer. First of all we need to implement a new predicate combinate/3 that gives us some combination according to information given about line and it's length. findall/3 is built-in predicate which will give us Combos: an array that will contain every Combo that satisfies combinate(Line, Size, Combo) statement. Now let's implement the combinate/3, it's the tuffest stuff in this part.
Let's look what the solution should look like depending on different conditions:
As you can see, combinate/3 uses a support predicate too. Now let's look at the more verbose version of it to figure how it works more easily:
This is an explanation of arguments and other variables of written above predicates.
By now we'll have two arrays of combinations by rows and by columns. All we need to do is find out which of them are correct.
Continue to Search for solution and Output in the 2nd part: "Nonogram solver in Prolog. Combinations matching." by McAngel(Ihor Mykhalevych).
Source code can be found at Logic-Functional-Programming repository.
Let's look what the solution should look like depending on different conditions:
- We get a row with only one digit that is 0. I don't remember if I've ever encountered such condition in japanese crosswords, but theoretically it's possible, but it's more exception than an option. Anyway it should be equivalent to an empty combinations list.
- We get a row with only one digit (let it be Number). So if will show it visually it vill look something like this:
so we'll have Size - Number + 1 options, each option will start on the position from array [1, Size - Number + 1] and will be Number positions long. I think we can coupe with it.[###____]
[_###___]
…
[____###] - What if we get an array of the conditions. Let's try to illustrate how will look options when all the blocks are separated with only one space:
It's very similar to our previous condition so we already know how many options like this are out there. Now let's look what will happen if we'll fix our first block in some of it's possible positions and try to move all the other stuff as it is:[#_##_###____]
[_#_##_###___]
…
[____#_##_###]
I've put the separator on purpose, so you can see that our new problem is the same as it's parent, this means recursion, and so we can write this down in Prolog. The length of our cortege that has only one space separators is equal to Sum_line_elements + Amount_line_elements - 1, we will have to pass from what position we start and all the other nasty things.[#|_##_###____]
[#|__##_###___]
…
[#|_____##_###]
[_#|_##_###___]
[_#|__##_###__]
…
[_#|____##_###]
We will also need to implement three supporting predicates.
In the end we'll end up this a code like this:
- Sum of list's elements:
sum(0, []). sum(Sum,[Head|Tail]):-sum(K,Tail),Sum is K+Head. - Number that is between two others:
% inRange(I, Low, High) I is between Low and High
inRange(Low, Low, High) :- Low =< High.
inRange(I, Low, High) :- Low < High, LessLow is Low + 1, inRange(I, LessLow, High). - List of consequent integers from the specified range:
range([N], N, N).
range([Low|Tail], Low, High) :- Low < High, LesLow is Low + 1, range(Tail, LesLow, High).
In the end we'll end up this a code like this:
combinate(Line, Size, Combo) :-
sum(Line, Sum),
length(Line, Length),
CortegeLength is Sum + Length - 1,
combinate_supp(Line, 1, CortegeLength, Size, [], Combo).
combinate_supp([0], _, _, _, _, []).
combinate_supp([Number], Start, _, Size, PreCombo, Combo) :-
End is Size - Number + 1,
inRange(First, Start, End),
Last is First + Number - 1,
range(EndCombo, First, Last),
append(PreCombo, EndCombo, Combo).
combinate_supp([Number|Tail], Start, CortegeLength, Size, PreCombo, Combo) :-
End is Size - CortegeLength + 1,
inRange(First, Start, End),
Last is First + Number - 1,
range(EndCombo, First, Last),
NewCortegeLength is CortegeLength - Number - 1,
NewStart is Last + 2,
append(PreCombo, EndCombo, LowCombo),
combinate_supp(Tail, NewStart, NewCortegeLength, Size, LowCombo, Combo).As you can see, combinate/3 uses a support predicate too. Now let's look at the more verbose version of it to figure how it works more easily:
combinate_supp(Line, StartPosition, CortegeLength, FrameSize, PreviousCombo, FinalCombo)This is an explanation of arguments and other variables of written above predicates.
- Line: list of line condition.
- StartPosition(Start): A position in frame(line on the nonogram), where we can start to insert our elements.
- CortegeLength: a length of all segments put together. e.i. separated only by one space.
- FrameSize(Size): a size of a frame(line on the nonogram).
- PreviousCombo(PreCombo): combo generated at the previous part of the frame(before Start).
- FinalCombo(Combo): resulting combo of this calculation.
- End: possible farthest point of the beginning of the cortege.
- First: a position of the beginning on the first segment from cortege. Value between Start and End.
- Last: a position of the beginning on the first segment from cortege. Greater then first by the length of that first segment.
- EndCombo: range representing position of the first segment from cortege. Defined by First and Last.
- NewCortegeLength: a length of all segments put together (separated only by one space), without the first one.
- NewStart: A start position for a new cortege (without first segment).
- LowCombo: A current combo that will be appended by the next calls to combinate/4.
By now we'll have two arrays of combinations by rows and by columns. All we need to do is find out which of them are correct.
Continue to Search for solution and Output in the 2nd part: "Nonogram solver in Prolog. Combinations matching." by McAngel(Ihor Mykhalevych).
Source code can be found at Logic-Functional-Programming repository.
thanx dude.it was very helpful.
ReplyDeleteYou are welcome
Delete