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   

Jigsaw problems
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sat Oct 11, 2008 11:09 am    Post subject: Jigsaw problems Reply with quote

I am having some problems with my jigsaw generator.

The two problems are generating the boxes and filling the grids with numbers.

To generate the boxes:
For each box I randomely place 1 square, then I look to find the other squares around it that are empty and randomely pick one. I keep doing this until I have a box of the right size. You regularly find that there are no empty squares nearby so I take some from another box that is next to it and redraw that one.

It works up to 4x4 and then even takes a couple of seconds.

To fill the grid with numbers:
For each row: If I get to the end of a row and it isn't full restart the row again. If I have to do this on the same row more than 18 times(for 9x9 2xthe width) then I restart the grid completely.

This worked only with 9x9 so I made a change:
If the number of redoes in total on the rows reaches 18000(for 9x9 2000xwidth) then it generates a new grid, because its likely that the grid it was working on is a hard grid to fill with numbers.

This works now up to 10x10.

Anyone have any ideas on how to impove generation methods so I can generate bigger puzzles?

Thanks
Mark
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Mon Oct 13, 2008 7:57 am    Post subject: Reply with quote

Hi,

I never made an attempt to generate jigsaws myself, but thinking it over, i guess i would handle the same approach as i do for normal sudokus. The only difference is that you have to translate the normal box cell adresses in your dlx-solver to the jigsaw-box cells for handling the box constraints.

Step 1: Generate a (randomly) filled grid
Step 2: Conceal a (randomly) single/pair of cell values
Step 3: Check for restrictions => passed or failed
Step 4: If step 3 failed then restore the last concealed single/pair of cell values and continue with step 2
Step 5: Solve the puzzle (dlx-solver) to see if a unique solution still exists => one solution=passed, more then one solution=failed
Step 6: If step 5 failed then restore the last concealed single/pair of cell values and continue with step 2
Step 7: Count the givens and continue with step 2 if you want to conceal more cell values
Step 8: Done

Marc.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Mon Oct 13, 2008 3:17 pm    Post subject: Reply with quote

Mi marc,

Thats what I do near enough...
The only problem is with step 1. With the irregular box shapes it makes it harder to generate a random grid. A possible solution might be to fill the grid a box at a time instead of a row at a time.

The other problem I had was generating the irregular box shapes.. Thats sorted now, It can generate box shapes for 12, 16, and 20 pretty quickly but it gets a lot slower when doing 25.
I have another Idea to improve the speed Smile

Mark
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Mon Oct 13, 2008 3:39 pm    Post subject: Reply with quote

mrmarky2 wrote:
The only problem is with step 1. With the irregular box shapes it makes it harder to generate a random grid. A possible solution might be to fill the grid a box at a time instead of a row at a time.


I see...
In that case you should determine the jigsaw parts first and then generate valid filled grids, but i guess that's what you're doing allready.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Mon Oct 13, 2008 4:51 pm    Post subject: Reply with quote

Hey again

Yeh thats what I'm doing, but the really hard part is after generating the jigsaw parts. Filling the grid with numbers is the hard part.
First I made it fill in row by row with random numbers, and it sometimes took over 100000 times redoing rows until it got a solution.

If I set it filling in each of the jigsaw bits one by one, it still is slow. I wander if a brute force solver will speed it up. Using it to find a solution to each box...

Do you think that would help?
If so have you got any code I could look at?

Thanks
Mark
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Mon Oct 13, 2008 8:17 pm    Post subject: Reply with quote

mrmarky2 wrote:
Filling the grid with numbers is the hard part.
First I made it fill in row by row with random numbers, and it sometimes took over 100000 times redoing rows until it got a solution.


I don't think that filling in the grid row by row with random numbers is the right approach. You need a brute force backtracking routine to do that job, and it doesn't matter if its row by row or not. Dancing links is the solution to your problems. It's obvious that all your filled grids eventually will end up with the first row showing 123456789, but you can switch those numbers on the whole grid afterwards to make it look more randomly. The problem is that you allways will get the first possible grid for the same jigsaw pattern. To ommit that you can randomly change the order of the candidates for each cell, or you can randomly change the order off the cells to fill in or you can do both. I use both techniques in my Sudoku Generator

Quote:
If so have you got any code I could look at?


You can take a look at the brute force backtracking solver code written in Visual Basic, wich is an easy language to understand, and use it as a guide for your own solver. See topic: Dancing Links and Visual Basic
The code in that topic is a substitute for Dancing Links without using pointers, and is based upon the 4 line brute force solver (see topic: four line sudoku solver ) where rwaddilove wrote:

Quote:
Sudoku puzzles can be solved with just 4 lines of code. Here's it is:

1 sp(cell(ptr))=(sp(cell(ptr)) + 1) mod 10
2 if sp(cell(ptr))=0 then ptr=ptr+1:goto 1
3 if countnum(cell(ptr))=3 then ptr=ptr-1
4 if ptr>-1 then goto 1

Of course, it needs a bit of explanation. This is a brute force method, but it is so short and simple that it is very fast. You need to create two arrays and a pointer like this:

sp(80) is the sudoku puzzle - 9 x 9 grid, 81 cells, numbered 0-80
cell(80) is a list of blank cells - when you read in the puzzle, store the blank cell numbers here
ptr=points to the last blank cell in the list

One other thing you need is a countnum() function. This counts how many times a number appears. It should appear once in a row, once in a column and once in a block (regular 3x3 block or jigsaw block), hence the if countnum()=3 then...

That's it.


Since you have to fill in the whole grid, the array cell() will contain all cell numbers and ptr will point to the cell which number is in cell(80). And as i said earlier, you can randomly order the cell numbers into the cell() array.

Marc.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Tue Oct 14, 2008 12:37 pm    Post subject: Reply with quote

Lunatic wrote:
I don't think that filling in the grid row by row with random numbers is the right approach. You need a brute force backtracking routine to do that job, and it doesn't matter if its row by row or not. Dancing links is the solution to your problems. It's obvious that all your filled grids eventually will end up with the first row showing 123456789, but you can switch those numbers on the whole grid afterwards to make it look more randomly. The problem is that you allways will get the first possible grid for the same jigsaw pattern. To ommit that you can randomly change the order of the candidates for each cell, or you can randomly change the order off the cells to fill in or you can do both. I use both techniques in my Sudoku Generator


Thanks for the tip, i'll try it now Smile

Mark
Back to top
View user's profile Send private message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Tue Oct 14, 2008 2:53 pm    Post subject: Reply with quote

Made a brute force solver without dancing links because I dont know what they are.
The problem is its no better than before. It takes longer to generate a full grid than before Confused.

Mark
Back to top
View user's profile Send private message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Tue Oct 14, 2008 3:25 pm    Post subject: Reply with quote

Do you think that If i generate the numbers before the cages, it will have any difference?
Then I can place the cages around the numbers.

Mark
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Oct 14, 2008 5:54 pm    Post subject: Reply with quote

mrmarky2 wrote:
Do you think that If i generate the numbers before the cages, it will have any difference?
Then I can place the cages around the numbers.


You must keep in mind that each cage must have nine cells with the numbers 1 to 9 in it. If you first generate the numbers you will generate a lot of uncageable grids.

EDIT: Just removed my next post with the example for step 1, be patient i'm working on it...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Wed Oct 15, 2008 3:47 pm    Post subject: Reply with quote

Hey again,

Lunatic wrote:
You must keep in mind that each cage must have nine cells with the numbers 1 to 9 in it. If you first generate the numbers you will generate a lot of uncageable grids.

EDIT: Just removed my next post with the example for step 1, be patient i'm working on it...


I thought that if i generated the numbers first I would get some uncageable grids... im gonna generate some grids with numbers and try it by hand.
And im guessing its a common problem generating jigsaw puzzles. menneske.no only has up to 16x16. Cool

Thanks for your help
Mark
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu Oct 16, 2008 5:37 pm    Post subject: Reply with quote

Consider a grid with cages A to I,
and cells are numbered top left to bottom right 0 to 80

Code:
ABBBBCDDD
AABBBCCDD
AAABBCDDD
AEAACCCFD
EEEGGCCFF
EEEGGHHHF
EEIGGHHHF
IIIIGGHFF
IIIIGHHFF


Cage 1 = A
Cage 2 = B
etc...

Now you need some global supporting arrays:

An array that can tell you for each cell what cage it belongs to
Example: CellsCageNumber (0 to 80)
CellsCageNumber(0) = 1
CellsCageNumber(1) = 2
CellsCageNumber(2) = 2
CellsCageNumber(3) = 2
CellsCageNumber(4) = 2
CellsCageNumber(5) = 3
CellsCageNumber(6) = 4
CellsCageNumber(7) = 4
CellsCageNumber(8) = 4
CellsCageNumber(9) = 1
CellsCageNumber(10) = 1
CellsCageNumber(11) = 2
CellsCageNumber(12) = 2
and so on...
...
...
until...
CellsCageNumber(77) = 8
CellsCageNumber(78) = 8
CellsCageNumber(79) = 6
CellsCageNumber(80) = 6

An array that holds the cellnumbers for each cage
Example: CageCellnumbers (1 to 9, 0 to 8)
The first dimension refers to the cagenumber, the second dimension refers to the cagecells
CageCellnumbers (1, 0) = 0
CageCellnumbers (1, 1) = 9
CageCellnumbers (1, 2) = 10
CageCellnumbers (1, 3) = 18
CageCellnumbers (1, 4) = 19
CageCellnumbers (1, 5) = 20
CageCellnumbers (1, 6) = 27
CageCellnumbers (1, 7) = 29
CageCellnumbers (1, 8) = 30
CageCellnumbers (2, 0) = 1
CageCellnumbers (2, 1) = 2
CageCellnumbers (2, 2) = 3
CageCellnumbers (2, 3) = 4
and so on...
...
...
until...
CageCellnumbers (9, 5) = 72
CageCellnumbers (9, 6) = 73
CageCellnumbers (9, 7) = 74
CageCellnumbers (9, 8) = 75

An array that holds the candidates for each cell (bitwise)
If candidate 1 is present then bit 0 is set => 1
If candidate 2 is present then bit 1 is set => 2
If candidate 3 is present then bit 2 is set => 4
If candidate 4 is present then bit 3 is set => 8
If candidate 5 is present then bit 4 is set => 16
If candidate 6 is present then bit 5 is set => 32
If candidate 7 is present then bit 6 is set => 64
If candidate 8 is present then bit 7 is set => 128
If candidate 9 is present then bit 8 is set => 256
Example: CellsCandidates (0 to 80) all set to 511 (all candidates present)

A boolean array that states if the last possible candidate is tried
Example: LastCandidate(0 to 80) all set to False

An array that can translate CellsCandidates() to the number of candidates so you don't have to count the bits of CellsCandidates() to determine the number of candidates present
Example: CountCandidates(0 to 511)
CountCandidates(0) = 0
CountCandidates(1) = 1
CountCandidates(2) = 1
CountCandidates(3) = 2
CountCandidates(4) = 1
CountCandidates(5) = 2
CountCandidates(6) = 2
CountCandidates(7) = 3
CountCandidates(8) = 1
CountCandidates(9) = 2
CountCandidates(10) = 2
CountCandidates(11) = 3
CountCandidates(12) = 2
and so on...
...
...
until...
CountCandidates(508) = 7
CountCandidates(509) = 8
CountCandidates(510) = 8
CountCandidates(511) = 9

You can fill this array in a small for-next loop like this:

Code:
For i = 0 To 511
    j = i
    CountCandidates(i) = 0
    Do While j > 0
       If (j Mod 2) Then CountCandidates(i) = CountCandidates(i) + 1
       j = (j - (j Mod 2)) / 2
    Loop
Next i


NOW, according the 4-line brute force solver...
You need two more arrays:
An array to keep the possible solution
Example: Solution(0 to 80) all initiated to 0

An array to keep the unsolved cellnumbers
Example: UnsolvedCells(0 to 80)
At first fill in the cellnumbers in normal order
Code:
For i = 0 To 80
    UnsolvedCells(i)=i
Next i

Then, randomly change the order of the cellnumbers:
Code:
For n = 1 To 500 'this will be enough to mix it up
    i = Int(81 * Rnd)
    j = Int(81 * Rnd)
    dummie = UnsolvedCells(i)
    UnsolvedCells(i) = UnsolvedCells (j)
    UnsolvedCells(j) = dummie
Next n


For the backtracking you need some global dynamic arrays to keep log
Example: LogCell() LogCandidate() LogColumn() LogRow() LogCage()
And we need a global variable that keeps track of the steps allready taken
Example: LogSteps

So here is, more or less, Step 1:

Code:
Sub GenerateJigsaw()

Dim Ptr As Integer 'local declaration
Dim CurrentCell As Integer 'local declaration

Randomize 'initiate randomizer

Do 'start main loop

Ptr = 80 'initiate ptr
LogSteps = 0 'reset logcounter (see subroutines RemoveCandidates and Undo)
RestartCountdown = 0

For i = 0 To 80
    CellsCandidates(i) = 511
    LastCandidate(i) = False
    Solution(i) = 0
    UnsolvedCells(i) = i
Next i

For n = 1 To 500 'this will be enough to mix it up
    i = Int(81 * Rnd)
    j = Int(81 * Rnd)
    dummie = UnsolvedCells(i)
    UnsolvedCells(i) = UnsolvedCells(j)
    UnsolvedCells(j) = dummie
Next n

Do While Ptr < 81
    If Ptr = -1 Then Exit Do 'a valid grid is generated, now try to conceal cells
   
    'if no valid grid within 50000 steps, restart generation
    RestartCountdown = RestartCountdown + 1
    If RestartCountdown = 50000 Then Exit Do
   
    CurrentCell = UnsolvedCells(Ptr)
    If Solution(CurrentCell) = 0 Then 'next cell
        'search for cell with least candidates
        For i = 0 To (Ptr - 1)
            If CountCandidates(CellsCandidates(UnsolvedCells(i))) < CountCandidates(CellsCandidates(UnsolvedCells(Ptr))) Then
                dummie = UnsolvedCells(i)
                UnsolvedCells(i) = UnsolvedCells(Ptr)
                UnsolvedCells(Ptr) = dummie
            End If
        Next i
        CurrentCell = UnsolvedCells(Ptr)
        For i = 1 To 9
            If CellsCandidates(CurrentCell) And (2 ^ (i - 1)) Then
                Solution(CurrentCell) = i
                Exit For
            End If
        Next i
        If CountCandidates(CellsCandidates(CurrentCell)) = 1 Then LastCandidate(CurrentCell) = True
        RemoveCandidates CurrentCell, Solution(CurrentCell), (Ptr - 1)
        Ptr = Ptr - 1
        If Ptr > -1 Then
            For i = 0 To Ptr
                If CellsCandidates(UnsolvedCells(i)) = 0 Then
                    Ptr = Ptr + 1
                    Exit For
                End If
            Next i
        End If
    Else 'try next candidate, if any, for CurrentCell
        If LastCandidate(CurrentCell) Then 'last candidate tried, undo, and go to previous cell
            Undo
            LastCandidate(CurrentCell) = False
            Ptr = Ptr + 1
        Else 'try next candidate for CurrentCell
            dummie = Solution(CurrentCell)
            Undo
            For i = (dummie + 1) To 9
                If CellsCandidates(CurrentCell) And (2 ^ (i - 1)) Then
                    Solution(CurrentCell) = i
                    Exit For
                End If
            Next i
            LastCandidate(CurrentCell) = True
            If i < 9 Then
                For j = (i + 1) To 9
                    If CellsCandidates(CurrentCell) And (2 ^ (j - 1)) Then
                        LastCandidate(CurrentCell) = False
                        Exit For
                    End If
                Next j
            End If
            RemoveCandidates CurrentCell, Solution(CurrentCell), (Ptr - 1)
            Ptr = Ptr - 1
            If Ptr > -1 Then
                For i = 0 To Ptr
                    If CellsCandidates(UnsolvedCells(i)) = 0 Then
                        Ptr = Ptr + 1
                        Exit For
                    End If
                Next i
            End If
        End If
    End If
Loop

If Ptr = -1 Then
    If ConcealCells2ValidJigsaw Then
        If MsgBox("Valid Jigsaw Sudoku generated, generate another based on that same pattern ?", vbYesNo, "Jigsaw Sudoku") = vbNo Then Exit Do
    end if
End If

Loop

End Sub


Code:
Sub RemoveCandidates(Cell As Integer, Candidate As Integer, RemovePtr As Integer)

Dim Row As Integer
Dim Column As Integer
Dim Cage As Integer

LogSteps = LogSteps + 1
ReDim Preserve LogCell(1 To LogSteps)
ReDim Preserve LogCandidate(1 To LogSteps)
ReDim Preserve LogColumn(1 To LogSteps)
ReDim Preserve LogRow(1 To LogSteps)
ReDim Preserve LogCage(1 To LogSteps)
   
LogCell(LogSteps) = Cell
LogCandidate(LogSteps) = Candidate
LogColumn(LogSteps) = 0
LogRow(LogSteps) = 0
LogCage(LogSteps) = 0

Row = Int(Cell / 9)
Column = Cell Mod 9
Cage = CellsCageNumber(Cell)

'remove all "Candidate" in Row, Column and Cage from "Cell"
For j = 0 To RemovePtr
    If CellsCandidates(UnsolvedCells(j)) And (2 ^ (Candidate - 1)) Then
        If Int(UnsolvedCells(j) / 9) = Row Then
            LogRow(LogSteps) = LogRow(LogSteps) Or (2 ^ (UnsolvedCells(j) Mod 9))
            CellsCandidates(UnsolvedCells(j)) = CellsCandidates(UnsolvedCells(j)) And Not (2 ^ (Candidate - 1))
        Else
            If UnsolvedCells(j) Mod 9 = Column Then
                LogColumn(LogSteps) = LogColumn(LogSteps) Or (2 ^ Int(UnsolvedCells(j) / 9))
                CellsCandidates(UnsolvedCells(j)) = CellsCandidates(UnsolvedCells(j)) And Not (2 ^ (Candidate - 1))
            Else
                If CellsCageNumber(UnsolvedCells(j)) = Cage Then
                    For i = 0 To 8
                        If CageCellnumbers(Cage, i) = UnsolvedCells(j) Then
                            LogCage(LogSteps) = LogCage(LogSteps) Or (2 ^ i)
                            Exit For
                        End If
                    Next i
                    CellsCandidates(UnsolvedCells(j)) = CellsCandidates(UnsolvedCells(j)) And Not (2 ^ (Candidate - 1))
                End If
            End If
        End If
    End If
Next j

End Sub


Code:
Sub Undo()

Dim Row As Integer
Dim Column As Integer
Dim Cage As Integer

Solution(LogCell(LogSteps)) = 0
       
Row = Int(LogCell(LogSteps) / 9)
Column = LogCell(LogSteps) Mod 9
Cage = CellsCageNumber(LogCell(LogSteps))

For i = 0 To 8
    If (LogRow(LogSteps) And (2 ^ i)) Then CellsCandidates((Row * 9) + i) = CellsCandidates((Row * 9) + i) Or (2 ^ (LogCandidate(LogSteps) - 1))
    If (LogColumn(LogSteps) And (2 ^ i)) Then CellsCandidates((i * 9) + Column) = CellsCandidates((i * 9) + Column) Or (2 ^ (LogCandidate(LogSteps) - 1))
    If (LogCage(LogSteps) And (2 ^ i)) Then CellsCandidates(CageCellnumbers(Cage, i)) = CellsCandidates(CageCellnumbers(Cage, i)) Or (2 ^ (LogCandidate(LogSteps) - 1))
Next i

LogSteps = LogSteps - 1

End Sub


I hope you can figure this out, it's Visual Basic, should be easy to understand. It's a modification of my Dancing Links pseudo-code, and tested.

The subroutine call 'ConcealCells2ValidJigsaw' is where steps 2 and further are coming in...

Marc.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


Last edited by Lunatic on Fri Oct 17, 2008 3:12 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu Oct 16, 2008 8:33 pm    Post subject: Reply with quote

If you, or anyone else is interested, you can download the little Visual Basic project where i developed and tested the code above, or the executable, from this webpage.


_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


Last edited by Lunatic on Sat Oct 18, 2008 7:23 am; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Fri Oct 17, 2008 3:02 pm    Post subject: Reply with quote

Hey again,

Thanks for the code. I'll have a look at it and see if I can figure it out.
Just wandering.. how fast does this code generate 12x12 and 16x16?

Thanks again
Mark
Back to top
View user's profile Send private message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Fri Oct 17, 2008 4:48 pm    Post subject: Reply with quote

Is that basically brute force?
Enter a number in the first cell
Stick another in the next
Move back to the last square if no entries could be made in the square

Mark
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
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