Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Unravelling Braids

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Thu Apr 27, 2006 5:34 pm    Post subject: Unravelling Braids Reply with quote

Hi Ruud, I'm giving you a return vist!

I thought I'd try your list of problems to test the braid analysis concept out. (http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=17&post=4155#POST4155 ) . After doing the simple stuff with singles and box/line reductions, No 28 gave in immediately!

It may have a higher utility value than I first thought.

DavidPB
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Apr 27, 2006 11:52 pm    Post subject: Reply with quote

Hi David.

welcome aboard this forum!

When I first quickly read your post, I thought you had reinvented Sherlocking, but on second inspection, this is certainly a new approach.

You should try to rephrase your explanation into a set of definitions and rules, followed by the examples. This gives the programmers a chance to build it into their solvers and give you a quick result on yield figures. The technique does not look difficult.

It is truly amazing that more than a year after these forums started, new techniques are discovered these days. I'm also following this thread on the player's forum: http://www.sudoku.com/forums/viewtopic.php?t=3967
Quote:
I thought I'd try your list of problems to test the braid analysis concept out.

Did you use my benchmark list? I did not number the puzzles in there. Which one gave this quick result?

cheers, Ruud.
Back to top
View user's profile Send private message Visit poster's website
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Fri Apr 28, 2006 8:43 am    Post subject: Reply with quote

Ruud, Thanks for your reply. I am delighted that I seem to have found something new, because I always thought I was probably re-inventing the wheel.

For readers who have not followed the link, my braiding analysis method looks for patterns in the candidate lists for the 9 box/line intersections in a tier or stack of boxes. It then checks to see if the distribution of the candidates in the individual cells allows any of them to be eliminated.

On your Sudoku.net site on Wednesday I found a list of 30 or so problems which needed algorithms to be added to your program to avoid having to do them by guesswork, and that is where I got my example to test. However, it appears that you have edited your site because I can't find them now, so I presume they were all rather old!

I take to heart what your suggestion about improving the description, but I originally thought someone was going to give me a name for what I was doing! I will give it a go. David
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Apr 28, 2006 9:36 am    Post subject: Traveling Pairs and Triples Reply with quote

Hi David,
You might find Traveling Pairs and Triples on the Players' Forum interesting.
Ron
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Fri Apr 28, 2006 10:22 am    Post subject: Reply with quote

Thanks a lot Ron,
Yep, it's the same concept, but I take the analysis further on to see what deductions I can wring out of it (I think).

I couldn't believe that no-one had made this discovery before!

David
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Apr 28, 2006 11:55 am    Post subject: Reply with quote

dpbobelisk wrote:
I take the analysis further on to see what deductions I can wring out of it (I think).

The equivalence of "Traveling Pairs and Triples" with line-box interactions (see aeb's post here) seems correct to me. Do you think your technique does more eliminations than line-box interactions?


Last edited by rkral on Fri Apr 28, 2006 2:53 pm; edited 1 time in total
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Fri Apr 28, 2006 1:19 pm    Post subject: Reply with quote

rkral,
Thanks for the extra lead which I have quickly read. I think that in many cases my braid analysis gives no more information that box/line interactions, but sometimes it can.

I think I was lucky with my first trial where it gave quite a large extra payback, but I'm not sure how frequently the system will score. I do it semi-automatically, using a spreadsheet to produce the candidate lists etc. and then take on manually from there, so testing is slow.

It seems that it is a technique that might only give good results when the information to hand is correctly dispersed for it, very early on there is usually little for it to go on, so no answers, and late on all it produces is stale news!

This is why I came to this forum. If someone can code it and plug it into their solver, we can gauge its usefulness.

I am trying to describe it better as Ruud asked, to make it easier to code up, so watch this space. In the meantime go to
[url]http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=17&post=4155#POST4155[/url] and see what you think.

David
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Mon May 22, 2006 4:00 pm    Post subject: New Description Reply with quote

Hi again Ruud & Ron,

Just dropping by to keep my promise to you.

It's taken some work, but I've done a new write up on Braid Analysis which I have posted here http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=29&post=4735#POST4735.

Ruud, I don't think it will be that easy to code up.

Ron, It's a pity that MrHamilton chose such a poor example for his 'Travelling Pairs' posting. With a better one his ideas would have got more support I'm sure.

Since I first wrote I have been using equivalence marks in conjunction with the braid analysis (explained in the write up) which increases its utility no end, but it still is a lot of effort and probably best kept well down the list of things to try next!
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue May 23, 2006 2:16 am    Post subject: Reply with quote

Hi David,

this must be one of those techniques where either you see it, or you don't. I still don't see it. But with limited time and lots of puzzles to deliver, I have to read very fast.

I will wait for the illustrated version and try again. Maybe then it clicks.

cheers,
Ruud.
Back to top
View user's profile Send private message Visit poster's website
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Fri May 26, 2006 1:06 am    Post subject: Illustrated version Reply with quote

[quote="Ruud"]Hi David,

I will wait for the illustrated version and try again. Maybe then it clicks.

Ruud.[/quote]


Ruud, its now ready for your quick reading talents at http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=29&post=4826#POST4826

Cheers, David
Back to top
View user's profile Send private message
The Ostrich

Joined: 20 Apr 2006
Posts: 49
:

Items
PostPosted: Mon May 29, 2006 9:59 pm    Post subject: Reply with quote

My god. I don't understand word 1 of this. Maybe I'm stupid. What is the technique supposed to do? I assume that it is some sort of candidate eliminator, but can't you give a practical example of an elimination that it performs - basically show a candidate that you can remove using the technique, and then explain the logic at a low-level?
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Mon May 29, 2006 10:34 pm    Post subject: Reply with quote

The Ostrich: There are two postings on the thread given in the two links above. The opening one is a text only description giving a spec that may be helpful for any programmer trying to code the system.

The second one, which is illustated with examples, shows a few of the deductions that can be made when used on puzzles which have been previously rated as unsolvable without trial-and-error methods.

I'm just wondering if you missed the second one.

If not, it's reasonably complex idea, and I'm sorry if my writing skills fail to do it justice in your eyes.
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Wed May 31, 2006 10:46 am    Post subject: Reply with quote

Ruud, Sudo Cue Download.

I don't really want to use anything more than my spreadsheets for solving puzzles, but I thought as you are taking up the braiding idea, I had better download your Sudo Cue.

Opening your downloaded installation file I get prompted to download .NET framework version 1.1.4322 which I reluctantly agree to, and then get taken to http://msdn.microsoft.com/netframework/downloads/updates/default.aspx which is stuffed with download options none of which has that number. Which shortcut do I follow for Windows XP please?
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed May 31, 2006 11:16 am    Post subject: Reply with quote

Hi David.

That is the most stupid thing Microsoft has ever done. Even I get confused by the options. I get this question so many times, so I better put a note on the download page.

Anyway,

Take this option:

.NET Framework Version 2.0 Redistributable Package
Download x86 version

and you'll be fine

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron