S^3 (Sniff Soduku Solver)

We've had a few sunny days recently - the sort of days where some people might sit on the balcony with a drink and maybe relax doing a crossword puzzle. Trouble is I'm rubbish at crosswords. Soduku looks more interesting, but it just seems like mental busywork. Filling in those boxes seems like the sort of thing you should get a computer to do... So... Sitting out, with a drink and writing a program to solve puzzles! That's more the thing.

Much as we did for some some of the other puzzle solving programs we start by trying to represent the problem on the computer (while code is the exiting part of programming - its the verbs, the doing, its the "nouns" are at least as important).

make fixed list of strings

when loadFixed

.delete all of fixed

.add"800000000" to fixed

.add"003600000" to fixed

.add"070090200" to fixed

.add"050007000" to fixed

.add"000045700" to fixed

.add"000100030" to fixed

.add"001000068" to fixed

.add"008500010" to fixed

.add"090000400" to fixed

Here I've encoded a puzzle as a list of strings - just as in the recent barcode examples, though Soduku looks like a game about numbers its actually a game about symbols. It could just as easily by rebranded to use the letters a-i and would work exactly the same. However its worth noting that there are two kinds of symbols on a soduku board - the ones that are fixed, and the ones you can change. We want to leave the fixed ones as they are so we make a copy that we can change:

make board list of strings

when loadBoard

.make counter number

.delete all of board

.repeat 9 using counter

..add item counter of fixed to board

We're also going to need a way to print out the board. Initially I just did something simple:

when showBoard

.make row number

.repeat 9 using row

..say  item row of board

but then at the end I made it a bit more pretty:

when showBoard

.make row number

.make col number

.make text string

.repeat 9 using row

..if row = 4 or row = 7

...say "---+---+---"

..set text to ""

..repeat 9 using col

...if col=4 or col=7

....set text to join text "|"

...set text to join text letter col of item row of board

..say text

.say ""

.wait 0.1 secs

Now at some point we're going to need to write a value into a square, so lets write the code to do that:

make x number

make y number

make val number

make boardOK boolean

when replaceLetter

.make counter number

.make newLine string

.set newLine to ""

.repeat x-1 using counter

..set newLine to join newLine letter counter of item y of board

.set newLine to join newLine [val]

.repeat 9-x  using counter

..set newLine to join newLine letter counter+x of item y of board

.replace item y of board with newLine

Here we replace letter x of item y of board with [val]. Unfortunately Scratch/Sniff don't support that operation directly (it would be rather neat if it it did, and I may consider quietly adding it...), so we copy the line a letter at a time into newLine, substituting val for the appropriate square.

Now its time to actually start thinking about how to solve the problem! What we've done so far is "bottom up" programming. I've built a load of useful things I'm pretty sure I'm going to need, so now I can use them to express the rest of the problem using those tools. The alternative is top-down. Build the program assuming the tools you need exist, then once the whole thing is written go back and fill in the missing operations.

The advantage of top down is that you know what tools you need to build, but the neat thing about bottom-up is that you start running the code that you have to do things immediately, even if you're not ready to solve the whole problem. A smart programmer uses both "as appropriate".

We're going to go through the board one square at a times and write a value in that square. Then we check if the board is valid. If it is we'll move on to the next square. If not we'll try a different value in this square. If there's no valid number that can go in this square, then we need to go back and change the previous square (which in turn may require going back to the previous square!).

This is exactly what a human player would do, but they would use skill and judgement to pick a square with only one or two possible values, so that they never have to go back too far. As we're doing this on a computer which has no skill and judgement then we'll just work through the square from top left to bottom right. This will mean we have to try a lot more combinations that a human would, but foruntatly the computer is super good at that!

If we consider what that looks like at the top level:

when start

.make counter number

.broadcast loadFixed and wait

.broadcast loadBoard and wait

.broadcast showBoard and wait

.set x to 1

.set y to 1

.repeat until y =10

..set val to value of letter x of item y of board

..broadcast checkBoard and wait

..if boardOK

...broadcast advance and wait

..else

...if val=9

....broadcast retreat and wait

...else

....change val by 1

....broadcast replaceLetter and wait

.broadcast showBoard and wait

After some running the initialisation, and printing the initial board (which we've already done - bottom up), we start at the top left and loop until we've covered the whole board. Each time round the loop we pull out the value of the current square, and check if the its a valid move. If it is OK then we move on to the next square. If its not OK then we need to fix that. The easiest way to fix that is to add one to the value in the current square and go round again to see if that fixes things. Unfortunately that's not always possible - if we've already tried all 9 values in that square and none of them have worked, then we need to retreat.

If the board is solvable then eventually we'll reach the bottom, and we can print out the completed results (of course during testing we can use the showBoard script a lot more to check the progress, but I've removed those as they're not needed in this final version).

Now we've switched to a top-down approach - I need to work out how to write checkBoard, advance and retreat, but once I do this should just start working.

when advance

.change x by 1

.if x=10

..set x to 1

..change y by 1

Here you can see advance is pretty simple - we just increment x, and if we've reached the end of the line, move on to the next line. However there's an implicit trick in this code... we don't have to worry about fixed positions on the board. Ideally we should skip over them, because we're not allowed to change them, but when we advance we're actually safe to advance to a fixed square, because when we test that its OK the next time round the loop we know that is will succeed because if it wasn't OK, then we'd already have noticed. We will never change fixed squares, so if we advance to a fixed square it must be OK.

This isn't the case when we retreat - we're moving back to the previous modifiable square, which makes this a bit more complex:

when retreat

.forever

..if value of letter x of item y of fixed = 0

...set val to 0

...broadcast replaceLetter and wait

..change x by -1

..if x=0

...set x to 9

...change y by -1

..

..if value of letter x of item y of fixed = 0

...set val to value of letter x of item y of board

...if val < 9

....change val by 1

....broadcast replaceLetter and wait

....stop script

If the square we're retreating from isn't fixed, then we set it to zero on the main board. Then we move back a square by subtracting 1 from x, and then checking if we need to move up a line.

Now we're on the new square we need to check if its fixed. If it's not fixed then we incremented it, to get the new value for that square, and stop the sciprt. On the other hand if it is fixed, or its already reached 9, then we need to retreat further, so we go back around until we find a previous square that we can increment.

The only thing left to add it the code to check if a current board position is legal. However we don't need to check the whole board - just that the current square doesn't make the new position illegal:

when checkBoard

.make dx number

.make dy number

.

.if val = 0

..set boardOK to no

..stop script

.

.set boardOK to yes

.repeat 9 using dx

..if not dx=x

...if value of letter dx of item y of board = val

....set boardOK to no

....stop script

.

.repeat 9 using dy

..if not dy=y

...if value of letter x of item dy of board = val

....set boardOK to no

....stop script

.

There are 4 steps to doing that, and the first three shown above are pretty easy: if the current square is 0 (empty) then that's not OK. Then we go along the line - if it contains the current value of the test square at a location other than the current square then that's not allowed either. Similarly for the column.

.set baseX to x-((x-1) mod 3)-1

.set baseY to y-((y-1) mod 3)-1

.repeat 3 using dx

..repeat 3 using dy

...if not (baseX+dx=x and baseY+dy=y)

....if value of letter baseX+dx of item baseY+dy of board = val

.....set boardOK to no

.....stop script

The final check is to make sure that each 3x3 group is valid. The tricky part of this is figuring out which square we're in without writing a ton of code. Unfortunatly to make things worse, Scratch/Sniff are "index from 1" languages. There's nothing wrong with that, and it makes some things much clearer, but this particular bit of code is much more complex. Basically we're dividing by 3 and keeping the remainder to find out where we are in the square. Then we subtract that from the position to find the top left corner of the square. The extra -1's are needed to make it work properly, so that when we access square 1,1 of the group we get the right position.

Once we have the origin of the 3x3 group we just loop over the rows/columns checking each square. If we find a cell other than the one we're testing which contains the value, then we have a bad square again.

And that's it! Now we have all the parts, when we run it, it prints out the initial board:

800|000|000

003|600|000

070|090|200

---+---+---

050|007|000

000|045|700

000|100|030

---+---+---

001|000|068

008|500|010

090|000|400

and about a second later it prints out the answer:

812|753|649

943|682|175

675|491|283

---+---+---

154|237|896

369|845|721

287|169|534

---+---+---

521|974|368

438|526|917

796|318|452

To get there the code considers over half a million possible board positions! But that's OK, because that's what computers are good for.

Robot arm upgrades

One of the most popular posts on the Sniff blog is my documentation of the robot arm build - lots of people get the kits on eBay or aliExpress and then they arrive without any instructions. You literally get a bag of black metal shapes and some screws!

When I built the original I was careful to document everything I did, as even searching online there were no good instructions. However my research did reveal that there was a "better" kit out there, that had previously been sold, but that the kits currently being sold contained 1 less set of brackets/servo holders. As I noted in the original post, all of the weight and stress from the robot is carried by the base servo, which really isn't great.

It's fairly easy to find the brackets sold separately, so I bought an extra bracket, and finally got round to rebuilding the base of the arm. While the base servo is still taking a lot of the weight, its now supported by the bracket, spreading the stress around, and making the whole thing a lot more stable.

Here are some pics of the new base during assembly:

You can see that the base servo is removed from its original bracket, and placed in a new one, which is bolted to the old one... while this may seem redundant, it means there's now clearance underneath to attach a u-bracket around the whole servo.

The bracket for the next servo is connected essentially as before, but now the bolts connect the bracket to both the servo horn and the new u-bracket. That means when the arm's weight starts to tip itself over, that sideways force is transmitted (at least in part) to the bearing at the bottom, rather than being fully carried by the neck of the servo.

The result is much more stable. The extra metal work does place some restrictions on range of travel, but only in positions where the gripper would probably be crashing into the table anyway, So generally its looks like a good upgrade.

Putting the bars in barcodes

For some reason I was thinking about barcodes... I'm not sure why, but I started wondering if we could make them in Sniff... turns out you can!

A traditional barcode that you find on a tin of baked beans (technically a UPC-A barcode) represents 12 digits. This first 6 are the manufacturers code, assigned to a company (which applies, and gets given its own number), and the last 5 which represent a specific item, as chosen by the manufacturer:

make manufacturerID string "097855"

make itemID string "08839"

make barcodeValue string

But wait a minute - that's only 11. The final digit is a checksum. When the barcode is printed the final digit is calculated from the other 11, and added to the end. When its read the same sum is calculated by the reader, and if the final digit doesn't match it knows something's gone wrong and it can reject the code.

when start

.if not length of manufacturerID = 6

..say "Bad Manufacturer ID"

..stop all

.if not length of itemID = 5

..say "Bad Item ID"

..stop all

.set barcodeValue to join manufacturerID itemID

.broadcast makeChecksum and wait

.say barcodeValue

Here's the beginnings of the main script. We check that the manufacturer and item ID's are the correct length and join them together to make the beginnings of the barcodeValue - the number that is printed along the bottom. You'll note that they're all strings, as the barcode isn't really a number - its more a sequence of digits, and its easier to handle them as strings.

when makeChecksum

.make counter number

.make sum number

.set sum to 0

.

.set counter to 1

.repeat 6

..change sum by value of letter counter of barcodeValue

..change counter by 2

.set sum to sum*3

.

.set counter to 2

.repeat 5

..change sum by value of letter counter of barcodeValue

..change counter by 2

.

.repeat until sum < 11

..change sum by -10

.set sum to 10-sum

.set barcodeValue to join barcodeValue [sum]

To calculate the checksum, we add up the odd placed digits and multiply by 3. Then we add the even placed digits. Once we have the sum we need to find the number to make the sum add up to a multiple of 10. i.e. if the sum is 74 then the final answer is 6, which would make it up to 80. There are a few ways of doing that, but the simplest is to keep subtracting 10 until its less that 11 (i.e. its now 1...10), then subtract it from 10. This is the checksum value and we tag it on the end of the barcodeValue.

Using our example code, the checksum is a 0, so we get:

097855088390

If you look closely at a bar code you'll notice that it has lines and spaces of varying thickness. In fact both the lines and spaces can be between 1 and 4 units wide. Each digit is represented by two lines and two spaces. To store that information we make a list called symbols:

make symbols list of strings

when initSymbols

.add "3211" to symbols

.add "2221" to symbols

.add "2122" to symbols

.add "1411" to symbols

.add "1132" to symbols

.add "1231" to symbols

.add "1114" to symbols

.add "1312" to symbols

.add "1213" to symbols

.add "3112" to symbols

These represent the digits 0 to 9.

make barcodeWidths string

when makeBarWidths

.make counter number

.make index number

.make symbol string

.

.

.set barcodeWidths to ""

.set barcodeWidths to "111 "

.

.set counter to 1

.repeat 6

..set index to value of letter counter of barcodeValue

..change index by 1

..set symbol to item index of symbols

..set barcodeWidths to join barcodeWidths symbol

..set barcodeWidths to join barcodeWidths " "

..change counter by 1

.

.set barcodeWidths to join barcodeWidths "11111 "

.

.repeat 6

..set index to value of letter counter of barcodeValue

..change index by 1

..set symbol to item index of symbols

..set barcodeWidths to join barcodeWidths symbol

..set barcodeWidths to join barcodeWidths " "

..change counter by 1

.

.set barcodeWidths to join barcodeWidths "111 "

A barcode begins with two lines 1 unit thick, with a 1 unit space between them, which is represented as 111. Then we add the symbols for the first 6 digits, so if the first digit was a 9 then we'd add 3112, meaning a 3 unit line, a 1 unit space, a 1 unit line and a 2 unit space.

In the middle of every barcode is the code 11111, representing 3 thin lines. We then continue on to the end of the barcodeValue, and then tag a "111" end sequence on.

111 3211 3112 1312 1213 1231 1231 11111 3211 1213 1213 1411 3112 3211 111 

In the case of our test code, that gives the above string. You'll note that program adds some extra spaces to separate each digit. These won't appear in the final barcode, but they're handy for checking that everything is working.

The next step is to turn those widths in to actually bars.

when makeBars

.make counter number

.make width number

.make isLine  boolean

.set isLine to yes

.set barcode to ""

.repeat length of barcodeWidths using counter

..if not letter counter of barcodeWidths = " "

...set width to value of letter counter of barcodeWidths

...repeat width

....if isLine

.....set barcode  to join barcode "|"

....else

.....set barcode  to join barcode   " "

...set isLine to not isLine

We simply loop over the length of the barcodeWidths string we just made and get the value of the digit. If its a line we print a vertical bar, otherwise we print a space. The number of lines or bars we print is the width of the line.

| |   || |   | || ||| || || ||| ||   | ||   | | | |||  | |  |   |  |   |    | ||| |  |||  | | |

And there it is - our barcode! It's not exactly pretty and its hard to read, because a thick lines appear as multiple vertical bars, when they should be solid, but trust me its the right answer...

make nativeFile device

make fileData string

make image bitmap device

make displayColor number

make displayX number

make displayY number

when drawBarcode

.set displayY to 40

.set displayX to length of barcode

.tell image to "new"

.repeat length of barcode using displayX

..if letter displayX of barcode="|"

...set displayColor to 000

..else

...set displayColor to 777

..repeat 40 using displayY

...tell image to "set pixel"

.set fileData to "barcode.bmp"

.tell image to "save"

Of course what we really should do is draw our barcode as a bitmap and save it to disk. Fortunately that turns out it be really easy - just go through the barcode and if its a "|" draw a line of black pixels. If its a space draw a line of white pixels. Once we're done, we save it to disk.

[tech note: currently on Windows, the Bitmap device requires that you also make a Window device - otherwise it gets confused that you want to make an image, without a way to ever display it! There's a fix in the next release]

And here it is!!! A perfect barcode, which looks just like the one on the box I took the original number from. Now all that's left to do is print out a bunch of these on sticky labels and go cause havoc in the school library! (actually books use a slightly different format!).

What's really nice about this project is that it would make a really great group project. It breaks down really neatly into 4 parts of similar difficulty, which all need to work to make the whole thing happen. On pair of students is given the ID's and has to make the barcode value with checksum. The second has to turn that into line widths, the next turn that into ascii bars, and the final pair draws the bars. As we have a worked example you can provide each pair with an example of the input they need to read, and the output they need to generate, so they can all work at the same time, and then when they know each part is working, they can bring them all together!