|
View previous topic :: View next topic |
Author |
Message |
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Sat Oct 11, 2008 11:09 am Post subject: Jigsaw problems |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Mon Oct 13, 2008 7:57 am Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Mon Oct 13, 2008 3:17 pm Post subject: |
|
|
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
Mark |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Mon Oct 13, 2008 3:39 pm Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Mon Oct 13, 2008 4:51 pm Post subject: |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Mon Oct 13, 2008 8:17 pm Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Tue Oct 14, 2008 12:37 pm Post subject: |
|
|
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
Mark |
|
Back to top |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Tue Oct 14, 2008 2:53 pm Post subject: |
|
|
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 .
Mark |
|
Back to top |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Tue Oct 14, 2008 3:25 pm Post subject: |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Tue Oct 14, 2008 5:54 pm Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Wed Oct 15, 2008 3:47 pm Post subject: |
|
|
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.
Thanks for your help
Mark |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Thu Oct 16, 2008 5:37 pm Post subject: |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Thu Oct 16, 2008 8:33 pm Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Fri Oct 17, 2008 3:02 pm Post subject: |
|
|
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 |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Fri Oct 17, 2008 4:48 pm Post subject: |
|
|
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 |
|
|
|
|
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
|