1 00:00:06,240 --> 00:00:10,530 In this video, I'm just going to walk through the starter file for our version 2 00:00:10,530 --> 00:00:14,200 of a Sudoku solver. The starter file includes the data 3 00:00:14,200 --> 00:00:18,559 definitions we're going to use and a couple simple operations on that data. 4 00:00:20,100 --> 00:00:22,390 Now, let me stress something really important here. 5 00:00:23,788 --> 00:00:30,980 It's totally okay, fine, if when you see these data definitions you say, hmm, I'm 6 00:00:30,980 --> 00:00:35,162 not sure I would have come up with those on the first try, I didn't come up with 7 00:00:35,162 --> 00:00:39,680 these on the first try. What I did was I came up with some data 8 00:00:39,680 --> 00:00:43,340 definitions, and then I started working on the rest of the design, and I 9 00:00:43,340 --> 00:00:46,555 realized, maybe I could have some data definitions that made things less 10 00:00:46,555 --> 00:00:51,487 cumbersome. That's totally okay, remember, if you're 11 00:00:51,487 --> 00:00:55,700 working systematically, what that does is it lets you take advantage of good 12 00:00:55,700 --> 00:00:59,580 decisions and it makes it easy to go back and change bad decisions. 13 00:00:59,580 --> 00:01:04,480 So don't worry if you wouldn't have come up with these data definitions. 14 00:01:04,480 --> 00:01:07,610 Anyways, now, I'm just going to walk through the ones I have to lay the 15 00:01:07,610 --> 00:01:14,970 foundation for the rest of the design. So here we go, I'm at sudoku-starter.rkt 16 00:01:14,970 --> 00:01:18,030 and the first thing I want to point out is I'm using a require that we've never 17 00:01:18,030 --> 00:01:21,150 used before. I'm saying require racket/list, and 18 00:01:21,150 --> 00:01:25,660 that's going to get me three new primitives that operate on lists that 19 00:01:25,660 --> 00:01:28,040 I'll end up using farther down in the starter file. 20 00:01:28,040 --> 00:01:30,895 So this is something I definitely didn't put in right away. 21 00:01:30,895 --> 00:01:38,320 I didn't know I needed this require until I got down to writing these functions. 22 00:01:38,320 --> 00:01:43,280 So here we go I've got a note at the top that says this is a brute-force Sudoku 23 00:01:43,280 --> 00:01:45,110 solver. And remember, we used to say that you 24 00:01:45,110 --> 00:01:48,090 would just put a one line description in the program. 25 00:01:48,090 --> 00:01:52,920 Here, I'm putting a little bit of a texture form of the domain analysis. 26 00:01:52,920 --> 00:01:56,220 I just feel the need to say a bit more at the beginning of this file about what's 27 00:01:56,220 --> 00:02:01,910 going on. Now, the constant are based on that 28 00:02:01,910 --> 00:02:04,990 domain analysis. Val is pretty straightforward. 29 00:02:04,990 --> 00:02:10,610 Val is just a natural from 1 to 9. And then I'm saying that a board, I'm 30 00:02:10,610 --> 00:02:16,260 going to represent a board as a list. We're going to represent it as a list, 81 31 00:02:16,260 --> 00:02:19,450 elements long. And what I'm saying here is that each 32 00:02:19,450 --> 00:02:22,818 element of the list is either a value or false. 33 00:02:22,818 --> 00:02:27,500 I could have made a new type here. I would have defined, I would have 34 00:02:27,500 --> 00:02:32,070 defined a type called something like entry, which would be one of value or 35 00:02:32,070 --> 00:02:35,200 false. But here, what I'm doing is I'm doing 36 00:02:35,200 --> 00:02:39,535 something a bit more compact. I'm saying just Val or false right here. 37 00:02:39,535 --> 00:02:44,850 I don't define the separate type. So this is kind of an unnamed type value 38 00:02:44,850 --> 00:02:49,154 or false. And here's the interpretation which just 39 00:02:49,154 --> 00:02:53,750 describes that the board is a 9 by 9 array of squares, where each square has a 40 00:02:53,750 --> 00:02:59,232 row and column number, but we're representing it as a single flat list. 41 00:02:59,232 --> 00:03:04,550 Now, in a single flat list, there's a position from the zeroth element up to 42 00:03:04,550 --> 00:03:11,770 the 80 element, 81 elements. And what I'm saying is in that single 43 00:03:11,770 --> 00:03:19,540 flat list, the way you convert between a row column in an actual Pos which is an 44 00:03:20,700 --> 00:03:27,646 index into the list is this way. If, if you got a Pos, if you got a 45 00:03:27,646 --> 00:03:32,670 position, then the row is the quotient of position in nine. 46 00:03:32,670 --> 00:03:39,820 In other words, you divide p by 9 and you just take the whole number and the column 47 00:03:39,820 --> 00:03:43,530 is the remainder. And I've got a little function here that 48 00:03:43,530 --> 00:03:46,640 goes the other way. It consumes a row in a column and it 49 00:03:46,640 --> 00:03:52,650 produces the position. Okay, so now, here's a third thing which 50 00:03:52,650 --> 00:04:00,695 is a unit, and the unit is a list of Pos, a list of positions of length nine. 51 00:04:00,695 --> 00:04:06,150 So what's this thing? It's the position of every square in the 52 00:04:06,150 --> 00:04:10,010 unit. And notice that I haven't been putting 53 00:04:10,010 --> 00:04:12,760 example data here. And that's because I've got all my 54 00:04:12,760 --> 00:04:18,604 example data down here. So here's a list of all the values 1 to 55 00:04:18,604 --> 00:04:23,233 9. I've picked this constant B to be false. 56 00:04:23,233 --> 00:04:26,385 B stands for blank. Why am I doing that? 57 00:04:26,385 --> 00:04:28,500 What I'll show you while I'm doing that right now. 58 00:04:28,500 --> 00:04:32,870 It makes it much easier for me to write some example data for the boards. 59 00:04:34,560 --> 00:04:38,310 So there is board 1. This is the empty board. 60 00:04:38,310 --> 00:04:42,930 Every square has false in it. That's why that B is there, it just makes 61 00:04:42,930 --> 00:04:46,069 this much more compact than if I had to write false, false, false, false. 62 00:04:47,370 --> 00:04:52,920 Here's another board. This board has one, two, three, four, to 63 00:04:52,920 --> 00:04:57,110 nine across the first row. Here's a board that has one, two, three, 64 00:04:57,110 --> 00:05:03,640 four, to nine in the first column. These are kind of silly boards, and then, 65 00:05:03,640 --> 00:05:07,978 what I did was I went out on the network and I found some example Sudoku games, 66 00:05:07,978 --> 00:05:10,620 right? Remember the way Sodoku works is you get 67 00:05:10,620 --> 00:05:13,880 given a starting board, and then you have to finish filling it in. 68 00:05:14,910 --> 00:05:20,462 So, here is Board 4, which I was told was an easy problem, and there's the solution 69 00:05:20,462 --> 00:05:24,640 to it. Here is Board 5, which I was told was a 70 00:05:24,640 --> 00:05:27,390 hard problem, and there's the solution to it. 71 00:05:27,390 --> 00:05:29,894 And here's Board 6, which some guy named Dr. 72 00:05:29,894 --> 00:05:35,486 Arto Inkala says is the hardest one ever. And there is Board 6. 73 00:05:35,486 --> 00:05:41,742 Here is Board 7, which I constructed deliberately to not have a solution. 74 00:05:41,742 --> 00:05:44,770 It's very easy to construct a board that doesn't have a solution. 75 00:05:44,770 --> 00:05:49,622 But this one, you know, takes a little bit longer to realize that it doesn't 76 00:05:49,622 --> 00:05:53,570 have a solution. This doesn't have a solution because the 77 00:05:53,570 --> 00:05:58,275 only thing that's missing in row 1 is 9. So you'd kind of like to put a 9 there, 78 00:05:58,275 --> 00:06:02,050 except you can't put a nine there, because there's already a 9 in that 79 00:06:02,050 --> 00:06:03,699 column. So this board has no solution. 80 00:06:06,210 --> 00:06:13,100 So those are some sample boards. Now, what I have here is, these are 81 00:06:13,100 --> 00:06:16,810 units. Remember that a unit is a list of 82 00:06:16,810 --> 00:06:24,100 position of length 9. So this constant rows is a list of units, 83 00:06:24,100 --> 00:06:31,145 and look at what it is. There's nine of them, and each one is the 84 00:06:31,145 --> 00:06:37,589 position of each square in the row. So for the first row, the positions of 85 00:06:37,589 --> 00:06:42,771 the squares are what? 0, 1, 2, 3, 4, 5, 6, 7, 8. 86 00:06:42,771 --> 00:06:46,994 It's simple for rows. Those are the positions, 9 to 17 and so 87 00:06:46,994 --> 00:06:51,678 on. But for the columns, for the leftmost 88 00:06:51,678 --> 00:06:54,973 column, then the positions of its squares are what? 89 00:06:54,973 --> 00:07:00,530 Well, there is 0, 9, 18, 27 and so on. So there is the columns. 90 00:07:00,530 --> 00:07:04,060 This is the first column, the second column. 91 00:07:06,530 --> 00:07:11,440 You can kind of see or if you look, the rows go this way, even columns, it's kind 92 00:07:11,440 --> 00:07:18,268 of transposed, right, 0,1, 2, 3 8, 9, 10, if you, if that makes your header just 93 00:07:18,268 --> 00:07:22,737 ignore it. And then for the boxes let me scroll this 94 00:07:22,737 --> 00:07:28,810 just right if I can, there we go. For the boxes, while the first box is, 95 00:07:28,810 --> 00:07:31,980 you know, 0, 1, 2 and then 9, 10, 11 and then 18, 19, 20. 96 00:07:31,980 --> 00:07:41,413 And here, the second box is 3, 4, 5 and then 12, 13, 14 and then 21, 22, 23. 97 00:07:44,130 --> 00:07:51,750 So if I take rows and columns and boxes and I append those together, then I have 98 00:07:51,750 --> 00:07:56,330 units. Remember, what these are is they're lists 99 00:07:56,330 --> 00:08:02,270 of the positions of the squares in the units. 100 00:08:02,270 --> 00:08:09,510 So there's my data definitions and my constants and I've also provided two 101 00:08:09,510 --> 00:08:12,920 primitive functions for operating on boards. 102 00:08:14,440 --> 00:08:20,990 One is called read-square and it consumes a board in a position, and it produces 103 00:08:20,990 --> 00:08:27,870 what's at that position in that board. So if you take read-square of Board 2, 104 00:08:27,870 --> 00:08:30,895 remember what Board 2 is for example, let's go get it. 105 00:08:30,895 --> 00:08:40,310 There's Board 2, and using the magic of video editing, what I'll do is I'll bring 106 00:08:40,310 --> 00:08:43,720 Board 2 down to the bottom here so we can see it for a second. 107 00:08:43,720 --> 00:08:45,710 I'll go all way back down to where we were. 108 00:08:45,710 --> 00:08:57,070 So, if I say read-square in Board 2, and then I use that function r-c to pos. 109 00:08:57,070 --> 00:09:01,620 And, so I'm going to read row 0, column 5. 110 00:09:01,620 --> 00:09:08,120 Then in Board 2, we see that that's a 6. Now, putting Board 3 off to the side for 111 00:09:08,120 --> 00:09:13,187 just a second. And see that if I do read-square in Board 112 00:09:13,187 --> 00:09:18,750 3 of row 7 column 0, that's an 8. So there's read-square. 113 00:09:18,750 --> 00:09:23,760 How does read-square work? Well, it just needs to go into that list 114 00:09:23,760 --> 00:09:26,469 and get the value of that position in the list. 115 00:09:28,460 --> 00:09:32,420 Turns out there is a primitive provided by racket slash list that does just 116 00:09:32,420 --> 00:09:39,730 exactly that called list-ref. So I'm using list-ref and fill-square is 117 00:09:39,730 --> 00:09:45,114 quite similar to read-square, except, it takes three parameters. 118 00:09:46,230 --> 00:09:51,690 It takes a Board and a Pos just like read-square does, but it also takes a 119 00:09:51,690 --> 00:09:54,770 vowel. And what it does is it produces a new 120 00:09:54,770 --> 00:09:59,962 board that's exactly the same as the old board, except at Pos, it now has the 121 00:09:59,962 --> 00:10:04,425 value Val. So this is a way of filling a board in. 122 00:10:04,425 --> 00:10:06,925 Read-square is a way of seeing what's already in a board. 123 00:10:06,925 --> 00:10:13,100 Fill-square is a way of writing a number into a board. 124 00:10:13,100 --> 00:10:18,142 And here, again, I'm using a couple primitives from racket/list. 125 00:10:18,142 --> 00:10:21,844 I'm not going to go into them exactly how take and drop work. 126 00:10:21,844 --> 00:10:26,410 That's what this primitive does. Just look at the signature and the 127 00:10:26,410 --> 00:10:29,080 purpose and know that that's what fill-square does. 128 00:10:29,080 --> 00:10:31,760 And the signature and the purpose have noted that's what read-square does. 129 00:10:31,760 --> 00:10:40,000 I will show you one aside here. Both of these functions consume Board and 130 00:10:40,000 --> 00:10:43,250 Pos. And Board and Pos are both types that are 131 00:10:43,250 --> 00:10:50,234 defined with a one of, so these are what are called functions that consume two one 132 00:10:50,234 --> 00:10:54,720 of types. And there a special part of the design 133 00:10:54,720 --> 00:11:00,680 recipe for designing functions like this, having to do with designing two functions 134 00:11:00,680 --> 00:11:04,200 that operate on one other data. And these are the ways we would have 135 00:11:04,200 --> 00:11:08,550 coded the functions and completed that part of the recipe if we had done it that 136 00:11:08,550 --> 00:11:11,600 way. I'm not going to go into that now. 137 00:11:11,600 --> 00:11:16,710 Really, what I want you to, to just know for the rest of these Sudoku lectures is 138 00:11:16,710 --> 00:11:21,300 these functions, read-squared, fill-square, will do the thing you need 139 00:11:21,300 --> 00:11:22,960 them to do. So there you go. 140 00:11:22,960 --> 00:11:28,730 That's a summary of the data definitions for Sudoku. 141 00:11:28,730 --> 00:11:33,050 and the two functions read-square, fill-square are not quite primitive 142 00:11:33,050 --> 00:11:36,058 functions cause they're not provided by racket. 143 00:11:36,058 --> 00:11:42,190 But the two functions that I'm giving you to operate on boards, and you know the 144 00:11:42,190 --> 00:11:49,200 key data definitions are vol, bored and pause, and then there's some very useful 145 00:11:49,200 --> 00:11:52,460 constants. I made these constants, my board 146 00:11:52,460 --> 00:11:55,090 constants, my very first time I started writing this. 147 00:11:55,090 --> 00:11:59,760 These units constants I didn't make until later. 148 00:11:59,760 --> 00:12:02,930 I realized later they would be very useful for me and I made them then. 149 00:12:02,930 --> 00:12:09,900 But you have all of them now. Why don't you review this a bit and do 150 00:12:09,900 --> 00:12:13,690 the questions in the video right now? And then, I'll see you in the next video. 151 00:12:13,690 --> 00:12:13,690 [BLANK_AUDIO]