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]