Sniff is a "Scratch-like" programming language that's designed to help Scratchers move gently from Scratch to more conventional languages. They can start writing programs, without having to learn a new language because Sniff is based on Scratch. They learn a little more about variables, compiling, syntax errors (!), and they can have fun controlling real hardware while they're doing it.

Friday, 31 March 2017

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.



1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete