In this video, I'm just going to walk 
through the starter file for our version 
of a Sudoku solver. 
The starter file includes the data 
definitions we're going to use and a 
couple simple operations on that data. 
Now, let me stress something really 
important here. 
It's totally okay, fine, if when you see 
these data definitions you say, hmm, I'm 
not sure I would have come up with those 
on the first try, I didn't come up with 
these on the first try. 
What I did was I came up with some data 
definitions, and then I started working 
on the rest of the design, and I 
realized, maybe I could have some data 
definitions that made things less 
cumbersome. 
That's totally okay, remember, if you're 
working systematically, what that does is 
it lets you take advantage of good 
decisions and it makes it easy to go back 
and change bad decisions. 
So don't worry if you wouldn't have come 
up with these data definitions. 
Anyways, now, I'm just going to walk 
through the ones I have to lay the 
foundation for the rest of the design. 
So here we go, I'm at sudoku-starter.rkt 
and the first thing I want to point out 
is I'm using a require that we've never 
used before. 
I'm saying require racket/list, and 
that's going to get me three new 
primitives that operate on lists that 
I'll end up using farther down in the 
starter file. 
So this is something I definitely didn't 
put in right away. 
I didn't know I needed this require until 
I got down to writing these functions. 
So here we go I've got a note at the top 
that says this is a brute-force Sudoku 
solver. 
And remember, we used to say that you 
would just put a one line description in 
the program. 
Here, I'm putting a little bit of a 
texture form of the domain analysis. 
I just feel the need to say a bit more at 
the beginning of this file about what's 
going on. 
Now, the constant are based on that 
domain analysis. 
Val is pretty straightforward. 
Val is just a natural from 1 to 9. 
And then I'm saying that a board, I'm 
going to represent a board as a list. 
We're going to represent it as a list, 81 
elements long. 
And what I'm saying here is that each 
element of the list is either a value or 
false. 
I could have made a new type here. 
I would have defined, I would have 
defined a type called something like 
entry, which would be one of value or 
false. 
But here, what I'm doing is I'm doing 
something a bit more compact. 
I'm saying just Val or false right here. 
I don't define the separate type. 
So this is kind of an unnamed type value 
or false. 
And here's the interpretation which just 
describes that the board is a 9 by 9 
array of squares, where each square has a 
row and column number, but we're 
representing it as a single flat list. 
Now, in a single flat list, there's a 
position from the zeroth element up to 
the 80 element, 81 elements. 
And what I'm saying is in that single 
flat list, the way you convert between a 
row column in an actual Pos which is an 
index into the list is this way. 
If, if you got a Pos, if you got a 
position, then the row is the quotient of 
position in nine. 
In other words, you divide p by 9 and you 
just take the whole number and the column 
is the remainder. 
And I've got a little function here that 
goes the other way. 
It consumes a row in a column and it 
produces the position. 
Okay, so now, here's a third thing which 
is a unit, and the unit is a list of Pos, 
a list of positions of length nine. 
So what's this thing? 
It's the position of every square in the 
unit. 
And notice that I haven't been putting 
example data here. 
And that's because I've got all my 
example data down here. 
So here's a list of all the values 1 to 
9. 
I've picked this constant B to be false. 
B stands for blank. 
Why am I doing that? 
What I'll show you while I'm doing that 
right now. 
It makes it much easier for me to write 
some example data for the boards. 
So there is board 1. 
This is the empty board. 
Every square has false in it. 
That's why that B is there, it just makes 
this much more compact than if I had to 
write false, false, false, false. 
Here's another board. 
This board has one, two, three, four, to 
nine across the first row. 
Here's a board that has one, two, three, 
four, to nine in the first column. 
These are kind of silly boards, and then, 
what I did was I went out on the network 
and I found some example Sudoku games, 
right? 
Remember the way Sodoku works is you get 
given a starting board, and then you have 
to finish filling it in. 
So, here is Board 4, which I was told was 
an easy problem, and there's the solution 
to it. 
Here is Board 5, which I was told was a 
hard problem, and there's the solution to 
it. 
And here's Board 6, which some guy named 
Dr. 
Arto Inkala says is the hardest one ever. 
And there is Board 6. 
Here is Board 7, which I constructed 
deliberately to not have a solution. 
It's very easy to construct a board that 
doesn't have a solution. 
But this one, you know, takes a little 
bit longer to realize that it doesn't 
have a solution. 
This doesn't have a solution because the 
only thing that's missing in row 1 is 9. 
So you'd kind of like to put a 9 there, 
except you can't put a nine there, 
because there's already a 9 in that 
column. 
So this board has no solution. 
So those are some sample boards. 
Now, what I have here is, these are 
units. 
Remember that a unit is a list of 
position of length 9. 
So this constant rows is a list of units, 
and look at what it is. 
There's nine of them, and each one is the 
position of each square in the row. 
So for the first row, the positions of 
the squares are what? 
0, 1, 2, 3, 4, 5, 6, 7, 8. 
It's simple for rows. 
Those are the positions, 9 to 17 and so 
on. 
But for the columns, for the leftmost 
column, then the positions of its squares 
are what? 
Well, there is 0, 9, 18, 27 and so on. 
So there is the columns. 
This is the first column, the second 
column. 
You can kind of see or if you look, the 
rows go this way, even columns, it's kind 
of transposed, right, 0,1, 2, 3 8, 9, 10, 
if you, if that makes your header just 
ignore it. 
And then for the boxes let me scroll this 
just right if I can, there we go. 
For the boxes, while the first box is, 
you know, 0, 1, 2 and then 9, 10, 11 and 
then 18, 19, 20. 
And here, the second box is 3, 4, 5 and 
then 12, 13, 14 and then 21, 22, 23. 
So if I take rows and columns and boxes 
and I append those together, then I have 
units. 
Remember, what these are is they're lists 
of the positions of the squares in the 
units. 
So there's my data definitions and my 
constants and I've also provided two 
primitive functions for operating on 
boards. 
One is called read-square and it consumes 
a board in a position, and it produces 
what's at that position in that board. 
So if you take read-square of Board 2, 
remember what Board 2 is for example, 
let's go get it. 
There's Board 2, and using the magic of 
video editing, what I'll do is I'll bring 
Board 2 down to the bottom here so we can 
see it for a second. 
I'll go all way back down to where we 
were. 
So, if I say read-square in Board 2, and 
then I use that function r-c to pos. 
And, so I'm going to read row 0, column 
5. 
Then in Board 2, we see that that's a 6. 
Now, putting Board 3 off to the side for 
just a second. 
And see that if I do read-square in Board 
3 of row 7 column 0, that's an 8. 
So there's read-square. 
How does read-square work? 
Well, it just needs to go into that list 
and get the value of that position in the 
list. 
Turns out there is a primitive provided 
by racket slash list that does just 
exactly that called list-ref. 
So I'm using list-ref and fill-square is 
quite similar to read-square, except, it 
takes three parameters. 
It takes a Board and a Pos just like 
read-square does, but it also takes a 
vowel. 
And what it does is it produces a new 
board that's exactly the same as the old 
board, except at Pos, it now has the 
value Val. 
So this is a way of filling a board in. 
Read-square is a way of seeing what's 
already in a board. 
Fill-square is a way of writing a number 
into a board. 
And here, again, I'm using a couple 
primitives from racket/list. 
I'm not going to go into them exactly how 
take and drop work. 
That's what this primitive does. 
Just look at the signature and the 
purpose and know that that's what 
fill-square does. 
And the signature and the purpose have 
noted that's what read-square does. 
I will show you one aside here. 
Both of these functions consume Board and 
Pos. 
And Board and Pos are both types that are 
defined with a one of, so these are what 
are called functions that consume two one 
of types. 
And there a special part of the design 
recipe for designing functions like this, 
having to do with designing two functions 
that operate on one other data. 
And these are the ways we would have 
coded the functions and completed that 
part of the recipe if we had done it that 
way. 
I'm not going to go into that now. 
Really, what I want you to, to just know 
for the rest of these Sudoku lectures is 
these functions, read-squared, 
fill-square, will do the thing you need 
them to do. 
So there you go. 
That's a summary of the data definitions 
for Sudoku. 
and the two functions read-square, 
fill-square are not quite primitive 
functions cause they're not provided by 
racket. 
But the two functions that I'm giving you 
to operate on boards, and you know the 
key data definitions are vol, bored and 
pause, and then there's some very useful 
constants. 
I made these constants, my board 
constants, my very first time I started 
writing this. 
These units constants I didn't make until 
later. 
I realized later they would be very 
useful for me and I made them then. 
But you have all of them now. 
Why don't you review this a bit and do 
the questions in the video right now? 
And then, I'll see you in the next video. 
[BLANK_AUDIO]