Over the next several videos we're going to design a program to solve Sudoku
puzzles. So if you've never ever heard of Sudoku,
you might want to take just a couple of minutes to do a Google search and go see
a little bit of what the game's all about.
But you don't need to get good at playing it, you just need to know the basic
roles. Because our program isn't going to use
human strategies for solving in the game. We're going to use something called Brute
Force Search. And it's a wonderful insight.
The insight basically is this. For some problems, what you can do is
rather than come up with a kind of human strategy for playing it.
You can generate the space of all possible solutions, and then just pick
the best one. That's what's going to happen here.
We're going to take a Sudoku board and we're going to generate a whole tree of
all the possible boards that come after it.
And then we'll just do a backtracking search over that to find the solution we
want. Now two more things in terms in the way
of intro. First, don't worry.
We would never have expected you to come up with this idea of generating the
search space at this point in the course. This was an idea that had to be invented
quite some time ago. It, it's quite an interesting idea, so
you wouldn't have to generate this idea. The amazing thing is once we layout this
idea, what you're going to find is that you're all set to design this program.
The rest of the week we're really only going to learn one more thing having to
do with designing programs. In some sense, the rest of this is
going to be a demonstration to you, by you, for you, of how much it is you
already know how to do.