Bit Based Sudoku Solver (BB_Sudoku) V0.5

JasonLion · Posted: Tue Jan 27, 2009 1:40 am Post subject:

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.

Adak · Posted: Tue Jan 27, 2009 2:35 am Post subject:

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.

briturner · Posted: Tue Jan 27, 2009 3:08 am Post subject:

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

Adak · Posted: Tue Jan 27, 2009 8:53 pm Post subject:

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.

briturner · Posted: Tue Jan 27, 2009 9:42 pm Post subject:

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

Adak · Posted: Wed Jan 28, 2009 3:21 am Post subject:

Thanks, Brit!

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

Very Cool

coloin · Posted: Sat Jan 31, 2009 10:15 am Post subject:

Hi, commendable work on your program

zhouyundong · Posted: Sun Feb 01, 2009 12:28 pm Post subject:

ok,I update my website.
www.eightclock.com
the wet site's speed is a bit slow,you can download my new version.

briturner · Posted: Mon Feb 02, 2009 1:53 am Post subject:

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

zhouyundong · Posted: Mon Feb 02, 2009 11:51 am Post subject:

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?

Adak · Posted: Wed Feb 04, 2009 12:12 am Post subject:

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.

briturner · Posted: Wed Feb 04, 2009 2:28 am Post subject:

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.

ChPicard

briturner · Posted: Wed Feb 04, 2009 7:23 pm Post subject:

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

briturner · Posted: Thu Feb 05, 2009 3:06 pm Post subject:

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