# A* algorithm to solve a title puzzle

The title puzzle has a setup of. Www_bbb where there are always 3 w's And 3 b's and 1_ .

The rules of the puzzle are to get all w's on the right side of all b's where location of _ does not matter, to do the puzzle you have 6 possible moves. The move are

1, take the closest w or b to the left and move it to the right of the _(example www_bbb to ww_wbbb)cost of 1

2, take closest w or b to the right and move it to the left of the _(example www_bbb to wwwb_bb) cost of 1

3, take one w or b from the right and jump one letter to move to the left of _ (wbw_wbb to ww_bwbb) cost of 2

4, take one w or b from the left and jump one letter to move to the right of _ (wbw_wbb to wbwb_wb) cost of 2

5, take one w or b from the left and jump 2 letters to move to the right of _ (wbb_wbw to bb_wwbw) cost of 3

6, take one w or b from the right and jump 2 letters to move to the left of _ (wbw_bbw to wbww_bb) cost of 3

The optimal path is to do this with the lowest cost

I am having difficulties on tring to figure out where to start and how to use heuristics of the a* algorithm

• What difficulties are you having? Can you imagine what the statespace is? Can you imagine any potential heuristic? What approaches have you considered? What is preventing you from making more progress on your own? – D.W. Feb 9 '18 at 0:28
• okay, so the state space i have found out that there is likely 140 different "possible" states just by the permutations and there are maximum of the 6 different ways you can get to each state from the starting state. I was originally thinking I would draw out the state phase diagram to actually figure out each state and then generate the whole graph that way and do it by hand but that would take way too much time i am thinking that way. – Jeffrey Hennen Feb 9 '18 at 1:46
• I am also thinking of the heuristic would be at least a cost of 12 because of the amount to take the right side and put it in the locations where they should be to make the answer correct. so first b from the left to left of the first w on the left and then after that move take the 2nd b from the left and move to the right of the first b from the left which is now in the location of bwww_bb and then 3rd b from the left and move to the right of the 2nd b from the right which is in the location of bbwww_b to get a final setup of bbbwww_. – Jeffrey Hennen Feb 9 '18 at 2:38