So in this video I'm still working on the wish list for Sudoku and I'm at find
blank. Let's see, what was it supposed to do?
It consumes a board and it produces a pause, and it's supposed to produce the
position of the first blank square. And it's allowed to assume the board has
at least one blank square, so here we go. Let's do some examples.
Let's see, check expect find blank. Now what was that board that's totally
blank. Now that's board one.
Board one is totally blank. Coming down here to find blank.
So if I call find blank on board one Then the first blank position is zero, the
position of the first cell. And let's see, check expect find blank.
And if I say cons, I don't know, it doesn't matter really, two into rest of
board one. So that's a board that only has it's
upper left full. Then that's supposed to produce one.
That's probably enough example, so I guess this is a list I should have two
deep. Really should I?
My guess, I don't know, let's try it. Check, expect find blank cons 2 cons 4
rest rest of board 1. So that's a board that starts with a 2
and a 4, then the whole rest is empty. Then in that case, the first blank is a
position 2. That's my examples.
So how are we going to template this. Define find blank.
Well, it consumes a board and it seems like it kind has to work its way through
a board. Yeah, so let's see.
That template's according to board. And board, of course, is just a list of
pos or val. So this is the list of template.
Empty board, dot, dot, dot, then quickly remind myself what board is a list of.
Board is a list of either val or false. So back down here, dot dot dot something
First, a board. And this is going to be either bow or
false. Rest of board.
Let's see, rest of board is of course, the rest of the boards, so this is still
under the list. So this is a natural recursion here, fine
blank rest of board. And let's see.
This case isn't supposed to happen. We've got an assumption that the board
has at least one blank square. So we're never supposed to run out of
board, before we find a blank. So this isn't suppose to happen.
We can treat this a number of different ways.
We can just return zero or something like that.
I'll show you something that you haven't seen yet before in this course.
It's not really a learning goal for this part of the course, but I'll just show it
to you quickly. There is a thing called error that lets
you say the board didn't have a blank space.
And what that will do is, is it will cause an error, of the kind of error that
you're used to seeing it's giving exactly that message, so you might want to do
that in this case. Let's worry about the case we're really
supposed to worry about. Let's see, now why is it that this board
has the blank in it? Why does it have a blank at position
zero? Well it has a blank at position zero,
because the first element of the list is false.
And in other cases we have to keep going. So let's see.
If the first of the board is false, then that means the position we're at right
now is a blank so let's produce 0. Otherwise we're going to do the natural
recursion. Lets see that means we'll take the rest
of the board and we'll go find a blank position relative to the rest of the
board. And that's key.
It's relative to the rest of the board. So because it's relative to the rest of
the board, what we're going to do with that, is we're going to add one to it.
And so that will find a value in the rest of the board.
Let's try that. It's name was previously defined as, oh
yeah, this is the usual I forget to comment out the stub problem.
Let's run it. And let's see some tests are failing we
need to see whether any of these are tests on find blank.
And let's see that one isn't. It's these tests unsolved.
You know what I'm going to do here at this point?
These tests are going to keep failing for a while.
Until the wish list is done. I've got them.
I've validated them. They have a good, they're well formed.
At this point I'm going to comment them out.
And what I'll do is I'll put a little note here.
Bang, bang, bang I'll put it on this line.
Bang, bang, bang to remind me that they're still commented out.
And now those tests will stop failing it will be easier for us to test other
things. Let's run it again.
Now, only one test is failing. And which one is that?
Oh. It's next boards test.
So find blank -- the three tests we have for find blank are working properly, and
we never got to the air condition. That's why that line of code Is
highlighted in black. So there we go, that's find-blank.
Now I'm going to do filled with one to nine.
Let's see, filled with one to nine consumes a position in a board.
And it produces a list of boards. Oh, right, it has to produce nine boards.
Where the blank is filled with one to nine.
So for example, let's do an example. If we say check expect.
Oh my goodness this is going to be long. Check expect fill with one to nine.
It's even hard to type. Fill with 1 to 9, let's just say position
0 and board 1. What are we going to get back, we'll
we're going to get list cons 1 master board 1 cons 2 master board 1.
And so on, right? All the way, there's going to be nine of
them. Let's see 3, 4, 5, 6, 7, 8, 9.
If you wanted to, rather than write that out, you could actually write the
expected answer with buildless, or you can write it out if you find it more
clear. Alright, let's make sure our test is
well-formed. It is.
Now form. Now let's see, how are we going to
template this Well, we need to fill with one to nine and it's a board we need to
fill. We have to produce nine results.
And the nine results come from the one to nine.
So we don't really want a template that's according to board because if we template
it according to board that's going to get us to a certain position in the board and
that'll be it. In fact there's a couple good ways to
template this but one nice way to template it is with build list.
So I'm going to template it that way. We need to fill the blank position with
one and nine. We need to build nine boards.
So we need to say, build list nine of something.
'Cuz this build list is going to build us nine boards.
Now let's see. We need to give build-list a function.
Build-list is going to call this function nine times, with the numbers 0, 1, 2, 3,
all the way up to 8. And that function needs to make a new
board. It's based on this board, and at this
position, it will put 1 plus the number build list gives it.
So, because that function is going to access to both of these parameters of the
enclosing function, it needs to be a closure, we need to define with a local.
[SOUND] So this'll be called build one, and it's going to get a number from 0
through 8 as its argument. Then what is it has to do?
Well, it has to build a new board with 1 plus this number at position p.
There is a function you might have forgotten it in all this time, but
there's a function called fill-square that does exactly that.
It consumes a board, a position and a value, and it produces a new board with
that value at that position. So jumping back now [COUGH], to fill with
one to nine and to build one in particular It's fill square, it consumes
a board, which is that board, a position, which is that position and now n is
going to be 0 through A. But in Sudoku, the values that we draw,
people design Sudoku weren't computer scientists because they counted from 1 to
9, rather than from 0 to 8, the way crazy computer scientists count.
So this is going to be plus N and 1. As we're going to be called with numbers
from 0 though 8, what we actually want to make boards that have values from 1
though 9, so we just add 1. And let's see, that's what we want to
call build list with. Let's try that.
Oh, I keep forgetting to comment on the stubs today.
One of the 11 tests failed. Hey, that's good because I think one was
already failing, wasn't it? That's this test failed.
That's not this one, great. Our test for fill with 1 to 9 is working.
So our test for find blank, our test for fill with 1 to 9 is working, that only
leaves Is keep only valid. If we do keep only valid I think next
boards would work. I think right now if we do a search for
bang, bang, bang, we don't need that, and we do a command U.
Let's see. There's a bang, bang, bang there.
Oh that's because in the end we need to uncomment those solve tests.
And there's a bang, bang, bang, there. Hey, we're gettin close to the end of
this thing. Unless of course, doing keep over valid
causes us to make some more wishes. Okay.
Let's work on keep over valid. It consumes list of board, and produces
list of board. And it's supposed to produce a list
containing only the valid boards. So let's see.
Check. Expect.
Keep only valid. See, this is a filtering function.
Right, we're given a list of boards, some of which are valid, and some of which are
not valid. You need to keep only the valid ones.
That's a filtering function. So I know already that I'm going to
template this to call filter. So I'm just going to have one test.
I'll say list, and let's see, I'll make an invalid board.
Cons 1, cons 2, rest, rest of board 1. So that's a board that has two, oop, not
cons 1, cons 2. That's a valid board.
Cons 1, cons 1. So that's a board that has two 1s right
away in the first round. That one's a loser for sure.
And we'll just have that as the only thing and the result of that is, of
course, empty. We're told to keep only the valid boards.
You only got a list with one invalid board.
That's empty. Remember because I know I am calling
filter, the task for keep-only-valid really needs to make sure did it pass an
appropriate predicate to keep-only-valid. So I will quickly template
keep-only-valid. [BLANK_AUDIO] that's filter something
lobd. Let's see what's the something.
Well the something has to be a predicate that consumes a board and produces true,
if it should stay in the list It's gotta be some function.
It doesn't have to be a closure because it doesn't have to see the LLBD argument,
so I'll just wish for it as a new top level function.
It'll be a predicate called valid board. And now let's do the wish list entry.
Let's see this consumers a board and it produces a boolean.
Produce true if board is valid, false otherwise...
Valid means no unit contains a duplicate value.
Let's see if I can say that a bit better. No unit on the board has the same value.
Value twice. So now lets squeeze that into our rule.
Produce true if no, unit on the board has the same value twice.
False otherwise. There's an example of where working to
collapse the purpose helps me start to figure out exactly what this function has
to do. Bang, bang, bang.
Oh let's get rid of this. And we'll get rid of this over here too.
Define valid board? board.
False. And now let's do some tests.
Well, let's see. Board 1, which is all empty, is valid for
sure. And all those boards At the top that
actually work are valid. So all the way down through five.
Now, right now I'm not generating tests based on any theory of how this functions
going to work. I'm just generating tests because I have
some examples lying around. And so I know all of those are valid so
I'm going to to throw those at this. because this seems like a complicated
function to me right now, I don't quite understand it, so I'm writing down some
examples that I have. Let me also write down some examples that
I know are troublesome. Let's go look at board 2, I think is a
good one. Board 2 has this row in it.
So, if we take board 2 and we replace the 1 at the beginning, what we've done there
is, oops, I've missed a question mark in all of these.
Is. What this does is it takes board 2 and it
strips off the first value, the upper left cell, and now we're putting a 2
there. Okay.
I could do that with with fill square of course.
It's just a bit simpler to do it this way.
So that boards not valid because now it's gonan have two 2's.
Let's do another eexample. [SOUND] Valid board question mark cons 2.
You know, Board 3 is the one that just has that column down the left.
Here's Board 3 and so now I've replaced the 1 in the upper left corner with a 2
and of course that makes the board invalid 'cause it has two 2s in that
column. There's two two's in the first column.
There's also two twos in the first box. So that wasn't valid.
And lets see if we can do another one. Check Expect val whoops.
Valid board, board? Lets go look for another example up here.
In our boards. See, what can we do with board 4?
Board 4 is a bit more interesting, isn't it?
If we change that 7 to a 6, then we'll have two 6's in the first the box, So
that would be an invalid board. Let's try that.
We'll take board four, and we need the second position, position one there to be
a six. So now we will use fill square because
it's a bit easier. Fill square board four position one is
going to be a And that's gotta be false. Let's see if all of these are well
formed. They are well formed, but they're, most
of them are failing. The first one's failing I guess because
the stub always produces, or the last one, one of these is.
These three are passing because the stub always produces false.
Those five are failing and we have an earlier test that's also failing.
So let's see. Now how are we going to template this
function? Now right here I'm going to stop this
video and leave you to work on this one for a bit.
It's a little bit complicated, but, I suggest you really work on it
systematically and remember what the purpose statement says.
We need to check all of the units and we have this constant called units.
We need to check that for all of the units on the board, no unit has the same
value twice. Paradoxically, this is actually the
hardest function to write in this program.
The solve function, which was the most interesting function Wasn't really the
hardest function right and this function isn't that hard either if you just work
systematically. There's lots of ways to do it, but I'll
just let you know, that I have what I think is a pretty nice solution.
It ends up using both n-map and map. So I'll stop this video here now.