Bit Based Sudoku Solver (BB_Sudoku) V0.5

zhouyundong · Posted: Sat Nov 22, 2008 2:41 pm Post subject:

thank you very much ,Adak.
I will change my program into English version and upload as you told me
tomorrow night or maybe one or two days later.

zhouyundong · Posted: Sat Nov 22, 2008 6:37 pm Post subject:

I ask a question, P2Group[x][y] and P2Group[(x<<2)+y],which is faster?(here declare P2Group[N][4])...I think complier handle P2Group[x][y] as x*4 + y,its speed is lower than P2Group[(x<<2)+y].

zerothbase · Posted: Sat Nov 22, 2008 7:06 pm Post subject:

briturner,

unless you have plans to handle larger puzzles (which I doubt considering you are using hardcoded tables rather than generating them on the fly), you might change the G struct to use all unsigned shorts (16 bits) instead of unsigned int. Small % improvement depending on how much it has to backtrack (less copying).

--zerothbase

briturner · Posted: Sat Nov 22, 2008 8:46 pm Post subject:

Greetings,

First, zhouyundong, I could not find your files in the link, so I could not run it. I did run the 5 puzzles you posted. Looks like they can all be solved with only using hidden singles and locked candidates. I ran them on my laptop (1.83 ghz T5600 intel processor). I got the following:
33.24 usec, 19.00 usec, 17.88 usec, 17.32 usec, 19.83 usec.

Adak, you are probably using the timer tick, which is around 16 millisec. since most solvers can solve puzzles faster than that, you will need a higher performance timer. I use QueryPerformanceCounter in windows, or clock_gettime in Linux, both being sub usec timers. There are some issues with each, but still much better than the timer tick.

brit

JasonLion · Posted: Sat Nov 22, 2008 8:59 pm Post subject:

briturner, Impressive work! Version 0.4 is dramatically better at the hardest puzzles, though it is just slightly slower at the very easiest puzzles.

I got a 3 or 4% improvement by changing the Min macro in MakeGuess to simply sum the values instead of taking a minimum. Conditionals are bad, and I wonder if summing isn't a better solution algorithmically as well.

I wonder about the value of the SolGrid array. It seems to me the same information could be extracted from G, which would eliminate the store to SolGrid inside of ProcessSingles. It is also messy to have SolGrid defined externally and yet have the solution actually passed back in an argument. I think SolGrid should either be local to bb_sudoku_solver.cpp or eliminated.

Also, I needed to give the structure that the G array holds a name ("struct foo {" instead of "struct {") to get the code to compile under gcc version 4.

briturner · Posted: Sat Nov 22, 2008 11:10 pm Post subject:

Greetings all,

Thanks for all the comments. v05 is now available http://tttarabians.com/sudoku/BB_Sudoku_v05.zip

Sol_Grid should have been moved into the other file, that has been fixed. It's use is so that the Grid can contain a 0 instead of a value for a known cell. Originally, I had it in Grid, but then had checks to not process knowns in the Grid.

I actually do plan on making 4x4, 5x5, etc, but they will take unique tables. My original solver (before bb_sudoku_v01) was very generic (2x3, 3x3, 4x4, 5x5, 4x7, and overlapping grids), but it was much slower, like 15 seconds for 20,000 sudoku. I plan on separate files for each size now.

I changed the min to +, now much change in speed, but it does make the hard puzzles a bit faster, easy puzzles a bit slower. It may just be because of the puzzle samples I use. I run these against 106600+ puzzles I have found on the web for timing comparison, but that is not an all inclusive set of puzzles.

So, big change for v0.5, Disjoint Subsets. they are done, but they are slow. locked candidates are much faster. Based on the number of times I call the guess routine, Locked Candidates reduce guesses by 40%, Subsets by 38%, and when both used, 50%. Problem is, the overhead of solving subsets causes the solver to take twice as long, even though there is less guessing and backtracking. Subsets are not used by default, but can be turned on with -MS (for Method Subset). Locked Candidates are always used, since they save time, even with their extra overhead.

here is how I handled subsets (a bit ugly):

JasonLion · Posted: Sun Nov 23, 2008 1:31 am Post subject:

Where to go next depends on your goals.

I normally use a brute force solver as part of game generation. The partial boards that game generators produce have very different characteristics than the puzzles you have been testing against. It is possible to be at least twice as fast as you are now on this kind of puzzle, normally at the expense of being significantly slower on the puzzles you have been testing against.

I have some sample puzzles that my generator checked as it was going through the process of creating real puzzles. The majority of these puzzles are invalid in one way or another, typically having multiple solutions. You can download a file with 500,000 "trial" puzzles from my generators internal process from http://www.enjoysudoku.com/gen_puzzles.zip. Optimizing for a set like this one is important for a checker used in puzzle generation.

If, on the other hand, you want to create a human style solver for use in ranking puzzle difficulty, you will want to go down a very different path. Human style solvers typically maintain much more state about the current board position. For example, finding naked subsets is much simpler if you have a map for each digit in each house of which cells in that house still allow that digit. A solver for puzzle generation can not afford to maintain that much state.

briturner · Posted: Sun Nov 23, 2008 2:04 am Post subject:

Thanks Jason,

quick question then, of the 500,000 puzzles in that file, how many have unique solutions?

I ran it through my solver (-S2 to check for uniqueness). I needed to increase my backtrack size to 34, and added a line to count both no solutions and multiple solutions as failures.

Came up with 763 with unique solutions, in 3.192 seconds (6.384 usec per puzzle checked).

brit

JasonLion · Posted: Sun Nov 23, 2008 2:09 am Post subject:

I show 763 with one solution, 12,786 with more than one solution, and 486,451 with no solutions.

zhouyundong · Posted: Sun Nov 23, 2008 7:25 am Post subject:

in that link, you must log in ,then you can see and download and free use my software, if it has virus,please forgive me,,because my computer is now under attack of virus.
log in : user ,you can use zhouyundong, password is 111111222222.
you should find the "log in" button, it is written in Chinese.
Your program is so good,and I learn to you.
I will try a way to use lookup table[54656] and table2[54656*54656],just try.

Adak · Posted: Sun Nov 23, 2008 10:03 am Post subject:

Zhouyungdong: I went to MediaFire and signed up, but you didn't give me the url for your program - so I can't download it.

It should be something like this: http://www.mediafire.com/?fjtiz8idnm2 (this is just an example).

Brit: Yes, I'm using tick counts. My solver was written with an old Turbo C compiler and knows nothing about Microsoft Windows. Smile

I'll have you know that it has *big* 16 bit integers, now!! Wooohooo!!

Wink

m_b_metcalf · Posted: Sun Nov 23, 2008 10:41 am Post subject:

zhouyundong · Posted: Sun Nov 23, 2008 1:53 pm Post subject:

thank you,Adak.here is my url
o,my god,dead link
it support upon mouse wheel,0-9,Numpad 0-9,up,down,left,down,del,backspace,left button,right buttom
Unify hasnot been written, you can click the middle of two board
'a' is get solution, 'q' is get question.
red led is no answer,green led is one answer, yellow red is more answers

JasonLion · Posted: Sun Nov 23, 2008 2:04 pm Post subject:

m_b_metcalf: briturner and I are both making all of those checks after propagating naked singles. However, I believe that he doesn't finish checking the entire board if a hidden single is found, while I go through the whole board each time I start looking for hidden singles.

Subtle differences in the search order, like checking for all hidden singles vs. only checking till you find one hidden single, affect the relative performance on the different classes of puzzles. The organization of data structures also makes a difference. I use a very different data structure, one that makes initial setup, guessing, and digit placement much cheaper at the expense of making naked and hidden singles just a little bit more expensive to find.

I have found that there are two important performance metrics. Briturner has been optimizing what I think of as the worst case performance, how long it takes to solve the occasional "tricky" (for a brute force solver) puzzle. Puzzle sets like top1465 have been specifically chosen to focus on this kind of puzzle.

For puzzle generation I am far more concerned with solving "simple" puzzles quickly. Most randomly created almost puzzles are simple for a brute force solver, nothing at all like the puzzles in top1465. Minor differences in setup time and search strategy can improve performance on these puzzles at the expense of taking longer on the tricky puzzles.

Solution time on tricky puzzles still matters. You don't want the kind of performance curve Sudocoo exhibits, where some puzzles take an inordinately long time to solve. That can result in the puzzle generator running quickly most of the time, but occasionally "freezing up" while it works on a tricky puzzle.

The best compromise for a solver used by a puzzle generator seems to be to focus on speed on the "simple" puzzles, while keeping the "tricky" puzzle time from getting worse than 5 to 10 times the ideal time. Keep in mind that I am using the terms "simple" and "tricky" relative to a brute force solver, which has nothing to do with human solving time.

zhouyundong · Posted: Sun Nov 23, 2008 2:23 pm Post subject:

hate: it is a dead link!!!!!!!!!!!!!!angry!
I send a dead link