Bit Based Sudoku Solver (BB_Sudoku) V0.5

zhouyundong · Posted: Thu Feb 05, 2009 5:26 pm Post subject:

I stop my work on Killer because I don't know your work,what did you do about Killer and your speed to solve the very diffucult Killer(very diffucult means there is no additional hint).
The same to GT, I want to test your program.

ChPicard · Posted: Fri Feb 06, 2009 11:51 pm Post subject: Output command

briturner · Posted: Sat Feb 07, 2009 12:37 am Post subject:

Greetings,

The undocumented options are (not case sensitive):

-I[fname] : specifies an input file, for example -Idata.txt
-O[fname] : specifies an output file, for example -Osolution.txt
-A[fname] : appends the output to a file, for example -Asolution.txt
-V : verify solution with an independent checker, mainly used when makeing changes to the solver to make sure the solver still works
-X : display stats, currently only the stats from the last puzzle solved

so for your example, it would be :
bb_sudoku_v06.exe -Idata.txt -Asolution.txt

I normally just use pipes to specify io, such as
bb_sudoku_v06.exe <data> solution.txt

brit

ChPicard · Posted: Sat Feb 07, 2009 12:59 am Post subject: Extremely impressive BRIT

briturner · Posted: Sat Feb 07, 2009 1:23 am Post subject:

Greetings,

Here are some options you can use to do different things

Solve the puzzle:

bb_sudoku_v06 < data.txt
- display solutions for valid puzzles, followed by " - solved"
- for invalid puzzles, the original puzzle is displayed, with " - No Solution"
- if a puzzle has multiple solutions, only the first is found and displayed

bb_sudoku_v06 -s2 < data.txt
- display solutions for valid puzzles, followed by " - solved"
- for invalid puzzles, the original puzzle is displayed, with " - No Solution"
- if a puzzle has multiple solutions, the first is displayed, and " - 2 Found"

bb_sudoku_v06 -s2 -p < data.txt
- always displays the puzzle, and either " - solved", " - No Solution", or " - 2 Found"

bb_sudoku_v06 -s0 -p < data.txt
- always displays the puzzle, and either " - solved", " - No Solution", or the actual number of solutions found. If there are lots of solutions, this could take a very long time.

If you use the -D0, then no puzzles or solutions are displayed. It is only used for timing purposes.

If you use -C to get a difficulty category, then it will take much longer to run, since it is solving each puzzle multiple times.

When I check puzzles, I use :
bb_sudoku_v06 -s2 -p -c < data.txt
but if you are using a different rating program, then you will want to use :
bb_sudoku_v06 -s2 -p < data.txt
which is much faster. Send the output file someplace, then grep for "Solved" to get a list of valid puzzles.

brit

ChPicard · Posted: Sat Feb 07, 2009 1:39 am Post subject:

briturner · Posted: Sat Feb 07, 2009 3:31 am Post subject:

Greetings,

ChPicard, I understand the idea. that feature is not implemented. I have to admit, since my generator is embedded with the solver, I do not print out invalid puzzles. I actually categorize the puzzles and don't print anything not at the expert level anymore. I'll consider it for the next release.

zhouyundong, I am combining my various builds into one build that has teh latest of all the variations. since it does not generate GT or Killer sudoku (yet), I only have a few test cases to time. I'll let you know what the times look like in a few days.

Also, you should not stop your work on variations. My GT solver is very slow. One test took almost 1/2 a second (which is a really long time for my solver). everyone has unique ideas, and yours could handle the variations better than mine. anyways, the only way to learn is to do things yourself.

brit

briturner · Posted: Mon Feb 09, 2009 7:46 pm Post subject:

Greetings,

zhouyundong, I promised you a timing of the GTLT puzzles. Here they are:

5 minutes, 29 seconds on a 1.83 GHz processor.

I realize that is terrible for timing, way longer than for normal sudoku puzzles, but I have not optimized for GTLT puzzles. I have 2 methods in mind that could speed up the solver for this variation, but I have not implemented them yet. It would also improve the timing for the generator, which is averaging like 6 seconds a puzzle. Some puzzles are generated in a fraction of a second (well under 0.5 seconds), but some take much longer.

anyways, if you want to test out your solver against my 5k test here is the link:
http://tttarabians.com/bb_gtlt_5k.zip

I do not have a killer sudoku generator, so I do not have timings for that.[/url]

brit

briturner · Posted: Wed Feb 11, 2009 8:05 pm Post subject:

Greetings,

I have thinking about what I want to do next. This is actually my second sudoku solver. My first solver handled grids up to 28x28 (4x7 boxes), and overlapping grids, but was not as fast as other solvers. My second solver (bb_sudoku) is fast, and I have at least one idea (not in the readme) that could make it a bit faster, but what is the point.

So, I am now planning on taking a bit of a break and coming back with a new solver that concentrates on variations. The primary reason to not continue with the current solver is that adding larger grids and jigsaw puzzles will be changing my base data tables. Once I start down that path, then changes will most likely cause the solver to slow down on the standard 9x9 grids, which goes against the goals of bb_sudoku, which was speed.

I have various pieces already working:
- Greater Than / Less Than Solver - Not as fast as I like, but running
- Greater Than / Less Than Generator - Also, not as fast as I like, but working. I can generate some 10k puzzles while I sleep on my laptop if I want. One interesting note on a generator is that even if you fill in every comparison, you are not guaranteed a unique solution.
- Killer Sudoku Solver working - No generator for this, so I only have a small number of test cases to work with
- Jigsaw Generator part 1 working - I can generate XxX grids with X boxes of X cells in each. I was playing around with this and generated up to 250x250 grids. I have not done the second part, which adds the numbers into the grids.

So, look forward to a future release of Vudoku (Variant Sudoku), coming to a forum near you.

brit

ChPicard · Posted: Thu Feb 12, 2009 4:35 pm Post subject:

m_b_metcalf · Posted: Thu Feb 12, 2009 7:50 pm Post subject:

gsf · Posted: Sun Feb 15, 2009 6:00 pm Post subject:

gsf · Posted: Wed Feb 18, 2009 12:59 pm Post subject:

is anyone seeing the latest posts in the forum main page?
[ edit ] this post has finally shown in the main programmer's forum page

zhouyundong · Posted: Thu Feb 26, 2009 4:04 pm Post subject:

I continue to work for somix:support editing of Extra, Jigsaw,GT,Killer GT,sosum.here is a mixture of them:
127983456835164279964752831573219648482576193691438725759841362216397584348625917000000000000000000000000000000000000000000000000000000000000000000001300000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000102000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010101020202030303010101020202030303010101020202030303040404050505060606040404050505060606040404050505060606070707080808090909070707080808090909070707080808090909000000000000000000000000000000000000000000000000000000000000000000000000000000000

zhouyundong · Posted: Fri Mar 06, 2009 2:30 pm Post subject:

Greetings,Briturner.
You wrote Killer Solver, Fastest Sodoku solver, Fastest GT solver, you made great contributions to the domain of this area.
I wrote a Editor, easily to edit a game with GT, Killer,Killer GT, Jigsaw, Extra.
I do very hope we cooperate. I will send to you my over 8000 rows source codes if you want to cooperate too.
I think if we cooperate and develop together, it must be a very very good software.
My email is lao_zhouxi9@163.com