[ Silence ]
>> Alright everybody, welcome to the walkthrough for Pset 4
or sudoku which is a very, very fun Pset.
On case interview, we're wondering
if the musical is beforehand.
If you recognized it, then you are as nerdy as I am
because that was in fact Dubstep remixes of video game songs.
So yeah, awesome!
So today I will first be going over the distribution code
which a lot-- there's a lot of it
so I'm hoping not to overwhelm you.
And then each of the things you have to do a sudoku,
so how to move the cursor around, how to input numbers,
blanks, make sure the users are allowed to do that
and then checking if the board has been won.
So just a reminder, it mentions this in the Pset spec.
But if you're used to using gedit
and the little terminal window below gedit to run
and compile your programs you probably don't wanna do
that with sudoku just because the board takes up more pixels
than that little terminal window is gonna allow,
unless you stretch it up so high you're editing one line of code
at a time which is good for procrastination
but it's not that productive.
So just a recap of the basic rules of sudoku,
you wanna have one number
in every single square on the board.
So it's 9 by 9, there are 81 squares,
so in every row there needs to be one of each number,
so the numbers 1 through 9, no duplicates,
same thing for every column.
And then this 9 by 9 board is divided into nine 3 by 3 squares
and you wanna have one of those numbers in each
of those 3 by 3 squares.
So let's just go through the distribution code,
so there is a lot like 600 lines-ish but that's not
so scary 'cause we'll go through all of it right now.
So it's not scary I promise.
So first inside of Main, it does things that, you know,
you're used to Main doing for you kind of what happened
in 15.C. We just did some things like [inaudible] the board,
doing some error checking.
And then it's also gonna have this Main game loop
where it's gonna be asking you for some input
and you're gonna respond to that input.
So you don't have to worry about any of those things.
There's also a new construction in C
that we're seeing in this Pset.
It's called the case switch statement.
So a lot of times in C you'll see something like this.
If, you know, this something--
this letter is an A then do something,
if it's a B then do something else,
if it's a C then do something else.
And this can get kind of annoying to type,
it's kind of more words than it needs to be.
So kind of an easier reading compressed way
of writing this is a case switch statement.
So your first block here switch and then some variable.
And this is the variable that was being used
in every single one of these if else if,
so it' kind of redundant to have to keep typing that variable.
So now you're gonna say, if C is the letter A, so in the case,
that is an A then there is a colon there
and then you could have all of your statements.
You can have if statements in there,
printfs whatever you want.
And then once you're done, you're gonna say break.
So that keyword is also used to do something like break
out of a while loop or a for loop.
In the case switch statement, it's the same word
and that means that this is the end of the case A
and now we can move on to the case that it's a B
and do something else and break and then so on and so forth.
So one thing to note is that everything after these cases has
to be integers, so you notice that I have chars here,
chars they're just integers, right?
Because they're just gonna be immediately converted
to their ASCII value which is an integer,
so I can't do something like a string here.
Only numbers but that's so common in C that we decided
to introduce a new construction for it.
So questions on case switch?
Yup?
>> You know how you had it set to C equals A
and you have an operation like a C is less than A or greater
than A or something like that?
>> So, in the case switch segment,
you can only do equality.
So with the, if and else if you can do things like an and or
and less than and all that but case switch statement is
so simple that it's really just equality.
Believe it or not this is pretty common thing
that you're gonna need to do in C, yup?
>> Can you have more than one line of code in these cases?
>> So can you have more than one line of code
in each of these cases?
Yes. It's only gonna stop as soon as you hit that break.
So this do something could be a hundred lines of code,
you probably don't want it
to be 'cause that's not the best design in the world
but you can keep going until this break statement.
We'll take a look at how we use case switch
in Main already, yup?
>> How do you-- how do you handle the else cases?
>> So how do you handle the else cases?
So we'll take a look at that later,
but there's basically a special case that says
if none of these are true.
So that's effectively our umbrella else.
Another question over here?
Yup?
>> Are there curly braces for each case
or will it [inaudible]?
>> So that's a good question,
are there curly braces for each case?
So there are curly braces around the switch
and this is definitely not like what we've seen in C before.
So instead of curly braces you're gonna have this colon
after the case and then you're kind
of end curly brace is the break statement.
So everything between a colon
and a break is what you're gonna do in each of the cases.
But the switch itself is enclosed in curly braces.
So definite a little bit unlike what we've seen before,
but it's a little bit easier to read and shorter to type.
Other questions?
Okay, so also written for you is this global structure.
So in our game of 15 we had one global array
and that just represented the board.
Now in sudoku we could do something like that
but we also need to keep track of some other things.
In the game of 15, we kind of just had one board, right?
If you typed in 15-4, you're always gonna get the same board.
In sudoku on the other hand,
we have a whole bunch of boards for you.
So something like, what board am I on,
is something you need to keep track of.
We also need to keep track of something like,
where is my cursor, right?
I can move the cursor around the board and it's gonna change X
and Y coordinates and I need to be able
to keep track of that somewhere.
So we could have created a bunch of global variables
and just put all those things as a separate variable.
But what we consider a better design is
to use something called a struct.
And a struct is basically a container
for a group of variables.
So G, this global variable G is a struct.
Meaning inside of G, I have a bunch of different variables.
Now, unlike arrays in which everything in my array has
to be the same type, if I say int A it's gonna have all ints.
Inside of a struct, I can have a bunch of different types
which I happen to have in this struct.
I have a couple of ints, I have an array
of ints, maybe a string.
So inside of G, there are a few pertinent ones,
so Y and X are gonna be the row and the column of the cursor.
So, unlike the game of 15 where we just say,
"What number do you wanna move?"
In sudoku we're gonna allow the user to move their cursor around
and then type a number, and then wherever the cursor is,
that's where the number is gonna go.
So we also have to represent the board somewhere,
so just like in the game of 15,
our board is a two-dimensional array.
So, it's gonna work exactly the same
as it did in the game of 15.
We also have the top left coordinates of the board,
which we'll get into and then the number,
just what game will I play in right now?
So if your implementation works on every number except 1,
you can find out where it's not working on,
but hopefully that doesn't happen.
So some other pertinent functions,
we'll also take a look at detail.
This restart game, so this is going to start a new game
but restart might be a little bit of a misnomer
because it's going to start the game that's based
on whatever board is specified in the G dot number.
So if I changed that struct,
to say I want a different board now, then call restart game,
it's not gonna reload the same board
but it's gonna load whatever board is specified
in that global struct.
So we also have these four drawing functions,
and these handle drawing different parts of the board.
So the borders handles like the plus and the pipes
and the minus signs and make it look pretty.
The grid logo numbers, they're kind of self explanatory here.
So we also have this show cursor function which we'll take a look
at and basically what that's gonna do is it's gonna set the
position of the cursor to somewhere in the board based
on what you set at the cursor location
in terms of row and column.
You can also show a message to the user with show banner.
This is gonna take a string
and it's gonna display whatever message you send it.
Now if you don't wanna display that message anymore,
you could just hide it with hide banner.
So let's take a look at this actual distribution code.
So, up here, we are first including the sudoku.hfile,
so inside of that we don't have any definitions of things,
but if we open up sudoku.h,
so we just have some defined statements.
So-- you know, the colors we're using,
you might wanna change something like author, hypothetically,
and then just down here we're setting up, you know,
what colors are gonna be used.
So we don't have to keep typing
in whatever numbers these actually represent.
So now, we're including a bunch of library functions,
one of which is this new one called ncurses
which we'll take a look at a lot--
take a look at in more detail shortly.
So now we're doing this super fancy defined statement,
you don't have to worry about what the heck all that means.
That's in a few weeks.
And so now, here is this global struct,
so we have the current level, the board's number,
and here's that int board.
So notice again it's just 9 by 9, it's a fixed size
and this is just a two-dimensional array,
so a grid of what our board is gonna be.
So, let's jump down into Main.
So here's all of our prototypes, so incase you need to remember,
oh like is there a functions in sudoku that already exists
or do I have to write this again?
You might just wanna flip up to this prototype sections instead
of going through all 600 lines of code.
So this is just a handy-- every function we've written
for you is listed right here.
So here we go, so once again, just a lot of our C checking,
the user supply the right amount of arguments, whatever,
figure out what kind of board they wanted,
in this case there are three levels,
debug which is a pretty much solve board,
[inaudible] which is kind of an easy board to solve,
and then Leap [phonetic] which is the hardest board to solve,
not the hardest but among the hardest,
so again just error checking, don't have to worry about that.
So now, what we need to do is, again, just board loading,
nothing fancy, so this is if the user says what board they want
and down here, well they didn't say what board we want then
we're just gonna pick one randomly, yup?
>> I have a question about the code that was a few lines up?
>> Sure.
>> It says ampersand G number ampersand C,
I don't understand why-- why it's doing that.
>> Sure, so what is this sscanf thing?
So this is something that were actually used
in GetInt or GetString.
We're using this sscanf function and what this does is gonna say
"I wanna take some string".
In this case the string I'm looking at is rgv2.
Now I wanna look for a number and a character
and I'm gonna save those in G dot number and G dot character.
So once this scanf is done,
those two variables are gonna contain whatever this percent D
and percent C turned out to be.
So it's kind of the backwards of printf.
In printf we said here's a percent D,
I want you to substitute what I tell you
for percent D. This is kind of the other way around.
This is saying "Okay, I have some string and I wanna look
for that first match in percent D. I'm gonna save it
in G dot number."
Same thing for this character
so why do we keep looking for this character?
Well this is kind of a cool little trick
to make sure that it's a number.
So if this is a number,
then only that percent D is gonna filled.
Five anything after it and that's gonna trigger
that percent C. Now what sscanf returns is the number
of things that were read in.
So the only way to make sure that I know
that this is a number is for only one of percent D,
percent D to be filled-- and percent--
percent D, present C. So percent D is always gonna be filled
first and if only that was red that means I typed in a number
and there's nothing after it, like there's no decimal,
there's no letter I have to have typed a number.
So that s just a fancy way of checking like we do in GetInt
to make sure that the user actually typed in a number.
And we'll see more of what these ampersand things means this week
in lecture and section, so yes,
so when in doubt just comment that's literally all we're
doing, make sure ends a number nothing else, other questions?
Yup?
>> What is fprintf?
>> So what is fprintf?
So this is unlike printf which just automatically prints
to the terminal like the standard output it's called,
like what the terminal is.
This just allows you to print somewhere else.
So this is something called standard error.
So just instead of print it to the terminal, you're gonna print
to some error thing that when we run our automated tests it's
gonna look to try to read in standard error
and see if this is printed.
So this just says, don't print out to the screen,
print somewhere else in this case to standard error.
So again stuff like, this you don't necessarily need
to totally understand in order to write sudoku,
just take our word for it that we're kind
of loading up the board.
So now we're starting up ncurses
which is this library we'll take a look at later.
And now we're kind of getting to code
that makes a little more sense.
So we're calling this restart game.
So even though a game hasn't been started yet,
we're calling restart game
because like I said it's gonna load the game based
on whatever value is stored inside of G. So notice up here,
we're storing that value inside of G dot number so now I come
down here to restart game?
I'm good to go to load some game
because we specified what I want to do.
So if this fails then we just kind of wanna shut down
and say I-- for some reason that failed,
I don't really know what you did.
And then you wanna draw the game for the first time.
So this draw all is basically just gonna take each one
of these individual draw functions and call them.
So instead of having to type them
out every time we have one function
that calls some group of functions.
So now we're in to something that looks very much
like what we had in the game of 15.
So just refresh the screen make sure that everything is good
to go, we've drawn everything and now we see this new function
to get the user's input.
So before we're using something
like GetInt now we're using this getch or getchar
and so we're just asking the user to type in some character,
so this is defined in ncurses this graphical library.
So this isn't something we wrote for you,
it's something someone else wrote for you and still gave
to you but all this is gonna do is return a single character
that the user typed in.
So if I type in A
in the keyboard this is gonna return the character, a char,
A. So now we just want to capitalize it
so if someone is playing sudoku with their caps lock
on because they just yelled at someone on the internet,
then we can still allow them to play and not have to worry
about handling lower case N
and then handling an upper case N is being the same thing.
So now here's the switch statement,
so we're switching over this character.
So in every single one of these case statements I'm gonna be
comparing it to the CH which is again the character the user
just typed in.
So in the case that it's an N I'm going to start a new game.
So here we're just setting the number,
we're saying I want a random new game,
make sure it's not too high
and we're gonna restart the game based on what that number is.
So now this break signifies that I'm done.
After I hit an N I don't wanna do anything below this break.
So in R you'll notice that it's pretty
like the exact same thing except
for what line is different or missing.
[ Inaudible Remark ]
>> Exactly this one that changes G dot number.
So if I call restart game G dot number,
the board I'm using hasn't changed,
I'm just gonna reload the same board.
So there is the difference between starting a new game
and restarting the same game.
I'm just not changing the currently loaded board
which is based on this global structure called G.
And finally we're using our fancy control macro
but you don't need to worry about how that works
and whenever the user hits control L,
it just forces the screen to be redrawn so this can be helpful
if you're debugging or something like that.
So now, after we've taken the action, we just want
to log the move for the purposes of automated tests
and keep going until the user types in a Q. So remember
that after all this we're just in a do while loop.
So you can take a look at this, if you actually click that brace
and scroll down, it will highlight the brace
that it matches so I'm inside, so that's the end
of my do statement and now here's the condition
for it to keep going.
So as soon as I type a Q this is not gonna continue to loop
and I'm gonna break outside of the code which is down here.
So questions on how this loop is going?
Basically, continually asking the user for a letter,
if that letter is a Q then we're getting out of here,
if it's another letter then we're taking action based
on these case statements.
Yup?
[ Inaudible Remark ]
>> Right.
[ Inaudible Remark ]
>> Yes, so restart game, if we look up here
into our prototypes we have bool restart game.
So this function's gonna return a Boolean.
It's either gonna be true or false.
So in the case that there is some error restarting the game,
like you deleted that bin file because you wanted
to see what would happen, then this is going to return false
and in the case that it returns false we just wanna send some
error message to the user saying,
you know, something went wrong.
So when we say this
if not restart game we're still calling this function.
So everything inside of this function is going
to get executed and then we're looking at its return value.
It's a little less explicit 'cause you're used
to seeing maybe like bool X equals restart game
and then looking at X but this is just kind
of a way of shortcutting that.
We're gonna look at whatever this returned and then
if it's true or false take action accordingly.
Okay, back down here so now once the user types Q we're just
gonna clear the screen and say thanks
for playing, so questions on main?
Okay, so just as a word of warning, you are gonna have
to kind of modify main or some
of the other functions we've written for you.
There's no-- unlike 15 where we gave you like--
just write your code for in it right here
and it's gonna work, we promise.
You do kind of have to modify functions like main in order
to add the functionality that we're asking you to add.
So now we're getting into the drawing functions
and let's take a look at the ncurses library before we try
to wrap our heads around those.
So before we do so because GDB is awesome we want you
to be able to use GDB for this Pset but as soon as you fire
up sudoku you'll notice it kind of takes over the entire screen.
So let's just walk through really quickly how we can still
use GDB with our program.
So if we have our plans and we open up a terminal window
and so notice that I'm using the full terminal not the little one
inside of gedit, so if I see the int of my Pset 4,
there's my sudoku, now I can run sudoku debug 1.
So you notice this kind of took up the whole screen.
There is no word GDB can kind of go.
So I loaded this debug board,
you notice there's only one space that's not solved
because we have a single dot.
So now let's say I wanna use GDB.
What I can do is up in the terminal,
go up here to File and Open Tab.
And so just like Firefox's tab or Chrome,
your terminal can have tabs so you don't have
to open up a new window.
Now over on this tab, I wanna find out where sudoku is running
so to do that I'm gonna type in P-I-D of and then the name
of my program, so sudoku.
So this says there is some process running on my system.
If you use Windows and you ever hit Control Alt Delete you can
see that long list of processes.
So each of one those processes has a unique ID.
So in this case, I'm running some process called sudoku
because I just typed in dot slash sudoku.
So I wanna get the number that identifies that process.
So in this case its 2220 so as long as sudoku is running,
this number is not going to change.
So instead of starting up a new sudoku, we wanna tell GDB,
"Actually I just want you to attach
to that already running process."
So to do that, we're gonna say, GDB then sudoku
and now we're gonna specify that process that we just got back
from pidof so 2220, hit Enter and now we get some random text,
don't worry about that.
So now let's set a breakpoint.
So we're gonna say "Break on restart game".
So this says as soon as I hit the function restart game,
I want you to pause so in GDB I can do things
like printf variable and step through the code.
So I say "break restart game" breakpoint one
if you wanna verify that that actually worked we can say
"info break" and you see we have one breakpoint it's located
at restart game which happens to be defined on line 489.
>> And so now when we ran this GDB we actually paused the
execution of our existing sudoku program.
So if I just type in continue, that means it's gonna be--
it's gonna continue to run.
So now we're basically sitting inside
of our do while loop inside of main and we're waiting
for the user to type something.
So because I put a breakpoint in restart game let's type
in an action that's gonna restart the game,
so let's just say N. So you notice over here
that my text turned red for a second,
which means there's new output in this tab.
So if I switch over to here, we can see we're back
into our normal GDB state, so I can see the line I'm
about to execute, if I wanna see the source code
around that I can say "list" and here is exactly
where I am inside of the running sudoku program in the other tab.
So does that make sense to everybody?
[ Inaudible Remark ]
>So when-- why do we say continue?
So when I have said GDB, sudoku and then the pid that paused it.
So before I can actually do anything I need to say,
"Okay, keep going now."
So that's the only reason I said continue so we wanna continue
until we hit some breakpoint where I said break restart game
and that's my breakpoint, other question?
Yup?
>> So how do you link sudoku to the other tab?
>> So how do we link through that other tab?
If you remember-- so let's just get out of here.
So remember we did two things.
We first started sudoku, then we came over to this new tab
and we said pidof sudoku
and this is gonna return the unique number
that represents the sudoku program that I'm running.
Now when I'm say GDB that number,
that process ID 2220 that's gonna say
"Don't run sudoku again"
but there's an already running sudoku and it's located at 2220.
So I want you to go and debug that rather
than starting a new one.
So now we're attached to this other tab, other questions?
Okay, so really quickly, whoa.
[ Pause ]
>> So the problem set mentions, you know, just using GDB
like that but there's an actual really cool feature of GDB
that allows you to browse the source code
as you're running it.
So this is the TUI or Text User Interface.
This is just a much cooler way of using GDB
that David didn't tell you about.
So now that you're all glad you came
to the walkthrough I can say, GDB sudoku 2220 and add
in this -tui for text user interface.
Now when I hit Enter, oh-ho, oh ho ho, we have this new output
so again it tells us to hit Enter and we do, all right.
So now let's just say the same thing we said before
so we can say, break restart game.
We have our breakpoint just like we did before
and now let's continue.
So now again we're continuing, we're waiting
for the user to do something.
So we come back over to this other tab, we're gonna try
to trigger that restart game so I'm gonna hit
"N" there is my red, oh yeah that's cool.
So now we can see exactly where we are
in the code above our GDB prompt.
So if I do something like next you can see up here
that I'm stepping through everything.
So now let's say I wanna go into draw numbers if I say
"step" now I'm inside of this draw numbers program
and this is this sodoku.c that you're working with.
Now if I type next just keep going I'll put a couple
of numbers you come over to this other tabs you can actually see
we're drawing the numbers step by step.
Yup?
>> So what's the difference between continue
and next just next just one by one?
>> So what's the difference between continue and next?
So that's a good question.
So continue is going to keep the program going
until you hit another breakpoint.
So if I had another breakpoint somewhere else
or even it came back to restart game and I said continue,
it's only gonna stop at a breakpoint.
If I just say next, it's only gonna go one line at a time.
So notice here actually even though I just hit next I can
keep hitting Enter and effectively going to next,
well if you don't type anything
at the GDB prompt it's gonna do the last thing
that you told it to do.
You know the short cut if you don't want
to type next you can just type
"N" it will do the same thing, question?
>> Is the breakpoint an error in the code?
>> So is a breakpoint in error in the code?
So breakpoint is just a little stop sign inside of your code.
That says when sudoku is running,
once I hit this line I want you to stop because I want
to be able to do things like see where I am inside
of the source code or print out variables
like if I wanna know what the current value
of ice I can just say printi
and I can know currently that I equals zero.
Now let's see, let's find out what J is.
So, if we print J. Now J is six and we go back over to sudoku
that kind of makes sense.
Because, I'm in the first row and I'm in the 0, 1, 2, 3, 4,
5-- 0, 1, 2, 3, 4, 5 and we're about to print the sixth column.
So breakpoint is not necessarily an error, it's just a place
where you want to stop.
It could be a line number or a function, question?
Yeah?
>> Is this a classified breakpoint
or is that [inaudible]?
>> So you do-- do you have to specify a breakpoint?
So yeah, so if you don't specify any breakpoints
and just say run, that's gonna be the equivalent
of just running it without GDB 'cause it's not gonna have any
place to stop.
So until you tell the program when to stop and when to be able
to step through the program line by line,
it's just gonna run normally.
So, if you wanna break on main, you can just say be--
create a new breakpoint on main.
And so this is gonna say before you go anywhere immediately stop
and let me step through line by line, other questions, yup?
>> Can you use next without using continue?
>> So, can you next without using continue?
Sure, I mean if I just say next then I can go to the next line,
right, or if I restarted-- if I restarted GDB,
just said the same thing.
I'm gonna break on restart game?
'Cause now when I say continue, okay we're gonna continue
until we hit this breakpoint and so at that point I can say next,
next, next, next, next
and I don't necessarily have to type continue.
If that's what you mean.
>> I'm sorry I'm still confused why you continue at all,
so if you didn't put continue
when are you gonna run off to that breakpoint?
>> Right. So, when we run GDB and this is kind
of a special case, it wasn't-- it didn't do this before
but because we're doing the special thing
where we're attaching to an already running program,
when we say, GDB, sudoku
and then give the pid it's pausing it.
So, until I say continue it's paused.
So, once I say continue it's gonna say okay, keep going now
and all the breakpoints I've created are now active
and they're live and they're gonna stop the code.
So, just yeah, so before you do anything
in this special two-tap thing just say continue.
After you set up all your breakpoints
and then you'll be good to go, yup?
>> So, do you have to put the breakpoints in your source code?
So, the breakpoints are defined by GDB
so once I quit GDB which I can.
As I quit, all of my breakpoints are now gone.
Whoa, okay so the G-- breakpoint is something that GDB creates
as it's running your code.
It doesn't actually modify the dot C file itself
and there's no way of putting
in a breakpoint into the dot C file.
But these are kind of thing you create on the fly
as you're running GDB.
Are there debugging questions, yup?
>> Can you put a breakpoint in the dot H file?
>> So, can you put a breakpoint in the dot H file?
So, generally in the header files there's no
executable code.
It's just kind of like definitions of things
and define statements so none
of that is ever gonna really be executed as a line of code.
So, typically you're only gonna put them
in the dot C files, other questions, yup?
>> Breakpoints will they generally always be in main?
>> So will breakpoints always be in main?
Not necessarily, so when we came over here,
we created a breakpoint inside of restart game.
So I can also put a breakpoint at an arbitrary line number
like instead of maybe I don't wanna break let's go
down here to-- so let's just come right here.
So, let's just say I wanna break out this line.
So if I say, break 168 it's gonna break at that line.
So this isn't necessarily in main and it's not necessarily
at the beginning of a function but I can kind
of break wherever I want.
If you wanna do something quick and just step
through it immediately you don't wanna go
to any functions you just say break main,
that's just gonna allow you to kind of start of fresh, just,
you know, print everything, go line by line you don't have
to worry about jumping to functions or anything
but you don't to have to say break main, it's just one way
of using GDB to pause immediately.
If that's what you wanna do, yup?
[ Inaudible Remark ]
>> Yeah, so the difference between next and step.
So let's go back into restart game.
And, again I'm gonna say continue because I paused it,
come back over here restart the game with N and now we're here.
So, if I say step then I'm going to jump
into the function load board.
So if I say right here step,
I'm now inside the function load board.
So now, if I say name so S printf this is just a function.
If I say step, I'm suddenly gonna be inside of S printf.
But for our purposes that's not very helpful,
so if I say next instead we're gonna kind of jump
over that function and execute it all at once.
>> So, step says I wanna go into the function and execute
that function line by line.
Next says that function is just one line execute it
and be done with it.
Are there last GDB questions?
[ Inaudible Remark ]
>> So if you're inside of a do while loop when you wanna kind
of get out of it so that's where continue comes in handy.
So, if you have this really long while loop
and you just wanna pause maybe at the beginning instead
of hitting next, next, next, next,
you can just say create a breakpoint at the beginning
of that loop and say continue.
And then, you can jump right back to the start
of that while loop if that's where your breakpoint is.
All right so let get out of GDB with Q say yes,
and that's it for GDB.
All right, so now let's take a look at ncurses.
So, this is the graphical user interphase library.
So, we're not quite at the level of web pages with buttons
or actual programs that you would run like Microsoft word
but this is a lot nicer than the game of 15.
So, what basically the advantage of ncurses is that we can print
to anywhere on the terminal.
So, in the game of 15 when we had that function draw,
we need to draw the board one row at a time.
Once you're finished printing a row,
we better hope you printed it right 'cause there's no
going back.
We already printed it.
With ncurses you can say I want an X at the 10th row
and the 70th column and it's just going to put it there.
So ncurses, it's operating on row--
a row column basis which I kind of like,
but I guess David doesn't based on the Pset.
We're-- maybe we're used to working XY
so just remember ncurses always row, column.
So, a couple of good functions in ncurses,
one is the move function, this is gonna take the cursor
and put it to wherever you want on the terminals.
So the first argument is the row second argument is the column.
Now, if you wanna write something
to the screen you're gonna use this move add stir,
move add [inaudible].
This is gonna say I want the cursor to go to some location
on the screen again my row and my column or my Y and my X
and I want you print a single character or a single string.
So, if I say move to you know zero,
zero and then I wanna print--
print like the letter A then I could say move add stir, zero,
zero A says "I want this character
in this place on the screen."
No longer do I need to printf things in order.
So, this other function we're getting input we saw earlier
because getch or this getch is a way
of getting a character from the user.
So, when they type in numbers on the screen,
it's going to get the char representation of those numbers.
So, a one is not going to be a one.
It's going to be a one in those singe quotes.
So, ncurses also build in some constants for characters
that otherwise don't have
like a letter representation like the arrow keys.
So this key underscore up and the same with down left
and right are defined constants inside of ncurses.
And this says whenever the user types an arrow key it's the same
as them typing one of these numbers.
So when you say getch you can actually determine
if they pressed an arrow key which you can't really do
if you we're just using something like GetIint.
And so finally, this control L not defined by ncurses
but something we wrote ourselves.
So, questions on how we're getting input from the user
or how to use these, yup?
[ Inaudible Remark ]
>> So, if I type-- so what happens
if I want a number and I use getch.
So, this is going to take
in the character representation of the number.
So, remember that nine is different than "9".
So, if I type in a nine into getch,
it's gonna give me back the character nine, so character
in this case not meaning letter but being the char data type
in C which represents a single symbol on the computer.
Does that make sense?
Okay. Other questions?
[ Inaudible Remark ]
>> So, the single quotes you remember,
is how we define a char, and C, or a char.
I don't even know how to pronounce it
but just a single character whether
that be a letter or a number.
So this translates to the ASCII values between zero and 127
and just making sure we cave
in these quotes distinguishes the ASCII value one
which is some non-printable character and the character one
which is the printable one.
So this is just like in Pset 2 when you had to deal
with converting an A to some number or some number
to it's actual ASCII number.
Other questions, yup?
[ Inaudible Remark ]
>> So, inside of sudoku if you--
we go back to what it looks like?
When we run it, when we hit the arrow keys we wanna be able
to move this letter green guy around.
So we need to detect if the user typed in a left, or an up,
or down, and the way we do that is we just compare it
to these defined constants.
So, if I call getch and the user types in an arrow key.
It's gonna return this constant key up
or key down left or right.
So, we can just-- we don't even have to worry
about what these numbers are--
what these constants actually represent.
We can just say if the character is the key
up then I wanna do something, so comparing it to these instead
of comparing it to some number or character.
Okay, so now we've covered the distribution code
and the library we've been using
so here is our to-do list for this Pset.
You wanna be able to move the cursor
around once we have the user be able
to move their cursor we wanna allow them to input some number.
After they input the number we wanna be able to tell them
if it's definitely wrong or some illegal move in Sudoku.
Then, once we have that working we want to allow the user
to erase their number.
So make sure that if they made a mistake and they wanna get rid
of their choice they can do that.
And finally, check if the board is one
and once the board is one, stop the user from playing anymore.
So, remember this function show cursor is going
to move the cursor based on the-- based on the values of g.y
and g.x. So, all the show cursor function does is it calls this
ncurses move function which is pretty complicated
when you actually look at all the math we're doing.
But all you need to worry about is changing the Y
and the X inside of this global struct because as soon
as I call show cursor it's going to read those values
that you changed and set the cursor according
to those values.
So you don't have worry
about calling the move function itself.
When I actually wrote this Pset I didn't figure this out
and so I had all this crazy ncurses code which is terrible.
So, instead of trying to worry about that, you just need
to change the values inside
of this global variable and call show cursor.
That's gonna read those values and put the cursor back.
So now, when you look at this board it's a little confusing
what we mean when we say, you know, X and Y is 4.
So, inside of our board we just have nine rows across
and nine columns down.
So zero, zero is not this plus sign or it's not the top
of the terminal window.
It's just the first number in the grid.
So this at the end here is board 2A, row 2 column 8,
I mean there's not that many characters in the row
because we have spaces, we have pipes,
and all that kind of thing.
But as far as your board representation is concerned
those don't exist.
We only care about what numbers are in each of the spaces, yup?
>> So, are the corners, the pipes and all that stuff is sort
of outside of the array?
>> Yes, so are these corners and pipes and stuff,
so the array doesn't even know they exist.
So these are gonna be drawn in one
of those different draw functions that we looked at.
So, similarly with the cursor if I have it in the middle
of the board, I'm in row 4 column 4.
Even though I have a bunch of space at the beginning
and these minus signs so just keep in that in mind
as you're writing your code.
Even though we have all these pretty aesthetics as far
as those global variables inside the structure are concerned it's
just a 9 by 9 grid and there's no fancy aesthetics.
So questions based on that?
>> So it just shows the cursor in the center
of the board to start off with?
>> Yes. So yes, so it's starts off in the center
of the board, other questions?
Okay so-- yup?
[ Inaudible Remark ]
>> So this, so when you just fight--
when you do a git clone on Pset 4 and you just fire
up sudoku, this is what you get.
So, all of these are already done for you.
And the way that we're displaying this is
with the ncurses library.
So, if you flip through all the draw functions, you'll see lots
of moves and move ad characters and stuff like that.
So, it's just a set of a real--
like a lot of functions that someone else wrote for you
that allows you to do things
like this a lot easier, so that's our board.
So, now let's take a look at how we would move it.
So in order to move the cursor, all we need to do is change
that Y and X. So, pressing a different arrow is gonna do a
different thing, right?
We're gonna need to make Y go up or down or make X go up or down.
Because we can only move in one direction at a time
and don't worry about diagonals
and we're only changing one of these at a time.
So right now, if we go back to main, you'll notice
that it only has a few cases.
If we go too far, way too far, so here in main we have the case
that you hit an N, the case you hit an R,
and the case you hit a Control L. So, here is probably
where I wanna put the case
in which I had the key up, what do I want to do?
So, you probably wanna write some function that says
if I hit something that's not already defined I wanna take
some action.
>> So one thing to keep in mind if we don't want allow the user
to move the cursor off the board, so that includes moving,
you know, into the edge or moving over to the D in sudoku.
And we just wanna make sure that the user stays
within this 9 by 9 grid area.
So before you just arbitrarily
like blindly make X bigger every time you wanna make sure
that you're still within the board before you can make
X larger.
So, questions on how we can go about moving the cursor, yup?
>> You can go back one slide [inaudible]?
>> So when we move-- when we hit some arrow key,
we just wanna modify this global struct and change the X and Y
and then the next time we call show cursor,
the cursor's gonna move because that's what that function does,
just reads those values and changes the cursor, yup?
>> Do you have to modify the case switch so that
if we use your [inaudible] left, right,
up or down then the case switch automatically changes?
>> Exactly, so we need to modify this case switch
in adding some new cases because this, everything inside
of this case switch is everything the user can possibly
do which right now is NR control L. So,
if we wanna allow the user to press some button we just need
to add a new case and define what pressing that button does.
Other questions on moving the cursor?
Okay, so now let's take a look at inputting numbers.
So, remember that we need to take the numbers 1 through 9
as input and these are not going to be returned from getch
as the number one, it would be returned as the character one,
so just remind if our ASCII works.
Quotes one is not one,
quotes one is instead quote zero, plus one.
So you can still do these things like add a character
to an integer and it will work fine.
But just remember that when the user types one,
if you think that's gonna be the integer value one,
then your code's gonna be little bit off.
So, representing the board is gonna be very similar
to what we did in 50.
Board is going to be these two dimensional grid and inside
of board IJ is gonna be the number at row I column J
because ncurses works in YX not in XY.
So, you know that the cursor is always
at row g.y column g.x. So, if we change the value of the board
at IJ it's gonna change the number that's displayed.
However, if we just changed it immediately that's not actually
gonna change what's displayed on the terminal
because that's not changed until we explicitly call one
of our draw functions.
So those draw functions are just gonna look
at what's stored inside of this board and iterate through it
and print out whatever is there basically.
So again, we don't need
to use this ncurses function move add character ourselves we
can just change the board
and redraw it using some redraw function
that was written for us.
But keep in mind that as far as efficiency is concerned
if I just a type in a number, I probably don't need
to change all the plus signs and the minus signs.
So just make sure you're using the right draw function
but you can kind of look at each of them,
they're self-explanatory just make sure you're not redrawing
things that you don't need
to redraw 'cause that's a little bit of a ding on efficiency.
So, one thing we need to keep in mind is we can't allow the user
to change the numbers that came with the board.
Else I would just saying 1, 2, 3, 4, 5,
6 and I'd win really fast.
So, once the game has started we need some way of remembering
which numbers were already on the board.
So, if I go and try to change a number that was already
on the board, your program says nope, can't do that.
So just a tip, if I have some array
like say it was called a G dot board for some reason
and I just tried to set it equal to some other array,
that's not going to work.
So, you need to figure out a way
to effectively copy your original array
into some other array that you keep track of somehow
and before you change any space,
make sure that you're allowed to change it.
So, questions on how that would work?
Cool. So inside of our case switch statement
to make things a little easier you can actually do something
like this and combine cases.
So, this says in the case of an A, or in the case of a B,
or in the case C, I wanna take some action.
So instead of saying case A, have some code,
copy paste that into case B, copy paste that into case C,
we can combine them just like this.
So this is effectively A, or B,
or C. So as I mentioned before we also have a special case
called default and that's going to be the else.
The if, none of these cases are true,
I still wanna do something.
It's gonna jump to this default case automatically.
So questions on how I'm combining these cases here?
You'll find this to be super helpful.
All right, so now just a word about design.
As you're designing your code, you wanna try to factor
out as much code as possible.
And what do I wanna mean by that?
So if you find yourself, you know,
writing the same three lines of code all over the place
which you may, you kind of wanna factor that out
into some function that you can reuse so instead of copying
and pasting code all over the place which is a very,
very nice temptation, what you wanna do is try
to design functions that are reusable
so I can use this function here
and even though this case is a little different I can still use
my function here because it takes some argument
or something like that.
And, also rather than going in and having all
of your codes stay in main you probably wanna create your
own functions.
So in 15, we did that for you.
We said here's the function called init,
it's probably a good size
for a single function put your code there.
In this case we're not really holding your hand that much
but what we do wanna do is take our changes and kind
of consolidate them into separate functions,
that from the existing code we can just call
that function instead of just adding swats of code to our main
or the draw numbers or whatever it is you need to modify.
So, questions on inputting a number, yup?
>> Can you go over again about the arrays
and why we can't use an array?
>> So you can't-- so you can use an array
and you probably want to.
But if I want to take array one and make a copy of array 2.
So, I have this existing array, array 2
and I wanna copy it into array 1.
I can't just say array 1 equals array 2
because this is just a pointer right?
So, it's just a reference to some memory address.
So, if I do this I just make array 1 and array 2 point
to the same memory address I didn't actually copy the values.
So, if I change array 1, array 2 is gonna change too
because they're just looking at the same location.
So you need to explicitly copy your array.
Other questions on inputting numbers, yup?
>> The user is inputting something
that we're thing that that's a char?
>> Yes.
>> You need to store that into the array with int array?
>> Yes.
>> So how is that working?
>> So we need to convert a char into an int.
So, this is very similar to what we did in Pset 2
with our [inaudible], we needed
to convert some char into an int.
So we're gonna do the same thing here.
The user types in a 1, we need to actually store a 1 inside
of our board not ASCII value of 1.
Other questions, yup?
>> Will you use the A-tui [phonetic] function to do that?
>> So, would you use the -tui function to do that?
So, A-tui takes some string, returns an integer
so we're not taking strings, we're taking single characters
so we basically need to look at the ASCII table and say,
"what value do I need to add or subtract in order to get
from quote zero to just the number zero?"
Other questions on inputting numbers?
Okay, so now for kind of the meat of the problem set.
Determining if a move is legal so in this case, after we--
and we enter any number, we need to check if that's a legal move.
And if it's not a legal move we wanna use this show better
function and say this is wrong.
So, just-- to avoid some confusion if I type
in a wrong move and I show the banner it's wrong
and then I type in a right move, my banner is gone.
And a few set makes this very explicit,
it doesn't need to persist.
But every time there is an illegal move, so the banner
and it just on it's like consider move by move.
You don't need to look at it
if there's still an illegal move on the board.
Just if it's a legal move show the banner
if it's not a legal move, don't show the banner.
So here are the three rules again
to make sure the move to be legal.
The number doesn't already exist in the same row,
the number doesn't already exist in the same column,
and the number doesn't already exist in the same 3 by 3 block.
So we need to check each of these cases.
There might be a temptation to get a little fancy here.
My advice is you don't because there a lot of things
that you're like, "Oh this probably works, right?"
And it probably doesn't unfortunately.
There are very few fancy ways of doing this so I'd advice you
to actually check each of these cases exclusively.
There isn't some mysterious design thing
that you should be picking up on.
You need to check all these cases.
So let's take a look at the row and the column case.
So we know that a user just inputted a number
into G dot board, g.y, g.x 'cause that the row
and the column of a cursor.
So whenever we make a change,
that's where the change just happened.
So in order to check everything in the same row and everything
in the same column, we just need to have some iterator
over the row and over the column.
So, we need to check if we just inputted something into zero,
zero, we need to check 0, 0, 0, 1, 0, 2, 0, 3, 0,
4 and similarly in the other direction.
So if the number is already found we know the move
is illegal.
So questions on what I mean by legality here?
So just if it's already in the row or it's already
in the column and we know the row in the column
that these are inputted then we know it's an illegal move
and we need to show the banner.
>> So, here's what I mean by that.
So if I just inputted this dot, here is my row everything
in row zero and the column is going from zero to 8 and inside
of my column, that second part of my array stays the same
and my rows are going again from zero to 8.
Does that make sense?
So, a harder one is the 3 by 3 block.
So notice that the board is divided into these contiguous 3
by 3 blocks so there are 9 of them.
So, if I input something onto this first block I only need
to check this first block.
I don't need to come down here, if I inputted something
on the top left corner.
So, the way that we're gonna check that block,
is we need to figure out where that blocks starts.
So let's say that I-- we just know
that let's say I inputted something in the middle.
I can't just go 3 columns over,
3 rows down because then we'd be kind of combining blocks here.
So, even though it's a 3
by 3 block it is not one of the 3 by 3 blocks.
So in order to do that, we need to determine where each of the 3
by 3 block starts which sounds like a job
for division very similar to what we did
in Pset 1 with making change.
So, after we determine the top left of the block then
at that point we can just go 3 columns over, 3 rows down,
and just look for that numbers.
So we need to actually iterate through that 3 by 3 block
and look at 9 numbers and look
if there's something that's already inputted.
So, questions on how we can do that, yup?
[ Inaudible Remark ]
>> Yeah.
>> What did you mean by that?
>> So just-- let's say that I inputted,
let's say that this board was totally blank,
or there are just a few numbers and I make a move.
And that could be at that point, it could be a legal move.
But it could be the wrong move like I later find out that,
that 6, was supposed to be a 5
but at the time 6 was still legal.
So you're not checking if it's wrong, you're only checking
if it's illegal or comp, you know, obviously wrong.
So just a subtle distinction there that because in order
to check if something's wrong, you actually need
to solve the board which is the hacker Pset,
so unless you wanna trick yourself
into doing a hacker Pset, just remember what that means, yup?
[ Inaudible Remark ]
>> So, inside of-- so G is our global structure
so the structure has a container for multiple variables so one
of those variables is board, just a two dimensional array
and two other integers, separate integers Y and X. And,
g.y is always the position of the cursor,
that row of the cursor and g.x is always the column
of the cursor.
So, after you implement moving the cursor, you're gonna make--
you wanna make sure that those values always contain
where the cursor is.
And so now, that's how I can figure
out what value the user just changed or value I need
to change on the board, yup?
>> So, every time the user moves a cursor we think
that they're actually inputting a number?
>> So not necessarily.
So the user can-- moving the cursor is different
than inputting a number.
When I move the cursor I wanna change this g.y and this g.x.
When I input a number I don't wanna change
where the cursor is, I instead wanna change the board based
on where the cursor currently is.
So depending on if they entered in a number
or hit an arrow key we wanna do two different things,
both modifying the struct
but modifying different parts of the struct.
Other questions?
Okay. So, that's move legality so we also wanna allow the user
to remove their number especially if you're
as bad as sudoku as I am.
So, the problem said specs, problem said specs says,
we wanna be able to delete the number if we hit the backspace,
the delete key, the dot, or the zero.
So, again ncurses comes in with these fancy constants.
Key backspace, Key DC for delete dot or the number zero
so it just as a note as your-- right in your palm set,
and you notice that "Oh, my key DC doesn't work",
or something like that.
Don't worry about it it's just your computer
and cursors isn't ready for your computer yet.
The Pset mentions this in a footnote but if you just--
just make sure you look at all four of these cases in order
for deleting a number and don't worry if something
like Key DC doesn't work.
Zero and period should definitely work though.
And so you notice you probably wanna do the same thing based
on multiple cases again.
Unlike we saw before, we can combine these cases
and only take one action instead of saying case key backspace,
copy paste, case key DC, copy paste and stuff like that.
So inside of draw numbers you'll notice
that a blank is represented by a zero,
so when we delete a key all we need
to do is set the board not equal
to whatever the user typed but a zero.
So, questions on blanks?
So again, just remember we can't delete numbers
that we came with-- that came with the board.
Now, remember I said factoring a common code,
this is something you need to do in two cases,
the user inputs a number and then makes sure
that I'm allowed to change it.
User inputs a blank.
I didn't make sure I'm allowed to change it.
So writing a reusable function here is gonna make our code much
better designed.
We're doing the same thing in two pretty different moves,
deleting a number and adding a number?
We still need to do the same thing
so we can call the same function.
So just a couple of lot of other questions,
is inputting a blank always legal, is it necessary check
for legality, and can I do need to check as the game as one
if I just removed the number.
So things like that, okay you think about efficiency.
I'll leave the answers to those to you.
So that's how we need to input a blank.
So any questions on what we need to do there?
>> It's always the last one?
[ Inaudible Remark ]
>> Right. So just-- this thing about efficiency like do I need
to necessarily check things?
If I just removed a number do I need to necessarily check
if the game is one now?
Just things like that to make your code a little bit
more efficient.
[ Inaudible Remark ]
>> Well no, what I'm saying is let's say that as a user,
I just typed in a blank.
>> Yeah.
>> As the program, did the user--
it did-- by inputting a blank.
Did the user just win?
Definitely not because the board needs to be filled,
so just little efficiency things like that like if I just--
if I just deleted the number, I definitely didn't win.
But if I just input a number,
I might have just input the last number.
And when I'm inputting a blank, I definitely didn't just--
that was at my last move.
So just things little efficiency things like that, not necessary
to correctness but they might be handy for design.
Other questions?
So finally, we wanna check to see if the game is won.
And in this case, you wanna freeze the game
and don't allow the user to make anymore moves except
for starting a new game-- quitting.
So the game is won under these four conditions:
if every square is filled in and every row contains one
of each number, every column contains one of each number
and every three by three block contains one of each number.
So, every time the user makes a move, it's then time
to check if the game is won.
So, when you're thinking about how you're gonna implement this
and efficiency, you only need to look
at every row and column once.
There's no need to look at the same column twice
if you've already verified that that column is okay.
So there are couple ways you could do this.
You could check to see if you found every number.
You now, have something like in array
of numbers, zero through nine.
And every time I-- yeah, zero through nine or one--
zero through eight or one through nine,
depend on how you set it up and just say, "Okay.
I found a one, that's a check mark.
I found the two, check that off."
Then once you've gone through the column,
see if you've check off every number or you could do something
like see how many times you see each number.
And if you ever see a number twice then it's definitely
not won.
So there are bunch of different ways to do this but it all boils
down to keeping track of what you've seen in a single row
or column and making sure that that's good
to go before you move on to the next row or column.
So using an array here is probably a good way
to approach this.
And again, this is where you have the tendency
to maybe I can get fancy here, don't.
Similarly, we only need to check every three
by three square once.
So there's no need to keep checking one
if you've already looked at that square, so you notice
that we we're thinking about move legality,
we probably already wrote a function to see if there's
about like having a given three by three block is valid.
So that's just one way of thinking
about designing your code.
I'm doing similar things and checking if the move is legal
and checking if the board is won.
So, design your functions to be reusable.
And so, just another efficiency question,
you notice we have these four conditions.
Do we really need to check the first one
if the last three are true?
I don't know.
So just-- lest you forget, reuse as much code as possible.
It'll make your Pset much more elegant and better designed.
And you'll get more points and we'll be happy.
So any questions on checking if the board is won?
Yup?
>> Should we be checking like every move or should we wait
until the whole board is-- ?
>> So should we be checking every move or shall we wait
for the whole board to be filled.
That's a question for you unfortunately.
You know, which-- which way do you think is more efficient,
or which way is the code more elegant,
which way is gonna run more efficiently, you know,
determine when your one is checked.
Okay, so just to recap, the question was do we need
to only check if one after every move for or do we need to--
or can we just wait until we know every square is filled in?
That's kind of a question for you.
Which of those ends up to be more efficient based
on your code, is it more efficient to look
at every square and then see if it's won or is it more efficient
to every time you make a move even if it's the first move,
look at every single square.
So that's up to you.
And as you run your code, you know,
you'll probably make a decision,
oh this one is way better, I'm gonna do that.
Other questions on the Pset as a whole?
Yup?
>> You said checking every numbers like doing a search
and you said don't be fancy.
So, when you're looking at efficiency, you wanna see
like really efficient searches or--
or can you really just be like looking
through like [inaudible]?
>> So what do I mean by don't get fancy?
So I do mean-- so I don't mean like trying
to binary search the sudoku.
That's not what we mean by efficient.
But things like I'm gonna multiply every number
and see if it equals this.
That's like a fancy thing.
That's not gonna work, so don't do that.
So, just stick to these-- stick to those three rules.
Let's say you're doing fancy like actually check
if every number is there.
>> Okay. So efficiency isn't necessary if you
like smart researchers or everything
and like binary [inaudible]?
>> Right. So I mean in this case,
we can't really binary search it right?
It just doesn't really apply to this problem and so, yes.
So based on this problem,
the most efficient way we can do this is
to actually look at every square.
>> Okay.
>> Instead of trying to do some like I just discovered this
and I made a breakthrough in sudoku algorithm.
Just look at every single one.
Other questions on the piece that has a whole?
Yup?
>> You recommend implementing each of these features
in the order that you listed them?
>> Yes, I do.
And in fact that's why I listed them in that order.
I do recommend [laughter] implementing them in this order
and that should be a numbered list.
That's actually my fault.
So yes, so, implementing in this order is kind
of just a logical way of stepping through it
and the functions that you wrote in the beginning steps,
you'll probably end up using
in the functions you wrote in the later steps.
So, reusable code is kind of our goal with this Pset.
So just before-- you don't--
remember that you need to implement one
of these additional features which I've listed here
and won't read to you 'cause you can read--
just make sure you do at least one of these.
If you wanna do more than one, go for it.
Become your TF's favorite student
but last questions on sudoku.
Yup?
[ Inaudible Remark ]
>> Sure. So, when you input a number, so, could we just go
like back to how we can reuse code and something
like checking or inputting a blank?
So, when we inputted number.
We need to make sure that the number that we're trying to--
the space we're trying to change did not come with the board.
Now when we input a blank, we need to make sure
that the number we're trying
to delete did not come with the board.
So if you just have some generic function that said, "Does this--
did the space come with the board?"
Then you can reuse that in the multiple--
multiple parts of the problem that you're trying to solve.
So that's what I mean by a reuse code.
Write some function once and use it as much
as your heart desires.
Are there questions on anything sudoku?
All right, then that's it for the walkthrough
and good luck with Pset 4.