|
| View previous topic :: View next topic |
| Author |
Message |
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
 Posted: Sun Jan 14, 2007 11:28 pm Post subject: |
 |
|
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 |
|
 |
| holdout
| | Joined: 30 Dec 2006 | | Posts: 8 | | : | | Location: Bowie, MD (USA) |
Items |
|
| Posted: Tue Jan 16, 2007 12:55 am Post subject: Row-Minimal Standard Form |
|
|
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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Tue Jan 16, 2007 5:16 am Post subject: Re: Row-Minimal Standard Form |
|
|
| 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 |
|
|
| holdout
| | Joined: 30 Dec 2006 | | Posts: 8 | | : | | Location: Bowie, MD (USA) |
Items |
|
| Posted: Tue Jan 16, 2007 3:57 pm Post subject: Re: Row-Minimal Standard Form |
|
|
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. 
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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Tue Jan 16, 2007 5:10 pm Post subject: Re: Row-Minimal Standard Form |
|
|
| holdout wrote: | To: gsf
2. No, I did not run time trials on one puzzle X times.
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 |
|
|
| holdout
| | Joined: 30 Dec 2006 | | Posts: 8 | | : | | Location: Bowie, MD (USA) |
Items |
|
| Posted: Tue Jan 16, 2007 5:43 pm Post subject: Re: Row-Minimal Standard Form |
|
|
| 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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Jan 18, 2007 10:24 pm Post subject: Re: Row-Minimal Standard Form |
|
|
| 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 |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Wed Jan 24, 2007 1:38 am Post subject: |
|
|
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 |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
| Posted: Wed Jan 24, 2007 8:08 pm Post subject: |
|
|
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 |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Thu Feb 01, 2007 9:16 pm Post subject: |
|
|
| 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 |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
| Posted: Sat Feb 03, 2007 2:14 pm Post subject: |
|
|
| 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 |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Sat Feb 03, 2007 7:33 pm Post subject: |
|
|
| 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 |
|
|
| enxio27
| | Joined: 10 Feb 2007 | | Posts: 12 | | : | |
Items |
|
| Posted: Fri May 25, 2007 2:44 am Post subject: Canonicalization |
|
|
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 |
|
|
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Sat Jan 17, 2009 3:06 pm Post subject: Canonicalize again and again! |
|
|
| 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 |
|
|
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Sat Jan 17, 2009 3:06 pm Post subject: Canonicalize again and again! |
|
|
| 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 |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
