Solving the sudoku

I know you were eager to taste some source code, so here you have a first version of the solver.
To try it, just follow the steps described in the post below (PIC Simulator, Assembler, Assemble & Load, Run).

To verify it works, you take a look at the status of the GPRs, and if you remember what was said here, you’ll know if it has properly solved the sudoku or not.

The sudoku it solves is defined by the few hundred lines of code enclosed in the region ’sudoku input’.
If you want to try another sudoku, just do what needs to be done.

This is a first version of the solver, and managed to solve ‘very easy’, ‘easy’, ‘medium’ and some ‘hard’ sudokus of those at this site. It did solve an ‘expert’ one , too. We are currently working on an improved version.

The following flowchart shows the strategy the program uses in order to solve the sudokus:

Hello, programmer

You’ve seen that we have already used some PICs (that colour sensor video some posts ago?), so we have programmed them. You’ve seen, too, that we have made a program (in Perl) that generates some assembly code to load the information of a sudoku into memory.

But, we haven’t really got into programming yet, have we?

Since we have already coded a first version of our sudoku solving program (and a second version too, actually), the time for a ’source code’-post is not far. But before that, let’s get ready to code!
In this post, we’ll explain how to set some tools up to ease the coding process.

Firstly, we will need PIC Simulator to test our programs. Let’s explain a bit how it works.

That’s what it looks like when you start PIC Simulator. You can select there which microcontroller you are going to be working with, and at which clock speed. Also, note the section dedicated to General Purpose Registers (GPRs).

If you go to Tools -> Assembler, a text editor will open. Here’s where you are supposed to write the code. Or you can File -> Open another .asm file. Then, Tools -> Assemble & Load and the program gets loaded and ready to be run.

At this point, one basically uses Simulation and Rate tabs at the main window of the program.
The breakpoints manager (Tools -> Breakpoints Manager) is also very helpful (particularly, if you are bug-hunting). This is how it looks:

So far, so good. But the editor that comes with PIC Simulator kind of sucks, and you do realize that when you are writing a program with many lines of code.

We didn’t like it’s poor color-coding, or the fact that it didn’t have code regions. So we decided to move on to an editor that had it all: Notepad++.

It’s a great text editor and, best of all, allows you to define your own languages (user defined languages, yay!).
So we defined a PIC16F language, and that way we had colour coding that we liked, and regions! (They start with the keyword ‘;region’ and end with ‘;endregion’)

If you want to use yourself this language with Notepad++, you just have to download the userDefineLange.xml file and paste it into the folder that opens when you type ‘%APPDATA%\Notepad++’ and press OK at Start->Run.

Well, I think that’s all. You learnt how to use the basic functionality on PIC Simulator and you have a powerful editor to program in. Next, we’ll give you some source code to play around. Later dudes and dudettes!

SudokusWeb to asm!

When we started working on our sudoku solving assembly (PIC16F648A) program we found we needed a simple way to load the initial data of the sudoku (in order to have something to solve!).

(For those who have read the post “The Data Memory Map”, the following will make more sense)
Loading the initial data of the sudoku basically consists of storing the input data about columns 1-3 at bank 0 (using 2 bytes per sudoku cell), moving on to bank 1, writing input data about columns 4-6, moving on to bank 2 and writing input data about columns 7-9.

The first time we did it manually, but that was a hell of a job. So we looked for a website that could supply us with daily sudokus, from very easy to expert, found one, and wrote a Perl program that, taking one of that site’s images as input, produces the assembly code we need as output.

Then we just paste this code into the part of our sudoku solving assembly program that’s destined to ‘input’, and voila, we can test different sudokus really easily.

Here you can download the source code of this program, as well as an example image to test it.

By the way, the example sudoku that comes in that .rar is already solved by our program. =D
Expect a post about the solver itself soon! (Among a few others hardware-related posts, yay!)

The Data Memory Map

The following image has been extracted from the datasheet of the PIC16F648A, as it’s the PIC we are currently using as ‘main brain’.

It’s main task (and the one that’s currently being coded) is to solve a given sudoku. In order to solve a sudoku, we need to store it’s data into memory. That’s what I’ll cover on this post.

As you can see, the data memory map is divided into 4 banks.

The GPRs (General Purpose Registers) are basically where you can store whatever you want to. There are three groups of GPRs (banks 0-2).
Positions 70h-7Fh are globally accessible (which means they can be accessed no matter which block you are currently at), so they are great for ‘global variables’.

So yea, 3 groups of GPRs (not taking 70h-7Fh into consideration):

• Bank 0: 20h-6Fh
• Bank 1: A0h-EFh
• Bank 2: 120h-16Fh

A sudoku is composed of 81 cells (9 rows and 9 columns). Each of these cells can have a value ranging from 1 to 9 (or it could be still unknown if it’s not been solved).

We are going to store columns 1-3 at bank 0, columns 4-6 at bank 1 and columns 7-9 at bank 2.
That means 27 (81/3) cells per bank.

Now, what to store per cell? We are going to do it like this:
2 bytes per cell.

First byte: each bit (let’s name them from 1 to 8) will indicate if that given number can be (or is) the value of that cell.
Second byte: first bit will indicate if number 9 can be (or is) the value of that cell, and the other 7 bits will be used for other purposes (such as a flag indicating if that number has a sure value [aka one and only one of the previous bits equals 1], a flag indicating if it has removed its sure value as possible from the rest of the cells of its column/row/zone already, etc.).

So, for example, if a cell has a value of 3, its corresponding 2 bytes in memory will look like:

0010 0000 0XXX XXXX (X at the flags, since you don’t care about their values =P)

If a cell had a value of 9, it would look like:

0000 0000 1XXX XXXX

And so on. Also, if a cell is unknown (aka it wasn’t one of those whose value they give you at a start):

1111 1111 1XXX XXXX

So, there are 3 banks with GPRs, three columns of the sudoku will be stored at each, and each cell of the sudoku takes 2 bytes.

This means that we will need 2 bytes * 3 columns * 9 cells = 54 bytes for sudoku data at each memory bank.
We will use:

• Bank 0: Positions 20h-55h
• Bank 1: Positions A0h-D5h
• Bank 2: Positions 120h-155h

The GPRs that the sudoku itself won’t cover will be used to store temporal values (’variables’).

So, basically, that’s how it’ll be organized. More to come!

Hello PICs!

We are going to use PIC microcontrollers to control our robot, and we are going to program them in assembly (yay for low-level coolness and total control!).

We plan to use a PIC16F648A (256 bytes of RAM for us to use, not much, just for it to be more exciting) as the main brain. It would be in charge of solving the sudoku and controlling (asking for information, and receiving information from) other, smaller PICs (12F675).

We had our first meeting (the trigeeks at my basement!) last Sunday, and since then we’ve started working harder!

Now I’m going to show you some videos so you can see some of what we have been doing. Follow the links (click on the videos) for a more detailed description of what’s going on in them.

Our very first test with a PIC (we had never used one before!):

Dealing with 7-segment displays:

And finally, our current masterpiece in terms of hardware. A first prototype of the colour sensor that will be used to detect different pieces (1-9). Also, note that here we have two PICs working together. =)

Movement: Decision taken

We are going to use the system they used in the checkers bot I mentioned a few posts ago.

Movement and design

Just some thoughts.

Our robot needs to be able to move both on the x axis and the y axis in order to be able to go through the whole board. It would optimally be able to move diagonally but it’s not required.

It could either be sort of an independent vehicle that moves on the board (1), or it could move over the board, suspended on some structure (2).

(1) Would require cells to be quite separate, so that the robot can move among them without touching/moving them. Diagonal movement isn’t that simple to achieve. Actually, having both horizontal and vertical movement isn’t that easy to achieve either… you either need some sort of wheels that can change the direction they are facing, or have both wheels pointing horizontally and vertically, and activate only the ones needed… not too fond on that.

(2) Sort of the same system they use on these things.
A friend of mine made a checkers bot some time ago, and he used that scheme, you can take a look at his robot (youtube video) here.

Option (2) is the one I will vote for. =P
(Note how it uses electromagnets to pick pieces, too. Our robot should behave similarly in that aspect aswell.)

Harder than we expected?

It’s taking us a bit to get started.

We first thought about using Lego NXT, but oh well, we don’t really have direct access to one (even though they have some at the University but hmm…) and they are expensive, way too expensive for our limited budget. =P

So now we are going to try to go the cheap way. That means using microcontrollers (I personally hadn’t used one before, and neither had my friends…).

We found some sort of good introduction tutorial for Atmel ATtiny2313, and there’s where we’ll start. Soon (quite a few exams arriving, oh no!).

So what problems will we have to face? Many. Some of them are:

• Movement
• Piece detection
• Piece picking and dropping

About movement, well, we want it to be able to move both on the x and y axis, so that it can easily go through the entire board (first for an analysis of which pieces are given as initial data, and then to pick and drop the appropiate pieces on the adequate locations).

Piece detection? We want the robot to know what number the piece below it represents. We are thinking about using cromatic sensors.

Piece picking and dropping: we could have the robot physically grab pieces, or we could use an electromagnet.

I’ll elaborate more on those topics in future posts.

It’s cool that we are finding some support. Actually, whenever we tell someone about the project, they want to help. Guess it’s a charismatic robot, ours (at least in our imagination, wahey!). But really, there are a couple of guys that will be of great help, I’m sure. ^^

Brief introduction

Yo dudes.

So I’m going to work with some friends (mainly jacano and minolo3ds I guess) on a robot.
We made a Guitar Hero bot a while back and enjoyed the experience, so we thought we could work on a new project and have some more geeky fun!

We want to make a sudoku solving robot. That is one that solves sudokus. >: D

So I think that counts as a brief introduction. More to come.