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   

To add a solver or not add a solver?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Wed Jan 14, 2009 7:12 pm    Post subject: To add a solver or not add a solver? Reply with quote

Hi,
I found a tutorial on building a generator for Sudoku, but I cannot post the link here because I do not have enough posts for this forum to allow me to add links. To understand the basic method, the program basically picks a random cell. Then it checks if it is legal. If it is not legal then it tries another number until it exhausted the numbers 1 through 9. If all numbers have been used, then it backtracks by picking another random cell, who's cell has been filled, and deletes it. The tutorial also warns the reader that the tutorial does not discuss about removing hidden cells, and the reader should remember if doing so, this could create one puzzle to have multiple solutions.

Now I have read through some of the forums here, and most of them say that to avoid multiple solutions, you also need to build a solver. However, if I am going to hold all the cell answers inside of an array, then wouldn't that solve the "multplie solution" problem? Also, what are the benefits of having a solver and a generator?
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Fri Jan 16, 2009 12:01 am    Post subject: Re: To add a solver or not add a solver? Reply with quote

BigPapa wrote:
Hi,
I found a tutorial on building a generator for Sudoku, but I cannot post the link here because I do not have enough posts for this forum to allow me to add links. To understand the basic method, the program basically picks a random cell. Then it checks if it is legal. If it is not legal then it tries another number until it exhausted the numbers 1 through 9. If all numbers have been used, then it backtracks by picking another random cell, who's cell has been filled, and deletes it. The tutorial also warns the reader that the tutorial does not discuss about removing hidden cells, and the reader should remember if doing so, this could create one puzzle to have multiple solutions.

Now I have read through some of the forums here, and most of them say that to avoid multiple solutions, you also need to build a solver. However, if I am going to hold all the cell answers inside of an array, then wouldn't that solve the "multplie solution" problem? Also, what are the benefits of having a solver and a generator?


Most Sudoku players want just one unique solution to the puzzle. That's all the local paper or magazine will show as an answer so, if there are 100 solutions, how would you ever know your solution was OK or not? The paper or mag will not print them all for you, and your solution probably isn't shown as the answer. Sad

If all your puzzles will be derived from a unique puzzle grid, (usually by making simple permutations of a base puzzle), then you don't need a solver to generate unique puzzles.

If you want to create puzzles outside the range of known unique puzzle permutations, then you'll have to have a solver to know if the grid has a unique solution, or not.
Back to top
View user's profile Send private message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Sat Jan 17, 2009 4:06 am    Post subject: Reply with quote

I did not think that could cause a problem since the player would be clicking on a "check your progress" button, but I guess the player could then argue when his answers works but it is not the same answers to the actual puzzle. So since it would be better to design a solver, then I have another question.

1. When randomly removing particular cells to the puzzle, what makes those removed cells cause it to have multiple solutions. Is it...

[list=]
1. removing too many cells
2. the locations of where the cells have been removed
3. is it both
[/list]

Here is my thoughts I could do...
1. In level 1, randomly remove 20 cells, and restricting the removed cells in the following ways...
1.a. restrain from removing more than 6 cells in a row
1.b. restrain from removing more than 6 cells in a column
1.c. restrain from removing more than 4 cells in a 3x3 region

2. In level 2, still removing only 20 cells, but build less restrictions when removing the random cells.

... and so on. I am not sure if this would work, but any suggestions would help.
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sat Jan 17, 2009 6:45 am    Post subject: Reply with quote

To be unique, minimum grids must have:

1) No stack or band (3 X 27 sqrs), can have more than 1 box empty

2) No stack or band can have more than one column (stack), or row (band), empty.

3) The grid must have 8 of the 9 digits, as givens.

I'm sure if you scout around this board, you can find more info. There may even be software readily available, or easily modifiable, that you can use.
Back to top
View user's profile Send private message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Sun Jan 18, 2009 2:33 am    Post subject: Reply with quote

Adak,
I really appreciate you giving me the what the restrictions are for unique puzzles. Also, I do have a few questions from the below quote, which I found after doing a search in this forum...


Quote:

Step 1: Generate a (randomly) filled grid
Step 2: Conceal a (randomly) single/pair of cell values
Step 3: Check for restrictions (no more than 4 empty boxes, no more than 1 empty line in the same band/stack, at least 8 of the 9 values are among the givens) => 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 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

Now for the solver from step 5...

It's obvious that the solver has to try out all possible values for each blank (concealed) cell, and this in same order (most likely ascending from 1 to 9). Based on the givens left, you can eliminate candidates in the blank cells first, this will shorten the brute force solving time.

In my solver (See topic: Dancing Links and Visual Basic) the blank cells their possible candidates are continiously updated each time the next value is tried for a cell. And it allways takes the blank cell with the least possible candidates to continue solving. That same principle is handled by real DLX-solvers. If a blank cell has 0 candidates than the previous filled in blank cell(s) caused it and must be reset by backtracking those cell(s) and applying the next possible candidate.

Marc.


Question 1
in step 2 Mark mentions this....
Quote:

Step 2: Conceal a (randomly) single/pair of cell values


What does Mark mean by the word "single/pair"?
isn't that a contradictory?

Question 2
in step 5 Mark discusses about the solver.

Can I use the "4 Line Solver" as below


Code:
While ptr > -1
  sp(cell(ptr)) = (sp(cell(ptr)) + 1) Mod 10
  If sp(cell(ptr)) = 0 Then
    ptr = ptr + 1
  Else
    If CountNum(cell(ptr)) = 3 Then ptr = ptr - 1
  End If
Wend

Quote:
That's the main program loop that solves the puzzle in sp() - just print out the array afterwards to see the solution. The CountNum() function just counts the occurances like this:


Code:

Function CountNum(ByVal n As Integer) As Integer
Dim i, j, k, r, c As Integer

k = 0   'count

'check the row and column
r = n \ 9   'row 0-8
c = n Mod 9   'column 0-8
For i = 0 To 8
  If sp(r * 9 + i) = sp(n) Then k = k + 1   'row
  If sp(c + i * 9) = sp(n) Then k = k + 1   'column
Next

'check the block
c = 3 * (c \ 3)   'left column of block 0/3/6
r = 3 * (r \ 3)    'top row of block 0/3/6
For i = 0 To 2
  For j = c To c + 2
    If sp((r + i) * 9 + j) = sp(n) Then k = k + 1
  Next
Next
CountNum = k

End Function


if I could use this solver than, I see at the beginning of the while loop, the variable ptr is not assigned a value. What should the value for the variable ptr be set at? Should it be 0

[/code]
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sun Jan 18, 2009 4:27 am    Post subject: Reply with quote

It appears the "ptr" is an integer pointing to an index in the array, rather than a C type of pointer (which is an address, not an integer). I don't think Visual Basic even has C style pointers.

There are several solvers with code, posted here. If Mark's looks good to you (that is, you understand it the best when you study the code), then give it a try. Be aware that there are whole threads on generators and solvers, so it will definitely pay off to look around.

Now that the forum's posting problems have cleared up, I hope you'll get more responses from others who have more experience with your kind of Sudoku project.
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Mon Jan 19, 2009 9:30 am    Post subject: Reply with quote

Big Papa -

I have just discovered from Mike Metcalf, in an old thread on the Player's forum, that it *IS* possible to have a unique Sudoku grid with 4 boxes empty (no givens in them).

It's very unusual, but it is definitely possible.

Quote:

Posted: Mon Jan 19, 2009 8:35 am Post subject: Reply with quote
Adak wrote:

1) No stack or band with 2 empty boxes
...

I've read that up to 4 empty boxes (houses), can be allowed and still have a valid Sudoku puzzle. If so, that violates #1, above.


A discussion on empty boxes can be found here. That allows 4 empty boxes altogether, and such beasts exist.

Regards,

Mike Metcalf


See Mike's post in the "Setting Sudoku" sub forum. The link at "here", didn't copy.
Back to top
View user's profile Send private message
Lunatic

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

Items
PostPosted: Thu Jan 22, 2009 6:30 pm    Post subject: Reply with quote

Adak wrote:
It appears the "ptr" is an integer pointing to an index in the array, rather than a C type of pointer (which is an address, not an integer). I don't think Visual Basic even has C style pointers.


Indeed, "ptr" is just what you described, there are no C style pointers in VB6 where the code was written for.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
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 Jan 22, 2009 6:35 pm    Post subject: Reply with quote

Quote:
Quote:
Step 2: Conceal a (randomly) single/pair of cell values

What does Mark mean by the word "single/pair"?
isn't that a contradictory?


Either you conceal a single cell
OR
if you want a grid with some symmetry then conceal a symmetric pair of cells

Quote:
Can I use the "4 Line Solver" as below

Yes, you can

Quote:
I see at the beginning of the while loop, the variable ptr is not assigned a value. What should the value for the variable ptr be set at? Should it be 0


ptr must be set to the index of the last unsolved cell from the array where all unsolved cells are collected. For example, the first unsolved cell is collected at index 0, the second unsolved cell at index 1 and so on...
If there are 55 unsolved cells then the 55th unsolved cell is stored at index 54, so ptr must be set to 54.

BigPapa, are you programming in Visual Basic ?

Otherwise, I have a link to C code based upon my VB code :
http://users.pandora.be/mpq/sudoku/random_sudoku_generator.c
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Sat Jan 24, 2009 4:20 am    Post subject: Reply with quote

This stinks that I cannot still post urls. I need to put my images to explain what is happening so far
Back to top
View user's profile Send private message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Sat Jan 24, 2009 4:20 am    Post subject: Reply with quote

Lunatic wrote:

ptr must be set to the index of the last unsolved cell from the array where all unsolved cells are collected. For example, the first unsolved cell is collected at index 0, the second unsolved cell at index 1 and so on...
If there are 55 unsolved cells then the 55th unsolved cell is stored at index 54, so ptr must be set to 54.


I apologize for not replying in a long time, but I was trying to work on this and I did come up with a problem. One problem I do see is I thought you are to start at the first unsolved cell. This caused the loop to stop after checking the first unsolved cell.

What I did was I created a random generator and then I saved that puzzle. This was done so that, if I ever came up with an error or a problem, I could reuse the same puzzle without having to regenerate a new puzzle. My puzzle looks like this

1. with all answers
[img]https://2650429921707232531-a-1802744773732722657-s-sites.googlegroups.com/site/gamedesignersclub/Home/m/originalpuzzlewithanswers.gif?attredirects=0&auth=ANoY7cpi2DoJ-vGChm-e5Rsn3_4GBOg08MC_fSbKPlo0pmNG2ZLDnd7Yqpba_5qzthr_2077NZPp3vlY5wOJYeUiB5keUWgiQn7n-jpTRCxhgZrPA4GS0w63A1EoNNbusIy-Y_LQxw2mYFEexhDV6mEHDDrzBbiOC98-dR3clBlChskgP9ps_SC2tAzqv3rgDdF2mYKM1COCZrBqn_NYp8_tl2f03Z_1rQAXUZOjPxr19BKJ-lHdZj8%3D[/img]

2. with concealed cells
[img]https://2650429921707232531-a-1802744773732722657-s-sites.googlegroups.com/site/gamedesignersclub/Home/m/myCencealedCells.gif?attredirects=0&auth=ANoY7crGqkZfiTubIER7MZxO-aokPGwmj8KFpFmqjZLr90Kq8_kUonKsOoREaa17oaArxh7_CfMICOvnKgyN9wKfCWzYn21x18VmEBFMG9kOTeiggx-GrgksHjvtGQEtEEimJBuDYKewEniEleeKmERn68MDMRYDEhoriGv0kWlGa5Yg0_lj_1knYkELLehkjgDIYVGxVAdR6sr3oCT2B8XDJrh8bK_z0kEeV7eYF3CA9VgiZRNhIlI%3D[/img]

3. when trying to use the solver
[img]https://2650429921707232531-a-1802744773732722657-s-sites.googlegroups.com/site/gamedesignersclub/Home/m/withUsingSolver.gif?attredirects=0&auth=ANoY7coMP-eCNjFKmdTo6fQuO2yMBzjlhBN5iQIxeoxKfZk6ir5OM7Den42QasDke4b_XIuYirLooGUa52VyCP6l0NBsFUI60SpV5L1klx4ldIvA2orAwkaqEo5vVt9uNIBKYL5yK4r8WsUpkQCqYxNyHmVZ3fWyWk8wesWN-UELU3612voWiaJs2nnFmHNsZFEctQE1pZ-xmHfMcwU-GREd4Y51innvyawEqq0IAdEBF30UwSS4XI0%3D[/img]

Lunatic wrote:

BigPapa, are you programming in Visual Basic ?


Otherwise, I have a link to C code based upon my VB code :
http://users.pandora.be/mpq/sudoku/random_sudoku_generator.c


No, I am not using VB. I am using Director MX11, which uses Lingo Scripting. However, I do know C, and I will take a look at your link when I get a chance.

For the mean time, I really would love to post my code, but I am afraid no-one here knows Lingo Scripting. It is all not that hard to understand, but a few things I think can confuse people here are how linear lists and property lists work. Should I post it anyways?
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sat Jan 24, 2009 4:36 am    Post subject: Reply with quote

I think more valuable than Lingo scripting code, would be a pseudo code of the logic you chose, in plain English. Walk us through what it does.

I prefer a description of the logic, rather than just hundreds of lines of code, especially if it's in a language other than C.
Back to top
View user's profile Send private message
Lunatic

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

Items
PostPosted: Sat Jan 24, 2009 12:14 pm    Post subject: Reply with quote

Bigpapa, since we don't see your images, i downloaded them and uploaded them on my own website, here they are...

1. with all answers


2. with concealed cells


Ok, so you concealed 17 cells.
Now, if you scan the grid from cell 0 (topleft) to cell 80 (bottomright), collect all unsolved cells in an array. The length of that array can be fixed at 81 elements (0 to 80). You can name that array UnsolvedCells (for example).

Normally, to solve a sudoku, you will never need more than total_cells - minimum_clues elements (total_cells for a 9x9 sudoku = 81, and minimum_clues = 17 (no 16-clue sudoku exists)). However, in order to use the same array for generating a solved grid from scratch, you better set the length of that array to 81 elements (total_cells).

Normally you will have another array where the values of the clues are kept, and if the cell is not a clue the value will be 0. For example, that array could have be named Clues() and has 81 elements (0 to 80).

Use a for-next loop to collect all unsolved cells like this (Visual Basic):
Code:
ptr=-1
for i= 0 to 80
    if Clues(i)=0 then
        ptr=ptr + 1
        UnsolvedCells(ptr)=i
    end if
next i


in C code this will look like this:
Code:
ptr=-1;
for (i=0;i<81;i++)
    {
    if Clues[i]==0
        {
        ptr++;
        UnsolvedCells[ptr]=i;
        }
    }


NOTE: I'm not sure you can use 'ptr', as it maybe is reserved in C. You better use CellPtr instead.

At the end of this loop all unsolved cells are collected in the array UnsolvedCells(), and ptr will contain the index pointing to the element in the array UnsolvedCells() where the last unsolved cell number is stored.

3. when trying to use the solver

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

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sat Jan 24, 2009 1:26 pm    Post subject: Reply with quote

ptr is OK to use, it's not a reserved word in C

Thanks for the pics and the explanation, Marc. Great explanation.
Back to top
View user's profile Send private message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Sat Jan 24, 2009 5:00 pm    Post subject: Reply with quote

Adak wrote:
ptr is OK to use, it's not a reserved word in C

Thanks for the pics and the explanation, Marc. Great explanation.


This is embarrassing because I am still lost.

Maybe if I step back get some things cleared off first.

1. If I understand correctly, the puzzle will be ready for a player to solve this puzzle after the following steps below are completed. Am I correct on this?


Quote:

Step 1: Generate a (randomly) filled grid
Step 2: Conceal a (randomly) single/pair of cell values
Step 3: Check for restrictions (no more than 4 empty boxes, no more than 1 empty line in the same band/stack, at least 8 of the 9 values are among the givens) => 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 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


If am correct, then this the procedure of what I have done so far...
1. First I initiated a two-dimensional list, which is similar to a two-dimensional array. This is so that it can hold 9 rows and 9 columns. For example, if you wanted to see cell 15, then list would look like this...
value = PuzzleSoduko[2][6] --this is equivalent to what is inside of cell 15 or row 2 column 6. Note that in a list, and not like in an array, the first element in a list starts at 1 instead of 0 like in other languages do.

2. Once the list has been initialized, I built a generator that will fill all the cells legally. This is done by picking a random unsolved cell and looping through the numbers 1 to 9. When it finds a legal number, then it stores that number inside the proper row and col of the list and moves onto the next random unsolved cell.

3. if the generator cannot fit any of the numbers 1-9, then it backtracks to a different random cell that has been already solved, deletes that cell, and goes back to step 2

in pseudo-code
1. repeat while an empty cell still exists
1.a. pick a random empty cell
1.b. set a variable called noCollision to false
1.c. set another variable called origNumIndex -- this will hold the last number that was used when counting from 1 to 9
1.c. repeat while noCollision = false or origNumIndex = currIndex
1.c.a. set currIndex to (currIndex + 1) mod 9
1.c.b. check if currIndex already exists in its row, col, and 3x3 region => true then go back to 1.c => false set noCollision to true and breakout of 1.c loop and move back to step 1.
1.c.c. if at any chance you have stepped through all 9 numbers then origNumIndex will be equal to currIndex and that means you go to step 2.
2. Do backtracking by doing the following...
2.a. pick a random cell that has already been solved
2.b. delete that cell
2.c. go to step 1

Once I had built a generator that can fill all the cells from a blank puzzle, without getting into technical detail, basically I have the ability to save what's on screen, which this is what I did. I saved the solved puzzle so that I can reuse that puzzle over and over again, until I get my unique solution solver finished. Now that I can reuse this puzzle, I made a very simple concealer. All this does is creates the 17 concealed cell picture above. I then converted Marc's VB script with the while ptr loop solver. However, all I get is the empty cells are filled with numbers that already exist in the puzzle like so...


[img]https://2650429921707232531-a-1802744773732722657-s-sites.googlegroups.com/site/gamedesignersclub/Home/m/fullSolveProblem.gif?attredirects=0&auth=ANoY7coXfonJAqC7ddjiWin2c4lJwQ7-3Y1oRyfd84p-ElzpJO7pjcNVNqU0a2JTI5UVb7AuOk1FYF45otIj4RdcCsdvx1We7muH3Nxure9W964DUmehUeA7SNCuS7gyIuF6uCA8K73KMQQd2C8rjQSrawRRxVojaypoLkFjtD4CqwIcLEUVHtiIX0DzCtwgmqEE2AKBxGEJeNU7M_bOVEQzPcGzTPODHbb0GAHeBEwILR-elOpy7R4%3D[/img]
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  Next
Page 1 of 2

 
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