The New Sudoku Players' Forum

[Rocco]

The first time I saw SuDoku, my immediate thought was that an elegant and symmetrical problem deserved an elegant and symmetrical solution. I knew I could build a sledgehammer program, but that would be like using a helicopter to get to the summit of Everest. I felt there was a more sympathetic way, using generalised logic along with simple, reusable data structures.

My first step was to prototype a solution in VBA using arrays and recursion. However, it soon became clear that this wasn't the best approach. I decided to start again - still using VBA, but this time using Object Modules and enumeration instead. I know the purists will argue that VBA isn't truly OO, but as I had no real requirement for polymorphism and inheritance, that is of no consequence. Instead, the VBA implementation of object heirarchies as indexed collections was a great benefit.

The classes and attributes were fairly easy to define. I ended up with:
Cel {Available_Candidates as String, Parent_Bloc as Collection} and
Bloc {Child_Cel as Collection} with associated Let / Get methods.
Bloc is instantiated once for each row, column and minigrid.
The collection attributes act as pointers from one class to the other. This satisfies the somewhat unusual recursive data structure whereby one Cel is contained by 3 Blocs (1 row, 1 col, 1 minigrid) and each Bloc contains 9 Cels.

The next step was to look at the logic. After generalising the solution I had been applying with pen and paper, I came up with two rules:
1/ If only the same n candidates appear in n Cels within 1 Bloc, then those candidates may be removed from all other Cels within that Bloc
2/ If the same n candidates appear only in n Cels within 1 Bloc, then all other candidates may be removed from those Cels
It doesn't take much thought to see that only values of 1 to 4 need to be considered for n, and of course where n = 1, the final value for that Cel is proven.

Implementing rule 1 was straightforward; create a method Bloc.Solve to enumerate Bloc.Child_Cel and, for each distinct set (n1) of Available_Candidates, find the set (n2) of Cels containing that exact set of candidates. If n1 = n2, then each of the candidates thus identified may be removed from all Cels outside that set. This is achieved by two more methods; Bloc.Remove_Candidates and Cel.Update_Candidates. The set of candidates just identified is passed as an argument to the first method, which invokes the second method for each Instance of Bloc.Child_Cel.

If Cel.Update_Candidates causes only one valid candidate to remain in a given Cel, it may be seen that a situation of n1 = n2 (= 1) has actually just been created. At this point Cel.Update_Candidates re-invokes Bloc.Remove_Candidates for each instance of Cel.Parent_Bloc (further demonstrating the entwined relationship between the two objects) to remove this candidate from all other Cels in the same row, column and minigrid.

When I had finished and tested these three methods, plus a few helper functions, I turned my attention to rule 2 and realised that it could be restated thus:
If only n Cels within 1 Bloc contain the same n candidates, then all other candidates may be removed from those Cels
This could therefore be implemented using exactly the same logic as rule 1, but with the structure of each Bloc "inverted".

To elaborate on what I mean by "inverted", take the case of an arbitrary Bloc which represents one row, column or minigrid. Each Cel (x) in that Bloc contains a string of candidate values, represented by Bloc.Cel(x).Available_Candidates
This may be restated as each candidate value (y) is contained by a collection of Cels, which could be represented by Bloc.Candidate(y).Available_Cels
x and y are both digits in the range 1 to 9, Cel and Candidate are identical object types, and Available_Candidates and Available_Cels are both simply strings of up to 9 digits. Therefore, both of the above cases may be represented by Bloc.object(1 to 9).string
As an example, if 7 is a candidate in arbitrary Blocs a and b, then
Bloc.Cel(a).Available_Candidates = "...7..." and
Bloc.Cel(b).Available_Candidates = "...7..."
Or another way of saying the same thing,
Bloc.Candidate(7).Available_Cels = "ab"

Rule 2 was therefore implemented by creating one more method, Bloc.Invert
When invoked from a "normal" Bloc, this populates an "inverted" Bloc and its contained Cels. Note that these Cels only have the inverted Bloc encapsulated in their Cel.Parent_Bloc collection. Each of these Cels represents a candidate number from the normal Bloc, and Available_Candidates for each Cel contains the set of Cels in the normal Bloc which contain each candidate. Bloc.Solve is then invoked for the inverted Bloc, and this works as previously stated. The final step is to call Bloc.Invert for the inverted Bloc. This inverts the data one more time and uses the results to re-populate the original normal Bloc.

Phew, This is going to be a massive post.

The final step (or so I thought) was to write a wrapper to instantiate all of the Cels (90) and Blocs (28), initialize all the attributes, set starting values for defined Cels (i.e. set up a "puzzle"), then iteratively invoke the Solve and Invert methods for each Bloc until either the puzzle has been solved or an impasse reached.

Unfortunately, there are at least three more rules. The first of these (now implemented using two additional methods and a few new attributes in Bloc, another two helper functions in the wrapper, and 9 additional instances of Bloc) is that if a candidate only appears in 2 or 3 Cels of one Bloc (e.g. a column), and those Cels are fully contained within an overlapping Bloc of a different type (e.g. a minigrid), then that candidate may be removed from all other Cels in the second Bloc. The other two rules that I am aware of are generically called X-wing and Swordfish. My belief is that these are actually different orders of the same rule. I may get around to proving that (and implementing it) if puzzles requiring this approach start appearing in The Times.

So what is the end result of this toil? I now have a logic based solver which runs to about 250 lines of structured code (including declarations), uses no unnecessary storage, is elegant in its simplicity, and can solve any well-formed puzzle in well under 1 second. However, I'm always on the lookout for new ways of doing this sort of thing, so if other people have different approaches, let's hear about them.

[simes]

...a helicopter to get to the summit of Everest.

That's pretty hard - they can't fly that high!

Edit: Oh yes they can...

[scrose]

...a helicopter to get to the summit of Everest.

That's pretty hard - they can't fly that high!

I thought the same thing, but it turns out that the altitude record is much higher than Everest.

[scrose]

...a helicopter to get to the summit of Everest.

That's pretty hard - they can't fly that high!

I thought the same thing, but it turns out that the altitude record is much higher than Everest.

However, I'm always on the lookout for new ways of doing this sort of thing, so if other people have different approaches, let's hear about them.

Getting back on topic, this thread has been discussing solving algorithms over the past few days. You could also check out the programmers' forum.

[Rocco]

With all due respect...
http://www.helis.com/news/1999/lamay30.htm
As Everest is only a paltry 8850 metres high, you could theoretically parachute down to the peak from this thing...

[Rocco]

[off topic (but funny) stuff]

Getting back on topic, this thread has been discussing solving algorithms over the past few days. You could also check out the programmers' forum.

Thanks for this, I looked at those previously. I felt it was worth starting a new topic as there didn't seem to be a lot of discussion about the use of objects and related data structures. Hope that's not out of order.

[scrose]

As Everest is only a paltry 8850 metres high, you could theoretically parachute down to the peak from this thing...

Getting back off topic: Theoretically, yes, but because the air is so thin, to generate enough drag you would need a gigantic parachute if you planned on opening it above 8900m -- presuming you wanted to survive the landing.

Hope that's not out of order.

Definitely not! I was only recommending them in case you hadn't seen them already.