Bit Based Sudoku Solver (BB_Sudoku) V0.5

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

I got an error message: Zero size reply

If you can put it up on Media Fire, OK. I can't go to lots of websites though. I get too many viruses that way.

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

hi,briturner,can you try this
000000000456789120789123450214365890065897210097214360031642970042978530000000000

what I got is :
Bit Based Sudoku Solver v0.2, by Brian Turner

000000000456789120789123450214365890065897210097214360031642970042978530000000000
000000000456789120789123450214365890065897210097214360031642970042978530000000000 - No Solution
---------------------
i got 123456789456789123789123456214365897365897214897214365531642978642978531978531642 and green led(means only one answer)
with my douzhi sodoku,win32 application
---------------------
another question:when you solve top 50000,do you give the result ,the result is "no answer, one answer, more answers"? It means when you get one solution,do you try to find if another solution is exist? Thank you.
I am now trace your source,very good source and very horner behaivor to upload source.

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

{ b = G[PIdx].Grid[Group[i][j]];
t2 = t2 | (t1 & b);
t1 = t1 | b;
if (B2V[b]) t3 = t3 | b;
}

t3 = ~(t2 | t3) & 0x01FF;
I know t1 means in 9 grids(3 kind of groups),111111111 is must.
t3 == true means this grid is single,such as 000010000

briturner · Posted: Mon Nov 24, 2008 1:59 am Post subject:

zhouyundong, in that code, t1 is the possibilities that have only been seen at least once, t2 is the possibilities that were seen more than one time. t3 is the numbers that are already known (This has been removed in newer versions).

A hidden single is then something that was seen one time, but not more than once, and is not already known

JasonLion, can I use the 500,000 puzzles you provided as another timing sample in my comparisons? I will not use it without your permission, but it would add a good point for people interested in generators.

I think i will do a generator next, already have some ideas of what I want to do. Basic idea I have is to place random numbers until I have a unique solution, then remove the givens one at a time to see if it was needed. I also plan on maintaining the partial solutions as I go along so I do not have to start from scratch with each new given added.

I have been reading other threads as well, and appreciate that my ideas are helping other people with their programs. There really is nothing new or revolutionary in what I am doing (unlike DLX which is a very elegant solutions that can be used in much more situations then my solver). I figured many others use similar ideas, since there are really only so many ways to write the solvers. I personally used the guide by Ruud as a basis of my program. I also appreciate people like JasonLion and zerothbase that have helped tweak parts of my algorithms.

brit

JasonLion · Posted: Mon Nov 24, 2008 1:06 pm Post subject:

briturner · Posted: Tue Nov 25, 2008 3:53 am Post subject:

ok JasonLion, I have updated the timing in the last post in the timing thread http://www.setbb.com/sudoku/viewtopic.php?p=10559&mforum=sudoku#10559

brit

zhouyundong · Posted: Tue Nov 25, 2008 11:05 am Post subject:

hi, briturner,
another question:when you solve top 50000,do you give the result ,the result is "no answer, one answer, more answers"? It means when you get one solution,do you try to find if another solution is exist? Thank you very much
and I think to generater, more than several ways can get.
what I do is: based on the given board by user, the result has 2 kinds:one is no answer or more answers,and another is only one answer.
if no answer or more answers,then random create board[0,1,2,3,4,5,6,7,8],then random create board[16,48,64,...128],top row and left column, but except board[the third row,the first column(32)],then get answer,here I have gotton random board[144].then random swap(1,2,3,4,5,6,7,8,9) for 20 times. then create random series[i], and one by one get rid of the board[series[i]],keep the result is only one answer
I can get 10000 games in 20000s
430021000000370000705000000060098004008000036000002008500009100000000070040000503
100004000000030608000700540006070080000309000098005000507100000809000000020000060
006000405320000000000307006010000700008050020000900040000003010500009000470000800
if only one answer,then create random series, and get rid of the board[series],keep the result is only one answer
for example:
when user give
006000405320000000000307006010000758008050020000900043000003010500009000470000800
run "Question",computer get
006000405320000000000307006010000700008050020000900040000003010500009000470000800

if the "QUESTION BOARD" has more than 24 numbers in it,then do Question again itself,until <= 24.

zhouyundong · Posted: Tue Nov 25, 2008 11:12 am Post subject:

zhouyundong · Posted: Tue Nov 25, 2008 11:18 am Post subject:

briturner · Posted: Tue Nov 25, 2008 12:53 pm Post subject:

greetings zhouyundong,

my program is currently a solver only, though I have started building a generator into it for the next version (not yet available to the public).

programwise, use a -s2 to check for uniqueness, -s+ for multiple results. in the code, when you call solver, you provide 3 parameters, the first telling if you stop at the first solution, 2nd, or try for all solutions. The first solution found is returned in the same buffer the puzzle is sent in.

My plan for a generator is similar, but will be integrated into the solver. Once a puzzle with a unique solution is found, I plan on running it through the solver with each given removed to minimize the puzzle.

I guess I am not sure exactly what you are asking.

brit

zhouyundong · Posted: Tue Nov 25, 2008 1:12 pm Post subject:

greetings briturner,
what user concern about is a question has one answer,no answer or more answer,if there are more answers,I think they have no interest to see every answer. even they have no interest to see the second answer.

So you may try to set a flag, tell solver to stop when solver has two solutions(not all solutions), and give user the first solution,and the same time give a message: more answers Very Happy

Can I use your public code into my software and sign "Kernel Written by Briturner" at the top bar of window?

briturner · Posted: Tue Nov 25, 2008 1:51 pm Post subject:

greetings zhouyundong,

I understand. as of the last version I released a few days ago, the Solver function does this.

When you call solver, you pass in if you want to stop at 1 solution, 2, or find all solutions. Only the first solution is passed back, even if more are found.

here are examples:

PuzCnt = Solver(1, ... // stops after 1 solution found. returns either 0 (no solution) or 1 (solution found)

PuzCnt = Solver(2, ... // Stops after 2 solutions, returns 0 (no solution), 1 (unique solution), or 2 (multiple solutions)

My code is posted so people can get their own ideas and build on my ideas, but please give me credit. If people want to use it for commercial profit, then we should discuss it.

I have not really published code, any one have a good idea of what license I should attach to this?

brit

zhouyundong · Posted: Tue Nov 25, 2008 5:05 pm Post subject:

About testing, not in allusion to any solver.

I think, speed test give result(0,1,2) and the first solution(result and solution do not display) is good than give the first solution only.
Embarassed

zerothbase · Posted: Tue Nov 25, 2008 11:19 pm Post subject:

JasonLion · Posted: Tue Nov 25, 2008 11:27 pm Post subject: