Sudoku Programmers :: View topic

FAQ

Memberlist

Usergroups

Profile

Jigsaw problems
Goto page Previous 1, 2, 3 Next

Sudoku Programmers Forum Index -> Programming sudoku

View previous topic :: View next topic

Author

Message

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Fri Oct 17, 2008 6:11 pm Post subject:

mrmarky2 wrote:

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

Yep, removing and replacing candidates (undo) avoids the brute force of making a lot of impossible moves. And picking the cell with the least candidates makes it faster too.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Sat Oct 18, 2008 8:02 am Post subject:

Here's a Visual Basic routine on how to generate random jigsaw patterns

Code:

Sub BuildJigsawPattern()

Dim Cage As Integer
Dim CagePtr(1 To 9) As Integer
Dim CageCell As Integer
Dim Direction As Integer
Dim CountFails As Integer

Do 'main loop

For i = 0 To 80
CellsCageNumber(i) = 0
Next i

Randomize 'initiate randomizer

CountFails = 0 'reset failure counter

For Cage = 1 To 9
For i = 0 To 80 'search for first available cell
If CellsCageNumber(i) = 0 Then
CellsCageNumber(i) = Cage
CageCell = i
Exit For
End If
Next i
For i = 1 To 8 'add 8 more cells
Do
DoEvents
Direction = Int(4 * Rnd) + 1 'choose random direction to expand cage
Select Case Direction
Case 1 'right
If (CageCell Mod 9) < 8 Then 'check boundary
If CellsCageNumber(CageCell + 1) = 0 Then 'check free cell
'add cell
CageCell = CageCell + 1
CellsCageNumber(CageCell) = Cage
If Not OpenField(8 - i, Cage) Then 'check impossible pattern
'pattern impossible to complete
CountFails = CountFails + 1 'increase failure counter
'remove last added cell
CellsCageNumber(CageCell) = 0
CageCell = CageCell - 1
Else
'pattern possible to complete
CountFails = 0 'reset failure counter
Direction = 0 'reset direction for indicating succes on adding cell
End If
ElseIf CellsCageNumber(CageCell + 1) = Cage Then
CageCell = CageCell + 1
End If
End If
Case 2 'down
If Int(CageCell / 9) < 8 Then
If CellsCageNumber(CageCell + 9) = 0 Then
CageCell = CageCell + 9
CellsCageNumber(CageCell) = Cage
If Not OpenField(8 - i, Cage) Then
CountFails = CountFails + 1
CellsCageNumber(CageCell) = 0
CageCell = CageCell - 9
Else
CountFails = 0
Direction = 0
End If
ElseIf CellsCageNumber(CageCell + 9) = Cage Then
CageCell = CageCell + 9
End If
End If
Case 3 'left
If (CageCell Mod 9) > 0 Then
If CellsCageNumber(CageCell - 1) = 0 Then
CageCell = CageCell - 1
CellsCageNumber(CageCell) = Cage
If Not OpenField(8 - i, Cage) Then
CountFails = CountFails + 1
CellsCageNumber(CageCell) = 0
CageCell = CageCell + 1
Else
CountFails = 0
Direction = 0
End If
ElseIf CellsCageNumber(CageCell - 1) = Cage Then
CageCell = CageCell - 1
End If
End If
Case 4 'up
If Int(CageCell / 9) > 0 Then
If CellsCageNumber(CageCell - 9) = 0 Then
CageCell = CageCell - 9
CellsCageNumber(CageCell) = Cage
If Not OpenField(8 - i, Cage) Then
CountFails = CountFails + 1
CellsCageNumber(CageCell) = 0
CageCell = CageCell + 9
Else
CountFails = 0
Direction = 0
End If
ElseIf CellsCageNumber(CageCell - 9) = Cage Then
CageCell = CageCell - 9
End If
End If
End Select
If Direction = 0 Then Exit Do
If CountFails = 50 Then Exit Do
Loop
If CountFails = 50 Then Exit For
Next i
If CountFails = 50 Then Exit For
Next Cage

If Direction = 0 Then Exit Do

Loop

'initiate supporting arrays
For Cage = 1 To 9
CagePtr(Cage) = 0
Next Cage

For i = 0 To 80
Cage = CellsCageNumber(i)
CagePtr(Cage) = CagePtr(Cage) + 1
CageCellnumbers(Cage, CagePtr(Cage) - 1) = i
Next i

End Sub

Code:

Function OpenField(CellsToCover As Integer, CurrentCage As Integer) As Boolean

Dim StartingCell As Integer
Dim CurrentCell As Integer
Dim CountCells As Integer
Dim CountFieldCells(10 To 11) As Integer
Dim CellAdded As Boolean

OpenField = True

'calculate free cells
CountCells = ((9 - CurrentCage) * 9) + CellsToCover
If CountCells = 0 Then Exit Function

'collect as much contigious free cells to the first exceptional cage
'starting with the first free cell available
For i = 0 To 80 'search first available free cell
If CellsCageNumber(i) = 0 Then Exit For
Next i
CellsCageNumber(i) = 10 'use first exceptional cagenumber
CountFieldCells(10) = 1
CellAdded = True

Do While CellAdded 'add all possible uncaged cells to the exceptional cagenumber
CellAdded = False
For i = 0 To 80
If CellsCageNumber(i) = 0 Then
'control right
If (i Mod 9) < 8 Then
If CellsCageNumber(i + 1) = 10 Then
CellsCageNumber(i) = 10
CountFieldCells(10) = CountFieldCells(10) + 1
CellAdded = True
Exit For
End If
End If
'control down
If Int(i / 9) < 8 Then
If CellsCageNumber(i + 9) = 10 Then
CellsCageNumber(i) = 10
CountFieldCells(10) = CountFieldCells(10) + 1
CellAdded = True
Exit For
End If
End If
'control left
If (i Mod 9) > 0 Then
If CellsCageNumber(i - 1) = 10 Then
CellsCageNumber(i) = 10
CountFieldCells(10) = CountFieldCells(10) + 1
CellAdded = True
Exit For
End If
End If
'control up
If Int(i / 9) > 0 Then
If CellsCageNumber(i - 9) = 10 Then
CellsCageNumber(i) = 10
CountFieldCells(10) = CountFieldCells(10) + 1
CellAdded = True
Exit For
End If
End If
End If
Next i
Loop

'compare cellsize of first exceptional cage to total of free cells
If CountFieldCells(10) = CountCells Then
'equal size, no division, grid can still be completed
For i = 0 To 80
If CellsCageNumber(i) = 10 Then CellsCageNumber(i) = 0
Next i
Exit Function
End If

'collect as much contigious free cells from those who were
'not added to the first exceptional cage to a second exceptional cage
'starting with the first free cell available
For i = 0 To 80
If CellsCageNumber(i) = 0 Then Exit For
Next i
CellsCageNumber(i) = 11 'use second exceptional cagenumber
CountFieldCells(11) = 1
CellAdded = True

Do While CellAdded
CellAdded = False
For i = 0 To 80
If CellsCageNumber(i) = 0 Then
'control right
If (i Mod 9) < 8 Then
If CellsCageNumber(i + 1) = 11 Then
CellsCageNumber(i) = 11
CountFieldCells(11) = CountFieldCells(11) + 1
CellAdded = True
Exit For
End If
End If
'control down
If Int(i / 9) < 8 Then
If CellsCageNumber(i + 9) = 11 Then
CellsCageNumber(i) = 11
CountFieldCells(11) = CountFieldCells(11) + 1
CellAdded = True
Exit For
End If
End If
'control left
If (i Mod 9) > 0 Then
If CellsCageNumber(i - 1) = 11 Then
CellsCageNumber(i) = 11
CountFieldCells(11) = CountFieldCells(11) + 1
CellAdded = True
Exit For
End If
End If
'control up
If Int(i / 9) > 0 Then
If CellsCageNumber(i - 9) = 11 Then
CellsCageNumber(i) = 11
CountFieldCells(11) = CountFieldCells(11) + 1
CellAdded = True
Exit For
End If
End If
End If
Next i
Loop

'compare sum of both exceptional cages to total of free cells
If CountFieldCells(10) + CountFieldCells(11) = CountCells Then
'both exceptional cages are covering the total free cells
'check if enclosed parts can be completed
If ((CountFieldCells(10) Mod 9) > CellsToCover) And ((CountFieldCells(11) Mod 9) > CellsToCover) Then OpenField = False
Else
'Total free cells are divided in three parts by the last added cell
'set return value to free last added cell
OpenField = False
End If

'clear exceptional cages
For i = 0 To 80
If CellsCageNumber(i) = 10 Then CellsCageNumber(i) = 0
If CellsCageNumber(i) = 11 Then CellsCageNumber(i) = 0
Next i

End Function

I've updated my downloadable project with this routine

The code for the 'Conceal' button is under construction...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

Last edited by Lunatic on Wed Oct 22, 2008 6:28 pm; edited 2 times in total

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Sat Oct 18, 2008 9:42 am Post subject:

Hey again, I had a look at your program, generating some grids and filling them with numbers. And on my really slow PC it can take longer than 10 seconds to fill a grid with numbers. I really don't know what I have told you about my program already, but on my program it generates a full grid for 9x9 in less than a second. Then it takes 5-6 seconds on average to generate a full grid for 10x10. But any bigger grid size and it takes forever, I left it generating a 12x12 for about 5 minutes and it just managed to find a grid. Have you tried your code on bigger sizes like 10x10,12x12 and 16x16? These are my big problem . menneske.no seems to only have up to 16x16 which is unusual for him and even then he only has 15 of them, big jigsaw generation seem to be a big problem. Thanks for all the help Mark

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Sun Oct 19, 2008 2:02 pm Post subject:

mrmarky2 wrote:

I had a look at your program, generating some grids and filling them with numbers. And on my really slow PC it can take longer than 10 seconds to fill a grid with numbers.
I really don't know what I have told you about my program already, but on my program it generates a full grid for 9x9 in less than a second.

Well, my program is written in Visual Basic, and it is known that programs written and compiled in Visual Basic often ar slower then other program languages. The only way to compare on a fair base are two programs both written in the same programming language.

The purpose of my project was to reach you a way of coding, easy understandable by most programmers, so you can decide if this code could be working better/faster then your own. Naturally, for a fair comparison, the code i provided must be translated to your own programming language. Now, as i stated before, the best way of testing uniqueness of any sudoku is the Dancing Links strategy, that's why a sticky post about it is at the top of the Programming sudoku page. The brute force backtracking code i use, is based upon the Dancing Links principle, but doesn't work with pointers, as Visual Basic 6, don't provide pointers.

One can argue about the fact if Dancing Links is needed to fill an empty grid, but in my humble opinion randomly filling in an empty grid can sometimes work fast with small grids, but the greater the grid the harder it will be to fill with random luck.

If you really want to break time records, then you sure need to program in assembler.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Sun Oct 19, 2008 6:18 pm Post subject:

Hey again,

Quote:

If you really want to break time records, then you sure need to program in assembler.

Thats not really the idea of the project, it was to be able to generate larger grids in a sensible amount of time. I was hoping to get a decent generator. My 12x12 doesn't even generate consistently, I guess I was lucky to get even 1 grid out of it.

Quote:

I dont think brute force is a faster solution, I tried to brute force 9 rows on a 25x25 grid and was working for a minute or so before I stopped it. With my other, non brute force, code I can generate a 25x25 full grid in a couple of seconds.

Quote:

One can argue about the fact if Dancing Links is needed to fill an empty grid, but in my humble opinion randomly filling in an empty grid can sometimes work fast with small grids, but the greater the grid the harder it will be to fill with random luck.

Have you tried your code on any bigger than 10x10 yet? I would be really interested to know if it works, that would be a great help because thats my big problem. Sad

Thanks for your help Smile

Mark

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Sun Oct 19, 2008 6:51 pm Post subject:

Had an idea. I was thinking of how to generate jigsaw X puzzles, and I filled the diagonals with numbers and pressed solve. Everytime it gets about 4 cells that can't have any numbers in, but if a program repeatedly tried it I think it might get a grid quite quickly. That same solution would work for normal jigsaws as well if it works for jigsaw X. Because with the diagonals already full, the solving process is the same. I'll just test it on my program. Mark

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Sun Oct 19, 2008 6:58 pm Post subject:

Bad idea.. it doesn't give you enough clues to solve larger puzzles. Mark

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Sun Oct 19, 2008 8:10 pm Post subject:

mrmarky2 wrote:

Have you tried your code on any bigger than 10x10 yet? I would be really interested to know if it works, that would be a great help because thats my big problem. Sad

I'm now busy with a 16x16 version of my jigsaw project, no problem to saw the pieces, but filling the grid with sequential brute force takes long, very long... don't have any filled grid generated this far, i'm keep running out of patience everytime...

Meanwhile, the code for concealing cells (9x9 version), randomly, is ready with good results, but after all, there is nothing special about that part i presume.

Did some improvements on the 'saw' code too.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Mon Oct 20, 2008 3:51 pm Post subject:

Quote:

Bad idea.. it doesn't give you enough clues to solve larger puzzles.

Actually quite a good idea as it generates me X sudoku now. I wonder if for larger puzzles, you could use it possibly in a slighty different way by filling the border and solving repeadly until a grid comes?

Mark

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Mon Oct 20, 2008 5:35 pm Post subject:

mrmarky2 wrote:

I was thinking of how to generate jigsaw X puzzles, and I filled the diagonals with numbers and pressed solve. Everytime it gets about 4 cells that can't have any numbers in, but if a program repeatedly tried it I think it might get a grid quite quickly.

I don't see how this would work, and if it works than it is just luck. If you don't start from a filled grid, how can you be certain that the puzzle has one unique solution ? Either, there will be multiple solutions (and then you maybe get a filled grid within an acceptable time), or there will be no solution (and you'll be wasting time).

Any Dancing Links or Dancing Links based brute force code will search sequential through ALL posibilities for the given grid, encountering more invalid then valid grids. It's often not difficult to fill half the grid this way, or even to fill 3/4 of the grid, but there's no guarantee that a full grid is in it based upon the partial filled grid.

Have you got any link to some example of your program so i can see what you allready accomplished ?
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Tue Oct 21, 2008 8:15 am Post subject:

Quote:

My old code wouldn't generate Jigsaw X filled grids, so I had to make a little change to get it working. Your brute should be able to do it.
My function to generate a grid for Jigsaw X is to fill the diagonals with numbers, solve the puzzle, if it solves then you have your full grid and you can use it to make a puzzle from, otherwise restart again by filling the diagonals again.

Quote:

Have you got any link to some example of your program so i can see what you allready accomplished?

Erm nope I only have the real thing, it's quite a large exe file, and has all of my code on it for every one of my sudoku generators. I merged them together to make 1 piece of code that works for any type and size.
What were you wanting to see by it? Were you wanting to look at generation speed or something?

Mark

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Tue Oct 21, 2008 10:28 am Post subject:

mrmarky2 wrote:

My old code wouldn't generate Jigsaw X filled grids, so I had to make a little change to get it working. Your brute should be able to do it.

Indeed, just have to add a few more lines in the remove/undo code. But applying more rules (from Jigsaw to Jigsaw X) is narrowing the possible grids, after all, Jigsaw X is just a subset of all Jigsaws. In fact, a normal sudoku is also a subset of all jigsaws where the cages are all the same.

mrmarky2 wrote:

What were you wanting to see by it? Were you wanting to look at generation speed or something?

Just curious about your code for randomly filling in the grid.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Wed Oct 22, 2008 3:44 pm Post subject:

Quote:

Just curious about your code for randomly filling in the grid.

Its would take a long time to copy make an example project, copying over functions and classes that you need, and deleting all the code in those functions that won't work without the whole program Sad

Heres what my program does:
9x9 jigsaw less than a second
10x10 jigsaw about 2-3 seconds
9x9 jigsaw X about 6 seconds
10x10 jigsaw X about 15 seconds

Got 16x16 working yet?

My PC is so slow its getting painful Sad

takes forever just to compile my program to check my code is working..

Mark

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Wed Oct 22, 2008 6:24 pm Post subject:

mrmarky2 wrote:

Got 16x16 working yet?

Sawing the grid is no problem, it's filling the grid that takes very long. We have to consider that the average time, needed to fill the grid, increases exponential with the size of the grid. I was thinking of doing some logic eliminations (hidden/naked singles; cage-line reductions; pointing pairs/triplets/quads; naked/hidden subsets) before invoking brute force. But i first have to modify the logic routines from my 'normal' sudoku program to jigsaw and from 9x9 to 16x16. Can take a while...

mrmarky2 wrote:

My PC is so slow its getting painful Sad

takes forever just to compile my program to check my code is working..

I'm working on a PC with Pentium III - 800 Mhz, that's not very fast either...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

mrmarky2

Joined: 13 Jan 2007

Posts: 64

Items

Posted: Thu Oct 23, 2008 2:57 pm Post subject:

Quote:

But i first have to modify the logic routines from my 'normal' sudoku program to jigsaw and from 9x9 to 16x16. Can take a while...

I'll tell you what I did, I have 2 arrays, boxes[width][width][2] and boxes2[width][width]. Width is the width of the grid obviously. Boxes 2 holds which box each cell is in, boxes holds which cell is in each box. Then my code for normal sudoku will work for jigsaw sudoku as well, because any solving technique that uses boxes uses the boxes arrays to find techniques. For the size, I wrote all my code using width instead of a number, so I can change the width integer and the code will for any size sudoku Smile

.
If you do that then you could test your code on 12x12 as well, which if you can generate in a sensible time i'd be really interested in.

Mark

Display posts from previous:

	Sudoku Programmers Forum Index -> Programming sudoku	All times are GMT Goto page Previous 1, 2, 3 Next
Page 2 of 3

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