1
00:00:06,130 --> 00:00:11,290
Over the next several videos we're 
going to design a program to solve Sudoku 

2
00:00:11,290 --> 00:00:13,840
puzzles. 
So if you've never ever heard of Sudoku, 

3
00:00:13,840 --> 00:00:17,580
you might want to take just a couple of 
minutes to do a Google search and go see 

4
00:00:17,580 --> 00:00:19,100
a little bit of what the game's all 
about. 

5
00:00:20,600 --> 00:00:24,310
But you don't need to get good at playing 
it, you just need to know the basic 

6
00:00:24,310 --> 00:00:27,120
roles. 
Because our program isn't going to use 

7
00:00:27,120 --> 00:00:31,590
human strategies for solving in the game. 
We're going to use something called Brute 

8
00:00:31,590 --> 00:00:35,750
Force Search. 
And it's a wonderful insight. 

9
00:00:35,750 --> 00:00:42,220
The insight basically is this. 
For some problems, what you can do is 

10
00:00:42,220 --> 00:00:45,860
rather than come up with a kind of human 
strategy for playing it. 

11
00:00:45,860 --> 00:00:50,830
You can generate the space of all 
possible solutions, and then just pick 

12
00:00:50,830 --> 00:00:54,160
the best one. 
That's what's going to happen here. 

13
00:00:54,160 --> 00:00:58,300
We're going to take a Sudoku board and 
we're going to generate a whole tree of 

14
00:00:58,300 --> 00:01:00,350
all the possible boards that come after 
it. 

15
00:01:01,790 --> 00:01:04,845
And then we'll just do a backtracking 
search over that to find the solution we 

16
00:01:04,845 --> 00:01:09,550
want. 
Now two more things in terms in the way 

17
00:01:09,550 --> 00:01:12,050
of intro. 
First, don't worry. 

18
00:01:12,050 --> 00:01:16,060
We would never have expected you to come 
up with this idea of generating the 

19
00:01:16,060 --> 00:01:20,360
search space at this point in the course. 
This was an idea that had to be invented 

20
00:01:20,360 --> 00:01:24,790
quite some time ago. 
It, it's quite an interesting idea, so 

21
00:01:24,790 --> 00:01:29,890
you wouldn't have to generate this idea. 
The amazing thing is once we layout this 

22
00:01:29,890 --> 00:01:35,310
idea, what you're going to find is that 
you're all set to design this program. 

23
00:01:35,310 --> 00:01:39,060
The rest of the week we're really only 
going to learn one more thing having to 

24
00:01:39,060 --> 00:01:43,420
do with designing programs. 
In some sense, the rest of this is 

25
00:01:43,420 --> 00:01:49,080
going to be a demonstration to you, by 
you, for you, of how much it is you 

26
00:01:49,080 --> 00:01:49,990
already know how to do.