GH II tournament winner!

On Friday night there was a Guitar Hero II tournament organized by metalsevilla and Bohemians’ Pub, and I won!

Looks like all those hours spent playing GH were worth something, after all! Haha. There weren’t many participants though (6, to be precise) but oh well, I got a t-shirt, a fancy diploma, and 2 passes for a concert. =)

Actually, only 2 of us had a chance of winning (the rest didn’t play that well, sorry) and I think that that other guy was a bit better than me. The final was awesome, and we battled each other 5 times. I finally won, but I must say that a draw would have been fairly fair! =)

Now, back to Guitar Hero III. And waiting for Aerosmith’s!

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!