Sudoku Collaboration Project: Discussion

[Merri]

Source code thread


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

[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.p...49#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

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.



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