>> ROB BOWDEN: Hi.
I'm Rob, and I hope your game for game of 15.
Now, there are four functions you need to implement in this program--init,
draw, move, and won.
So, let's look at init.
>> Here, we see the first thing we're going to do is declare a variable
called counter.
It's going to be initialized to d times d minus 1.
Remember that d is the dimension of our board.
How init is going to work is it's going to iterate over the entire board
and we're going to start at the top left.
>> And let's just say we have a 4 by 4 board.
So the top left we're going to say is 15.
And then we're just going to count through the boards, saying 15, 14, 13,
12, 11, 10, 9, 8, 7, 6, 5, 4, and so on.
So the top left, we expect to be d times d minus 1, which in the 4 by 4
case is going to be 16 minus 1, which is correctly 15.
>> And now here's where we're going to iterate over the entire board.
And we're going to set each position in the board to the current value of
our counter, and then counter is going to decrement, so that the next
position we reach is going to have counter be one less than
the previous position.
So we initially had 15 and decrement counter.
So then we're going to assign 14 to the next position, decrement counter,
and we're going to assigned 13, and so on.
>> Finally, we need to handle that corner case where, if the board has an even
dimension, then just doing 15, 14, 13, 12, all the way down to 3, 2, 1, is
going to leave us with an unsolvable board.
And we have to swap the 1 and the 2.
So, if d mod 2 equals 0, that's how we're going to check
to see if it's even.
If d mod 2 equals 0, then in row d minus 1, which is the bottom row, and
position d minus 2, or column d minus 2, we're going to set that to 2, and
column d minus 3 we're going to set to 1.
So that's just reversing where the 1 and 2 currently are.
>> Finally, we're going to set the very bottom right equal to blank, where
blank has been hash defined at the top as 0.
So, that wasn't strictly necessary, since this for loop is going to have
set the bottom right to 0, since counter will naturally reach 0.
But that relies on us knowing that blank was hashed to find a 0.
If I go into this program and later change blank at the top to 100, it
should still work.
>> So this is just making sure that the bottom right is actually equal to our
blank value.
Finally, we have two global variables, so blank i and blank j, and we see
those declared at the top.
And we're going to use those two global variables to keep track of the
position of the blank, so that we don't need to look through the entire
board to find the blank every single time we try to make a move.
So the position of the blank always is going to start at the bottom right.
So the bottom right is given by indices d minus 1, d minus 1.
So, that's init.
>> Now we move on to draw.
So, draw is going to be similar where we're going to iterate
over the entire board.
And we just want to print the value that's in each position of the board.
So here, we're printing the value that's in each position of the board.
And notice that we're doing -.
And that's just telling printf that regardless of if it's a one digit or
two digit number, we still want it to take up two columns in the print out,
so that if we have two digit and one digit numbers in the same board, our
board will still look nice and square.
>> So we want to do that for every value in the board, except for the blank.
So, if the position in the board equals the blank, then we specifically
want to print out just an underscore to represent the blank, instead of
whatever the value of the blank actually is.
>> Finally, we want to print out a new line.
Notice that this is still inside the outer for loop, but outside
the inner for loop.
Since this outer for loop is iterating over all rows, and so this printf is
going to just print a new line, so we move on to print out the next row.
And that's it for draw.
>> So, now let's move on to move.
Now, we pass move, the tile that the user is entered in the game--they
enter the tile they want to move--and you're supposed to return a bool, so
either true or false, depending on whether that move was actually
valid--whether that tile can be moved into the blank space.
>> So here, we declare a local variable, tile_1 and tile_j, which are going to
be similar to blank_i and blank_j, except it's going to keep track of the
position of the tile.
Now here, we're going to use blank_i and blank_j and say all right, so
here's the blank on the board.
>> Now, is the tile above the blank?
Is the tile to the left of the blank?
Is the tile to the right of the blank?
Is the tile below the blank?
So, if the tile is in any of those positions, then we know that the tile
can be moved into the blank spot and the blank can be moved to where the
tile currently is.
>> So here, we say if board at position blank_i minus 1 blank_j.
So this is saying is the tile above the current blank?
And if so, we're going to remember that is the position of the tile.
The tile is in position blank_i minus 1 and blank_j.
now first, we also have this check right here, so blank_i is
greater than 0.
>> Why do we want to do that?
Well, if the blank is in the top row of the board, then we don't want to
look above the blank for the tile since there is nothing above the top
row of the board.
This is how you might end up getting something like a segmentation fault or
your program might just work in unexpected ways.
So, this is making sure that we don't look in places that aren't valid.
>> Now we're going to do the same thing for all other possible combinations.
So here, we're looking below the blank to see if that's the tile.
And we also have to make sure we're not on the bottom row, or else we
shouldn't look for the tile.
Here, we're going to look to the left of the blank to see if it's the tile.
And we shouldn't look to the left if we're in the leftmost column.
And here we're going to look to the right of the blank, and we shouldn't
look to the right if we're in the rightmost column.
>> So, if none of those things were true, that means the tile was not adjacent
to the blank and we can return false.
The move was not valid.
But, if one of those were true, then at this point, we know that tile_i and
tile_j are equal to the position of the tile.
And so, we can update the board at positions tile_i and tile_j.
We know the new value will be the blank and that the position blank_i
blank_j , which was the original blank--we know the tile is going to
move there.
>> Notice we don't actually have to do a real swap here, since we know the
values that need to be inserted into those positions.
We don't need a temporary variable around.
>> Finally, we need to remember that we have our global variables that are
keeping track of the position of the blank.
So we want to update the position of the blank to be where the tile
originally was.
Finally, we return true since the move was successful.
We successfully swap the blank with the tile.
>> All right, so last we need to check won.
So, won similarly returns a bool where true is going to indicate that the
user has won the game.
And false is indicating that the game is still going.
The user has not won.
So, this is going to be pretty much the opposite of init, where init,
remember, we initialize the board to 15, 14, 13, 12, so on.
Whereas won, we want to check if the board is 1, 2, 3, 4, 5, and so on.
>> So, we're going to initialize our counter to 1 since that's what the top
left of the board should be.
And then we're going to loop over the entire board.
Let's ignore this condition for a second.
And this condition is just going to check is the board at this position
equal to the current counts?
If so, increment the count so that the next position we look at is one higher
than the position we are at right now.
>> So that's how we get the top left should be 1.
Increment the count to 2.
Look at the next position.
Is this 2?
If so, increment the count to 3.
Next position, is this 3?
If so, increment the count to 4, and so on.
So, if there is any position on the board that does not equal our count,
then we want to return false since that means there's some tile that is
not in the correct position.
>> So here, what is this condition doing?
Well, remember that the blank is supposed to go on the bottom right.
And the blank's value might not necessarily equal the value of the
counter that is going to be reached at the bottom right.
So we specifically want to check if i equals equals d minus 1 and j equals
equals d minus 1--which is saying if we are looking at the bottom right of
the board--then we just want to continue.
We want to skip this particular iteration of the for loop.
>> And so, if we manage to get through this nested for loop, that means that
there was no tile that was in the incorrect position.
And we break out of the loop and come here, where we can return true.
All tiles were in the correct positions and that means the user has
won the game.
And that's it.
My name is Rob Bowden, and this was 15.