Tag Archive: Puzzles


A strange bug moving from 64bit to 32bit.

So I installed an SSH client on my iPhone today, TouchTerm (which so far I think is excellent, especially how it handles ctrl keys etc.), and the first thing I do? SSH to my server and compile the previously mentioned code. I load it and after changing the font to a fixed width one it all looks good. The puzzle loads, I hit ‘g’ to solve it and …. oh… it got part of the way through the recursive solution and stopped saying ‘Solution Found’. Except it hadn’t. I coded a refresh routine with vi on the phone to make sure it wasn’t a terminal or iphone issue, nope. It really had got part way in and decided the problem was fixed. How odd. The code was written in 64bit Intrepid running in VirtualBox on 64bit Win 7. The server was (it’s upgrading now) running 32bit Jaunty and is only a 32bit system anyhow.

Anyone? Strange strange bug. If the upgrade fixes it I will be surprised as the only external library of note is ncurses and it really isn’t an ncurses problem. My data structures are fairly boring:


struct _cell {
bool readonly;
int value;
};

struct _sudoku {
bool complete;
int iteration;
struct _cell cells[SUDOKU_VALUES][SUDOKU_VALUES];
};

And of that I only actually use the two dimensional array and the value. The readonly, complete and iteration fields are there in case I do implement weirder algorithms as they will be necessary then for distinguishing user input from generated across generations and keeping track of generations, so ancient incomplete ones can be culled as evolutionary dead ends. :) Of course the second one is marked complete the program would end and display it. Anyhow I find the above problem odd, when the upgrades are complete I’ll check and if it persists drop it into gdb for a bit of an autopsy.

It lives!

Finally. Stripped out loads of code having realised that keeping a list of possible answers to each square is all well and good but the computational time spent maintaining it outweighs the benefits of just err.. well figuring it out each time you need to know. So

For some reason the above thumbs are truncated on the left. The clickable images are not.


diziet@ono-sendai:~/Programming/C/Sudoku$ time ./sudoku

real 0m4.071s
user 0m0.390s
sys 0m0.110s

in an ubuntu virtualbox instance on a windows7 box that’s watching a movie. :P

Yay. What next? The backtrack algorithm I used is essentially a brute force. I may now implement my non brute force version to compare. Although I have a feeling I am painting a new room at the village hall tomorrow.

Now with added video?

Sudoku Solver

So ncurses operates on a y,x co-ordinate system.  All of it’s functions expect y first, for example:

getyx(y,x);

which gets the location of the cursor putting the values into y and x.  This sounds a bit counter intuitive to us, we are used to x then y. We think of going across the screen and then down.  So throughout my code I’ve thought of ncurses as counting down the screen then across and my code as counting across the screen and then down.  Which is right and the way I want it. Except when you declare an array as:

int fish[12][9];

You have 12 rows and 9 columns. It is also Y and then X. So a loop such as:


for(int x=0;x {
for(int y=0;y {
array[x][y]=0;
}
}

Does go down and across. So although conceptually you are going across then down if you print the array out with the same logic via say printf("%d ",array[x][y]) you'll find you print down and across. I think.... :P

So I have a sudoku puzzle where the first row at the start is effectively:

7 1

Yet my save routine saved out:


diziet@ono-sendai:~/Programming/C/Sudoku$ cat dm3.sud
0 0 0 0 7 1 0 8 3
0 0 0 0 0 0 2 5 0
0 1 0 0 0 3 4 0 0
7 0 3 5 0 0 0 0 0
0 0 0 0 0 8 9 1 0
0 0 0 9 0 0 0 0 0
0 0 0 0 6 0 1 0 8
1 6 0 0 0 4 0 0 0
0 4 0 0 2 0 3 0 0

So all of my loops have held the data going down and then across the array.   This is not a problem, it changes nothing really except it makes the save files look funny.   So I changed it all thus producing a patch from git with:

git format-patch origin/master

all because ncurses functions put y before x thus making me think it was odd. A snippet from the patch:


@@ -547,12 +547,12 @@ int display_sudoku(WINDOW *wi_sudoku, struct _sudoku *st_sudoku)

getyx(wi_sudoku,old_dy,old_dx);

- for(int x=0; x
+ for(int y=0; y
{
- for(int y=0; y
+ for(int x=0; xcells[x][y].value;
+ cell_value = st_sudoku->cells[y][x].value;

Ho hum.  At least now I can type in a potential sudoku once and keep loading it to test various ideas.  Of course we all know the backtracking algorithm will be the best but it's not the point of this entire exercise anyway.

I’m getting there.

For a about three weeks, although only about 7 days work, I’ve been writing a small ncurses based sudoku solver.  The aim being rather obvious but the reasons more detailed.  I’ve not written anything in C with any true aim in mind for almost 7 years and not on a commercial basis for a decade (although this is not commercial).   The last program I wrote that worked as a Tsunami puzzle solver.  It populated 100 or so solutions randomly, scored them for efficiency against the criteria and bred (crossover, random mutation) the highest scorers to make another 100 until one scored 100%.   The code is now lost somewhere on a random server.  The main file was matrix.c++ which shows how long ago it was.

Anyway, back on topic, things are coming along nicely.  I have one algorithm almost working which is a very human approach.  The next to implement is a recursive backtracking algorithm and more fanciful things from there such as the sort of genetic approach mentioned above.  However to test the code I’ve been typing in the puzzles so now I am implementing a simple save and load feature. It had to be in there anyway according to the System Requirements document I wrote for it.

Powered by WordPress | Theme: KLG based on Motion by 85ideas.