2 Step Through the Search
By the end of this chapter, a Step button waits in the navy bar, and the parchment card keeps count. Each press checks one more Board while the Tiles stay still. After 20, the next press says Goal found.
The game as it is at the end of this chapter. Click the game to play.
If your game and this chapter part ways, here is the chapter’s finished project. Open it and compare, or start Chapter 3 from it.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.
2.1 The Idea
Try the game above. Press Step, the new button in the navy bar, or press Space. Not a Tile moves. On the parchment card, under the Goal, a count reads States checked 1, and under it the card says Searching... Press Step again, and the count reads 2. Again, 3.
Keep going. The Tiles sit still the whole time, and only the count climbs. When it reaches 20, press once more. The words change to Goal found, and the count stays where it is.
Something else is working the puzzle now. It never touches a Tile. It works on Board States, the nine-digit slips from Chapter 1.
Here’s the problem it has. Four Boards are one Move from your puzzle, and every one of them leads to more. Sliding Tiles away from the Goal can make 181,440 different Boards. This search checks 20 of them, and the way it finds to the Goal has the fewest Moves there are. How does it choose which Boards to check?
It keeps a notebook, full of slips like the one from Chapter 1. Every Board it finds gets a line, and each line has two numbers. The first is how many Moves it took to reach that Board from your puzzle, its Moves so far. The second is a guess at how many Moves are still left, the Estimate. Add the two, and you have the Board’s score.
The Estimate comes from the Tiles. For each Tile, count the rows and the columns between where it sits and where the Goal wants it, as if no other Tile stood in the way. Tile 1 is three Slots from home. Tiles 5 and 4 are two each, and the other five Tiles are one each. That makes 12.
A Move slides one Tile one Slot. So no Route can take fewer Moves than that count, and the Estimate never guesses too many. Hold on to that. It’s what lets the search stop at the Goal and be sure.
Now count out the first Step. The search writes your puzzle down with 0 Moves so far and an Estimate of 12, a score of 12. Each line it writes is a Search State. This one is the only line in the notebook, so it’s the best one there.
The search Expands it. It closes that line, and it writes down every Board one Move away, the line’s Neighbors. Your puzzle reads 5, 4, 2 along the top row, then 7, the Blank and 3, then 8, 1, 6. The Blank is in the center, so four Tiles touch it, and there are four Neighbors. Tile 4 sliding down and Tile 1 sliding up each bring a Tile one Slot nearer home. So their Estimate drops to 11. With 1 Move so far, their score stays 12. Tile 7 sliding right and Tile 3 sliding left each take a Tile farther away, and their score is 14.
That’s the whole rule. Each Step, take the open line with the lowest score, and Expand it. It has a name: A* Search. Textbooks write it in letters, g for Moves so far, h for the Estimate, and f = g + h for the score. You’ll meet the letters once, on a card.
On the second Step, Tile 4’s line and Tile 1’s tie. Both score 12, with the same Estimate. Which goes first? The line written first, and that’s Tile 4’s. None of this is drawn. Only the count moves, and this is what happens behind it.
From your puzzle, every Board the search Expands scores exactly 12. The Goal turns up on the 20th Step, written down as a Neighbor with 12 Moves so far and nothing left to guess. The search doesn’t stop there. On the 21st Step it picks the Goal as its best open line, and only then does it accept it. That’s when the card says Goal found.
Why wait? Every open line’s score is real Moves plus a guess that’s never too high. When the Goal has the lowest score of all, no way still waiting in the notebook can be shorter.
One more thing, so the middle of this chapter doesn’t worry you. The first three parts each end with something new on the screen: the count, the button, and a puzzle refused. The three parts after them build the search itself, and none of it shows until the last part joins it up. Two small Functions from Chapter 1, Slot Distance and Board After Move, come back in those parts.
2.2 The Plan
Here’s how the pieces work together. Read each line from left to right, once for its shape. Most of the names are new, and that’s fine. Come back to this map after the last part, and you’ll have built every one.
- The Scene starts -> Start Board asks Check Start Board whether your puzzle can reach the Goal at all -> if it can, it becomes
$boardState. - You press Step -> Send When Pressed sends
stepPressedto Puzzle Rules -> Run Search takes one Step. Space does the same through Run Search’s own Command Event. - The first Step -> Add Search State writes your Board down as the first open Search State -> Expand Best State Expands it at once.
- Each Step -> Expand Best State asks Pick Best Open State for the open Search State with the lowest score -> Expand State closes it and adds 1 to
$statesChecked. - Expand State finds each Board one Move away -> Store Neighbor writes it down -> Add Search State asks Estimate Moves Left for its guess.
- The best open Search State is the Goal -> Expand Best State sends
goalAccepted-> Run Search says Goal found and stops. - You slide a Tile -> Hand Moves sends
boardChanged-> Run Search empties Search States and puts the count back to 0.
2.3 Set Up
This chapter’s Set up card is short: one Command, one Global and two placements.
COMMANDS has one, Step, a Button joined to Space. Make it in the Input Manager, the way you made the eight in Chapter 1. Run Search listens for it, but not until near the end of the chapter, once there’s a search to run.
GLOBAL VARIABLES has one too, $statesChecked, the count on the card. It’s a Number that starts at 0. On Start Board’s canvas, press + on the Globals card and choose New Global…, as you did for the others. Type its name without the $.
PLACE THESE names the two new Objects, and each part places its own, once it exists. The Set up card on the Making page says more about each block.
Space2.4 The Count
First, the parchment card learns to count.
Under the Goal picture, above the line where Solved appears, the card gets one more line. It reads States checked, then a number, and the number is $statesChecked. It counts the Boards the search has Expanded.
States Checked is a Screen UI Object with a Text / UI and nothing else, made like the Status Line. Its Text is States checked {$statesChecked}, braces and all. Remove its UI Interaction.
Its card has no Bounding Box line, and it needs none. The Text / UI’s Text Bounds stays on Fit to Text, the way it starts, so the box grows to fit the words. The Status Line works the same way.
Window / UIUIStates checked {$statesChecked}16Semibold#233947CenterVectorPlace it at 766 and -559, from PLACE THESE. Run the game. The card says States checked 0, under the Goal. Nothing makes it climb yet.
2.6 A Puzzle with an Answer
Before any search begins, the puzzle has to be one it can finish.
In Chapter 1’s Challenge, you made puzzles by sliding Tiles away from the Goal, and every one of those can be solved. A Board typed into Puzzle Settings might not be. Swap Tiles 7 and 8 on the Goal, and you get 123456870, a Board that looks one Move from done. No amount of sliding will ever put that one right.
The reason is a count. Read a Board in reading order, and look at every pair of Tiles. A pair where the larger number comes first is an inversion. The Goal has none. Your puzzle has 14. And 123456870 has only one, the 8 that comes before the 7.
A Move never changes whether that count is even or odd. Slide a Tile left or right, and the reading order stays exactly as it was, so the count can’t change. A Tile sliding up or down passes two other Tiles in reading order. Each of those two pairs turns around. So the count goes up by two, or down by two, or one pair goes each way and it stays the same. An even count stays even forever, and an odd one stays odd. Your puzzle’s 14 is even, like the Goal’s 0, so it can get there.
2.6.1 Count Inversions
Count Inversions counts them. It takes each Slot in turn as the earlier one, and for each, it looks at every Slot again as the later one. A pair counts when the later Slot really comes later, holds a Tile, not the Blank, and holds a smaller number. Those are the three tests in its If’s one box, joined by &&.
That’s a Repeat inside a Repeat, and each one has its own local.index. Inside the inner Repeat, local.index means the inner count. So before the inner Repeat starts, the outer Slot is copied into earlierSlot, where the inner one can still read it.
Two Declare Variables come first: earlierSlot, and inversions, the count. The inner Repeat is step 6. It’s the third block in the outer Repeat’s panel, after steps 4 and 5. So right-click the outer Repeat and choose Add inside Repeat for it, as for those two. Then right-click the inner Repeat to fill its own panel. If, Else, Repeat and While on the Making page shows both. Last, a Return hands back inversions.
The number of inversions of a Board: pairs of Tiles where the larger number comes first in reading order. The Blank is not counted. A Move never changes whether this number is even or odd: a Tile sliding left or right keeps the reading order, and a Tile sliding up or down passes two other Tiles.
- Name
earlierSlot- Value
0
- Name
inversions- Value
0
9times- Variable
earlierSlot- Value
local.index
- Action Name
earlier- board
board- slot
earlierSlot
9times- Action Name
later- board
board- slot
local.index
local.index > earlierSlot && later.value > 0 && earlier.value > later.value- Variable
inversions- Operator
+=- Value
1
- Value
inversions
2.6.2 Check Start Board
Check Start Board answers one question before any search begins: can this Board reach the Goal? It says yes only when four things are true at once.
Every digit from 0 to 8 is there. The Board’s inversions and the Goal’s are both even, or both odd. The Board is a whole number, and it has nine digits at most.
Every digit there is the first check. It’s a Repeat over the digits. Here local.index is a digit, not a Slot, and Slot Of Tile looks for it. A digit it can’t find leaves its slot at -1, and missingDigits goes up by 1.
All four meet in one If, step 9. Its box holds four tests, joined by &&, and the first, missingDigits == 0, says no digit was missing. In the second, % 2 is the remainder after dividing by 2: 0 for an even count, 1 for an odd one. In the third, floor() drops anything after the decimal point. A Board equals its own floor only when it’s a whole number. The last test keeps it under ten digits.
The answer is canReachGoal, a Boolean, a true or false. It starts at false, and the If’s one step sets it to true. So the RETURN TYPE is Boolean.
Whether a Board can reach the Goal: it must hold every digit 0 to 8 exactly once, in at most nine digits, and its number of inversions (Count Inversions) and that of the Goal must be both even or both odd. A Move never changes whether the count is even or odd, so a Board that differs from the Goal there can never reach it.
- Name
missingDigits- Value
0
- Type
Boolean- Name
canReachGoal- Value
false
9times- Action Name
where- board
board- tile
local.index
where.value == (-1)- Variable
missingDigits- Operator
+=- Value
1
- Action Name
boardInversions- board
board
- Action Name
goalInversions- board
data('Puzzle Settings', 'puzzle', 'goalBoard')
missingDigits == 0 && (boardInversions.value % 2) == (goalInversions.value % 2) && board == floor(board) && board < 1000000000- Variable
canReachGoal- Value
true
- Value
canReachGoal
2.6.3 Start Board, Changed
Start Board asks Check Start Board first now. A Board that can reach the Goal, and isn’t the Goal already, becomes the Board State, as before. Any other Board is refused. The Board opens as the Goal, and the Status Line says Try a new puzzle. A puzzle that’s already solved leaves the search nothing to do, so it’s refused too.
Those words are a new row of Messages. The other two new rows, searching and goalFound, wait for Run Search, and Changes cards on the Making page shows how to read the marks.
SolvedSearching...Goal foundTry a new puzzle.Start Board’s old Change Variable is struck, and six new steps take its place. Its If joins two tests with &&. The first asks whether Check Start Board said true. The second asks whether the start Board differs from the Goal.
Sets up the Board State when the puzzle opens: the Start Board from Puzzle Settings, when it can reach the Goal (Check Start Board) and is not already the Goal. A Board that cannot, or that leaves nothing to solve, is refused: the Board opens as the Goal, and the Status Line asks for a new puzzle.
Any Object- Variable
$boardState- Value
data('Puzzle Settings', 'puzzle', 'startBoard')
- Action Name
startCheck- board
data('Puzzle Settings', 'puzzle', 'startBoard')
startCheck.value == true && data('Puzzle Settings', 'puzzle', 'startBoard') != data('Puzzle Settings', 'puzzle', 'goalBoard')- Variable
$boardState- Value
data('Puzzle Settings', 'puzzle', 'startBoard')
- Variable
$boardState- Value
data('Puzzle Settings', 'puzzle', 'goalBoard')
- Variable
$statusLine- Value
data('Messages', 'tryNew', 'words')
Run the game. Your puzzle opens as it always did, because 542703816 can reach the Goal.
To see a refusal, open Puzzle Settings and type 123456870 into startBoard. Run the game. The Tiles open in Goal order, and the card says Try a new puzzle. Close the game and put 542703816 back.
2.7 The Search’s Notebook
Now the search itself.
The next three parts build it, and nothing new shows on the screen until the last part joins them up. The Board stays put, and so does the count. Keep going. Each piece is small.
The notebook is a Data Table, Search States. A line in the notebook, a Search State and a row of the table are one thing, so read any of the three names the same way. It starts with no rows, and that’s right. The search writes a row for each Board it finds, while the game runs. Each row is named by its Board’s nine digits, so no Board can be written down twice.
Its four columns are the line in the notebook, and they’re the four fields of Search States Entry, the Data Structure Myth makes with the table. The Moves so far go in movesSoFar, and the Estimate in estimatedMovesLeft. In parentState goes the Board this one was reached from, and Chapter 3 follows those back to build the Route. The last, isOpen, is a Boolean. It’s true until the line has been Expanded. A Data Table card on the Making page says more about a table with no rows.
One row of the "Search States" Data Table.
Search Settings says how many rows the notebook may hold, 4096. From your puzzle, the search writes 35 before it accepts the Goal, so there’s plenty of room. A search that would need more stops and asks for a new puzzle.
4096Its Search Settings Entry has one field, maxStates. The default is 4096 already, so the one row only needs its name, search.
One row of the "Search Settings" Data Table.
2.7.1 Estimate Moves Left
Remember Slot Distance, from Chapter 1? This is who it was for.
Estimate Moves Left goes through the Slots in reading order. In each one, Tile In Slot says which Tile is there, and the If skips the Blank. For a Tile, Slot Of Tile finds its home, the Slot that holds the same number in the Goal. Slot Distance counts the Moves between, and total adds them up.
Its three Function calls have Action Names: here, home and away. So home.value is where the Tile lives in the Goal, and away.value is how far it has to go.
The Estimate of the Moves still needed from a Board to the Goal (Manhattan distance): for each Tile, the rows plus the columns between its Slot and its Slot in the Goal. The Blank is not counted. It never guesses more Moves than are really needed, which is what lets A* find the shortest Route.
- Name
total- Value
0
9times- Action Name
here- board
board- slot
local.index
here.value > 0- Action Name
home- board
data('Puzzle Settings', 'puzzle', 'goalBoard')- tile
here.value
- Action Name
away- fromSlot
local.index- toSlot
home.value
- Variable
total- Operator
+=- Value
away.value
- Value
total
2.7.2 Add Search State
Add Search State writes one line in the notebook, named by the Board’s nine digits. The guess comes from Estimate Moves Left.
Control Data Row’s card gives its Action Name, Table and Row. Leave its Operation on Add or Update, the way it starts, and its Values boxes empty. An empty box keeps that column’s default.
The fourth column, isOpen, needs no Action at all, because a new row takes every column’s default, and isOpen’s is true. Actions, one at a time on the Making page names the Actions that write in a table.
Stores a Board the search has just found as a new, open Search State: its route so far (movesSoFar and parentState) and its Estimate of the Moves left. A new row starts open.
- Action Name
guess- board
board
- Action Name
addedRow- Table
"Search States"- Row
text(board)
- Table
"Search States"- Row
text(board)- Column
"movesSoFar"- Value
movesSoFar
- Table
"Search States"- Row
text(board)- Column
"estimatedMovesLeft"- Value
guess.value
- Table
"Search States"- Row
text(board)- Column
"parentState"- Value
parentState
The notebook is ready to be written in.
2.8 Every Board One Move Away
Next, the search learns to look around a Board and write down what it finds there.
2.8.1 Store Neighbor
Store Neighbor writes down one Neighbor. It’s handed the Board it starts from, parentState, and the Moves so far to reach it, parentMoves. It’s also told which Tile slides: the one in fromSlot, into the Blank at blankSlot.
First the slip changes. Board After Move, from Chapter 1, slides the Tile, and the new Board is one Move farther from your puzzle than its parent was. Those are neighborState and newMoves.
Has the search seen this Board before? Check Data Row Exists answers, as storedBefore.value, by looking for a row with this Board’s name. A Board seen before keeps the line it has, unless the new way there is shorter. Then the shorter way takes its place, and the line opens again. From your puzzle, that never comes up. From some puzzles it does.
Reopening a line sets its isOpen to Yes, and Expand State will set it to No. Type Yes bare, as the card shows it. The box takes it. Yes is true written another way, so a later If can ask whether isOpen == true.
A Board not seen before gets a new line from Add Search State, if there’s room. Step 15’s dataCount('Search States') is how many rows the table holds right now, and it has to stay under maxStates. A full notebook writes nothing. Then isFull turns true, and the Return hands it back.
This card has three Ifs. The outer one is step 9. Step 10 sits in its Then panel, and has no Else of its own. Step 15 sits in its Otherwise panel, and it does have one. So step 14 is step 9’s Else and step 17 is step 15’s, and when you choose Add Else, right-click the If you mean.
Stores the Board made by sliding the Tile in fromSlot into the Blank, reached from parentState (whose route takes parentMoves). A new Board becomes an open Search State (Add Search State); a Board stored before takes the new route only when it is shorter, and is then open again. isFull is Yes when a new Board would not fit in Search Settings / maxStates.
- Name
neighborState- Value
0
- Name
newMoves- Value
0
- Type
Boolean- Name
isFull- Value
false
- Action Name
neighbor- board
parentState- fromSlot
fromSlot- toSlot
blankSlot
- Variable
neighborState- Value
neighbor.value
- Variable
newMoves- Value
parentMoves
- Variable
newMoves- Operator
+=- Value
1
- Action Name
storedBefore- Table
"Search States"- Row
text(neighborState)
storedBefore.value == truenewMoves < data('Search States', text(neighborState), 'movesSoFar')- Table
"Search States"- Row
text(neighborState)- Column
"movesSoFar"- Value
newMoves
- Table
"Search States"- Row
text(neighborState)- Column
"parentState"- Value
parentState
- Table
"Search States"- Row
text(neighborState)- Column
"isOpen"- Value
Yes
dataCount('Search States') < data('Search Settings', 'search', 'maxStates')- board
neighborState- movesSoFar
newMoves- parentState
parentState
- Variable
isFull- Value
true
- Value
isFull
2.8.2 Expand State
Expand State is one Expand. It closes the Board’s line by setting isOpen to No, and it adds 1 to $statesChecked. That’s the count on the card.
Then it looks around the Blank. Every Tile beside the Blank could slide into it, and each of those slides makes a Neighbor. Slot Distance finds those Slots, and Store Neighbor writes each Neighbor down.
If Store Neighbor ever answers that the notebook is full, Expand State remembers it in isFull. Once the looking is done, a full notebook means the search can’t go on, so Expand State tells Puzzle Rules searchStopped.
Expands one Search State: closes it, adds it to States checked, and stores every Board one Move away (Store Neighbor). Tells Puzzle Rules "searchStopped" when a new Search State would not fit.
- Type
Boolean- Name
isFull- Value
false
- Table
"Search States"- Row
text(state)- Column
"isOpen"- Value
No
- Variable
$statesChecked- Operator
+=- Value
1
- Action Name
blank- board
state- tile
0
9times- Action Name
apart- fromSlot
local.index- toSlot
blank.value
apart.value == 1- Action Name
stored- parentState
state- parentMoves
data('Search States', text(state), 'movesSoFar')- fromSlot
local.index- blankSlot
blank.value
stored.value == true- Variable
isFull- Value
true
isFull == true- Applies To
puzzleRules- Custom Event
searchStopped
From any Board in the notebook, the search can now write down every Board one Move away.
2.9 The Lowest Score
Now the choice the whole search turns on: which line comes next.
2.9.1 Pick Best Open State
This is the longest card in the chapter, so take it one question at a time.
Pick Best Open State reads the notebook from top to bottom, in the order the lines were written. Its Repeat runs once for each row. Type dataCount('Search States') into its Count box, how many rows there are. Like most boxes, the Count takes a formula. Here local.index is a row’s number, counting from 0, and data() can read a row by its number as well as by its name.
It skips a closed line. For an open one, it works out the score: movesSoFar, with the estimate added on.
Next it asks whether this line beats the best one so far. There are three reasons it might, each with its own If, and each If sets isBetter. It’s the first open line it has seen. Its score is lower. Or its score is the same, and its estimate is lower.
With none of those, the best so far stays. A full tie changes nothing. The line written first keeps its place.
When isBetter is true, this line becomes the best: its Board, its score and its estimate. The Board comes from dataRow(), which gives the row’s name, the nine digits as words. You don’t wrap it in anything. Because bestState is a Number, Change Variable turns the words back into a number by itself.
It hands back two answers. found says whether any line was open at all, and state is the best Board. Two answers make a small Data Structure, Pick Best Open State Result, as Slot Position’s x and y did in Chapter 1. Make it first, so it’s on the Return Type list. Inside the Function, isFound and isBetter are Booleans, and they start at false. The Return gives isFound back as found.
What Pick Best Open State gives back: found is Yes when an open Search State was found, and state is that Search State's Board State.
Finds the open Search State with the lowest score, movesSoFar + estimatedMovesLeft (f = g + h). On a tie, the lower estimatedMovesLeft wins; on a further tie, the one stored first. found is No when no Search State is open.
- Type
Boolean- Name
isFound- Value
false
- Name
bestState- Value
0
- Name
bestScore- Value
0
- Name
bestEstimate- Value
0
- Name
score- Value
0
- Name
estimate- Value
0
- Type
Boolean- Name
isBetter- Value
false
dataCount('Search States')timesdata('Search States', local.index, 'isOpen') == true- Variable
estimate- Value
data('Search States', local.index, 'estimatedMovesLeft')
- Variable
score- Value
data('Search States', local.index, 'movesSoFar')
- Variable
score- Operator
+=- Value
estimate
- Variable
isBetter- Value
false
isFound == false- Variable
isBetter- Value
true
score < bestScore- Variable
isBetter- Value
true
score == bestScore && estimate < bestEstimate- Variable
isBetter- Value
true
isBetter == true- Variable
isFound- Value
true
- Variable
bestState- Value
dataRow('Search States', local.index)
- Variable
bestScore- Value
score
- Variable
bestEstimate- Value
estimate
- found
isFound- state
bestState
2.9.2 Expand Best State
Expand Best State is one Step of the search, from start to finish. It asks Pick Best Open State for the best open line. If none is open, the search has run out of Boards, and it tells Puzzle Rules searchStopped. If the best is the Goal, it tells Puzzle Rules goalAccepted. Otherwise, it Expands that Board.
That middle check is the one The idea promised. The Goal is accepted only when it’s the best open line, not when it’s first written down. Only then is its way sure to be the shortest.
The card has an If inside an If, and each has an Otherwise. Step 5 is the inner If’s Else, and step 7 is the outer one’s, so right-click the If you mean when you choose Add Else.
One Step of the A* search: picks the best open Search State (Pick Best Open State). If it is the Goal, the Goal is accepted ("goalAccepted"); otherwise it is Expanded (Expand State). When no Search State is open, the search stops ("searchStopped"). Both messages go to Puzzle Rules.
- Action Name
best
best.found == truebest.state == data('Puzzle Settings', 'puzzle', 'goalBoard')- Applies To
puzzleRules- Custom Event
goalAccepted
- puzzleRules
puzzleRules- state
best.state
- Applies To
puzzleRules- Custom Event
searchStopped
Every piece of the search is built, and it waits for its first Step.
2.10 Step by Step
Last, Step gets someone to listen.
2.10.1 Run Search
Run Search listens for Step, and it decides what a Step does. That depends on where the search has got to, so On Step Pressed has three Modes: Not Started, Searching and Finished.
Build it in this order. First comes puzzleRules, on its Shared Variables card, and then its two Events. The first is When Step Is Pressed, a Command Pressed Event for Step. The second is On Step Pressed. It listens for the message stepPressed, so make it with Add Custom Event…, as you made On Tile Chosen in Chapter 1. Rename its Mode Not Started, and add two more, Searching and Finished. Not Started is the Starting Mode. After those, make On Goal Accepted, On Search Stopped and On Board Changed.
The Actions come next. Switch Mode picks the Event and the Mode by name, so every Mode is there before the first Switch Mode. Modes on the Making page shows each step. Your hands know this from Hand Moves.
Space rings the same message the button does: When Step Is Pressed sends stepPressed to Puzzle Rules. The first Step is Not Started’s. Unless the Board is the Goal already, it writes your Board down as the first open line, with no Moves so far and no parent, -1. It puts Searching... on the Status Line and switches to Searching. In the same Step, it Expands that first line. That’s why the first press already reads 1.
Runs the A* solver one Step at a time, from the Board shown. The Step button and the Space key send stepPressed for each Step. The first Step stores that Board as the first open Search State; each Step then Expands the best open Search State (Expand Best State) until the Goal is accepted (goalAccepted). When the Goal is accepted or the search stops (searchStopped), Step has nothing more to do (Finished). A hand Move cancels the search.
Any Object- Applies To
@self.puzzleRules- Custom Event
stepPressed
$boardState != data('Puzzle Settings', 'puzzle', 'goalBoard')- board
$boardState- movesSoFar
0- parentState
-1
- Variable
$statusLine- Value
data('Messages', 'searching', 'words')
- Event
On Step Pressed- Mode
Searching
- puzzleRules
@self.puzzleRules
After that, each Step is Searching’s, and Searching does one thing: Expand Best State.
A search ends in one of two ways. Expand Best State sends goalAccepted, and the card says Goal found. Or it sends searchStopped, and the card says Try a new puzzle. Either way, On Step Pressed switches to Finished, which has no Actions, so Step does nothing more.
- puzzleRules
@self.puzzleRules
- Variable
$statusLine- Value
data('Messages', 'goalFound', 'words')
- Event
On Step Pressed- Mode
Finished
- Variable
$statusLine- Value
data('Messages', 'tryNew', 'words')
- Event
On Step Pressed- Mode
Finished
Slide a Tile, and the search was for the old Board. On Board Changed empties the notebook with Reset Data Table, and it puts the count back to 0. It clears the Status Line too, unless the Board is now the Goal and Check Goal has said Solved a moment before. Last, it switches back to Not Started, so the next Step searches from the new Board.
- Table
"Search States"
- Variable
$statesChecked- Value
0
$boardState != data('Puzzle Settings', 'puzzle', 'goalBoard')- Variable
$statusLine- Value
""
- Event
On Step Pressed- Mode
Not Started
Now attach Run Search to Puzzle Rules. There’s nothing new to pick. Its puzzleRules has the same name as Tile Keys’, so Puzzle Rules holds only one, already set to Puzzle Rules itself.
Puzzle Rules2.10.2 Check Goal, Changed
Check Goal loses its Else. In Chapter 1, it emptied the Status Line after every Move that wasn’t the last one. Now the search speaks on that line too, and clearing it after a hand Move is Run Search’s job. Delete the Else and the Change Variable under it, and Check Goal is back to one If.
Says "Solved" on the Status Line when a Move makes the Goal, as its Tile begins to slide.
Any Object$boardState == data('Puzzle Settings', 'puzzle', 'goalBoard')- Variable
$statusLine- Value
data('Messages', 'solved', 'words')
- Variable
$statusLine- Value
""
Run the game, and press Step. Searching... appears under the count, and the count reads 1. Press again, and again. The Tiles never move, and the count climbs one Board at a time. At 20, press once more.
Goal found.
Your search worked the puzzle out, and not a Tile moved.
Here is what to watch for, one thing at a time.
- The card says States checked 0, under the Goal, and the line under it is empty. A cream Step button sits at the left of the navy bar.
- Press Step. Not a Tile moves. The count reads 1, and Searching... appears under it.
- Press Space. The count reads 2. Space and the button take the same Step.
- Keep going, one press at a time. The count climbs by one each time, and the Tiles stay still.
- At 20, press once more. The words change to Goal found, and the count stays at 20.
- Press Step again. Nothing changes, because the search is finished.
- Click Tile 4. It slides down, the count goes back to 0, and the words go.
- Press Step. The count reads 1 and Searching... is back, for a new search from the new Board.
- Start the game again and solve it by hand: 1, 8, 7, 5, 4, 1, 5, 4, 1, 2, 3 and 6. Solved appears, as in Chapter 1. Press Step, and nothing happens, because there’s nothing left to search for.
Each Step takes the open line with the lowest score and writes down its Neighbors. A score is Moves so far plus the Estimate. The Estimate counts each Tile’s Slots from home, so it never guesses too many. The Goal is accepted when it’s picked, not when it’s found. Start Board refuses a puzzle with no answer, and a hand Move starts the search over.
Underneath all of it is one idea. The search always looks next where a Route could be shortest, and it can be sure of that because its guess is never too high. From your puzzle, every Board it Expanded scored 12, the length of the shortest Route. It never had to look at a Board that scored more. That’s how 20 checks were enough.
2.11 If It Didn’t Work
A search has many small parts, and one of them may be a little off the first time. That’s normal. Run the game, watch the count and the words, and think it through one piece at a time.
The Step button does nothing, but Space works? Look at Send When Pressed’s Custom Event box. It should hold self.message, and its Per Instance Variables card should have message starting at stepPressed. Look too at the button’s puzzleRules, under Variables, and for its UI Interaction.
Neither the button nor Space does anything? Is Run Search on Puzzle Rules? Is Not Started the Starting Mode of On Step Pressed? And is stepPressed spelled the same, letter for letter, in all three places?
The count stops at 1? Perhaps Not Started never switched to Searching. Look at its step 4, Switch Mode, and at Searching’s one Action, Expand Best State.
Searching... appears, but the count stays at 0? Look at step 3 of Expand State, $statesChecked with +=. If that’s right, the States Checked Text should read States checked {$statesChecked}, braces and all.
The count goes past 20 before Goal found? The search is choosing its lines in a different order, so perhaps a score is off. In Pick Best Open State, steps 11 and 12 make the score: movesSoFar, then += with the estimate. In Estimate Moves Left, the If skips the Blank with here.value > 0. In Store Neighbor, newMoves gets += 1.
Try a new puzzle. appears the moment the game starts? Start Board refused your puzzle. Look at Puzzle Settings first, where startBoard should be 542703816. After that, look at Check Start Board’s step 9, an If of four tests, and at Count Inversions.
Try a new puzzle. appears partway through the search? The notebook filled up. Look at Search Settings, where maxStates should be 4096, and at step 15 of Store Neighbor.
Sliding a Tile doesn’t put the count back to 0? Look at Run Search’s On Board Changed.
A piece that does nothing at all, even though every value matches its card? Look for a block standing apart from its line, with no arrow into it. Connect to sequence joins it.
A box the editor marks as an error? Count its quote marks and its brackets, because one may be missing.
Each of these is one small fix. Make it, run the game again, and you’re back with the chapter. The catch-up download at the top of this chapter is its finished project, if you’d like to compare.
Make the notebook small. Open Search Settings and type 10 into maxStates, then run the game and press Step until something changes. After 5 Steps, the search runs out of room. The card says Try a new puzzle.
Now put 4096 back, and try a puzzle of your own, as in Chapter 1’s Challenge. Start one Move from the Goal, at 123456708, and count the Steps. Then go two Moves away, and three. Watch how the count grows as the puzzle gets harder.
Before Chapter 3, put 542703816 back in startBoard. Its numbers are about that puzzle.
The search has found the Goal, and not a Tile has moved. In Chapter 3, it shows you the way there.