Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Problem with delayed goals

Status
Not open for further replies.

Neztov

Programmer
May 13, 2009
3
0
0
BE
Hello,

I'm trying to solve the Japanese puzzle kuromasu with prolog (Eclipse clp).

In this game you have to colour every cell of a grid black or white.
One of this game constraints is that you may not have two black cells next to each other. (this is atm the only constraint I have programmed)

My idea in programming this with prolog was to make a WhiteList and a BlackList.
These consist of all the cells who are white/black.

Initially you know only that the numbered cells are white.
So I suspend the other cells of being a member of either WhiteList or BlackList.

The initial creation (create_puzzle) works fine and and with 17 delayed goals exactly as expected.

The problem start when I'm putting the constraints on my lists. For example if I say no_neighbours(BlackList) this results in an empty list, because it doesn't wait until the delayed goals are solved.

What I like to find out is a way that every time the search function labels a new cell to be black it checks if the BlackList has no_neighbours.

I know this is quite an open question but any suggestion is welcome, even if it is a completely different perspective.

This is my code so far:

Code:
:- lib(ic).
:- lib(lists).
:- lib(arrays).

kuromasu(Id, Board, BlackList, WhiteList) :-
	puzzle(Id, Dim, NumberList),
	create_puzzle(NumberList, Dim, Board, BlackList, WhiteList),
	constraints(Board, NumberList, BlackList, WhiteList, Dim),
	search(Board),
	print_board(Board).


create_puzzle(NumberList, Dim, Board, BlackList, WhiteList) :-
	dim(Board, [Dim,Dim]),
	
	( foreach((I,J,Value), NumberList),
	  param(Board)
	do
		subscript(Board,[I,J],0)
	),
	Board :: [0..1],
	( for(I,1,Dim),
	  param(Dim,Board, BlackList,WhiteList)
	do
		( for(J,1,Dim),
		  param(Dim,I,Board,BlackList,WhiteList)
		do
			Box is Board[I,J],
			( var(Box) ->
				suspend(				
				( Box =:= 0 ->
					memberchk((I,J),WhiteList)
				;
					memberchk((I,J),BlackList)
				),2, Box->inst)
			;
				( Box =:= 0 ->
					memberchk((I,J),WhiteList)
				;
					memberchk((I,J),BlackList)
				)
			)
		)
	).
	
constraints(Board, NumberList, BlackList, WhiteList, Dim) :-
	no_neighbours(BlackList).	


no_neighbours(X:[]).
no_neighbours((X,Y):Xs) :-
	nonmember((X+1,Y),Xs),
	nonmember((X-1,Y),Xs),
	nonmember((X,Y+1),Xs),
	nonmember((X,Y-1),Xs),
	no_neighbours(Xs).




search(Values) :-
    term_variables(flatten(Values), Vars),
    labeling(flatten(Values)).

print_board(Board) :-
	( foreachelem(El,Board,[_,J])
	do
		( J=:= 1 -> nl ; true),
		write(' '),
		(var(El) -> write('_') ; write(El) )
	).

puzzle(1,5,[ (2,1,8),(2,3,8),(2,5,5),(3,2,7),(3,4,7),(4,1,8),(4,3,8),(4,5,6)]).
Thanks in advance.
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top