Martin C Harvey's Pages

Hi folks! So, I have been a busy little bee, and have been trying to work out how many isomorphisms there are for a certain number of givens (pre-existing placements) – that is, initial configurations which are the same, modulo row, col, stack, band permutations, and reflection. This is just the given locations, not the contents of those cells. I get the following numbers:

Order2 board ( 4×4 cells):

 There are 1 isomorphisms with 0 givens, order2
 There are 1 isomorphisms with 1 givens, order2
 There are 5 isomorphisms with 2 givens, order2
 There are 10 isomorphisms with 3 givens, order2
 There are 33 isomorphisms with 4 givens, order2
 There are 53 isomorphisms with 5 givens, order2
 There are 101 isomorphisms with 6 givens, order2
 There are 122 isomorphisms with 7 givens, order2
 There are 153 isomorphisms with 8 givens, order2
 There are 122 isomorphisms with 9 givens, order2
 There are 101 isomorphisms with 10 givens, order2
 There are 53 isomorphisms with 11 givens, order2
 There are 33 isomorphisms with 12 givens, order2
 There are 10 isomorphisms with 13 givens, order2
 There are 5 isomorphisms with 14 givens, order2
 There are 1 isomorphisms with 15 givens, order2
 There are 1 isomorphisms with 16 givens, order2

Order3 board ( 9×9 cells, “standard” sudoku board):

---

 There are 1 isomorphisms with 0 givens, order3
 There are 1 isomorphisms with 1 givens, order3
 There are 5 isomorphisms with 2 givens, order3
 There are 21 isomorphisms with 3 givens, order3
 There are 109 isomorphisms with 4 givens, order3
 There are 548 isomorphisms with 5 givens, order3
 There are 3074 isomorphisms with 6 givens, order3
 There are 16847 isomorphisms with 7 givens, order3
 There are 92393 isomorphisms with 8 givens, order3

Now. That took me 12 CPU core hours. The magic number I want to get to with order3 boards is of course 17, the lowest number of givens in any standard sudoku puzzle. All of a sudden this looks like it will take some serious CPU grunt. I’m not exactly sure, but for small numbers of givens (less than 1/4 the cells on the board), it looks like adding one extra placement multiplies the number of isomorphisms by a factor of roughly 5.5.

With respect to computational cost, determining isomorphisms is reasonably fast (at least 200k per CPU core second on average), but since there’s no easy way of “sorting” that I know about, there’s no “log N” shortcut, and determining uniqueness requires an N^2 comparison cost, so the computational cost is proportional to the square of the number of isomorphisms.

Plugging these numbers into a spreadsheet, assuming (conservatively) 4 CPU cores per machine (your average laptop), I can then calculate the costs in thousand machine years:

Givens	CPU Hours	Thousand machine years
0	1.35899570417687E-09	3.87841239776503E-17
1	1.35899570417687E-09	3.87841239776503E-17
2	3.39748926044217E-08	9.69603099441258E-16
3	5.99317105541998E-07	1.71037986741438E-14
4	1.61462279613254E-05	4.60794176978463E-13
5	0.000408111845947	1.16470275669843E-11
6	0.012841797290722	3.66489648707831E-10
7	0.385712075584426	1.10077647141674E-08
8	11.601021233041	3.31079373089068E-07
9	350.930892299489	1.00151510359443E-05
10	10615.6594920595	0.000302958318837
11	321123.699634801	0.009164489144829
12	9713991.91395273	0.277225796631071
13	293848255.39707	8.3860803480899
14	8888909725.76137	253.67893052972
15	268889519204.281	7673.78764852402
16	8133907955929.51	232132.076367851
17	246050715666868	7021995.31012751

Now, as it turns out, distributed computing is my sort of thing, so I reckon getting up to about 12 givens (277 machine years) is pretty doable, but 17 looks somewhat out of the question, unless I can find a way to answer these two questions:

• Currently I compare all boards against all other boards, with a couple of “tricks” for rapid comparison that removes the need to consider permutations in most cases. I could possibly re-apply some of those tricks to reduce the cost from N^2, but I’m not sure it’ll give anything more than a constant cost improvement. Probably won’t reduce the cost to N log N. (Details available after some discussion).
• My math assumes a constant 5.5 increase for each extra given. Do we have any reasons to assume that that that number might decrease above 9 or 10 givens?

Little sudoku update. So, I’ve been working on various algorithms to try and work towards solving a pretty knotty problem with respect to Sudoku. It’s turning out to be much more difficult than expected.

I have a “naive” algorithm which gets correct results for smaller board sizes, but which will not complete for a regular sudoku board in my lifetime.

I have a “clever” algorithm, which is slower for small boards, but bigger for fast ones. Unfortunately, it gets wrong results (for reasons I understand), which is not the end of the world, and fixable – it misses some cases.

However, the clever algorithm also seems to get inconsistent results: if I swap a board where the squares are filled with an equivalent board where the squares are empty, I should get the same answer, and I don’t. Debugging in progress: I have probably taken a shortcut somewhere that I shouldn’t have done.

I have also attempted a modest improvement at improving the speed of the exact cover algorithm by improving how it picks constraints. To my astonishment, unless the number of constraints is very large, and the subset of them which change is quite small, it’s actually not any quicker than the naive algorithm, which is n/2 cost.

Regardless, both algorithms are too slow, and I also have some more unusual-ish ideas about how to make a faster algorithm. The only problem it takes so much code to try out each new idea and then find whether it works or is bust. Perseverance will be required!

Once I have a good algorithm, then I can start thinking about distributing it across lots of CPU’s.

So, wanting to improve my knowledge of sudoku, I have now implemented a “proper” DLX solver, which solves all sudoku problems in the blink of an eye, yes it’s about a thousand times faster than a naive algorithm.

You can download a copy of the testapp here.

Rest assured, this is just the start of some rather more interesting problem solving with respect to sudoku.

[ Note for readers – none of this is a comment on my current employer, or fellow employees, who I think are fab! ]

I wonder if any of you have ever bought a skeleton watch? For people that like gadgets, they’re quite cool: you can wind the watch up, see all the moving parts whirring back and forth, and for a brief moment think wow, that’s really neat.

The joy of creating: The best parts of software development are like that, especially when you’re developing something new: you find a neat way of solving the problem, maybe some cool algorithm, or maybe some way of putting existing software components together, and when you’ve put the whole thing together, it whirrs into action like some finely crafted watch, and if your debugging skills are good, you can see all the various parts moving back and forth doing what they’re meant to do.

If you did a computer science degree, that’s probably the bit that you thought was fun, and kept you interested.

Conversely, there are some parts of software development that I think most people find a pain. I find them a pain, and not particularly fun. Maybe there are some guys out there that like them. Specifically: build systems and test frameworks.

When you initially develop them, there is of course the coolness factor of getting everything up and running, however after that it gets less pleasant, for a couple of reasons:

Scripting: Scripting can be a pain in the backside: You’re having to tie together disparate software systems, with different ways of working, and may have to know several different scripting languages with different conventions to get everything to work.

Test frameworks: In a test framework, you may not be writing just an algorithm, but instead are having to take some set of commands and pipe them through various frameworks to execute remotely on various machines, and then collate the results. If you built the test system, then it’s OK, but if you’re changing it because you’ve added functionality elsewhere, then you need to learn a load of plumbing that makes no sense at all, just to add some extra test for some new functionality.

Test compatibility and versioning control. Is it me, or is getting test frameworks to run reliably a pain? Simple test frameworks are fine, but as they grow bigger and bigger, the number of things you need to control for increases exponentially e.g.:

• We need to check our software works. All the different deployments and variants.
• On various different OS builds. All of which need to be taken into account…
• … and might be hotfixed and patched or not.
• Which need to be installed and deployed in an automated manner….
• … requiring more framework to install / deploy, across multiple OS’es.

After a little while, the whole thing can turn out to be positively labyrynthine. I guess that why people hire hordes of test engineers.

Third party software. Third party software can be a pain. It’s not that there’s anything wrong with it, per-se. It’s just that it’s third party stuff. And hence you don’t have the source / don’t know how it works. Even more annoying is when it auto-upgrades itself, and the first you know is when your tests break for no apparent reason.

Almost all of the most difficult and confusing bug hunts I have been on have involved bugs in third party software. Typically what happens is that the flow of control disappears into the complete black lagoon of some third party component, and then never reappears for some reason that is not immediately apparent. You then have to fight a huge battle to get some other organisation to find and fix their bug.

So, there you have it. The ups and downs of software development.

The very quickest of quick notes on open source software. I can’t help but feel that software developers, as a whole, have somewhat given away too much. A browse of github / sourceforce and the like would indicate that for just about every sort of software that the end consumer would be happy to pay good money for, there is a version or competing product which is available in open source form for free.

Although the reasons for individual projects being open sourced differ, there seem to be several categories that are of note:

Category 1, part, or ex-commercial software:

Companies have been unable to make a profit or viable product from a software project, and upon winding the project down, have decided to open-source the software.

Alternatively, the company has gone bust, but the developers have been loath to throw away many man years of work, and have hence open sourced it.

Or, the company has a product of sorts, but has not been able to obtain or hold on to the manpower or expertise to keep it viable, so in the hope of spurring development (often towards third party add-ons, improvements), they decide to open-source it.

Category 2. Convenience and altruism.

Truth be told, most projects are too small for just one guy, and quite often, collaborative projects need many people, widely distributed across the globe. However, in many cases, these people do not fall under the easy case of being employed by the same company, or, the project is simply a group of like minded people, who have a common goal and want to work on the project in their spare time. In such cases an open source development model seems ideal.

So what’s the downside?

The downside is that there are only so many new things under the sun.

The open source model is based on the premise that freely available software ecosystems stimulate further development by lowering barriers to entry. This is certainly the case. It’s also true that open source software is often (but not always) of relatively high quality, there being more eyes to examine, understand, and fix the code.

The problem is that I and many other software developers take the point of view that given years of learning, training and career progression, we’d like to be able to make money out of our skillset. Open source software makes it increasingly difficult to do that – if something has been done well, and it’s been open sourced, and exists in a free distribution, then savvy consumers are less likely to pay money for a similar product, if they can get something good enough for their needs for free.

Note the phrase there: “good enough for their needs”. For example: If I want an office suite, I could buy a copy of MS office, or I could use LibreOffice (ex StarOffice) which is free.

Truth be told, MS Office is probably the better product: It’s newer, has more features, and is kept up to date with the very lastest GUI toolkits and OS releases. However, I probably only use about 10% of the features in the product, and all of the features I use are also in LibreOffice, hence I use the latter.

The case now comes that if I am Joe software developer, and I want to make money by writing and developing an office suite, there is no way that I’m going to be able to make any money out of it.

So, here’s the question. Have OSS developers gone and cheapened their trade by writing so much free software?

We will all be vaccinated and let out of purgatory some time in 2021. Some quick social notes for you folks:

• Look good.
• Be nice.
• No silly magic games.
• Exercise good judgement.
• Show some degree of common sense and initiative.
• Go for older men.

Considering the huge spanner in the works that COVID has presented to the economy and our way of living, What level / frequency of side effects might be considered acceptable?

Vaccine development is usually ultra-ultra cautious, esp if the vaccine developers are not in the same region of the world as those afflicted. Would we accept a higher risk level given the considerable harm presented not only to people’s health, but also their living standards.

Next thing: Are we still vaccinating for the “original”COVID. We now have some more prevalent / trasmissible mutations. Will we get a Vaccine V2 in a couple of years like we do for flu?

So, apart from taking the time to improve the golf swing, I’ve noticed an interesting reticence amongst some people to take certain courses of action. It works like this: People get into a train of thought:

“Well if we do X, then they’ll do Y, or Z, but if they do Z, then it’ll look really stupid and embarrassing, so we won’t do X”.

My question is this: “How do you smack into these people’s heads that the chain of verbal logic they’re going through, bears no resemblance to reality whatsoever.” Here’s why:

• You’re assuming that you know their thought processes. You don’t.
• You’re assuming that they think the same way you do. They probably don’t.
• You’re assuming that the outside forces of nature / chance / unknown unknowns can be discounted. They normally can’t.

And so we get people doing things for political (verbal / thought out) reasons, when sometimes the chain of logic / reasoning bears no resemblance to reality whatsoever.

Half the challenge in life is working out what’s real, and what isn’t.

For example: people who do things like PR / Advertising. The effects of PR / Advertising / Setting up a movement are statistical. That is, you’ll either convert some people to the cause, or your won’t. Convincing yourself that you can convert any one individual, or that you can rationalise individuals actions based on a widespread (relatively) nonspecific set of information or disinformation is false.

I’ve noticed that people get better at this as they get older. People in the 20-35 age bracket are really poor at telling what is genuine information from what is just hearsay, PR and disinformation. Or more particularly, even if they can verbally reason these things through, their behaviour is governed more by the group understanding, than the underlying realisty. They overestimate the credibility of hearsay, and the importance of groupthink, and they underestimate how important it is to check the facts and/or reality of the specifics. Hence: “my mate says that X” … governs their behaviour more than “x is true”.

Call me a rationalist.

So, I did a bit of reading, and wrote a little solver. Will solve most puzzles instantly, and all puzzles with a unique solution in under thirty ten seconds. Not bad for a days work. Doesn’t even need multiple CPU cores.

I notice that Knuth has a clever way to do it a thousand times faster. I have not represented all the constraints explicitly….

My solver is here.

Before:

After:

Answers to questions:

• Yes.
• Not necessarily, but for human solvable problems, the decision tree is pretty constrained. There may be heuristics I don’t know about.
• Depends on initial constaints, sometimes yes, sometimes no.
• That’s the next big thing I have to figure out. It looks much more tricky.
• As one passes the point where there is not enough information to find a unique solution, for every digit you remove from the initial configuration, the solution space goes up by a factor of between 10 and 100 roughly.
• With no initial constraints, taking symmetries into account, the state space is five billion. Not taking symmetries into account it’s one trillion times that again.

• Is there an initial configuration of the board which looks sensible, but has a logical inconsistency so there aren’t actually any solutions.
• In the puzzles posed by newspapers (at least the easy ones I have done), there is normally always a fully constrained position for every next move. Is this always the case?
• If there isn’t a fully constrained position for every next move, are all subtrees except one blind alleys, or not?
• How does one generate a puzzle where one knows that there are always enough constraints to make a reasonably unambiguous decision?
• In the case of underconstrained configurations how large is the state space?
• In the case of no initial constraints (no numbers at all), how large is the state space of all possible solutions?