That would be optional. At the moment there is no display/support in the core, but if there is interest on that (atleast two persons willing to make a 16x16 solver logic), I can add the support at some point.
Printable View
That would be optional. At the moment there is no display/support in the core, but if there is interest on that (atleast two persons willing to make a 16x16 solver logic), I can add the support at some point.
I've added my solver, it's a little scruffy to look at. Currently it can solve around 85% of the minimum Sudokus. It seems to average just under 0.0002 seconds to solve (or to not solve) on my 2.8ghz system. Although not fully optimised I am making extensive use of Merri's rather useful helper tables.
I've still to implement further logic and (if it is considered non brute force) a guess routine.
Should we set some time goals for providing solver functions so there is something to aim to? This doesn't mean someone couldn't send code later on, just that people would get something to look forward to.
I haven't had much time to spare on this project, but that was to be expected. I'm on vacation next week, and only that week, but I'm probably spending all the time available on another long time project of mine (a website).
Interesting site. I can't read any of it, but i like the layout. What is the Browser icons represent? Compatibility?
The icons link to the compatibility page, telling mostly which browsers have been tested and how compatible they are (and that there are separate fixes for various versions of IE).
We should also define these functions. I've been looking at Andrew Stuart's site which Lord Orwell linked to. I think it provides an excellent list of strategies, some 36 in all, only 2 of which involve guessing.Quote:
Originally Posted by Merri
For my part I'm just tidying up an improved algorithm (I'll post it later this week) which now covers...
This now solves about 90% of the minimum set or Sudokus and around 10% of the hard.
- Singles in a row/column/block
- Naked Pairs/Triples/Quads (all combinations)
- Hidden Pairs/Triples (all combinations)
- Block/line Reduction
Might I at this point also suggest a possible change to the core code. Would it be possible for the core to store a bitset Long(80) array instead of a solved String(80) array. The idea being that most of the strategies, especially the more complex ones do not necessarily solve any squares but simply reduce the possibilities. This way we can experiment with different strategies and see the results visually. I also think it would be useful to display the possibilities as well as the solved squares.
One more thing, as of next Tuesday I'm on holiday and away from keyboard *gulp* until early August.
Dammit: not had a chance to finish my code, or work Merri's soz
I've also thought about the interface, and a bit masked long array would work the best for it (as visual hints about possibilities makes it more readable). I originally chose string as it might be most familiar to most programmers, but in the other hand as we now do have the conversion functions it is all the same which format is preferred by the core program.
I don't know if the list of strategies should be limited to certain ones; of course, there are some interesting effective ones that would be nice to see in action.
As for my time, I'm now on vacation but as told, I probably focus on the another project. Doing kBs of code after kBs of code for it at the moment. You can submit your own improved and fixed version of the core if you want to do so, I probably don't have the time (vs. interest) just right now.
We could implement the solver in the game itself as a "hint" routine which would perhaps not even tell you which number is where, but tell you which method of solving you need to use to get the next square.
I'm on holiday for a few weeks so I've posted my latest version as described in #46. Anyone fancy coding the X-Wing strategy?
My solver uses bit masks. The following screenshot has debugging turned on so it shows more of the behind-the-scenes data.... (green means a 1x1 square is solved, red means still unsolved, the numbers in the parentheses are the remaining possibilities for that particular square (solved ones have a single number and 8 dots int the parentheses)).Quote:
Originally Posted by Merri
If I finally get the time to finish this then I'll do some benchmark tests and post them on this thread. If its fast enough then I'll optimise it a bit more and post the C code here too.
Does anyone know a good place to get deterministic and non-deterministic sudoku puzzles? I need a selection of both types in order to finish my algorithm.
Try Sudoku Programmers forum.
I wrote a QBasic program than instantly solves any Sudoku puzzle that has only one solution.
But to CREATE Sudoku puzzles is a REAL challenge. We could sell the results to newspapers. But they have to be symmetric and be rated according to difficulty. I long gave up on this. :(
Mac
Code:Started to post code but it was too long.
So here is a typical output:
38-4-95--1--6--39--92-3-----18---9-----9
81-----9----5---1-9-625-23-65--9965--4-73
Calling Function with above puzzle
Entering function at level 1
38-4-95--1--6--39--92-3-----18---9-----981-----9----5---1-9-625-23-65--9965--4-73
Locked candidate 2 in box 3
Locked candidate 5 in box 5
Locked candidate 4 in box 9
Hidden pair 18 in row 6
Hidden single 2 in col 7
Hidden single 7 in col 7
Hidden single 4 in col 7
r3c6 = 8
Hidden single 8 in row 2
Hidden single 8 in row 6
Hidden single 8 in col 8
Hidden single 8 in row 9
Hidden single 2 in row 9
r6c9 = 1
r8c1 = 7
r8c4 = 1
r9c7 = 1
r3c4 = 5
r7c2 = 4
r2c5 = 7
r2c6 = 2
r6c5 = 4
r7c1 = 8
r1c5 = 1
r1c8 = 6
r1c9 = 2
r2c2 = 5
r2c3 = 4
r3c1 = 6
r3c9 = 4
r4c5 = 5
r6c1 = 2
r1c3 = 7
r3c8 = 1
r4c1 = 4
r4c8 = 3
r5c1 = 5
r5c3 = 6
r5c8 = 4
r5c9 = 7
r4c9 = 6
r5c2 = 3
r6c2 = 7
r6c4 = 3
r6c6 = 6
r7c4 = 7
r7c6 = 3
r4c4 = 2
r4c6 = 7
Got 387419562154672398692538714418257936536981247279346851841793625723165489965824173
Returned from Function with following result
3874195621546723986925387144182579365369
81247279346851841793625723165489965824173
----------------------------------------------------------------------
Recursive Hierarchy Summary
---------------------------
Entering function at level 1
i submitted code that creates the puzzle number grid. The problem is coming up with the mask for it. I guess you could just keep a stored array of masks or randomly place 12 -14 squares in the upper left half of the grid (divided diagonally) and then mirror it on the lower right half. Then take that grid and check for multiple solutions with a brute force method. But to determine the actual difficulty you would loop through all of the logic methods like inthe link i posted earlier and the farther down the list it makes it, the harder the puzzle is.
Also please note that the code should be submitted in the other thread. This thread is for discussion only.
For a rotationally symmetrical grid, just remove pairs of numbers, one x spaces before the centre square and the other x spaces after the centre.
Reflective symmetry would be different of course.