Class Assignment Prolog 2N+1 puzzle

[BMutev]

Hello people from Daniweb, nice to meet you!
I am a student and registered today, but I am familiar with these type of sites.
Now to the point of this post.
As I stated I am student, and have an assignment for my AI discipline.(Because of some
circumstances i was not able to attend classes at all and I was not slacing)
What I want to ask is for a tip or a point in the right direction nothing more,
even if I ask please ignore me for some time I have to learn. :)

My assignment is to do a depth bound search with backtrascking for a game(puzzle) called "2n+1".
Atleast that is what my teacher calls it.

Game:
We have N black and N white plates(N is the same for both)
placed in a line with one empty place between.
Let's take N=3, B=Black, W=White, so it looks like this: WWW_BBB.
The puzzle is solved when all black plates are on the left of the white plates,
for this example. The blank space is of no concern. Plates can be moved to adjacent
cell if it's free or hop over other plate, the limit of hopping is N-1. The costs
are the number of hopped over plates + 1.
So for my example 2 plates can be hopped over.

STATE     COST
WW_WBBB     1
W_WWBBB     2
WBWW_BB     3
WBWWB_B is not valid

What I tried:
As I was not limited to what programming language to use I first tried with Java.
But it did not worked. After that a colleague told me that it is easier to use Prolog for this type of problem,
and I focused on this language. The general idea of the language I understand, but there was
another problem. I had two ways to go one was to define all the possible states and let
Prolog find the solution, or define the initial state and few operators and then let Prolog
find the solution. First one is out of the question, the depth and branching is enormous.
I chose to go with the second one. To clarify i've done similar problem before with the language PDDL,
that problem consisted of towns connected with paths and I had to move people and cargo
from one town to another nothing more. And what's more I had
the graph and I had only to define the operators for the Blackbox which it used to
search for the path. I have not done this type of problem(2n+1) before that is why I am asking for some
general idea to what I could do.

Sorry for the long post, but I had to explain.

Best regards,
BMutev

[llaspina]

Since you have not done this type of problem before, start by doing the problem. By that I mean, play the game. Get some black and white chips or poker chips or cards. Line them up and play the game. Or work out examples on paper like you did in your post. Create enoguh examples that you understand the algorithm and you can either solve the puzzle or declare it unsolvable.

Once you can solve the probme by hand, try to converty the algorithm you discovered into code in the language of your choice.

This puzzle may be famous, but I have not heard of it. It looks like a simpler version of the 15 puzzle (which is very famous). You might learn something by researching the 15 puzzle since this seems like a one-dimensional variation.

[Hiroshe]

Try to represent the "possible" solutions/states to this puzzle as a tree on a peice of paper. (Notice at each stage you have a finite amount of options, each option bringing you to another state).

Next, program a representation of state and start searchong for the solution using backtracking (this is implemented with either recursion or a stack).

Couldn't be much simpler then that.

[BMutev]

Thanks both of you for replying. I am doing some progress for the moment. When I started defining the states of the state space I found out that they're not that many and it's doable. Now I am trying to "craft" the algorithm for searching. If I have more questions Soon I will have more questions so I wont mark the topic as solved yet.

Regards,
BMutev

[BMutev]

Hello again,
With some help from here and there(code snippets) I was able to write a working algorithm. There is one problem though. The algorithm gets stuck at one point and I can't find where the problem is exactly. I start searching from the default position w,w,w,0,b,b,b and I am searching for w,w,w,b,0,b,b, and it starts looking through w,w,0,w,b,b,b; w,0,w,w,b,b,b; 0,w,w,w,b,b,b and then it starts to loop between w,0,w,w,b,b,band 0,w,w,w,b,b,b.

Here is my code:

%% GOAL INSTANCES
    %NOT IMPLEMENTED YET

goal([b,b,b,w,w,w,0]).
goal([b,b,b,w,w,0,w]).
goal([b,b,b,w,0,w,w]).
goal([b,b,b,0,w,w,w]).
goal([b,b,0,b,w,w,w]).
goal([b,0,b,b,w,w,w]).
goal([0,b,b,b,w,w,w]).

%% POSSIBLE MOVES

/* MOVE 0 LEFT*/
move([X1,X2,X3,X4,X5,X6,0],    %% one by one
     [X1,X2,X3,X4,X5,0,X6]).
move([X1,X2,X3,X4,X5,0,X6],
     [X1,X2,X3,X4,0,X5,X6]).
move([X1,X2,X3,X4,0,X5,X6],
     [X1,X2,X3,0,X4,X5,X6]).
move([X1,X2,X3,0,X4,X5,X6],
     [X1,X2,0,X3,X4,X5,X6]).
move([X1,X2,0,X3,X4,X5,X6],
     [X1,0,X2,X3,X4,X5,X6]).
move([X1,0,X2,X3,X4,X5,X6],
     [0,X1,X2,X3,X4,X5,X6]).

/* 0 starts from pos 7  */
move([X1,X2,X3,X4,X5,X6,0],   %% over one
     [X1,X2,X3,X4,0,X6,X5]).
move([X1,X2,X3,X4,0,X6,X5],
     [X1,X2,0,X4,X3,X6,X5]).
move([X1,X2,0,X4,X3,X6,X5],
     [0,X2,X1,X4,X3,X6,X5]).

move([X1,X2,X3,X4,X5,X6,0],   %% over two
     [X1,X2,X3,0,X5,X6,X4]).
move([X1,X2,X3,0,X5,X6,X4],
     [0,X2,X3,X1,X5,X6,X4]).

/* 0 starts from pos 6  */   
move([X1,X2,X3,X4,X5,0,X6],   %% over one
     [X1,X2,X3,0,X5,X4,X6]).
move([X1,X2,X3,0,X5,X4,X6],
     [X1,0,X3,X2,X5,X4,X6]).

move([X1,X2,X3,X4,X5,0,X6],   %% over two
     [X1,X2,0,X4,X5,X3,X6]).    

/* 0 starts from pos 5  */
move([X1,X2,X3,X4,0,X5,X6],   %% over one
     [X1,X2,0,X4,X3,X5,X6]).
move([X1,X2,0,X4,X3,X5,X6],
     [0,X2,X1,X4,X3,X5,X6]).

move([X1,X2,X3,X4,0,X5,X6],   %% over two
     [X1,0,X3,X4,X2,X5,X6]).

/* 0 starts from pos 4  */
move([X1,X2,X3,0,X4,X5,X6],   %% over one
     [X1,0,X3,X2,X4,X5,X6]).

move([X1,X2,X3,0,X4,X5,X6],   %% over two
     [0,X2,X3,X1,X4,X5,X6]). 

/* 0 starts from pos 3  */
move([X1,X2,0,X3,X4,X5,X6],   %% over one
     [0,X2,X1,X3,X4,X5,X6]).


/* MOVE 0 RIGHT */
move([0,X1,X2,X3,X4,X5,X6],   %% one by one
     [X1,0,X2,X3,X4,X5,X6]).
move([X1,0,X2,X3,X4,X5,X6],
     [X1,X2,0,X3,X4,X5,X6]).
move([X1,X2,0,X3,X4,X5,X6],
     [X1,X2,X3,0,X4,X5,X6]).     
move([X1,X2,X3,0,X4,X5,X6],
     [X1,X2,X3,X4,0,X5,X6]).
move([X1,X2,X3,X4,0,X5,X6],
     [X1,X2,X3,X4,X5,0,X6]).
move([X1,X2,X3,X4,X5,0,X6],
     [X1,X2,X3,X4,X5,X6,0]).

/* 0 starts from pos 1  */
move([0,X1,X2,X3,X4,X5,X6],   %% over one
     [X2,X1,0,X3,X4,X5,X6]).
move([X2,X1,0,X3,X4,X5,X6],
     [X2,X1,X4,X3,0,X5,X6]).
move([X2,X1,X4,X3,0,X5,X6],
     [X2,X1,X4,X3,X6,X5,0]).

move([0,X1,X2,X3,X4,X5,X6],   %% over two
     [X3,X1,X2,0,X4,X5,X6]).
move([X3,X1,X2,0,X4,X5,X6],
     [X3,X1,X2,X6,X4,X5,0]).

/* 0 starts from pos 2  */   
move([X1,0,X2,X3,X4,X5,X6],   %% over one
     [X1,X3,X2,0,X4,X5,X6]).
move([X1,X3,X2,0,X4,X5,X6],
     [X1,X3,X2,X5,X4,0,X6]).

move([X1,0,X2,X3,X4,X5,X6],   %% over two
     [X1,X4,X2,X3,0,X5,X6]).

/* 0 starts from pos 3  */
move([X1,X2,0,X3,X4,X5,X6],   %% over one
     [X1,X2,X4,X3,0,X5,X6]).
move([X1,X2,X4,X3,0,X5,X6],
     [X1,X2,X4,X3,X6,X5,0]).

move([X1,X2,0,X3,X4,X5,X6],   %% over two
     [X1,X2,X5,X3,X4,0,X6]).

/* 0 starts from pos 4  */   
move([X1,X2,X3,0,X4,X5,X6],   %% over one
     [X1,X2,X3,X5,X4,0,X6]).

move([X1,X2,X3,0,X4,X5,X6],   %% over two
     [X1,X2,X3,X6,X4,X5,0]).

/* 0 starts from pos 5  */
move([X1,X2,X3,X4,0,X5,X6],   %% over one
     [X1,X2,X3,X4,X6,X5,0]).

%% DFS ALGORTIHM

go( Start, Goal ) :-
    push_s( Start, _Empty_closed, Closed ),
    path( Start, Goal, Closed ).

path( Goal, Goal, Closed ) :-
    %reverse_list(Closed, New_path),
    print_l(Closed),
    !.

path( State, Goal, Closed ) :-
    move(State, Next),
    nonmember(Next, Closed),
    push(Next, Closed, New_closed),
    path( Next, Goal, New_closed), !.

/* % WORK IN PROGRESS
reverse_list(Inputlist,Outputlist):-
reverse(Inputlist,[],Outputlist).    
reverse([],Outputlist,Outputlist).    

reverse([Head|Tail],List1,List2):-
    reverse(Tail,[Head|List1],List2).
*/

push_s(X,[],[X|[]]).
push(X,T,[X|T]).

nonmember(Arg,[Arg|_]) :-
        %!,
        fail.
nonmember(Arg,[_|Tail]) :-
        !,
        nonmember(Arg,Tail).
nonmember(_,[]).

print_l([]).    
print_l([H|T]):-
    print_l(T),
    write(H),
    nl.

And sorry for posting the whole code(if it's a problem) but I don't know where the problem may lie at.
I am doing the DFS problem after that i'll do Backtracking.

Regards,
BMutev

[Hiroshe]

This happens if one move have reverse another. One way around this is:

Use a hashtable (or anything with near O(1) read/write) to keep track of all of the positions already visited. If a move results in a position being revisited, skip that move.

This has a second effect: if nothing is deleted from the hashtable (it's state is kept throughout the entire computation), then you'll also ignore entire branches that your already visited elseware, making it find the solution the faster.

[BMutev]

I'll try to do that, thank you!

[BMutev]

Yesterday I had a lot of work and didn't though about what you said. The hash table you meant is implemented through

nonmember(Arg,[Arg|_]) :-
        !,
        fail.
nonmember(Arg,[_|Tail]) :-
        !,
        nonmember(Arg,Tail).
nonmember(_,[]).

I did some rework and it works well now.
The main thing I did was to change this segment

path( State, Closed ) :-
    goal(State),
    %reverse_list(Closed, New_path),
    print_l(Closed),
    !.

where I added the goal(State) check. This I did so I can seek all the possible outcomes, which speeds the search tremendously.

Well that's for the DFS, I'll do the Backtracking now and see if I have any more questions.

Edit: Stupid me, this is Backtracking algorithm without the depth limit...
Anyway thank you for the help again Hiroshe and llaspina. I'll mark this as solved.

BMutev