Skip to content

Instantly share code, notes, and snippets.

@justinhj

justinhj/help.md

Created September 22, 2015 18:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save justinhj/f016a4cd7a0c21b3e1cd to your computer and use it in GitHub Desktop.
Save justinhj/f016a4cd7a0c21b3e1cd to your computer and use it in GitHub Desktop.
Download ZIP
Water jug help for A*
Raw
help.md

State representation

In the 8Puzzle the state of each step in the solution is an array of tiles. In the water jug it can be an array of jug levels [0,0]

You can replace tiles with jugs TILE tiles[ BOARD_WIDTH*BOARD_HEIGHT ]; int jug_levels[ 2 ];

State transitions

Valid state transitions are encode in the function GetSuccessors

In the 8puzzle example a valid successor is worked out by figuring which tiles can move. In your case the valid moves are all the combinations of emptying and filling each jug.

IsGoal will need to check that the 4 gallon jug has the correct level

GoalDistanceEstimate will return something that you decide. For example the difference in level between the 4 gallon jug and the goal level

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment