Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Canonical sudoku algorithm?
Goto page Previous  1, 2, 3, 4, 5, 6  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Jan 14, 2007 11:28 pm    Post subject: Reply with quote

Here is some canonicalization code in VB.Net

How to use:

1. create a New Grid(dt As String) : dt is a string with 81 digits. Empty cell may be any character.
2. get Grid.CanonicalGrid.Text to retrieve the canonical form.

How it works:

1. Rearrange the clue pattern to find the bottom-most and right-most configuration.
2. Relabel the clues from top to bottom, left to right.

When at any stage equal alternatives are found, the program branches to investigate all alternatives. Boxes are not defined in the code, but chutes are. The Fixed flags control what rearrangements can still be made at any stage.

The code is not optimized, but it runs pretty fast.

The supporting classes:

Code:
Public Class Cell
   Public Index As Integer
   Public Digit As Integer
   Public OldDigit As Integer

   Public Sub New(ByVal dg As Integer, ByVal ix As Integer, ByVal gd As Grid)
      Me.Index = ix
      Me.Digit = dg
      Dim Row As Sector = gd.Rows(ix \ 9)
      Row.Cells(ix Mod 9) = Me
      Dim Col As Sector = gd.Columns(ix Mod 9)
      Col.Cells(ix \ 9) = Me
   End Sub

End Class

Public Class Sector
   Public Type As SectorType
   Public Index As Integer
   Public Chute As Chute
   Public CrossChutes(2) As Chute
   Public Fixed As Boolean
   Public Cells(8) As Cell

   Public Sub New(ByVal tp As SectorType, ByVal ix As Integer, ByVal ch As Chute, ByVal cs() As Chute, ByVal fx As Boolean)
      Me.Type = tp
      Me.Index = ix
      Me.Chute = ch
      Me.Fixed = fx
      Me.CrossChutes(0) = cs(0)
      Me.CrossChutes(1) = cs(1)
      Me.CrossChutes(2) = cs(2)
      Me.Chute.Sectors(Me.Index Mod 3) = Me
   End Sub

   Public ReadOnly Property LowestPermutation() As Integer
      Get
         Dim g1 As Integer = Me.CrossChutes(0).LowestPermutation(Me.Index)
         Dim g2 As Integer = Me.CrossChutes(1).LowestPermutation(Me.Index)
         Dim g3 As Integer = Me.CrossChutes(2).LowestPermutation(Me.Index)

         If Not Me.CrossChutes(0).Fixed Then If g1 > g2 Then Me.Swap(g1, g2)
         If Not Me.CrossChutes(2).Fixed Then If g2 > g3 Then Me.Swap(g2, g3)
         If Not Me.CrossChutes(0).Fixed Then If g1 > g2 Then Me.Swap(g1, g2)

         Return (g1 * 100) + (g2 * 10) + g3
      End Get
   End Property

   Private Sub Swap(ByRef d1 As Integer, ByRef d2 As Integer)
      Dim ds As Integer = d1
      d1 = d2
      d2 = ds
   End Sub
End Class

Public Enum SectorType
   Row
   Column
End Enum

Public Class Chute
   Public Sectors(2) As Sector
   Public Fixed As Boolean

   Public Sub New(ByVal fx As Boolean)
      Me.Fixed = fx
   End Sub

   Public Function FillCount(ByVal index As Integer) As Integer
      Dim rs As Integer = 0
      If Me.Sectors(0).Cells(index).Digit > 0 Then rs += 1
      If Me.Sectors(1).Cells(index).Digit > 0 Then rs += 1
      If Me.Sectors(2).Cells(index).Digit > 0 Then rs += 1
      Return rs
   End Function

   Public Function LowestPermutation(ByVal index As Integer) As Integer

      Dim d0 As Integer = 0
      Dim d1 As Integer = 0
      Dim d2 As Integer = 0
      Dim dt As Integer

      If Me.Sectors(0).Cells(index).Digit > 0 Then d0 = 1
      If Me.Sectors(1).Cells(index).Digit > 0 Then d1 = 1
      If Me.Sectors(2).Cells(index).Digit > 0 Then d2 = 1
      If (d0 > d1) And Not Me.Sectors(0).Fixed Then
         dt = d0
         d0 = d1
         d1 = dt
      End If
      If (d1 > d2) And Not Me.Sectors(2).Fixed Then
         dt = d1
         d1 = d2
         d2 = dt
      End If
      If (d0 > d1) And Not Me.Sectors(0).Fixed Then
         dt = d0
         d0 = d1
         d1 = dt
      End If
      Return (d0 * 4) + (d1 * 2) + (d2)
   End Function
End Class


The Grid class:

Code:
Public Class Grid
   Public Towers(2) As Chute
   Public Floors(2) As Chute
   Public Rows(8) As Sector
   Public Columns(8) As Sector
   Public Cells(80) As Cell
   Public BrancheIndex As Integer
   Public Branches As ArrayList

   Public Sub New(ByVal gd As Grid, ByVal br As ArrayList)
      br.Add(Me)
      For n As Integer = 0 To 2
         Me.Towers(n) = New Chute(gd.Towers(n).Fixed)
         Me.Floors(n) = New Chute(gd.Floors(n).Fixed)
      Next
      For n As Integer = 0 To 8
         Me.Rows(n) = New Sector(SectorType.Row, n, Me.Floors(n \ 3), Me.Towers, gd.Rows(n).Fixed)
         Me.Columns(n) = New Sector(SectorType.Column, n, Me.Towers(n \ 3), Me.Floors, gd.Columns(n).Fixed)
      Next
      For n As Integer = 0 To 80
         Me.Cells(n) = New Cell(gd.Cells(n).Digit, n, Me)
      Next
   End Sub

   Public Sub New(ByVal dt As String)
      Me.BrancheIndex = -1
      For n As Integer = 0 To 2
         Me.Towers(n) = New Chute(False)
         Me.Floors(n) = New Chute(False)
      Next
      For n As Integer = 0 To 8
         Me.Rows(n) = New Sector(SectorType.Row, n, Me.Floors(n \ 3), Me.Towers, False)
         Me.Columns(n) = New Sector(SectorType.Column, n, Me.Towers(n \ 3), Me.Floors, False)
      Next
      For n As Integer = 0 To 80
         If dt Is Nothing Then
            Me.Cells(n) = New Cell(0, n, Me)
         Else
            Me.Cells(n) = New Cell("123456789".IndexOf(dt.Chars(n)) + 1, n, Me)
         End If
      Next
      Me.Branches = New ArrayList
      Me.Optimize()
      For n As Integer = 0 To Me.Branches.Count - 1
         CType(Me.Branches(n), Grid).BrancheIndex = n
      Next
   End Sub

   Public ReadOnly Property BranchesCount() As Integer
      Get
         Return Me.Branches.Count
      End Get
   End Property

   Public ReadOnly Property CanonicalGrid() As Grid
      Get
         If Me.Branches.Count = 0 Then Return Nothing
         Dim gd As Grid = CType(Me.Branches(0), Grid)
         For n As Integer = 1 To Me.Branches.Count - 1
            If gd.CompareTo(Me.Branches(n)) > 0 Then gd = Me.Branches(n)
         Next
         Return gd
      End Get
   End Property

   Public ReadOnly Property Text() As String
      Get
         Dim rs As String = String.Empty
         For Each ce As Cell In Me.Cells
            rs &= ce.Digit.ToString
         Next
         Return rs
      End Get
   End Property

   Public Function CompareTo(ByVal gd As Grid) As Integer
      Dim rs As Integer
      For n As Integer = 0 To 80
         If Me.Cells(n).Digit > 0 Then
            If gd.Cells(n).Digit = 0 Then Return 1
         Else
            If gd.Cells(n).Digit > 0 Then Return -1
         End If
      Next
      For n As Integer = 0 To 80
         rs = Me.Cells(n).Digit.CompareTo(gd.Cells(n).Digit)
         If rs <> 0 Then Return rs
      Next
      Return 0
   End Function

   Private Sub Optimize()
      Dim bv As Integer = Integer.MaxValue
      Dim bs As New ArrayList

      For n As Integer = 0 To 8
         Dim rv As Integer = Me.Rows(n).LowestPermutation
         If rv < bv Then
            bv = rv
            bs.Clear()
            bs.Add(Me.Rows(n))
         ElseIf rv = bv Then
            bs.Add(Me.Rows(n))
         End If
      Next

      For n As Integer = 0 To 8
         Dim rv As Integer = Me.Columns(n).LowestPermutation
         If rv < bv Then
            bv = rv
            bs.Clear()
            bs.Add(Me.Columns(n))
         ElseIf rv = bv Then
            bs.Add(Me.Columns(n))
         End If
      Next

      For Each sc As Sector In bs
         Dim gd As New Grid(Me, Me.Branches)
         If sc.Type = SectorType.Column Then gd.SwapRowsCols()
         gd.MoveRow(sc.Index, 0)
         gd.Floors(0).Fixed = True
         gd.Rows(0).Fixed = True
         gd.OptimizeRow0Fixed(Me.Branches)
      Next

   End Sub

   Private Sub MoveRow(ByVal nf As Integer, ByVal nt As Integer)
      If nf = nt Then Return
      Dim gf As Integer = nf \ 3
      Dim gt As Integer = nt \ 3
      If gf <> gt Then
         Me.SwapFloors(gf, gt)
         nf = (gt * 3) + (nf Mod 3)
      End If
      If nf = nt Then Return
      Me.SwapRows(nf, nt)
   End Sub

   Private Sub OptimizeRow0Fixed(ByVal br As ArrayList)
      Me.OptimizeRow(0)
      Dim rp1 As Integer = Me.Rows(1).LowestPermutation
      Dim rp2 As Integer = Me.Rows(2).LowestPermutation
      If rp1 < rp2 Then
         Me.OptimizeFloor0Fixed(br)
      ElseIf rp2 < rp1 Then
         Me.SwapRows(1, 2)
         Me.OptimizeFloor0Fixed(br)
      Else
         br.Remove(Me)
         Dim gd As Grid
         gd = New Grid(Me, br)
         gd.OptimizeFloor0Fixed(br)
         gd = New Grid(Me, br)
         gd.SwapRows(1, 2)
         gd.OptimizeFloor0Fixed(br)
      End If
   End Sub

   Private Sub OptimizeFloor0Fixed(ByVal br As ArrayList)
      Me.OptimizeRow(1)
      Me.OptimizeRow(2)

      Dim bv As Integer = Integer.MaxValue
      Dim bs As New ArrayList

      For n As Integer = 3 To 8
         Dim rv As Integer = Me.Rows(n).LowestPermutation
         If rv < bv Then
            bv = rv
            bs.Clear()
            bs.Add(Me.Rows(n))
         ElseIf rv = bv Then
            bs.Add(Me.Rows(n))
         End If
      Next

      If bs.Count = 1 Then
         Dim sc As Sector = bs(0)
         Me.MoveRow(sc.Index, 3)
         Me.Floors(1).Fixed = True
         Me.Rows(3).Fixed = True
         Me.OptimizeRow3Fixed(br)
      Else
         br.Remove(Me)

         For Each sc As Sector In bs
            Dim gd As New Grid(Me, br)
            gd.MoveRow(sc.Index, 3)
            gd.Floors(1).Fixed = True
            gd.Rows(3).Fixed = True
            gd.OptimizeRow3Fixed(br)
         Next
      End If

   End Sub

   Private Sub OptimizeRow3Fixed(ByVal br As ArrayList)

      Me.OptimizeRow(3)
      Dim rp1 As Integer = Me.Rows(4).LowestPermutation
      Dim rp2 As Integer = Me.Rows(5).LowestPermutation
      If rp1 < rp2 Then
         Me.OptimizeFloor1Fixed(br)
      ElseIf rp2 < rp1 Then
         Me.SwapRows(4, 5)
         Me.OptimizeFloor1Fixed(br)
      Else
         br.Remove(Me)
         Dim gd As Grid
         gd = New Grid(Me, br)
         gd.OptimizeFloor1Fixed(br)
         gd = New Grid(Me, br)
         gd.SwapRows(4, 5)
         gd.OptimizeFloor1Fixed(br)
      End If

   End Sub

   Private Sub OptimizeFloor1Fixed(ByVal br As ArrayList)
      Me.OptimizeRow(4)
      Me.OptimizeRow(5)

      Dim bv As Integer = Integer.MaxValue
      Dim bs As New ArrayList

      For n As Integer = 6 To 8
         Dim rv As Integer = Me.Rows(n).LowestPermutation
         If rv < bv Then
            bv = rv
            bs.Clear()
            bs.Add(Me.Rows(n))
         ElseIf rv = bv Then
            bs.Add(Me.Rows(n))
         End If
      Next

      If bs.Count = 1 Then
         Dim sc As Sector = bs(0)
         Me.MoveRow(sc.Index, 6)
         Me.Rows(6).Fixed = True
         Me.OptimizeRow6Fixed(br)
      Else
         br.Remove(Me)

         For Each sc As Sector In bs
            Dim gd As New Grid(Me, br)
            gd.MoveRow(sc.Index, 6)
            gd.Rows(6).Fixed = True
            gd.OptimizeRow6Fixed(br)
         Next
      End If

   End Sub

   Private Sub OptimizeRow6Fixed(ByVal br As ArrayList)

      Me.OptimizeRow(6)
      Dim rp1 As Integer = Me.Rows(7).LowestPermutation
      Dim rp2 As Integer = Me.Rows(8).LowestPermutation
      If rp1 < rp2 Then
         Me.OptimizeFloor2Fixed()
      ElseIf rp2 < rp1 Then
         Me.SwapRows(7, 8)
         Me.OptimizeFloor2Fixed()
      Else
         br.Remove(Me)
         Dim gd As Grid
         gd = New Grid(Me, br)
         gd.OptimizeFloor2Fixed()
         gd = New Grid(Me, br)
         gd.SwapRows(7, 8)
         gd.OptimizeFloor2Fixed()
      End If

   End Sub

   Private Sub OptimizeFloor2Fixed()
      Me.OptimizeRow(7)
      Me.OptimizeRow(8)

      Dim DigitMap(9) As Integer
      Dim LastTarget As Integer = 0
      For n As Integer = 0 To 80
         If Me.Cells(n).Digit > 0 Then
            Dim dg As Integer = Me.Cells(n).Digit
            If DigitMap(dg) = 0 Then
               LastTarget += 1
               DigitMap(dg) = LastTarget
            End If
            Me.Cells(n).Digit = DigitMap(dg)
         End If
      Next
   End Sub

   Private Sub OptimizeRow(ByVal n As Integer)

      If Not Me.Towers(0).Fixed Then
         If Me.Towers(0).FillCount(n) > Me.Towers(1).FillCount(n) Then Me.SwapTowers(0, 1)
      End If
      If Not Me.Towers(2).Fixed Then
         If Me.Towers(1).FillCount(n) > Me.Towers(2).FillCount(n) Then Me.SwapTowers(1, 2)
      End If
      If Not Me.Towers(0).Fixed Then
         If Me.Towers(0).FillCount(n) > Me.Towers(1).FillCount(n) Then Me.SwapTowers(0, 1)
      End If

      If Me.Towers(0).FillCount(n) <> Me.Towers(1).FillCount(n) Then Me.Towers(0).Fixed = True
      If Me.Towers(2).FillCount(n) <> Me.Towers(1).FillCount(n) Then Me.Towers(2).Fixed = True
      Me.Towers(1).Fixed = Me.Towers(0).Fixed And Me.Towers(2).Fixed

      If Me.Towers(0).FillCount(n) > 0 Then Me.OptimizeTower(Me.Rows(n), 0, 1, 2)
      If Me.Towers(1).FillCount(n) > 0 Then Me.OptimizeTower(Me.Rows(n), 3, 4, 5)
      If Me.Towers(2).FillCount(n) > 0 Then Me.OptimizeTower(Me.Rows(n), 6, 7, 8)

   End Sub

   Private Sub OptimizeTower(ByVal rw As Sector, ByVal c0 As Integer, ByVal c1 As Integer, ByVal c2 As Integer)
      If Not Me.Columns(c0).Fixed Then
         If (rw.Cells(c0).Digit > 0) And (rw.Cells(c1).Digit = 0) Then Me.SwapColumns(c0, c1)
      End If
      If Not Me.Columns(c2).Fixed Then
         If (rw.Cells(c1).Digit > 0) And (rw.Cells(c2).Digit = 0) Then Me.SwapColumns(c1, c2)
      End If
      If Not Me.Columns(c0).Fixed Then
         If (rw.Cells(c0).Digit > 0) And (rw.Cells(c1).Digit = 0) Then Me.SwapColumns(c0, c1)
      End If

      If (rw.Cells(c0).Digit = 0) And (rw.Cells(c1).Digit > 0) Then Me.Columns(c0).Fixed = True
      If (rw.Cells(c2).Digit > 0) And (rw.Cells(c1).Digit = 0) Then Me.Columns(c2).Fixed = True
      Me.Columns(c1).Fixed = Me.Columns(c0).Fixed And Me.Columns(c2).Fixed
   End Sub

   Private Sub MoveColumn(ByVal nf As Integer, ByVal nt As Integer)
      If nf = nt Then Return
      Dim gf As Integer = nf \ 3
      Dim gt As Integer = nt \ 3
      If gf <> gt Then
         Me.SwapTowers(gf, gt)
         nf = (gt * 3) + (nf Mod 3)
      End If
      If nf = nt Then Return
      Me.SwapColumns(nf, nt)
   End Sub

   Private Sub SwapRows(ByVal r1 As Integer, ByVal r2 As Integer)
      For n As Integer = 0 To 8
         Me.Rows(r1).Cells(n).OldDigit = Me.Rows(r1).Cells(n).Digit
         Me.Rows(r1).Cells(n).Digit = Me.Rows(r2).Cells(n).Digit
         Me.Rows(r2).Cells(n).Digit = Me.Rows(r1).Cells(n).OldDigit
      Next
      Dim f1 As Boolean = Me.Rows(r1).Fixed
      Me.Rows(r1).Fixed = Me.Rows(r2).Fixed
      Me.Rows(r2).Fixed = f1
   End Sub

   Private Sub SwapColumns(ByVal r1 As Integer, ByVal r2 As Integer)
      For n As Integer = 0 To 8
         Me.Columns(r1).Cells(n).OldDigit = Me.Columns(r1).Cells(n).Digit
         Me.Columns(r1).Cells(n).Digit = Me.Columns(r2).Cells(n).Digit
         Me.Columns(r2).Cells(n).Digit = Me.Columns(r1).Cells(n).OldDigit
      Next
      Dim f1 As Boolean = Me.Columns(r1).Fixed
      Me.Columns(r1).Fixed = Me.Columns(r2).Fixed
      Me.Columns(r2).Fixed = f1
   End Sub

   Private Sub SwapFloors(ByVal n1 As Integer, ByVal n2 As Integer)
      For i As Integer = 0 To 2
         Me.SwapRows(n1 * 3 + i, n2 * 3 + i)
      Next
   End Sub

   Private Sub SwapTowers(ByVal n1 As Integer, ByVal n2 As Integer)
      For i As Integer = 0 To 2
         Me.SwapColumns(n1 * 3 + i, n2 * 3 + i)
      Next
   End Sub

   Private Sub SwapRowsCols()
      For n As Integer = 0 To 80
         Me.Cells(n).OldDigit = Me.Cells(n).Digit
      Next
      For n As Integer = 0 To 8
         For p As Integer = 0 To 8
            Me.Columns(n).Cells(p).Digit = Me.Rows(n).Cells(p).OldDigit
         Next
      Next
   End Sub

End Class


Disclaimer: This code serves no particular purpose. No comment is included.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
holdout

Joined: 30 Dec 2006
Posts: 8
:
Location: Bowie, MD (USA)

Items
PostPosted: Tue Jan 16, 2007 12:55 am    Post subject: Row-Minimal Standard Form Reply with quote

Some use "canonicalization" to refer to the transformation of a Soduko puzzle to some unique standard form. Other use the term in reference to the completion of a puzzle to standard form.

I don't believe it really matters, as the accepted transformation operations are the same. The uncompleted puzzle just has a lot of zeros (unknowns).

I've just finished a C++ routine which does both, and at a rate of about 25,000 transformations/second on a 2.1 Ghz computer.

The "standard form" I've chosen to implement transforms the input into the smallest 81-digit number possible.

The code, with a lot of comment, follows:

[Ruud: Code is corrupted when copied into this post. You can find the source file here]

Message to RUUD: I've copied and tested the (above) code. It seems to work just fine. Thank you.


Last edited by holdout on Thu Jan 18, 2007 9:42 pm; edited 4 times in total
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Tue Jan 16, 2007 5:16 am    Post subject: Re: Row-Minimal Standard Form Reply with quote

holdout wrote:

The code, with a lot of comment, follows:

the compile crapped out here:
Code:

for ( pass=rownum=0; rownum <9>= 3)

also, did you run your time trial on one puzzle X times?
Back to top
View user's profile Send private message Visit poster's website
holdout

Joined: 30 Dec 2006
Posts: 8
:
Location: Bowie, MD (USA)

Items
PostPosted: Tue Jan 16, 2007 3:57 pm    Post subject: Re: Row-Minimal Standard Form Reply with quote

To: gsf

1. Yes, compile fails at the point you quote. It must have happened in the "copy" process in preparing the document. When I deleted the code in the posting and replaced it with a fresh copy, the same errors popped-up. I will be contacting the site administrator.

2. No, I did not run time trials on one puzzle X times. Surprised
I did use, however, one million independent puzzles 82 times each.
Each time I started with a valid full puzzle. Then I randomly deleted one clue each time. So, most of the time I was using puzzles with multiple solutions. Of course, this must happen when there are less than 17 clues.

I think this explains to some degree why I got a slightly better performance in the time trials on 17-clue puzzles than with the Royle puzzle set (28036 vs. 25053 puzzles per second). The test procedure most likely generated more clumps of zeros than the Royle set.

3. Tks for giving it a try. Maybe the system administrator can help.


Last edited by holdout on Tue Jan 16, 2007 5:30 pm; edited 2 times in total
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Tue Jan 16, 2007 5:10 pm    Post subject: Re: Row-Minimal Standard Form Reply with quote

holdout wrote:
To: gsf
2. No, I did not run time trials on one puzzle X times. Surprised
I did use, however, one million independent puzzles 82 times each.
Each time I started with a valid full puzzle. Then I randomly deleted one clue. So, criticize if you wish, most of the time I was using puzzles with multiple solutions. Of course, this must happen when there are less than 17 clues.

I'm interested in reproducability
how about a trial on real data, say 30 copies of gordon royle's 17's
Back to top
View user's profile Send private message Visit poster's website
holdout

Joined: 30 Dec 2006
Posts: 8
:
Location: Bowie, MD (USA)

Items
PostPosted: Tue Jan 16, 2007 5:43 pm    Post subject: Re: Row-Minimal Standard Form Reply with quote

gsf wrote:

I'm interested in reproducability how about a trial on real data, say 30 copies of gordon royle's 17's


As requested (my output is followed by Gordon's input):
Code:

000000001000000020000003000000040500006000300007810000010020004030000070950000000 000000010400000000020000000000050407008000300001090000300400200050100000000806000 00001
000000001000000020000003000000040500006000300007180000010020004030000070950000000 000000010400000000020000000000050604008000300001090000300400200050100000000807000 00002
000000000000000012000034000000005306007000000021080000050100800400000000600700000 000000012000035000000600070700000300000400800100000000000120000080000040050000600 00003
000000000000001002034000050000000360000070000100008000000002001056300000070000008 000000012003600000000007000410020000000500300700000600280000040000300500000000000 00004
000000001000000023004005000000002000010000400360070000000610000005000800007030000 000000012008030000000000040120500000000004700060000000507000300000620000000100000 00005
000000001000000023004005000000004607010060000020000000000103000006000800900000500 000000012040050000000009000070600400000100000000000050000087500601000300200000000 00006
000000001000000023004005000000010000000304600072000800000800000060009500300000000 000000012050400000000000030700600400001000000000080000920000800000510700000003000 00007
000000001000002030004050000000000006070008400290007000000060090000140000700000000 000000012300000060000040000900000500000001070020000000000350400001400800060000000 00008
000000001000000023004005000000006500020070000830000000000201000000830000009000700 000000012400090000000000050070200000600000400000108000018000000000030700502000000 00009
000000000000000012003045000000006507010000000080003000000210000007000000500080300 000000012500008000000700000600120000700000450000030000030000800000500700020000000 00010
000000001000000023004005000000004600020070000830000000000201000000830000009000700 000000012700060000000000050080200000600000400000109000019000000000030800502000000 00011
000000001000000023004005000000006400020000000710000000000010060000230000008700900 000000012800040000000000060090200000700000400000501000015000000000030900602000000 00012
000000001000002000003000045000000600000040270018900000000380000200050000700000000 000000013000500070000802000000400900107000000000000200890000050040000600000010000 00013
000000001000002000003000045000000600000050270081300000000830000200040000700000000 000000013000700060000508000000400800106000000000000200740000050020000400000010000 00014
000000001000002000003000045000000600000050270081300000000930000200040000700000000 000000013000700060000509000000400900106000000000000200740000050080000400000010000 00015
000000001000002000003000045000000600000050270018900000000380000200040000700000000 000000013000800070000502000000400900107000000000000200890000050040000600000010000 00016
000000000000000012003004000000010000000052400067000300000308000210000070500000000 000000013020500000000000000103000070000802000004000000000340500670000200000010000 00017
000000000000001002034000050000020030100006000700000000000300001000540000200000089 000000013040000080200060000609000400000800000000300000030100500000040706000000000 00018
000000000000001002034000050000020030100000000600007000000300001000540000200000089 000000013040000080200060000906000400000800000000300000030100500000040706000000000 00019
000000000000001002034000050000030001000450000600000078000600030100000000200009000 000000013040000090200070000607000400000300000000900000030100500000060807000000000 00020
000000000000001002034000050000030001000450000600000078000600030100009000200000000 000000013040000090200070000706000400000300000000900000030100500000060807000000000 00021
000000001000000020003004000000003405021006000700000000000070800000820000005000300 000000013200800000300000070000200600001000000040000000000401500680000200000070000 00022
000000001000000020003004000000005400060000700810000000000060000002109000007000850 000000013400800000200000070000400900001000000060000000000501600380000200000070000 00023
000000001000000002003004000000000050000120060007080000020000700180000000600005400 000000014000000203800050000000207000031000000000000650600000700000140000000300000 00024
000000001000002000034000000000000030000030450200006000000400010670000002800070000 000000014000020000500000000010804000700000500000100000000050730004200000030000600 00025
000000001000002000003000045000000260000030000040100000000050704206008000300000000 000000014008005000020000000000020705100000000000000800070000530600140000000200000 00026
000000001000002000003000045000000260000030000040500000000010704206008000300000000 000000014008005000020000000000020805100000000000000700070000530600140000000200000 00027
000000001000002000003000045000000260000030000070500000000010807206009000300000000 000000014008009000020000000000020805100000000000000700070000930600140000000200000 00028
000000000000000012003045000000000004000000006010200500000702030400000080600100000 000000014700000000000500000090014000050000720000600000000900805600000900100000000 00029
000000001000002000003000045000000260000780000010000000000050307090000000620100000 000000014790000000000200000000003605001000000000000200060000730200140000000800000 00030
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Thu Jan 18, 2007 10:24 pm    Post subject: Re: Row-Minimal Standard Form Reply with quote

holdout wrote:
gsf wrote:

I'm interested in reproducability how about a trial on real data, say 30 copies of gordon royle's 17's


As requested (my output is followed by Gordon's input):

I compiled the code and it works really well for puzzles
but deteriorates for solution grids which require tactics based on sudoku counting
I used holdout's code as an independent source to verify a change in my canoncalization from
box-normal (top left box fixed to 123/456/789) to row-normal (top row fixed to 123456789)

note that solution grid canonicalization requires all 81 clues so there is a place for both techniques
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Wed Jan 24, 2007 1:38 am    Post subject: Reply with quote

Im interested in an alternative canonicalization of puzzles.

I cant program it myself so Im relient on your imput but I feel that it might be worthwhile in terms of puzzle construction.

Most minimal puzzles have a variation of a 6/9 different clue pattern/template - in fact a large number of relabelled and swopped versions [the ones that dont are "extreme" puzzles constructed from sub-grids with 3 and more empty boxes - which I am considering to be irrelevant !]
Code:
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|.9.|
|...|...|...|
+---+---+---+


More commonly there are a few 7/9 [two types] in almost every puzzle.
Code:
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..7|...|...|
|...|...|.9.|
|...|...|...|
+---+---+---+
or
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|..6|
+---+---+---+
|...|...|...|
|...|...|.9.|
|...|...|...|
+---+---+---+




It is certainly possible to classify every minimal puzzle according to the maximum score found in the puzzle. [rarely there are 9/9 ]

Possible use.

Canonicalizing and relabelling groyles series of 17 clue puzzles to this method might give us a few identical combinations of 15 clues. That would be 7 fixed clues plus 8 others - effecting a concentrated search for furthur puzzles - if indeed there are any !

holdouts output of puzzles looks to going some way to present puzzles in this format - although a larger sample and using puzzle isomorphs may increase clue coincidement ?

It may not be useful for a variety of impractical reasons !

C


Last edited by coloin on Thu Jan 25, 2007 3:47 pm; edited 1 time in total
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Wed Jan 24, 2007 8:08 pm    Post subject: Reply with quote

The methods to date rely of fixing 9 symbols out of the 81

the trick is find how many more clues can be fixed in addition to the original 9......

Then that would result in an improved algorithm,.... does this make sense?!!!

Now with the box normal method I've read somewhere that the 4s (I don't know how many out of the 9 possible 4s) always show up in the same place........

Would that be of any help in finding that better algorithm ??

tarek
Back to top
View user's profile Send private message
Red Ed

Joined: 04 Nov 2006
Posts: 21
:

Items
PostPosted: Thu Feb 01, 2007 9:16 pm    Post subject: Reply with quote

Why do we need a better algorithm? I assume you (tarek) are talking about canonicalisation of solution grids, not puzzles. The usual method involves building a catalogue of 648 possible canonical forms -- each of which can be calculated very quickly -- and then just picking the "smallest" of them. This is so quick that canonicalisation is hardly ever the slow step in sudoku experiments.
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Feb 03, 2007 2:14 pm    Post subject: Reply with quote

Red Ed wrote:
I assume you (tarek) are talking about canonicalisation of solution grids, not puzzles. The usual method involves building a catalogue of 648 possible canonical forms


thanx, I was referring to some other method that does not use an anchor digit...

How many operations do you need though to align the anchor digits....how would that affect the 648 number ?

would it not be easier to adopt this or is it just the same priciple, as the "smallest" to me is the smallest number when the solution puzzle is displayed in line format.........
Code:
1 2 3 | 4 5 6 | 7 8 9
. . . | 1 . . | . . .
. . . | . . . | 1 . .
------+-------+------
. 1 . | . . . | . . .
. . . | . 1 . | . . .
. . . | . . . | . 1 .
------+-------+------
. . 1 | . . . | . . .
. . . | . . 1 | . . .
. . . | . . . | . . 1


tarek
Back to top
View user's profile Send private message
Red Ed

Joined: 04 Nov 2006
Posts: 21
:

Items
PostPosted: Sat Feb 03, 2007 7:33 pm    Post subject: Reply with quote

tarek wrote:
How many operations do you need though to align the anchor digits....how would that affect the 648 number ?
The 648 comes from picking the box to fill 1-9 (9 ways), the anchor digit (9 ways) and whether or not to do some swaps and a transpose (8 ways). For each of those 648 choices, you then have to align the anchor digits: this involves no further choices (of the 4 x 6^4 ways of doing it, only one is valid) and is very easy to do by setting the row/column permutations within each band/stack independently. I would guess that if we "costed" the algorithm in terms of memory accesses then anchor alignment would contribute a few percent of the total runtime in what is in any case a very fast algorithm.

Quote:
would it not be easier to adopt this or is it just the same priciple ...
It's just the same principle: you still have to loop through 648 grid permutations and process the grid in all sorts of funny orders before hitting upon the right answer.
Back to top
View user's profile Send private message
enxio27

Joined: 10 Feb 2007
Posts: 12
:

Items
PostPosted: Fri May 25, 2007 2:44 am    Post subject: Canonicalization Reply with quote

I've been trying very hard to follow this thread (making the mistake several times of trying to read it too late at night). Do I understand correctly that the purpose of canonicalization is to identify two (or more) solution grids that are merely rotations, permutations, or relabelling of one other?

I've seen references to gsf's algorithm (or code), but no links. Where do I find it to look at it?
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Jan 17, 2009 3:06 pm    Post subject: Canonicalize again and again! Reply with quote

Lummox JR wrote:
I think I understand gsf's algorithm from the source code, now, well enough to explain it here.

Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.

Each column or row of entire boxes we'll call a band. The P-bands will be P boxes stacked to PxN in size, and the Q-bands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.

Step 1: "Loop A". Loop through each box, and each orientation (original or transposed).


Loop A: What for and how?

Lummox JR wrote:
This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P- and Q-bands till they reach the desired position.



How to choose the good box?

Lummox JR wrote:
Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36.



Loop B: What for?

Thank you very much for explanations.
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Jan 17, 2009 3:06 pm    Post subject: Canonicalize again and again! Reply with quote

Lummox JR wrote:
I think I understand gsf's algorithm from the source code, now, well enough to explain it here.

Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.

Each column or row of entire boxes we'll call a band. The P-bands will be P boxes stacked to PxN in size, and the Q-bands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.

Step 1: "Loop A". Loop through each box, and each orientation (original or transposed).


Loop A: What for and how?

Lummox JR wrote:
This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P- and Q-bands till they reach the desired position.



How to choose the good box?

Lummox JR wrote:
Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36.



Loop B: What for?

Thank you very much for explanations.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page Previous  1, 2, 3, 4, 5, 6  Next
Page 5 of 6

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron