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   

Bit Based Sudoku Solver (BB_Sudoku) V0.5
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
JasonLion

Joined: 16 Nov 2008
Posts: 61
:
Location: Silver Spring, MD

Items
PostPosted: Tue Jan 27, 2009 1:40 am    Post subject: Reply with quote

The greatest depth I have seen is in the high 30s, so I set the max to 40 and it has solved every puzzle I have.
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Tue Jan 27, 2009 2:35 am    Post subject: Reply with quote

Now I'm confused - the array G[] is only sized for 32 elements. Did you enlarge G[] to 40, as well?

Seems Pidx (which Max Depth is compared with), would go out of bounds of the G[] array at 40, otherwise. Or is Pidx constrained?

I'm being so particular because I have billions of grids to be tested, and more piling up 24/7.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Jan 27, 2009 3:08 am    Post subject: Reply with quote

Greetings,

People have found a couple issues with my solver that I have released fixes for. Version 05b (Nov 08) increased the guesses to 62. Version 05c (Jan 09) also fixed a problem with sending near complete puzzles into the solver.

Here is the latest link:
http://www.tttarabians.com/sudoku/bb_sudoku_v05c.zip

That is the last version I released, though I have posted preliminary code for the generic fishy method and the 1 step commonality. V06 also included a normalizer and puzzle generator which I was never real happy with, so I have not released the code. It also included a rating based on what methods are needed to solve the puzzle, but only categorizes the puzzles into 4 categories.

Version 07 does killer sudoku and the greater and less than puzzles. I am also in the process of adding jigsaws, diagonals, windows, larger grids (all really just the same code). Of course, this is just in my spare time, so no timeline for when it will be done.

brit
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Tue Jan 27, 2009 8:53 pm    Post subject: Reply with quote

Thanks for the updated program, Brit. That does the trick for my obstinate grids (so far).

In the help it mentions "-m" as an option, but I didn't see any explanation of what "-m" does.

Have you received any feedback on your revised algorithm, yet? I haven't examined it in detail yet, but your description made it sound like something perhaps new and different.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Jan 27, 2009 9:42 pm    Post subject: Reply with quote

Greetings,

Someone once said it is much easier to code then to document. This is very true.

The -m options allow you to turn on and off individual solving methods. For example, it you wish to study the timing differences when using subsets, and not using subsets, you would use these two commands:

bb_sudoku_v05 -ms+ < t.txt (this uses subset checking)
bb_sudoku_v05 -ms- < t.txt (this turns off subset checking)

If you want to see if a puzzle can be solved without guessing and only using naked and hidden singles, you would use

bb_sudoku_v05 -mg- -ml- < t.txt (turns off guessing and locked candidates)

I see I did not update the help text for the -mg commands. sorry.


For the 1 step commonality, first, I can not really determine if it is unique or different from anyone else's. I rarely look at how other people have done their code since the challenge and enjoyment for me is developing my own ideas. I do accept suggestions for improvement, but the basic ideas for all these are my own, even if other peoples did it the same way before me. I believe the DLX code was the only other solver I have actually examined in detail. When I needed improvement, I went to a guide for solving by hand for suggestions, rather than look at other peoples code.

Also, I would not really call the 1 step commonality new, but rather a generalization of many old techniques. It works great for programming solutions, but is difficult for hand solving. I basically use it to give a general rating (if I need to use the 1 step it is rated hard, if I need to use the 2 step it is rated insane). I have not found a puzzle that needed more then that.

brit
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Jan 28, 2009 3:21 am    Post subject: Reply with quote

Thanks, Brit!

I'm setting aside some time to study your algorithm, as well as DLX/Algorithm X.

Very Cool
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sat Jan 31, 2009 10:15 am    Post subject: Reply with quote

Hi, commendable work on your program

gsf wrote:
CAVEATS
This is a puzzle and algorithm analysis program.
Look elsewhere for interactive gaming and GUIs.
Its easier to solve than to generate,
and easier to generate than to rate,
and much easier to code than to document.

hope you dont mind....but ive sent you a batch of puzzles.

perhaps you could indicate which is the best method / command for rating such tricky puzzles.

comparing to -q2 and suexratt and champagne's methods may well prove interesting

here is another one for you to look at
Code:
....3.7.5.8.4...9.5.........2..48..........2.6.92...........1...6.9...4...1..7..3   #colz001
5.362 msec
using bb_sudoku_v05c -ms+ < test0.txt [on my machine]
Code:
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....#golden nuggett
4.646 msec

unfortunatly the isomorhpic variation is disapointing with this puzzle......

perhaps more consistant results may be obtained with an average value over several thousand isomorphs - althoug this wasnt enough with suexratt !

C
Back to top
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Sun Feb 01, 2009 12:28 pm    Post subject: Reply with quote

ok,I update my website.
www.eightclock.com
the wet site's speed is a bit slow,you can download my new version.
Back to top
View user's profile Send private message Send e-mail
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Feb 02, 2009 1:53 am    Post subject: Reply with quote

Greetings,

on the matter of rating, I completely agree with gsf, generating a rating is hard, and somewhat subjective. even with 10000 iterations suexratt had a good 15% variation, my attempt at a rating had similar problems (yes I did try). The biggest problem with generating a rating with my code is that I wanted a very generic solver. So I do not differentiate between a hidden quad and a naked pair, or an X-Wing and a Jellyfish. I wanted code that could also be used in larger grids (well, locked candidates are having to be rewritten for jigsaws).

I could use timings, but them there are problems running from PC to PC. There is also a problem with Windows XP and AMD cores which gives negative timings from time to time. Linux times vary a bit as well, so timing is not a good method to base a rating on.

Anyways, my solution for ratings was to generate a category based on the hardest method needed to solve the puzzle (no guessing allowed). I then feed them into gfs's sudoku program to get -q1 and -q2 ratings. Still not the best, since some puzzles I categorize as expert level get a q1 rating under 1000 (my best from my generator is a 98771 q1 rating).


I have been playing around a bit, trying things. saved a little time on harder puzzles (6% faster on the Pearly6000), but much better on the gen 500k test (almost twice as fast). I will clean up ver 6, remove the parts I didn't like. That will get the categorizing and all my generic methods out. I will not have the Greater than solver or killer solver in the build.


zhouyundong, i looked at your site. though I don't understand some of the variations, like the second puzzle. 2 blocks can not equal 28, so it is not addition. I'll message you separately.

brit
Back to top
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Feb 02, 2009 11:51 am    Post subject: Reply with quote

28 is 5 girds(2 separate blocks) .
I will not have the Greater than solver or killer solver in the build. what does it mean?
Back to top
View user's profile Send private message Send e-mail
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Feb 04, 2009 12:12 am    Post subject: Reply with quote

Hi Brian,

I'm looking at your BB solver ver. 5c, and wondering when, if ever, I might want or need to use the DoubleCheck() function.

I have a huge number of grids, and every bit of time saved, is a real benefit, but I don't want to miss a critical grid solution either.

Given this situation, is DoubleCheck() needed? Are there grids that would be unsolved or solved incorrectly, without this function?

Thanks.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Wed Feb 04, 2009 2:28 am    Post subject: Reply with quote

Greetings,

The double check option was for my own use as I was testing various methods. It provided exactly what it sounds like, and independent double check. It does not serve any real purpose at this point. I would not use this option.

In a good news / bad news things. Version 0.6 is ready to be sent out. It has some more options, and more methodologies. it is faster than 0.5c in all my tests, though I did have a test build (0.5d) that was a little faster on the gen 500k test. The speed increases are not that large, but this is mainly a methodology and options build.

Code:

                Top 50000    Top 1465    Pearly6000    Sudoku 17    zeroth 600k    Gen 500k    bb puzzles
Sudocoo           2.656        0.578        2.031       123.609       48.859         dnf          1.453
fast_solv_9r2     5.000        0.421        3.203         4.593       55.859        28.921        1.515
Sudocoup          4.281        0.406        9.640         2.953       43.515        57.032        6.219
zerodoku v2       2.515        0.375        3.015         2.703       27.937       677.187        1.671
BB_Sudoku v0.1    1.982        0.224        2.108         1.856       22.263       528.890        1.206
BB_Sudoku v0.5c   1.432        0.075        1.317         0.935       14.795         3.275        0.803
BB_Sudoku v0.5d   1.354        0.073        1.229         0.919       13.388         1.811        0.752
BB_Sudoku v0.6    1.355        0.073        1.219         0.904       13.348         2.030        0.745

All times in seconds


bad news, I am having a problem with my web host, and my pages are temporarily down. Once they get my site back up, I will post the latest build.

brit
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Wed Feb 04, 2009 12:56 pm    Post subject: Please add a save in file function Reply with quote

briturner wrote:
Greetings,

In a good news / bad news things. Version 0.6 is ready to be sent out. It has some more options, and more methodologies. it is faster than 0.5c in all my tests, though I did have a test build (0.5d) that was a little faster on the gen 500k test. The speed increases are not that large, but this is mainly a methodology and options build.

brit


Please add a "Save in file " function, very useful to verify validity of a big batch of sudoku grids. Now I am using sudoku from gsf because it has more options available.

Thank you.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Wed Feb 04, 2009 7:23 pm    Post subject: Reply with quote

Greetings,

I also use gsf's sudoku program and encourage other people to use it. His program is far more developed then mine, and has many more features that I do not plan on ever implementing.

I have added the ability to specify an input file, and output or append the results to another file. These were originally added so I could use the debugger since piping is difficult to use when debugging. They are not documented in the small help output (same for the double check and stats info), since they were intended for developer use.

Once I get my sites rehosted, I will post the files. You will want to look at the -I for input, and either -O or -A for output, see if they help you.

brit
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Thu Feb 05, 2009 3:06 pm    Post subject: Reply with quote

Greetings,

I mostly have my web sites back up. The sudoku files did not transfer, and the dns may not have updated yet, but the most recent solver of mine is at http://www.tttarabians.com/bb_sudoku_v06.zip.

brit
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Page 7 of 9

 
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