Where In The World Is Poland?

Did you ever take a closer look at the timezone tab on the Windows date and time panel? Depending on your Windows version, it is quite likely that Poland seems to be flooded on the timezone world map. Raymond Chen knows why.

Just Another Sudoku Solver (C++)

Closing this topic, here is the sourcecode of the C++ Sudoku Solver (originally in Java). Remember that this a template class, so all this code has to go to a header file. All allocation actions should be the same as under Java - which is important for runtime behavior comparison.

I coded this last night between 1am and 2am in the morning, so please don't shoot me in case of any mistakes ;-).

#pragma once
#include <vector>
#include <math.h>

template<int D> class Sudoku
{

public:

    Sudoku(int _startGrid[D][D])
    {
        solutions = new std::vector<int(*)[D]>();
        dimSqrt = (int)sqrt((double)D);
        for (int x = 0; x < D; x++) {
            for (int y = 0; y < D; y++) {
                squareIdx[x][y] = 
                (x / dimSqrt) * dimSqrt + (y / dimSqrt);
            }
        }

        copyGrid(_startGrid, startGrid);
    }

    virtual ~Sudoku() {
        for (std::vector<int(*)[D]>::iterator it = 
            solutions->begin(); it != solutions->end(); it++) {
            delete[] *it;
        }
        delete solutions;
    }

    std::vector<int(*)[D]>* solve() {
        for (std::vector<int(*)[D]>::iterator it = 
            solutions->begin(); it != solutions->end(); it++) {
            delete[] *it;
        }
        solutions->clear();
        copyGrid(startGrid, grid);
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < D; j++) {
                usedInRow[i][j] = false;
                usedInColumn[i][j] = false;
                usedInSquare[i][j] = false;
            }
        }
        for (int x = 0; x < D; x++) {
            for (int y = 0; y < D; y++) {
                int val = grid[x][y];
                if (val != 0) {
                    usedInRow[x][val - 1] = true;
                    usedInColumn[y][val - 1] = true;
                    usedInSquare[squareIdx[x][y]][val - 1] = true;
                }
            }
        }

        digInto(0, 0);
        return solutions;
    }

private:

    void copyGrid(int src[D][D], int tgt[D][D]) {
        for (int x = 0; x < D; x++) {
            // for compatibility reasons with java we 
            // copy one-dimensional arrays only
            memcpy(tgt[x], src[x], D * sizeof(int));
        }
    };

    void digInto(int x, int y) {
        if (startGrid[x][y] == 0) {
            int square = squareIdx[x][y];

            for (int val = 1; val <= D; val++) {
                int valIdx = val - 1;
                if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] || 
                usedInSquare[square][valIdx]) {
                    continue;
                }
                grid[x][y] = val;
                usedInRow[x][valIdx] = true;
                usedInColumn[y][valIdx] = true;
                usedInSquare[square][valIdx] = true;
                if (x < D - 1) {
                    digInto(x + 1, y);
                }
                else if (y < D - 1) {
                    digInto(0, y + 1);
                }
                else {
                    addSolution();
                }
                grid[x][y] = 0;
                usedInRow[x][valIdx] = false;
                usedInColumn[y][valIdx] = false;
                usedInSquare[square][valIdx] = false;
            }

        }
        else {
            if (x < D - 1) {
                digInto(x + 1, y);
            }
            else if (y < D - 1) {
                digInto(0, y + 1);
            }
            else {
                addSolution();
            }
        }
    };

    void addSolution() {
        int (*solution)[D] = new int[D][D];
        copyGrid(grid, solution);
        solutions->push_back(solution);
    };

    int startGrid[D][D];
    int grid[D][D];
    int dimSqrt;
    std::vector<int(*)[D]>* solutions;
    bool usedInColumn[D][D];
    bool usedInRow[D][D];
    bool usedInSquare[D][D];
    int squareIdx[D][D];

};

Previos Posts:

• Just Another Sudoku Solver
• Java Vs. .NET Vs. C++ Performance

Follow-Ups:

• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

Computers In Old Movies

A colleague of mine - knowing about my interest for ancient computers - recently asked me whether I knew which system they were using in the 1968 movie "Hot Millions" with Peter Ustinov. I remember having seen this picture once, and I also remember they had a mainframe in the scenery. But the only image I could look up in internet is this one with Ustinov sitting in front of a terminal. I guess I will have to watch "Hot Millions" again in order to find out.

Anyway, this question caught my attention, so I did some more research and discovered that the first appearance of a computer in a cinema movie was probably a mockup named "EMERAC" (reminiscenting about ENIAC or UNIVAC?) in "Desk Set" with Katherine Hepburn from 1957. It even consisted of real computer parts, namely IBM 704 magnetic tapes and some panels from the famous SAGE military computer (based on vacuum tubes and ferrite core memory).



No list of computers in old movies would not be complete without HAL9000 from "A Space Odyssey". Timeless.

Java Vs. .NET Vs. C++ Performance

Well I am done with porting my little Sudoku Solver to C++. I took care to keep the algorithm equivalent, esp. on memory allocation (actually the only memory that is dynamically allocated is for storing away puzzle solutions). Not really surprisingly, C++ beats both C# and Java:

Platform	Execution Time (for several thousand valid solutions)
C++	250ms
C# (.NET 1.1) after NGEN	390ms
Java (JDK 1.4.2)	680ms
C# (.NET 1.1)	790ms

I calculated the execution time by feeding the solver with a sparsely populated puzzle that has thousands of valid solutions (Sudoku purists will point out that this is a non-well-formed puzzle). The algorithm uses a slightly optimized brute force approach (my intention was runtime comparison, not building a hyperfast solver algorithm) - so it finds all the solutions.

The algorithm, when implemented in C++, delivers around 60.000 valid solutions per second on my 2.4GHz Athlon for average one-solution 9x9 Sudoku puzzles. The time it takes to solve one of those can hardly be measured, and I didn't want to inject the same puzzle a thousand times for the benchmark.

It depends heavily on the intial puzzle values, though. I digged out a puzzle - one that is considered more or less unbreakable for humans - that took the C++ implementation 15ms to solve. 15ms for one solution, mind you.

I doubt that there is a lot of optimzing potential for Java Hotspot other but compiling the algorithm's main method (which only consists of a few lines of code anyway) to native code as soon as possible. Dynamic memory allocation only happens for storing away solution arrays, and those are not going to be garbage collected until the end, so there is not a lot of optimizing potential on the memory management side. The .NET CLR should JIT all of the code at startup anyway. I did some tests to go sure, and the numbers did not change neither under Java and nor under .NET even after running the same stack of puzzles many times in a row.

Previos Posts:

• Just Another Sudoku Solver

Follow-Ups:

• Just Another Sudoku Solver (C++)
• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

Java Vs. .NET Performance

As a sidenote, I just ported yesterday's Sudoku Solver to C#, ran the same stack of puzzles, and compared execution times. Here is the result:

Platform	Execution Time (for several thousand valid solutions)
Java (JDK 1.4.2)	680ms
C# (.NET 1.1)	790ms
C# (.NET 1.1) after NGEN	390ms

What I did here was to feed the solver with a sparsely populated puzzle that has thousands of valid solutions, and measure the time of execution to find all the solutions in a brute-force manner. Just finding one solution would be beyond the scale of time measurement.

Right now I am working on a C++ port, so this will be another interesting comparison (my C++ coding is slower than it used to be, since I have not written a single line of C++ over the last two years).

Vanilla DAL 0.2.2 Released

I received some valuable feedback from some projects employing the Vanilla .NET Data Access Framework, so the following changes have been incorporated in release 0.2.2:

• SqlServer: quoted identifiers for table names and column names (square brackets).


• New Property FillParameter.SchemaHandling for defining whether DataSet schema should be preserved or updated by DB schema.


• SQL code may now be passed in directly, as well as pre-processed before execution. The sample application provides more details.


• Class "StatementID" has been renamed to "Statement".

Just Another Sudoku Solver

Yes, it's only brute force (just avoiding digging deeper into the search tree when it's proven wrong already), and yes, it's Java which implies array bounds checking, but it still delivers around 30.000 valid solutions per second for average 9x9 Sudokus on my 2.4GHz Athlon. Faster than my father-in-law who has been messing around with a single puzzle all night long. I couldn't watch it any longer [;-)], so I hacked in the following code.

package com.arnosoftwaredev.sudoku;

import java.util.ArrayList;
import java.util.Collection;

public class Sudoku {

 private int[][] startGrid;
 private int dim;
 private int dimSqrt;
 private ArrayList solutions;
 private boolean usedInColumn[][];
 private boolean usedInRow[][];
 private boolean usedInSquare[][];
 private int squareIdx[][];
 private int grid[][];

 public Sudoku(int[][] startGridParam) {
     if (startGridParam == null) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length == 0) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length != startGridParam[0].length) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     dim = startGridParam.length;
     if (dim != 4 && dim != 9 && dim != 16 && dim != 25) {
         throw new IllegalArgumentException("Grid is invalid");
     }

     solutions = new ArrayList();

     dimSqrt = (int) Math.round(Math.sqrt(dim));

     usedInColumn = new boolean[dim][dim];
     usedInRow = new boolean[dim][dim];
     usedInSquare = new boolean[dim][dim];
     squareIdx = new int[dim][dim];
     startGrid = new int[dim][dim];
     grid = new int[dim][dim];
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             squareIdx[x][y] =
             (x / dimSqrt) * dimSqrt + (y / dimSqrt);
         }
     }
     copyGrid(startGridParam, startGrid);
 }



 private void copyGrid(int[][] src, int[][] tgt) {
     for (int x = 0; x < src.length; x++) {
         System.arraycopy(src[x], 0, tgt[x], 0, src[x].length);
     }
 }

 private void digInto(int x, int y) {
     if (startGrid[x][y] == 0) {
         int square = squareIdx[x][y];

         for (int val = 1; val <= dim; val++) {
             int valIdx = val - 1;
             if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] ||
             usedInSquare[square][valIdx]) {
                 continue;
             }
             grid[x][y] = val;
             usedInRow[x][valIdx] = true;
             usedInColumn[y][valIdx] = true;
             usedInSquare[square][valIdx] = true;
             if (x < dim - 1) {
                 digInto(x + 1, y);
             }
             else if (y < dim - 1) {
                 digInto(0, y + 1);
             }
             else {
                 addSolution();
             }
             grid[x][y] = 0;
             usedInRow[x][valIdx] = false;
             usedInColumn[y][valIdx] = false;
             usedInSquare[square][valIdx] = false;
         }

     }
     else {
         if (x < dim - 1) {
             digInto(x + 1, y);
         }
         else if (y < dim - 1) {
             digInto(0, y + 1);
         }
         else {
             addSolution();
         }
     }
 }

 private void addSolution() {
     int[][] solution = new int[dim][dim];
     copyGrid(grid, solution);
     solutions.add(solution);
 }

 public Collection solve() {
     solutions.clear();
     copyGrid(startGrid, grid);
     for (int i = 0; i < dim; i++) {
         for (int j = 0; j < dim; j++) {
             usedInRow[i][j] = false;
             usedInColumn[i][j] = false;
             usedInSquare[i][j] = false;
         }
     }
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             int val = grid[x][y];
             if (val != 0) {
                 usedInRow[x][val - 1] = true;
                 usedInColumn[y][val - 1] = true;
                 usedInSquare[squareIdx[x][y]][val - 1] = true;
             }
         }
     }
     digInto(0, 0);
     return solutions;
 }

}

Follow-Ups:

• Java Vs. .NET Vs. C++ Performance
• Just Another Sudoku Solver (C++)
• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

The Software Projekt Triangle

From Microsoft Project Online:

If time, money, or what your project accomplished were unlimited, you wouldn't need to do project management. Unfortunately, most projects have a specific time limit, budget and scope.

It is this combination of elements (schedule, money and scope) that we refer to as the project triangle. Understanding the project triangle will allow you to make better choices when you need to make tradeoffs. If you adjust any one side of the triangle, the other two sides are affected.

For example, if you decide to adjust the project plan to

• Bring in the scheduled finish date, you might end up with increased costs and a decreased scope.


• Meet the project budget, the result might be a longer schedule and a decreased scope.


• Increase scope, your project might take more time and cost more money in the form of resources

Quality is at the center of the project triangle. Quality affects every side of the triangle, and any changes you make to any side of the triangle are likely to affect quality. Quality is not a factor of the triangle; it is a result of what you do with time, money, and scope.

For example, if you find you have additional time in your schedule, you might be able to increase scope by adding tasks and duration. With this extra time and scope, you can build a higher level of quality into the project and its deliverables.

Or if you need to cut costs to meet your budget, you might have to decrease scope by cutting tasks or reducing task durations. With decreased scope, there might be fewer opportunities to achieve a certain level of quality, so a lower quality results from the need to cut costs.

Jeff Atwood even carpented "the iron stool of software project management" out of this.

Macs Do Windows Too

Harsh words on the Apple Boot Camp site (Boot Camp lets you install Windows XP on Intel-based Macs), e.g.:

Macs use an ultra-modern industry standard technology called EFI to handle booting. Sadly, Windows XP, and even the upcoming Vista, are stuck in the 1980s with old-fashioned BIOS. But with Boot Camp, the Mac can operate smoothly in both centuries.

Good for Apple that they don't have to worry about backward compatibility on old hardware. I also remember the pre-2002 era, when Mac OS still lacked memory protection and preemptive multitasking. How "1980s" does that sound?

Guy Kawasaki: The Art Of The Start