Can I code one in FreeBASIC? :D
Printable View
Can I code one in FreeBASIC? :D
Quote:
Originally Posted by Something Else
who is "we" ?
where is that area ?
Are you saying, there is(or will be) a sudoku-programming contest in C ?
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?
could you translate that teethy smiley into English ?Quote:
Originally Posted by Merri
you're going to bite someone ?
OK, I won't post the link to the announced paper.
Just a quote:
"A new strategy to select the next variable and the value to branch on
for Latin square problems was proposed in [4](2003) . This strategy clearly outperforms all the previous ones that have been tested.It consists of
selecting the variable with the minimum domain size and then select the value
which occurs the fewest times in the domains of the variables of the rows
and the columns of the selected variable.We have improved this strategy...."
"We" are you and me, everyone who particibates in VBForums.Quote:
Originally Posted by dukuso
http://www.vbforums.com/forumdisplay.php?f=23Quote:
where is that area ?
I'm sure if you asked TPTB {ie.. the Mod of the contest area}, he might accept your C entry, and compete it against every single one of the other C entries. Of course, I have no say in this matter. But if he DOES take it, You'll probably be the Best C entry for this contest to date!Quote:
Are you saying, there is(or will be) a sudoku-programming contest in C ?
heh! Show Off!Quote:
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?
:wave:
-Lou
Heres some more patterns.
I have no idea if they've become any harder. I added a counter to weight the pattern development with iteration counts on the several strategies in my generator. Let me know if I broke it.
-Thanks
-Lou
NotLKH: this is your fifth set this far, not fourth :) Unless I'm very badly mistaken...
Anyways, still relatively easy. 25 ms for 314 files = 0,08 ms per file. Compared to minimum set of 453 files: 103 ms; 0,22 ms per file. If you'd get rid of the all-too-easy ones, then your puzzles would start to compare.
I make a "human difficulty rating" to my code after the contest is over, so then we can more clearly see which puzzles are hard and which are not. Computer speed isn't the only measure one should take into account. I already have an idea on how to make it.
I'd like to, hence My Ratings.
I just need feedback to determine what the ratings signifies in difficulty.
If you can list each ones speed, that'd help me determine whats what.
:wave:
-Lou
The contest is for VB6, VB.Net and C#. I don't really know if it would be fair to compare a C entry with any of those...
It would be, dukuso already mentioned mine is faster :D Aren't we keeping it separate anyways or will all be in the same category and compared against eachother?
The 3 categories I mentioned are going to be marked seperately. I meant that C doesn't fit in any of the 3 categories so I don't know if it would be fair to compare it with the entries of any of the 3 categories. Better now? :)
2 More days!
Here's the last that I'll post before the contest. Any feedback would be nice!
If you've wondered, the followin is what the numbers mean in the sol file name.
Given a filename like : 026_0674_0015-000019__Solved.sol
The first Set, 3 digits, indicates the number of exposed cells in the initial puzzle.
The second set, 4 digits, is the sequence index it was generated at.
The third set, 4 digits, is a binary composite:
- A Zero means it only used naked and hidden singles
- 1 s: If it detected a number in a shared set of 3 cells at the intersection of a row/col and a 3x3 square that wasn't anywhere else in the row/col, but was in multiple other cells in the SQUARE, it was removed from the other multiple cells.
- 2: Same as 1, except the other way
- 4: Naked pairs were detected and processed
- 8: Hidden pairs were detected and processed
- 16: Naked and/or hidden trips were detected and processed
- 32: If I had it activated, it would mean naked/hidden Quads were detected and processed
- 64: This means, if after iterating thru all the first strategies until exhausted, and the puzzle still wasn't solved, then it went into the full iterate all posibles mode, until it found a solution. In my generator, it also counts all the solutions possible, and any that had more than 1 solution was considered a failure. None of these really should have more than 1 solution.
The 4th set, 6 digits, meant 2 possible things:
- If the 3rd set < 64, then it is the count of how many times it looped adding sets of cells with only 1 possible into the solution matrix
- if the third set was >= 64, then it indicates how many total possibles were available to all the unassigned cells, before it went into the 64 mode. Then I added 100.
This 4th number was what I used to filter on my generator as I tested removing revealed cells from an initiating set of succesful revealed cells.
Lets say, if I had a msk set of 26 cells that led to a solution, I would build and test 26 subsets, each of the the 26 combinations of 25 cells of this msk set, removing 1 of each 26 revealed cells. I would note which subset worked, and I would select the one with the largest 4th number as the new msk to test.
As I worked down, once I reached a set that had no good subsets, then that is the one that I'd output as a new msk entry.
Attached is my newest set, using the strategies as I've explained them, above.
:wave:
-Lou
Finally submitted the code. Did some final changes to actually meet the contest requirements... noticed the required output timings file format just when doing last time reading of the rules.
Happy benchmarking!
I think I joined the contest a little too late. I am just now to the point of optimizing things (after finishing my backtracker). Each optimization I do breaks the whole solver for a while (until I can work out all the bugs), so I will be lucky to get 0 based arrays and 1-D arrays done by friday.
Can I turn it in at midnight on friday (my time zone)?
You're slow. You get eaten. That's the rule of the jungle.
You ought to be a monkey so code like one! Code like mad!
Easier said than done, but I'm done already so there shouldn't be much to complain about :D Oh, btw, I tried converting my solver to do 5 x 5 puzzle... it would be great, if all my optimization arrays worked in that mode, they take almost 100 MB unless I counted wrong... my computer just swaps when I start the project :D Don't know if it solves, this far I've had some typos... too many of them. Subscript out of range etc.
I'll accept entries submitted till midnight Friday GMT. It's the easiest to keep track :)
Well, I got the base 0 arrays working and got a slight speed increase and 1-D arrays are coming along nicely (although I am not far enough to get to the debugging part yet and I think they might turn out to be hell).
I have at least 10 other optimizations to do and I know I won't have time for all of them. The only reason I am getting so much done today is because my girlfriend is busy for the first day in the last 2 weeks and we aren't hanging out today (well, we are, but not until later tonight).
GMT sounds fair enough manavo.
/me walks over to google to find a time convert
EDIT: Crap! Thats 7AM friday for me. I won't even be up by then. I guess I can stay up all night thursday and be useless. Fun fun!
You sure you counted to 23:59 of Friday and not 0:00 of Friday? Afaik you have 30 hours to go at the moment.
I mean the night from Friday to Saturday midnight...
Thats it. I have submitted my contribution. I don't stand a chance agains Merri's solver ;) , but I'll be happy as long as I don't loose.
The most important thing is to participate, not to win... I guess :rolleyes:
Huh? :confused: :confused: :confused:Quote:
Originally Posted by manavo11
The entries will be accepted if they are submitted until 23:59 Friday night... Now?
In plain Finnish that means "sinulla on alle 24 tuntia aikaa" which translated to English means "you have less than 24 hours to go". About 23:25 if I'm not mistaken.
GMT at the moment it's 01:37 AM... if i'm not mistaken...
Well according to the time converter I went to then Oregon (USA) is GMT - 7 so midnight GMT is 7AM the same day. Am I mistaken?
I think it means that you have till 17:00 (5 PM) to submit...
When it's midnight GMT, you will be 7 hours behind, which means 5 PM...
That saves me a lot of stress. Thanks manavo. :)
Just uploaded the 1011 patterns for the contest.
T - 16ish hours...
:)
-Lou
Later today, 8 hours or so, I'll tweak My code , generate some patterns that return more than 1 solution, {Hence, UNSOLVABLE Sudoku} and get those submitted, to allow testing on the SOLVED or FAILED requirement.Quote:
The file format should be:
Quote:
Quote:
FileName001.msk: (SOLVED or FAILED) in 0,000000 seconds!
:wave:
-Lou
Err... my solver solves those as well, in case you mean just more than one solution. It just gives one of the possible answers. There is nowhere said in the rules that "sudokus with multiple solutions are equal to invalid sudoku, thus the solver function must return false when it meets such a sudoku". However, if you mean really unsolvable (board that can't be solved because there must be two or more of the same number in certain row/col/block) then it gives FAILED just fine.
I agree with Merri... If there is more than one solution the app won't fail to solve it, it will only fail if it can't find any of the possible solutions...
Darn!
I hoped you wouldn't point that out.
:(
{In terms of a generator, I consider a multi solution sudoku as a failure, along with those that throw off conflicted cell values.}
Oh, well. That would take a bit more development time. Never mind.
:)
-Lou
It is very easy to do such sudokus just by hand. For example, there can be only one completely symmetrical group of numbers within a sudoku. Thus if you place numbers in symmetrical way in the board, you get an invalid sudoku. So if you just make enough symmetric placements that first seem to be valid, you easily make an invalid sudoku. A completely symmetric placement of any numbers require that the centermost cell is included... thus if you try to place all numbers according to the symmetry, then all numbers are pointing to the centermost cell... the problem is that only one number can be there and thus you'd get eight invalid placements to the centermost block.
True. Its easy to make an invalid base.
Now Hide all but "N" of them.
Now, Solve this msked arrangement.
Is the result necessarily the base you just created, or could it be a true sudoku?
Last minute question... when you load the sudoku problem into my program it fills some lookup arrays other than the normal 'grid'...is this acceptable or must this be in the solver routine.
And since my code is implemented in a Module (not a class) can I have a Initialise subroutine?
I would say, if by "Lookup" grids they are not created by any analysis of the puzzle, but are constant from 1 puzzle to the next, like an intermapping between the 2x2 position of the 81 cells in relation to the 9 rows and 9 columns, then I'd think you would want to initialize them in the form_load event.
But if they ARE unique to each puzzle, if you do any analysis of the puzzle whatsoever to build these grids, then I'd have to say they need to be in your solver area.
Of course, thats only My opinion.
Ask Manavo!
:)
-Lou
Thanks.
Yet another question....after you have completed solving one problem...where do you put the 'cleanup - clearing arrays etc.' code in the same subroutine as the solver or can you put it elsewhere so it isn't timed?
I would think that, any arrays that "Need" to be cleaned up would be redimmed at the start of each solving, in your solver, hence they would be timed.
If the arrays are static, ie.. again an intermapping between 2D coordinates and 1D, then they never have to be cleaned up. But any arrays that are used for temperary values, obviously if any preexisting values interferes with the next puzzle processing, would have to be cleaned up, and IMHO, that should be part of the timing.
Of Course, it could also be argued that, if all you are doing is zeroing existing arrays, without truly adding any information into them, then they should also be outside of the timeing.
So, I officially have no idea.
:wave:
-Lou
Yeah , Im just zeroing my arrays....hope that's ok.
I have a sub call PrepareSudoku that sets all my relevant modular level arrays to 0 (or whatever their default value is) that is not based on the contents of the current puzzle in any way. I don't time this. I don't think Merri does either.Quote:
Originally Posted by NotLKH
Manavo, can you clear this up (again? :D)? :)
Thanks!
Posted :D it ...hope it does well :D
3 hours to go exactly. I guess I don't have time for any more optimizations, so I guess I will re-read the rules and scan the code a couple times (and remove things that are there for testing purposes only) then submit.
Hehe, I left my code in a pretty unclean state. Ten minutes to go and the deadline is here... I weren't able to comment all the code as well as I wanted to, there just were too many things I tested. I've a lot of undone code as well... just the way it is. No time to do everything I want.
At the moment MegaTokyo translation is getting close to my heart again, so I've been working with it for the last three days. I need to work a few more so I don't need to think about it too much in three months or so. Needs about a week more work and I'm there. Then I can spend time with other things as well.
I submitted mine about 10 minutes too late and I really hope manavo accepts it. I am pretty sure he will. I left home and what I did took extra long then I rushed back to submit it in time.
Hehe yeah I don't think 10minutes late is too bad :D.
When do the results come out?
He'd have to give you a 10 second penalty for being late. Should have said your clock was wrong :)
Maybe you could argue "Monkey Time" ?
10 second penalty YIKES!....might as well give up :D
Now I feel bad :( I didn't answer all your questions before the end :(
However, NotLKH's unofficial answers are correct, so I hope you listened to him :)
eyeR, 10 minutes isn't a problem, don't worry ;)
When are the results gonna come out?
I have just downloaded all the entries. Not many :( I'll probably start marking now :)
Good luck everyone :)
Thanks :D
Question for all contestants :
Do you want the marking to be in the IDE or compiled?
The answers I need are from :
Brick1 : Compiled
bpd : IDE
Merri : Compiled
kaffenils : Compiled
Raedwulf : Compiled
eyeRmonkey : Compiled
Thanks :)
Compiled. With all advanced optimizations turned on in each. Saves you a lot of time :D
Compiled :D.. Same as Merri 'all advanced optimizations turned on'
OK, since majority rules, if 1 more person picks compiled I'll release the compiled results :)
Tension rising :D
Tick tock Tick tock.....
Im growing impatient :P
1 hour after the announcement 3/6 votes
3 hours after the announcement 3/6 votes
....Last vote please :D
I'm sure that the majority will pick compiled, but just incase, I'll wait for the other 3 members to reply :)
Ok manavo, just read it.
To be honest, i dont care IDE or compiled. No difference if it's for everyone the same.
But agree for compiled, to get things going.
Wow, not too many entries. I feel special now.
I vote for compiled with all advanced optimizations if possible. Also if you are on a Pentium, do that optimization too. :)