BUG-Lite vs. BUG+N

Advanced methods and approaches for solving Sudoku puzzles

Re: BUG-Lite vs. BUG+N

Postby RSW » Sat Jan 26, 2019 2:25 pm

I was just looking at SpAce's BUG+23 solution to the Nov. 6, 2018 puzzle. Coincidentally, I'd been wondering just how far you could take the BUG+N technique. Since I'd just managed to get my BUG algorithm working, I tried it on that puzzle, and using only the BUG routine plus basic techniques, it came up with the same solution. So, I decided to see how it would make out with other puzzles. I've now tested it with all the puzzles from Jan. 18 to Jan. 25, and it's able to solve them all using only BUG+N and basic techniques. The most extreme is the Jan. 22, which is a BUG+60 :D

Here's the BUG+60 solution to the Jan. 22 puzzle.
Code: Select all
 +---+---+---+
 |..3|.56|...|
 |..7|...|..6|
 |.42|..3|.1.|
 +---+---+---+
 |...|89.|...|
 |.9.|4..|.3.|
 |..5|...|..2|
 +---+---+---+
 |.6.|...|...|
 |...|32.|..1|
 |..1|..9|..5|
 +---+---+---+

Basic steps gives:
Code: Select all
+--------------+----------------+-------------------+
| 189  18  3   | 1279 5    6    | 2478   2478  4789 |
| 1589 158 7   | 129  148  148  | 3      28    6    |
| 6    4   2   | 79   78   3    | 5      1     789  |
+--------------+----------------+-------------------+
| 147  3   46  | 8    9    2    | 1467   5     47   |
| 2    9   68  | 4    167  5    | 1678   3     78   |
| 1478 178 5   | 167  3    17   | 146789 46789 2    |
+--------------+----------------+-------------------+
| 478  6   489 | 5    1478 1478 | 24789  24789 3    |
| 4578 578 489 | 3    2    478  | 46789  46789 1    |
| 3    2   1   | 67   4678 9    | 478    478   5    |
+--------------+----------------+-------------------+

BUG+60, Cells: r1c1 r1c4 r1c7 r1c8 r1c9 r2c1 r2c2 r2c4 r2c5 r2c6 r3c9 r4c1 r4c7 r5c5 r5c7 r6c1 r6c2 r6c4 r6c7 r6c8 r7c1 r7c3 r7c5 r7c6 r7c7 r7c8 r8c1 r8c2 r8c3 r8c6 r8c7 r8c8 r9c5 r9c7 r9c8

You'll have to excuse the notation here. This is generated by the solver program. It's gradually getting closer to being something that could be parsed into Eureka. There are 9 eliminations:

? r3c9=7 > (r5c9=8 > r5c3≠8) & (r4c9=4 > r4c3=6 > r5c3≠6) > r5c3=X ∴ r3c9≠7
? r4c7=7 > (r5c9=8 > r5c3≠8) & (r4c9=4 > r4c3=6 > r5c3≠6) > r5c3=X ∴ r4c7≠7
? r5c5=7 > (r6c4≠7) & (r6c6=1 > r6c4≠1) & (r3c5=8 > r3c9=9 > r3c4=7 > r9c4=6 > r6c4≠6) > r6c4=X ∴ r5c5≠7
? r5c7=8 > (r5c9=7 > r4c9≠7) & (r5c3=6 > r4c3=4 > r4c9≠4) > r4c9=X ∴ r5c7≠8
? r6c4=1 > (r6c2≠1) & (r6c6=7 > r6c2≠7) & (r5c5=6 > r5c3=8 > r6c2≠8) > r6c2=X ∴ r6c4≠1
? r6c7=4 > (r4c9=7 > r5c7≠7) & (r4c9=7 > r5c9=8 > r5c3=6 > r5c7≠6) & (r4c9=7 > r5c9=8 > r5c3=6 > r5c5=1 > r5c7≠1) > r5c7=X ∴ r6c7≠4
? r6c7=6 > (r6c4=7 > r6c2≠7) & (r6c4=7 > r6c6=1 > r6c2≠1) & (r6c4=7 > r6c6=1 > r5c5=6 > r5c3=8 > r6c2≠8) > r6c2=X ∴ r6c7≠6
? r7c5=7 > (r3c5=8 > r3c9=9 > r3c4≠9) & (r9c4=6 > r6c4=7 > r3c4≠7) > r3c4=X ∴ r7c5≠7
? r8c6=7 > (r6c6=1 > r6c2≠1) & (r9c4=6 > r6c4=7 > r6c2≠7) & (r6c6=1 > r5c5=6 > r5c3=8 > r6c2≠8) > r6c2=X ∴ r8c6≠7

This is the result. (None of the other 51 BUG candidates lead to any eliminations.) Then just basic techniques to the end.
Code: Select all
+--------------+----------------+------------------+
| 189  18  3   | 1279 5    6    | 2478  2478  4789 |
| 1589 158 7   | 129  148  148  | 3     28    6    |
| 6    4   2   | 79   78   3    | 5     1     89   |
+--------------+----------------+------------------+
| 147  3   46  | 8    9    2    | 146   5     47   |
| 2    9   68  | 4    16   5    | 167   3     78   |
| 1478 178 5   | 67   3    17   | 1789  46789 2    |
+--------------+----------------+------------------+
| 478  6   489 | 5    148  1478 | 24789 24789 3    |
| 4578 578 489 | 3    2    48   | 46789 46789 1    |
| 3    2   1   | 67   4678 9    | 478   478   5    |
+--------------+----------------+------------------+

I'm certainly not suggesting this to be used on a regular basis, but it's interesting to see the extreme to which it can be taken. However, the chaining technique that is used to do the eliminations can likely be generalized into a non-BUG technique. That's my next little project.

Edit:
Explanation of the notation. This:
? r3c9=7 > (r5c9=8 > r5c3≠8) & (r4c9=4 > r4c3=6 > r5c3≠6) > r5c3=X ∴ r3c9≠7
Translates to this:
If r3c9=7, then this implies (r5c9=8 which implies r5c3≠8) and also implies (r4c9=4 which implies r4c3=6 which implies r5c3≠6) which results in no valid candidates for r5c3. Therefore r3c9≠7, and candidate 7 is eliminated from r3c9.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: BUG-Lite vs. BUG+N

Postby SpAce » Sat Jan 26, 2019 5:42 pm

RSW wrote:I was just looking at SpAce's BUG+23 solution to the Nov. 6, 2018 puzzle. Coincidentally, I'd been wondering just how far you could take the BUG+N technique. Since I'd just managed to get my BUG algorithm working, I tried it on that puzzle, and using only the BUG routine plus basic techniques, it came up with the same solution. So, I decided to see how it would make out with other puzzles. I've now tested it with all the puzzles from Jan. 18 to Jan. 25, and it's able to solve them all using only BUG+N and basic techniques. The most extreme is the Jan. 22, which is a BUG+60 :D

A commendable effort. I don't see much value as a practical solving method for those extreme cases (including my own BUG+23, of course, which was meant more or less as a joke), but more tests might produce interesting statistics about the prevalence of theoretical BUG possibilities. Could you produce grid diagrams for those eight tested puzzles? It's kind of hard to make any determinations without visualizing the BUGs, and I don't feel like doing it by hand. Similar to this (where the +candidates are the +N extras):

Code: Select all
.----------------.-------------------.---------------.
| 5  1     79+4  | 69+47   2   47    | 46+9  3     8 |
| 8  69+4  47+9  | 37+469  5   13+47 | 49+6  16+9  2 |
| 2  46+9  3     | 89+46   16  48+1  | 5     19+6  7 |
:----------------+-------------------+---------------:
| 1  3     2     | 5       4   9     | 8     7     6 |
| 9  8     6     | 27      3   27    | 1     5     4 |
| 4  7     5     | 1       8   6     | 3     2     9 |
:----------------+-------------------+---------------:
| 7  49    18+49 | 48+6    16  5     | 2     69    3 |
| 6  2     14    | 34      9   13+4  | 7     8     5 |
| 3  5     89    | 26+8    7   28    | 69    4     1 |
'----------------'-------------------'---------------'

November 6, 2018: BUG+23

PS. You do realize that there's a crucial difference between your method and my BUG+23? Despite its appearance, mine is a single verity move which works exactly like its smaller counterparts (BUG+1 being the simplest case). Yours has multiple contradiction moves eliminating as many candidates, which makes it practically no different from simple T&E (except that the tested candidates are apparently picked from the set of BUG extras). I don't really understand why you even need the BUG for that, and I definitely wouldn't call it a BUG+N move. The core of the BUG logic is in the derived strong inference set between the +N candidates, but I don't see how your method utilizes that at all -- at least in the given example. Or perhaps I just didn't quite get it.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby SpAce » Sat Jan 26, 2019 7:31 pm

RSW wrote:I've now tested it with all the puzzles from Jan. 18 to Jan. 25, and it's able to solve them all using only BUG+N and basic techniques.

How exactly is that possible? I just took a look at Jan 25, and there's no BUG+N (I haven't looked at the others yet). Are you sure you know the definition of a BUG? If all the +candidates are removed, a BUG grid contains only bivalue cells with candidates that are bilocation-paired in all directions (row, col, box). Thus everything is paired, which is why such a grid would have exactly two solutions. There's no such possibility in the Jan 25 puzzle:

Code: Select all
.-----------------.----------------.--------------.
|  49    5  49    | 23   23    7   | 6    1   8   |
|  6     8  3     | 4    1     5   | 9    2   7   |
|  27    1  27    | 9    8     6   | 4    3   5   |
:-----------------+----------------+--------------:
|  235   6  8     | 1    25    23  | 7    4   9   |
|  1235  4  2(5)  | 7    2569  239 | 12   8   126 |
|  129   7  29    | 26   4     8   | 3    5   126 |
:-----------------+----------------+--------------:
| (57)   2  6     | 3(5) 39    1   | 8    79  4   |
| (45)   9  1     | 8    7     24  | 2(5) 6   3   |
|  8     3  4(5)7 | 256  269   249 | 125  79  12  |
'-----------------'----------------'--------------'

Look at the three 5s in box 7. For a BUG to exist, exactly one of them should be removed (i.e. it's a +candidate) to pair the 5s in the box, but you can't remove any of them without breaking the BUG-potential elsewhere. 5r78c1 are both in bivalue cells and also bilocation-paired row-wise, so they're locked. 5r9c3 is bilocation-paired column-wise, so it's locked too. Thus none of them can be a plus-candidate, which means that there's no BUG-potential.

I'm suspecting this might be the case with some of the other puzzles you tested as well (except Jan 18, because I used a BUG+3 there myself). Like I said, I don't feel like checking them all out by hand, so it would be easier if you provided the grid diagrams of what you considered to be BUG+Ns.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby SpAce » Sun Jan 27, 2019 12:07 am

No word from you, so I took a look at the rest. Here's my verdict:

Jan 25: no BUG
Jan 24: BUG+22
Jan 23: no BUG
Jan 22: no BUG
Jan 21: no BUG
Jan 20: two BUGs (edited; was: "no BUG (I think -- a weird case, though)")
Jan 19: BUG+10
Jan 18: BUG+3

So, 3/8 actual (usable) BUGs in that list. No BUG+60, sorry. I think your algorithm needs a bit more work. (The fact that it solved those puzzles just means that the contradiction chains work, but why wouldn't they -- it's just normal T&E and you've had that implemented for a long time. Any BUG-related logic in the algorithm must be flawed, though, because it can't even tell BUGs from no-BUGs. It just doesn't produce errors because you're not really using any recognizable BUG-logic anyway. Or so it seems to me.)
Last edited by SpAce on Tue Jan 29, 2019 4:33 am, edited 1 time in total.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby RSW » Sun Jan 27, 2019 3:43 am

I was tied up all day, so I just saw your replies now. When I have time, I'll add some additional diagnostic code to my program so that it will give better details of what it considers to be the BUG candidates and the +N candidates.

The program now produces grid diagrams as shown in my previous post, but without any annotations. So it's currently of limited value. It shouldn't be too difficult to have it add annotations, and I'll do that when I find the time.

SpAce wrote:Are you sure you know the definition of a BUG?

Good question. Obviously, a BUG+1 is easy to ID and to solve. However, the reason why I started this thread in the first place is because in any of the explanations that I've come across, things start to become very vague for N>1. Again, I think that in the case of a BUG+2 or +3 it's clear that at least one of the +N candidates must be true to prevent a deadly pattern. The question then is how do you determine which of the +N candidates is the correct one. This is where the descriptions seem to get very vague. From what I've seen, these candidates are just tested with some simple chain technique, which is really just a restricted T&E. If there's some more direct logic involved, then I haven't found any explanation of it. Certainly not in general terms.

It's also worth asking whether my solver program knows the definition of a BUG. Certainly, its definition is extremely broad at the moment, which is no doubt why it claimed to find all of BUG solutions for these puzzles. I didn't back check them. I just quickly ran them and posted the results. It is interesting that it was able to take these detected patterns and then solve the puzzle. Even though these may not be true BUGs, it appears that the solve logic is still valid. Either that, or it's been extremely lucky. For most of the more advanced techniques, the solver does a fast pre-screen of possible cells in order to save time, and then applies additional logic tests to the subset to do a complete determination. Obviously, there's been some logic missing in the final testing.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: BUG-Lite vs. BUG+N

Postby SpAce » Sun Jan 27, 2019 7:32 am

RSW wrote:When I have time, I'll add some additional diagnostic code to my program so that it will give better details of what it considers to be the BUG candidates and the +N candidates.

Good idea. I would have started with that before coding anything else. How did you expect to verify the results of your code in the first place?

The program now produces grid diagrams as shown in my previous post, but without any annotations. So it's currently of limited value. It shouldn't be too difficult to have it add annotations, and I'll do that when I find the time.

You can add those manually too, you know. It's an excellent idea to have your program eventually produce that stuff in a presentable form, but in the meantime you could just edit it yourself. It's probably quicker. (Or do you have a principle that you can't manually touch anything your program outputs? This is related to the discussion in the Puzzles section as well.)

SpAce wrote:Are you sure you know the definition of a BUG?

Good question. Obviously, a BUG+1 is easy to ID and to solve. ...

I must guess the answer is no, then. Fixing that is where you need to start with BUGs. How you actually use them for solving has meaning only after you know for sure when you have a valid BUG+N situation and when you don't.

However, the reason why I started this thread in the first place is because in any of the explanations that I've come across, things start to become very vague for N>1.

You only had a vague understanding, yet you thought it was a good idea to code a generic solver for BUG+N of any size N and confidently post its results? You're much braver than I am, that's for sure :)

Did you read the BUG+3 thread I linked at the very beginning of this discussion? Not sure what you consider vague, but there should be pretty detailed answers to your questions. You just probably lack some prerequisites to understand it all. I'd recommend you started gathering those by studying basic chaining, i.e. AICs, first. They're easy because they only have two end-points to worry about. If you understand them, then you can easily understand how BUG+2 (and some special cases of larger BUGs) work. Bigger than that and you need Kraken (i.e. Forcing Chain; verity type) logic, which is more complicated but also pretty easy to understand if you know your AICs (the same idea but with multiple end-points).

If you don't have that stuff under your belt, you really can't expect to understand how larger BUGs are actually used, and if you don't understand it, you can't expect to be able to code it correctly either. It's probably not trivial to code even if you do.

Again, I think that in the case of a BUG+2 or +3 it's clear that at least one of the +N candidates must be true to prevent a deadly pattern.

You got that exactly right. It's the same for any BUG+N, and that's all there is to it. Really. You just have to know how to use that knowledge, but for that, read the previous paragraph. There are plenty of good sources that explain those prerequisites in detail.

The question then is how do you determine which of the +N candidates is the correct one. This is where the descriptions seem to get very vague.

Because it's the wrong question. Read (again) what I wrote here. Yogi had very similar problems with the BUG stuff but he eventually got it, I think. I'm not about to repeat myself, so read it again until you get it too, or find better sources if you can. More than anything, study those mentioned prerequisites, because I'm pretty sure that's where the real problem is. It's also a must for understanding and posting one-stepper solutions in the Puzzles section. Once you master those, then this stuff should be self-explanatory.

From what I've seen, these candidates are just tested with some simple chain technique, which is really just a restricted T&E. If there's some more direct logic involved, then I haven't found any explanation of it. Certainly not in general terms.

Dunno what you mean by "general terms", but otherwise you've certainly found it. You just either haven't read or understood it. It's got nothing to do with T&E, but because you thought it did, that's how you implemented it. As a result, your BUG logic now has everything to do with T&E (which looks for contradictions) and little to do with BUGs (which are typically used to produce verities). AICs and Krakens produce verities, not contradictions. A very important distinction.

It's also worth asking whether my solver program knows the definition of a BUG.

How could it if you don't?

I didn't back check them. I just quickly ran them and posted the results.

So it seems. You have surprising confidence in the results of untested software implementing poorly understood concepts.

It is interesting that it was able to take these detected patterns and then solve the puzzle. Even though these may not be true BUGs, it appears that the solve logic is still valid.

Yes, the solve logic for your contradiction chains/nets seems to be fine (probably), but it has little to do with BUGs or other solving methods typically preferred by humans. Still, you can certainly build on that foundation once you understand other types of chains better. (Edit: I just took a closer look at your chains which turned out to be mostly nets, actually. That's something else to think about, as linear chains are preferred whenever possible.)

Added. I can see one possibility of using your approach to solve BUGs in multiple steps, but it's not very elegant or efficient. It's also explained in the BUG+3 thread here as the two-stepper solution. In other words, if you can't form a single AIC or Kraken to use a BUG+N with a large N directly, then you can first eliminate some of those plus-candidates to make the N smaller. Your T&E contradiction chains/nets would surely do the trick, but they're not very elegant, especially for presentation purposes. Also, unless you can reduce it all the way to BUG+1 (which is not always possible, of course, because the +N may contain several true candidates and you can obviously only eliminate false ones), you still need to know how to do the actual BUG-solving at the end (the principles are the same no matter the size of the +N).

For example, if you wanted to try that approach with the BUG+22 of Jan 24, you would need to eliminate 20 candidates to get to BUG+2 (it has two true +N, which you of course can't know beforehand) which is much simpler to solve but might still need an AIC (and does, but a very short one -- see next post). Of course that elimination process may solve the puzzle earlier by other means, but you get the idea. You also see that in the worst case scenario that kind of BUG-solving process would mean 20+1 steps, which obviously isn't very efficient for a puzzle that can be solved in one short non-BUG step. Thus it makes no practical sense to use such huge BUGs, no matter how you do it. The single-step Kraken approach (my way) may be more elegant, but not really more efficient except in the step-count department -- that's why my BUG+23 was certainly not meant as a practical solving example.

Note: From the previous observations one can conclude that a much more efficient way to use a BUG+N with a big N is to target anything but its plus-candidates. So, once you get your algorithm to recognize BUGs and their plus-candidates reliably, you should probably do the exact opposite of what you've been trying to get to a solution quickly. Instead of using the set of plus-candidates for T&E, use its complement. That should break the puzzle in no time.
Last edited by SpAce on Mon Jan 28, 2019 11:35 am, edited 1 time in total.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby SpAce » Sun Jan 27, 2019 10:15 pm

Here's a fun exercise for you. Let's assume that you have fixed your algorithm to recognize valid BUGs and their plus-candidates. Then you run it against the BUG+22 of the Jan 24 puzzle. Let's also assume that it can find all of the 20 valid eliminations among those plus-candidates (ignoring the last note in the previous post) and thus reduces the puzzle into this BUG+2:

Code: Select all
.--------------.------------.------------.
| 3     2   4  | 67  79  5  | 8   69  1  |
| 78    78  9  | 23  1   46 | 24  36  5  |
| 5     1   6  | 39  24  8  | 24  79  37 |
:--------------+------------+------------:
| 79    5   2  | 1   34  46 | 69  37  8  |
| 46    49  37 | 5   8   2  | 69  1   37 |
| 16    38  18 | 67  37  9  | 5   4   2  |
:--------------+------------+------------:
| 149   47  15 | 8   29  17 | 3   25  6  |
| 189   39  58 | 29  6   13 | 7   25  4  |
| 2     6   37 | 4   5   37 | 1   8   9  |
'--------------'------------'------------'

Note that it's still not solvable with basics, even after 20 eliminations! That's only logical because it's a BUG+N puzzle and eliminating only plus-candidates does not break it. With that revelation we can actually conclude that your current BUG algorithm -- if it were correctly implemented (i.e. it would test and eliminate those plus-candidates only, as you apparently had intended) -- would never solve any BUG puzzle completely. It would just reduce it to a smaller N. Since it did solve all of those eight puzzles to the end, it's just further proof that it's flawed (counter-intuitive, huh?). The reason it did solve them must have been that it unintentionally targeted non-plus-candidates (and non-BUG-puzzles too).

Question 1: Based on the grid, how do you verify that it's a BUG+2?
Question 2: Which candidates are the extras and how do you know?
Question 3: What is the easiest way to solve it from here?

Once you can answer those questions easily, then you have some hope of eventually working with bigger BUGs.
Last edited by SpAce on Mon Jan 28, 2019 11:48 am, edited 1 time in total.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby RSW » Mon Jan 28, 2019 11:45 am

Yes you're quite right that for some of those puzzles the detected BUG did not lead to an immediate solution. Sometimes it required some additional techniques such as box/line or naked subset exclusions. In some cases it resulted in a smaller BUG.

The Jan 24 puzzle is an interesting example. The program does indeed detect a BUG+22, without giving a complete solution at that point. However, it doesn't result in the same BUG+2 that you show. In fact, it doesn't result in a second BUG+N at all, unless I force the program to immediately run the BUG+N routine again without first checking for hidden singles (and also disabling some other logic).

The reason for the difference is that the solver's BUG+N routine actually results in 29 exclusions, rather than your expected 20. Yes, it seems impossible to have more than 22 exclusions from a BUG+22. The explanation is that after making a BUG related exclusion, a number of things may happen, all related to the fact that the puzzle's cell candidates change dynamically during many of the solving routines, including the BUG+N routine. For example, the solver may discover a hidden single which it processes immediately, rather than waiting until finishing all BUG exclusions. This is inherent in the way the solver handles exclusions. It's done on purpose, because processing singles is the fastest exclusion technique, and often avoids the need to continue searching for more complex patterns. Whenever an exclusion occurs, resulting in a cell's candidate count dropping to 1, that cell is solved and all intersecting cells' candidates are immediately re-evaluated. This can lead to an avalanche of exclusions. The inference chain algorithm may also discover a non BUG exclusion, as it processes the BUG candidates, and erroneously report it as a BUG exclusion. (At the moment, the inference chain routine doesn't back-check the exclusion to see if it was on the +N candidate list, but this should be an easy program change.) Regardless, the exclusions are all valid, even though they may not be in the set of +N candidates and therefore not part of the BUG+N. So, there's some programming work that could be done to report the non-BUG exclusions separately.

This is the grid at the point where the solver detects the BUG+22. (Sorry, still no automatic annotations.)
Code: Select all
+--------------+---------------+-----------+
| 3    2   4   | 679  79    5  | 8  679 1  |
| 78   78  9   | 236  1     46 | 24 36  5  |
| 5    1   6   | 2379 23479 8  | 24 379 37 |
+--------------+---------------+-----------+
| 679  5   2   | 1    347   46 | 69 37  8  |
| 469  49  37  | 5    8     2  | 69 1   37 |
| 1678 378 18  | 367  37    9  | 5  4   2  |
+--------------+---------------+-----------+
| 1479 479 15  | 8    29    17 | 3  25  6  |
| 189  389 158 | 29   6     13 | 7  25  4  |
| 2    6   37  | 4    5     37 | 1  8   9  |
+--------------+---------------+-----------+

And this is the grid, immediately following the 29 exclusions.
Code: Select all
+----------+-----------+-----------+
| 3  2  4  | 69 79  5  | 8  679 1  |
| 78 78 9  | 3  1   46 | 24 36  5  |
| 5  1  6  | 29 279 8  | 24 79  37 |
+----------+-----------+-----------+
| 7  5  2  | 1  4   46 | 69 37  8  |
| 49 49 37 | 5  8   2  | 69 1   37 |
| 16 8  18 | 7  37  9  | 5  4   2  |
+----------+-----------+-----------+
| 14 4  15 | 8  29  17 | 3  25  6  |
| 9  3  8  | 29 6   13 | 7  25  4  |
| 2  6  37 | 4  5   37 | 1  8   9  |
+----------+-----------+-----------+

Obviously this one isn't a BUG+2, because it's solvable as singles.

I'm not discounting the possibility that the solver may require some tweaks to the logic in order to handle large BUGs, but dealing with large BUGs is not that high on my list of priorities at the moment. My testing of the BUG routine on the daily puzzles was a just for fun spur of the moment thing, with no real intention of going anywhere with it. While finding a BUG+22 may be an amusing solution to a puzzle, I'd much rather develop the software to find simpler solutions. Fortunately, the inference chain algorithm that I've implemented is fast and seems to work very well. So, I'll be experimenting with that, and developing it to solve more general patterns.

For the BUG+2 that you posted, unfortunately I currently have no practical way to enter a partial solution grid into my solver. I could enter the fully solved cells as clues, but there's no easy way to set the candidate values of the unsolved cells exactly as shown. So, I'll have to leave it for the time being. Entry of partial solution grids is not a difficult feature to add. I'll just put it on my ever-growing to-do list. :)
I have a busy week, so I may not get back to this until next weekend.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: BUG-Lite vs. BUG+N

Postby SpAce » Mon Jan 28, 2019 11:53 am

Did you read my just-added note (two posts back)? Target the actual BUG-candidates, not plus-candidates, for much more efficient solving.

RSW wrote:For the BUG+2 that you posted, unfortunately I currently have no practical way to enter a partial solution grid into my solver. I could enter the fully solved cells as clues, but there's no easy way to set the candidate values of the unsolved cells exactly as shown. So, I'll have to leave it for the time being. Entry of partial solution grids is not a difficult feature to add.

And you missed the point, once again. It was for YOU to answer those simple questions, not your program. If you can't answer them, how can you expect to write a correct and efficient program that produces elegant solutions for human consumption? Beats me, or maybe the latter part is not your goal at all. Seems that you refuse to do anything manually. Somehow I doubt that's good for the development of either your own skills or those of your program. Well, none of my business anyway, and perhaps you'll prove me wrong.

"Don’t be too proud of this technological terror you’ve constructed. The ability to destroy a planet is insignificant next to the power of the Force." ;)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby RSW » Mon Jan 28, 2019 12:12 pm

Sorry, no. I just saw your post about the Jan 24 puzzle and replied to that. I'll go back and review your other comments later.

Just a quick answer though: The BUG+N detector determines the list of +N candidates by first finding a cell's BUG candidates, and then comparing them against the cell's complete set of candidates for differences, to get the +N candidates.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: BUG-Lite vs. BUG+N

Postby RSW » Mon Jan 28, 2019 3:40 pm

SpAce wrote:Did you read my just-added note (two posts back)? Target the actual BUG-candidates, not plus-candidates, for much more efficient solving.

RSW wrote:For the BUG+2 that you posted, unfortunately I currently have no practical way to enter a partial solution grid into my solver. I could enter the fully solved cells as clues, but there's no easy way to set the candidate values of the unsolved cells exactly as shown. So, I'll have to leave it for the time being. Entry of partial solution grids is not a difficult feature to add.

And you missed the point, once again. It was for YOU to answer those simple questions, not your program. If you can't answer them, how can you expect to write a correct and efficient program that produces elegant solutions for human consumption? Beats me, or maybe the latter part is not your goal at all. Seems that you refuse to do anything manually. Somehow I doubt that's good for the development of either your own skills or those of your program. Well, none of my business anyway, and perhaps you'll prove me wrong.

"Don’t be too proud of this technological terror you’ve constructed. The ability to destroy a planet is insignificant next to the power of the Force." ;)

I guess I'll keep missing the point again and again, if you keep going back and changing your posts after I reply to them.
RSW
 
Posts: 611
Joined: 01 December 2018
Location: Western Canada

Re: BUG-Lite vs. BUG+N

Postby SpAce » Tue Jan 29, 2019 5:53 am

RSW wrote:I guess I'll keep missing the point again and again, if you keep going back and changing your posts after I reply to them.

Lol. That'd make some sense if I'd changed something relating to the point I mentioned. You're almost as good as finding excuses as moving goal posts:

dealing with large BUGs is not that high on my list of priorities at the moment. My testing of the BUG routine on the daily puzzles was a just for fun spur of the moment thing, with no real intention of going anywhere with it. While finding a BUG+22 may be an amusing solution to a puzzle, I'd much rather develop the software to find simpler solutions.

You seemed pretty enthusiastic about it until I pointed out the error of your ways. But hey, if you don't like free advice -- which you obviously need -- be my my guest. I have no vested interest in helping someone who doesn't understand the value of what he's getting.

The inference chain algorithm may also discover a non BUG exclusion, as it processes the BUG candidates, and erroneously report it as a BUG exclusion. (At the moment, the inference chain routine doesn't back-check the exclusion to see if it was on the +N candidate list, but this should be an easy program change.) Regardless, the exclusions are all valid, even though they may not be in the set of +N candidates and therefore not part of the BUG+N. So, there's some programming work that could be done to report the non-BUG exclusions separately.

Exactly as I suspected. You knew that from the get-go but didn't deem it necessary to tell? I don't think those revelations match your opening claims very well:

Since I'd just managed to get my BUG algorithm working, I tried it on that puzzle, and using only the BUG routine plus basic techniques, it came up with the same solution. So, I decided to see how it would make out with other puzzles. I've now tested it with all the puzzles from Jan. 18 to Jan. 25, and it's able to solve them all using only BUG+N and basic techniques [emphasis added]. The most extreme is the Jan. 22, which is a BUG+60 :D

You kind of skipped the part that your BUG+N algorithm includes, well, kind of everything. Still, it seems that I remote-(de)bugged your program pretty well anyhow. I'm quite happy I don't have to actually do it, because it seems so chaotic that even you have trouble knowing what it's doing. (My diagnosis is that it's suffering from a case of premature optimization, among other things.)

Anyway, the only question remaining is whether it actually detects valid BUG+Ns or not, and that remains open because you can't or won't produce useful grid diagrams indicating the plus-candidates. The fact that you originally talked about BUG+60 situations doesn't give high confidence in that ability either. It's still a total mystery how your program detects BUG+Ns and determines the plus-candidates. And no, this doesn't answer that question at all:

Just a quick answer though: The BUG+N detector determines the list of +N candidates by first finding a cell's BUG candidates, and then comparing them against the cell's complete set of candidates for differences, to get the +N candidates.

I have no idea what you're talking about. But that wasn't even what I asked. I asked how YOU would recognize and verify a BUG and determine the plus-candidates, and gave a very trivial example to try that on. Your answer would have given some indication whether your program's algorithm has even a chance to work or not (unless you've created an awesome AI that can figure things out on its own). That was the point you missed (this time).
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: BUG-Lite vs. BUG+N

Postby SpAce » Fri Feb 01, 2019 2:30 am

Well, it wasn't all for nothing as your post spawned an interesting side discussion about multi-BUGs. Dunno about you, but I sure learned something here and there. Thanks for that (and I mean it)! :)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Previous

Return to Advanced solving techniques