Sudoku Collaboration Project: Discussion

[Merri]

Source code thread (http://www.vbforums.com/showthread.php?t=475397)


Original post:
It is easy to make a sudoku solver with a backtracker, ie. by guessing values and see if solving succeeds by throwing a guess. Now, how about making a solver that doesn't use these "easy" methods of solving at all? Although, I guess there is already atleast one algorithm that can solve any sudoku entirely without any guessing, but that doesn't mean we can't code it again.

The question is: do people want to go for a challenge (contest without a prize) or for a collaboration project, where people first make codes on their own and then start looking into which way it is good to go, suggesting ideas etc. freely, eventually aiming for a full sudoku solver with a nice interface and so on (so there would be other aspects to the solver other than just algorithms).

Challenge could be changed to a real contest if I can donate my own prize from the last sudoku solver contest: custom title with HTML formatting. I never claimed that prize.

[Atheist]

Sounds like a good idea. I vote for collaboration project:bigyello:

[Milk]

I've got some code that solves simple Sudokus by logic... I stopped developing it when saw it only ran at half the speed of your own (Merri's) brute force method. One word to finish, Kakuro!

Edit: Here is the very much work in progress (and dumped to sidelines) code so far, it's based on an older (one of my first in VB, so full of Variants) project which worked on the lines of logic first, brute force later when the odds are reduced. I'm sure it can be vastly improoved.
Option Explicit
Public AppPath As String
Public InPath As String
Public OutPath As String

Dim Found(80) As Byte
Dim Checked(80) As Byte
Dim RowFound(80) As Boolean
Dim ColumnFound(80) As Boolean
Dim BlockFound(80) As Boolean
Dim Impossible(728) As Boolean
Dim SqLookUp(35) As Byte
Dim QBlock(8) As Byte
Dim x9(80) As Integer
Dim Depth As Byte
Dim Solved As Boolean


Public Function LoadSudoku(FilePath As String) As Boolean
Dim i As Long, ii As Long
Dim BadFile As Boolean
Dim Buf(96) As Byte
i = FreeFile
Open FilePath For Binary As #i
If LOF(i) = 97 Then Get #i, 1, Buf Else BadFile = True
Close #i
If Not BadFile Then
For i = 0 To 96
If ii = 81 Then BadFile = True: Exit For
Select Case Buf(i)
Case 46: ii = ii + 1
Case 49 To 57: Found(ii) = Buf(i) - 48: ii = ii + 1
Case 10, 13
Case Else: BadFile = True: Exit For
End Select
Next i
End If
LoadSudoku = Not BadFile
End Function

Public Sub DrawSudoku(tgtpic As PictureBox, ByVal Size As Long)
Dim i As Long, ii As Long
Dim UnitSize As Long
Dim YAdjust As Long, XAdjust As Long


UnitSize = Size \ 9
YAdjust = UnitSize \ 10
XAdjust = UnitSize \ 20
tgtpic.FontSize = UnitSize / 20


tgtpic.Cls

For i = 0 To 9
Select Case i Mod 3
Case 0: tgtpic.DrawWidth = 2
Case 1: tgtpic.DrawWidth = 1
End Select
tgtpic.Line (0, i * UnitSize)-Step(Size, 0)
tgtpic.Line (i * UnitSize, 0)-Step(0, Size)
Next i

For i = 0 To 80
If Found(i) Then
tgtpic.CurrentY = (i \ 9) * UnitSize - YAdjust
tgtpic.CurrentX = (i Mod 9) * UnitSize - XAdjust
tgtpic.Print Found(i)
End If
Next i

If Depth > 0 Then
tgtpic.FontSize = UnitSize / 70

For i = 0 To 80
If Found(i) = 0 Then
For ii = x9(i) To x9(i) + 8
If Not Impossible(ii) Then
XAdjust = ((ii Mod 9) Mod 3) * (UnitSize / 3)
YAdjust = ((ii Mod 9) \ 3) * (UnitSize / 3)
tgtpic.CurrentY = (i \ 9) * UnitSize + YAdjust
tgtpic.CurrentX = (i Mod 9) * UnitSize + XAdjust
tgtpic.Print ii Mod 9 + 1
End If
Next ii
End If
Next i
End If

End Sub

Public Sub Solve()
Dim i As Long, ii As Long, iii As Long

Dim Row As Long, Column As Long, Block As Long, BlockPos As Long, BlockI As Long
Dim Ct As Long, V As Long, P As Long
Dim dct As Long

'QueryPerformanceCounter TStart
Depth = Depth + 1

'Debug.Print vbNewLine & Depth & ":-------------------------"
'1st Pass: Mark latest solved squares as exclusive to each row, column and block
For i = 0 To 80
If Checked(i) = 0 Then
If Found(i) Then
Row = (i \ 9)
Column = i Mod 9
Block = (i \ 27) * 27 + (Column \ 3) * 3
BlockPos = (i - Block)
BlockPos = (BlockPos Mod 9 + (BlockPos \ 9) * 3) * 4
'BlockI = (i \ 27) * 3 + (Column \ 3)

'RowFound(x9(Row) + Found(i) - 1) = True
'ColumnFound(x9(Column) + Found(i) - 1) = True
'BlockFound(x9(BlockI) + Found(i) - 1) = True

'mark Row
For ii = x9(Row) To x9(Row) + 8
If Found(ii) = 0 Then
Impossible(x9(ii) + Found(i) - 1) = True
End If
Next ii

'mark Column
For ii = Column To Column + 72 Step 9
If Found(ii) = 0 Then
Impossible(x9(ii) + Found(i) - 1) = True
End If
Next ii

'mark Block
For ii = BlockPos To BlockPos + 3
If Found(SqLookUp(ii) + Block) = 0 Then
Impossible(x9(SqLookUp(ii) + Block) + Found(i) - 1) = True
End If
Next ii

Checked(i) = Depth
End If
End If
Next i

'2nd Pass: Search each Row, Column and Block for exclusive numbers
'Search Rows
For i = 0 To 8 'Row index
For ii = 0 To 8 'Number
'If RowFound(x9(i) + ii) = False Then
Ct = 0
For iii = 0 To 8 'Column index
If Checked(x9(i) + iii) = 0 Then ' better higher
If Not Impossible(x9(x9(i) + iii) + ii) Then
Ct = Ct + 1
If Ct <> 1 Then Exit For
V = x9(i) + iii
End If
End If ' better higher
Next iii
'Else
'dct = dct + 1
'End If
If Ct = 1 Then Found(V) = ii + 1 ': Debug.Print "Row " & i, V, ii + 1
Next ii
Next i

'Search Columns
For i = 0 To 8 'Column index
For ii = 0 To 8 'Number
'If ColumnFound(x9(i) + ii) = False Then
Ct = 0
For iii = 0 To 8 'Row index
If Checked(x9(iii) + i) = 0 Then ' better higher
If Not Impossible(x9(x9(iii) + i) + ii) Then
Ct = Ct + 1
If Ct <> 1 Then Exit For
V = x9(iii) + i
End If
End If
Next iii
'End If
If Ct = 1 Then Found(V) = ii + 1 ': Debug.Print "Column " & i, V, ii + 1
Next ii
Next i

'Search Blocks
For i = 0 To 8 'Block index
For ii = 0 To 8 'Number
'If BlockFound(x9(i) + ii) = False Then
Ct = 0
For iii = 0 To 8 'Block Position
If Checked(QBlock(i) * 3 + QBlock(iii)) = 0 Then ' better higher
If Not Impossible(x9(QBlock(i) * 3 + QBlock(iii)) + ii) Then
Ct = Ct + 1
If Ct <> 1 Then Exit For
V = QBlock(i) * 3 + QBlock(iii)
End If
End If
Next iii
'End If
If Ct = 1 Then Found(V) = ii + 1 ': Debug.Print "Block " & i, V, ii + 1
Next ii
Next i

'x Pass: Searches for Squares with one possible answer
For i = 0 To 80
If Found(i) = 0 Then
Ct = 0
For ii = x9(i) To x9(i) + 8
If Not Impossible(ii) Then
Ct = Ct + 1
If Ct <> 1 Then Exit For
V = ii Mod 9 + 1
End If
Next ii
If Ct = 1 Then Found(i) = V ': Debug.Print "Unique", i, V
End If
Next i
'QueryPerformanceCounter TEnd
'Debug.Print dct
'FrmSudoku.Caption = GetTime(6)
End Sub
Public Sub FillLookups()
Dim i As Long

For i = 1 To 80
x9(i) = 9 * i
Next i

For i = 1 To 8
QBlock(i) = (i Mod 3) + x9(i \ 3)
Next i

SqLookUp(0) = 10
SqLookUp(1) = 11
SqLookUp(2) = 19
SqLookUp(3) = 20
SqLookUp(4) = 9
SqLookUp(5) = 11
SqLookUp(6) = 18
SqLookUp(7) = 20
SqLookUp(8) = 9
SqLookUp(9) = 10
SqLookUp(10) = 18
SqLookUp(11) = 19
SqLookUp(12) = 1
SqLookUp(13) = 2
SqLookUp(14) = 19
SqLookUp(15) = 20
SqLookUp(16) = 0
SqLookUp(17) = 2
SqLookUp(18) = 18
SqLookUp(19) = 20
SqLookUp(20) = 0
SqLookUp(21) = 1
SqLookUp(22) = 18
SqLookUp(23) = 19
SqLookUp(24) = 1
SqLookUp(25) = 2
SqLookUp(26) = 10
SqLookUp(27) = 11
SqLookUp(28) = 0
SqLookUp(29) = 2
SqLookUp(30) = 9
SqLookUp(31) = 11
SqLookUp(32) = 0
SqLookUp(33) = 1
SqLookUp(34) = 9
SqLookUp(35) = 10
main
End Sub

[Lord Orwell]

anyone with average (not beginning) program skill can write a solver. The question i have is: How do you generate a sudoku game in the first place? This might be a more useful question. I have no idea how to create one and i want to write a sudoku program. I have code to do it actually, but it is in xml.

[Phill64]

your signature is hypnotic.

[Lord Orwell]

i stole it from thehampsterdance.com

[Milk]

anyone with average (not beginning) program skill can write a solver. The question i have is: How do you generate a sudoku game in the first place? This might be a more useful question. I have no idea how to create one and i want to write a sudoku program. I have code to do it actually, but it is in xml.
I would have thought if you have code that can solve a Sudoku, then you pretty much have code that can produce a Sudoku. As long as the solving code can detect whether a starting grid has one unique answer or multiple answers then you have a puzzle generator.

One thing to be said about a combination Logic and Brute Force is that the simplest logic steps quickly reduce certain squares to 2 possible answers which means it becomes very easy to remember the point of first guess, and very easy to detect multiple solutions.

[Lord Orwell]

I thought so to, until i tried writing one today. I can't see what's wrong with it. Maybe you can look and tell me.
http://www.vbforums.com/showthread.php?p=2918549#post2918549

[Merri]

only ran at half the speed of your own (Merri's) brute force method
That is a good result for a non-brute force method, what I remember for looking at the logics is that most of them weren't easy to optimize for speed, often due to their complexity.

At the moment we aren't really looking at speed at all (if collaboration is to happen), most important is to find something that actually solves all the sudokus without brute force methods. Once we have that, there is something that could be analyzed to see if it can be made faster.

[Milk]

I've voted for collaboration. I'm not so sure pure logic provides the best way for a computer to solve Sudoku, but I like the idea of pinning down in code the different logical steps used when solving a puzzle by hand.

[Logophobic]

I'm interested, voting for collaboration.

[Merri]

Hmm, maybe we can include a sudoku generator into the project as well, so it could be a "complete" sudoku program? Thus those who are interested in coding a generator can do so.


I guess we have to standardize some features so that we can have modularity in the project and so that it is easy to combine code together. Already saying this as it begins to look like it will be a collaboration project that we do :)

So what we should use as our input and output format in the functions?

Suggestion 1: byte array?
Dim SudokuGrid(80) As Byte
Public Function SolveUsingXXX(ByRef SudokuGrid() As Byte) As Byte()

Suggestion 2: string?
Dim SudokuGrid As String * 81
Public Function SolveUsingXXX(ByRef SudokuGrid As String) As String

Suggestion 3: long array?
Dim SudokuGrid(80) As Long
Public Function SolveUsingXXX(ByRef SudokuGrid() As Long) As Long()


I think I could put together an initial file loading, saving and data displaying interface. I'm on a vacation now anyway :D

Another question: would it be a good idea to open another thread purely for code submissions and leave this one only for discussion?

[Milk]

Without getting pinned by any code is it not worth discussing the logical steps the code might have to make first.

*Mark each new solved square as being exclusive to it's row, column and block
*Search each row, column and block for any exclusive numbers, and mark as solved
*Search every unsolved square for any with one possible answer, and mark as solved

Here's a few more logical steps, which I find easier to describe with a picture.
The example has used the above logical steps to get where it has.

57698

*Circled in red are possible answers exclusive to a blocks sub row/column, these numbers can be discounted from the rest of the row/column.

*This in turn reveals some pairs (circled in blue) which are exclusive to the block, so all other possibilities within those squares can be discounted. Also happens in threes and more.

There must be more, any ideas?

[Merri]

I'm now coding an initial core project which will have enough features to get people started with the way they want to go. I'm doing conversion functions which will convert from strings to byte or long array and vice versa.

I'm also adding bit constants and helper arrays.

String can hold numbers from 0 to 9.
Byte array can hold numbers from 0 to 9.
Long array holds data as bit representation, where 0 = all bits active, 1 = bit #1 active etc.

I have to see what I should include from my own old contest project, I guess adding too much isn't a great idea. However, I want to make the core flexible enough so that everyone could code as they want and prefer to.


I'll open another thread for code and sudoku file submissions when I have the initial project done. Hopefully that'll be done in a few hours.

[Merri]

I now submitted the core project in to the new source code thread (http://www.vbforums.com/showthread.php?t=475397). If there is any code you wish to include into the core (such as generic helper functions that others may find useful), let me know. Suggestions are welcome of course.

For the core, one of the current big questions is how the generator modules should be implemented. Because I believe people who make generators want to also give input parameters to those, so this leads me to think that the core project should be flexible enough to be able to automatically give a proper interface for the generator modules.


This is the beginning of the collaboration project. I leave the poll open, I probably remove it sometime next month.

[NotLKH]

Building a solver is an interesting challege.

And, as pointed out, building a Generator is also an interesting puzzle in and of itself.

The logic overlaps.

There are articles that describe how to generate sudoku, but I havn't looked for any lately.

A while back, when I did google, they all seemed to be non-programmic in philosophy.

"Place a number in a square, then go along the row/Column, and do somethingsomething and/or other>..."

To create a programmic sudoku generator, in a logical fashion, starting by creating a matrix odf numbers such that they conform to the rules of sudoku, requires iteration. Cell X from 1 to 9, per cell, while you are inspecting to see if you've created any non-sudoku condition.

Then, you need to figure out what cells to "blank". {at least thats how I did it}. at this point I randomely selecetd a set of 60 or so cells to "blank", and see if my solver could solve it. if so, then I would blank out each unblanked remainging cell, and see which I could still solve. of those that I could still solve, I'd blank out another, and so on, until my solver failed on the one remaining generation.

It worked, but still...

with an iteration method, then you insure a single sudoku solution pattern is NOT that much different from the next one you solve.

Which is great in that, once you've generated one sudoku, you are almost guarenteed that the next generated one will be in milliseconds in coming.

However, it also means that 90+% of it will be identical to the last one generated.

So, the succesful Sudoku Generater MUST:

Use a seeding method that will guaurentee that the next sudoku is largely different from the last.

and

the seeding method will still allow iteration such that all sudokus will still be eventually generated.

At least, that would be my philosophy, if I were to build a proper sudoku generator.

[Lord Orwell]

I think i will fill in a known sudoku grid, then randomly flip/mirror/rotate it, swap sections of 3 horiz or vertically, then swap random lines around inside each set of 3 lines. This should thoroughly scramble the resulting grid.

NotLKH, it sounds like your solver might fail on the sudokus that make you guess a number and eventually you figure out it is wrong and you try a 2nd number. They are high-level puzzles and very time-consuming. I believe from studying that to test a sudoku you almost have to brute-force it after you create it to make sure it only has one solution. A solver that solves by logic might not tell you that.

[wossname]

Have you guys considered writing the core algorithm into a C dll for absolute speed? That way you can use inline ASM to optimise tight loops. I offer my services to this end if you like that idea. If so send me a PM.

ps. it would be a good idea to put the new puzzle generator code into such a dll too. Then all the core code is in the same place.

[Merri]

I uploaded a new version of the core project as there was a major bug in SudokuStringToByteArray and SudokuByteArrayToString. So this is how the three different data formats work now:
String: 81 numbers as characters "0", "1", "2", "3", "4", "5", "6", "7", "8" or "9"
Byte array: 81 numbers as values 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9
Long array: 81 numbers as active bits: 111111111, 000000001, 000000010, 000000100, 000001000, 000010000, 000100000, 001000000, 010000000, 100000000


I also included my old contest code for sample solving and for counting the number of solutions (and thus validating that the numbers on the screen actually are a real sudoku).

[Milk]

Okay, so I'm just implementing my half working code module into the project...
Stupid question No. 1) The Codewrapper functions are passed a board and return a board. Can I work the original passed board or must it be preserved?

[Merri]

You can work on whatever is passed as you wish, you can change it as much as you like. Undo and redo mechanism works automatically and you don't need to care about it.

The only important thing is that you output the board from the wrapper as a string of 81 characters.


Also, for general knowledge, it doesn't matter if the sudoku has been completed or not. This makes it possible to create modules that do just one kind of algorithm.


wossname: if you want to, you can create an ActiveX DLL using language of your choice, it is possible to wrap it in to the project just like any other code as long as it is possible to call the DLL from VB6 :)

[wossname]

ActiveX is an unnecessary layer. Just a plain vanilla C DLL would be best.

I'll wait a while until you've settled upon a stable solving algorithm then I can port it.

[Milk]

I've a simple help sub I'd like to add to the 'ModHelpers' module, it just dumps a sudoku image (like the one in post #13 (http://www.vbforums.com/showpost.php?p=2919380&postcount=13)) to an object supporting draw and print methods. I'm using it at the point where my logic function fails (i.e. can't find any more numbers), I find it useful for debugging as it shows what numbers my algorithm has discounted. If people are interested I'll modify it to take a byte array (to show the solved squares) and bitset long array (to show the possible solutions).

[Merri]

Sure, go ahead. Send the module to me via pm or attach it in the source code thread so I can update the core project.

[Milk]

:) I'll send it tomorrow, I need to tweak it to comply and right now bed is a bigger priority.

[Lord Orwell]

I guess your generation code speed must vary greatly depending on how you are doing it then. I created a grid and randomly rearranged the numbers (keeping it a legit sudoku) and the new grid appears as soon as i click the button with no noticable delay.

[Merri]

Well, this has been quiet. My vacation didn't start afterall, a slight misunderstanding, so now I'm doing some extra hours. Thus no time to push things with this project more than:

Nobody willing to do some of the basic solving algorithms? One can find already working code, JavaScript examples and so on easily. Shouldn't be too hard to make those in :)

[Lord Orwell]

Do you have the code to generate the grid yet? I wrote an algorithm in both vb6 and vb2005 to generate the initial filled-in puzzle. I don't have anything to create the mask off of it though. FYI it doesn't generate the way i said above. I like to think it is generating it the same way a human would. All the ones, then the twos, etc. It uses a byte array (8, 8) and a couple of other worker arrays inside the function. It uses a function and a sub because of the way it is designed.

[Merri]

No, there isn't a generator code or interface for multiple of them (as that is the idea, to have different kinds of implementations: with generators I'd believe every one is very different).

As for how many functions or subs you have, it won't really matter in the end. You can have your own code the way you want to, there will be only some extra requirements on formatting the return value. Although this is missing at this point as I haven't made the generator interface.

[Milk]

Just to say I've a solving algorithm I'm working up. I'm away for a few days but the beta should be postable next week shortly after I get back.

[tr333]

A quick search on google found a three line sudoku solver (http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html). It was written in Perl so it's not the easiest code to understand.

[Milk]

Obfuscation-tastic :)... Not that I can read it that well but I'm pretty sure it's a Brute force method.

Here's (http://www.sudokusolver.co.uk/solvemethods.html) a nice website dedicated to logic solving.

[wossname]

What sort of solve times are you guys getting? (eg. in milliseconds taken to solve an average puzzle). Let me know your CPU speeds too please. I want to know if my algorithm needs to be faster in order to be of any use.

[Lord Orwell]

That 3-line sudoku solver is linux only, and that is because it isn't really 3 lines. GREP is a binary-search program, so you would have to implement a similar program in your code.

[Milk]

That 3-line sudoku solver is linux only, and that is because it isn't really 3 lines. GREP is a binary-search program, so you would have to implement a similar program in your code.Regardless, as far as I can tell , the code makes a guess and then recurses, if this fails it tries the next number and recurses again... This is invalid to this project as (at least I think) this is about finding code that uses pure logic and never has to make a guess.

Although I think it could be argued that a certain amount of guesswork might also be considered logic, I think we should leave that until we have come up with some of the code for the layers of logic (theres at least 7) that could be applied first.

At first I thought this was kind of pointless (Brute force is easy and it always works), but if one was going about making a Sudoku creator and you have a good logic solver you effectively have a good way of grading any creations by scoring the logic steps used. Brute force methods can't really tell how hard a Sudoku is.

[Merri]

Yeah, there is atleast the "if I do this, will the sudoku remain valid?" logic. It isn't really brute force, because it doesn't recurse/return back to another state more than that one step, but it does check numbers that are in certain order and then see which ones of them do work. In the long run this isn't very fast way to go, but it is sort of a human way of solving; thus something that might be helpful for a player or for judging hardness.

No, don't ask me any real life samples of this, this was something I read through and thought over two years ago :) But I'd assume this isn't one of the easiest human way of solving logics to code.

[Milk]

<snip> ...But I'd assume this isn't one of the easiest human way of solving logics to code.Well I'm all posts and no code ATM so perhaps I can't talk but, even my crappy solver above can get at least some squares in the hardest Sudokus down to two possible answers. In the Human situation I could take a guess, apply my crappy logic, and write all the resulting numbers in (with say a dot so i can erase it later) and then prove it valid or invalid. Is that a valid point to apply the guess code? Surely without further logic code I'm only really able to tell if it's easy or hard. With more logical steps at least I know I had to apply step B three times and C twice and then F only once before I had to take a fifty fifty guess (if i have to take a guess at all). I'd then get a much more accurate picture of the difficulty.

Btw. I'm only working on step B atm, just in case I'm sounding cocky

[Lord Orwell]

Has anyone been here?http://www.scanraid.com/sudoku.htm
It is an on-line sudoku solver that doesn't use brute-force. It has a description of every known logic-way of solving a sudoku. I am sure with a little effort, we could recreate each of the methods in separate subroutines. Perhaps we could parcel them out to individual collaberators to work on?
His solver has yet to fail, and the methods i would like to implement.

[Milk]

Well from that link I've worked up test 1 and 2 as my basic logic and I'm working test 6 (Box Line Reduction Strategy (a.k.a. Intersection Removal)) as the one I want to post later this week (when I've got some time again with my IDE)

[wild_bill]

Should the solver be able to handle 16X16 puzzles, as well as 9x9 puzzles?

[Merri]

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.

[Milk]

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.

[Merri]

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 (http://kontu.info/)).

[Lord Orwell]

Interesting site. I can't read any of it, but i like the layout. What is the Browser icons represent? Compatibility?

[Merri]

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).

[Milk]

Should we set some time goals for providing solver functions so there is something to aim to?We should also define these functions. I've been looking at Andrew Stuart's site (http://www.scanraid.com/sudoku.htm) which Lord Orwell linked to. I think it provides an excellent list of strategies, some 36 in all, only 2 of which involve guessing.

For my part I'm just tidying up an improved algorithm (I'll post it later this week) which now covers...
Singles in a row/column/block Naked Pairs/Triples/Quads (all combinations) Hidden Pairs/Triples (all combinations) Block/line ReductionThis now solves about 90% of the minimum set or Sudokus and around 10% of the hard.

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

[Merri]

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.

[Lord Orwell]

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.

[Milk]

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?

[wossname]

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).

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)).

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.

[wossname]

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.

[Merri]

Try Sudoku Programmers (http://www.setbb.com/phpbb/?mforum=sudoku) forum.

[Mr.Mac]

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


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

[Lord Orwell]

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.

[wossname]

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.