Last step in generating Sudoku Puzzles
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Last step in generating Sudoku Puzzles

  1. #1
    Join Date
    May 2009
    Posts
    5

    Post Last step in generating Sudoku Puzzles

    I have some code here that I need some help finishing. This code generates a random Sudoku Puzzle, problem is though that the one thing it is currently not checking for is having only one of each number in a set of three. I'm not quite sure on how to code that. Any help would be appreciated.

    import java.util.*;

    // produce a Sudoku grid
    public class SudokuGenerator {

    // the grid with the numbers
    private int[][] grid;
    // a single row
    private int[] row;
    // random and aray list
    private Random ran;
    private ArrayList<Integer> al;
    // number of row and column
    private int size;

    // size of the Sudoku grid is received as parameter
    SudokuGenerator(int size) {
    this.size = size;
    // this this the grid that we will fill
    grid = new int[size][size];
    // this is to store a row that we are trying to build
    row = new int[size];
    // random number generator
    ran = new Random();
    // arraylist that will contain the possible values for every case in the grid
    al = new ArrayList<Integer>();

    // now let's fill the grid row by row
    for(int i = 0; i < size; i++)
    fillRow(i);
    }

    // will call genRow() to fill row
    // then will copy that row into the grid... the main reason for this method is to display debug info
    private void fillRow(int n) {
    genRow(n); // get a new row
    // ok i can copy the row into the grid
    System.out.print("Row " + n + ":");
    for(int i = 0; i < size; i++) {
    grid[n][i] = row[i];
    System.out.print(" " + row[i]); // optional debug statement
    }
    System.out.println();

    }
    // fill the instance variable row with a new row
    private void genRow(int n) {
    // will be used to flag which values are available or not
    boolean[] used = new boolean[size];
    // it might take more than one trial to fill a row
    // imagine the following case
    // 1 2 3 4
    // 2 3 4 1
    // now if I add for the third row
    // 3 then
    // 3 4 then
    // 3 4 2 then
    // the only possible case for the last column is 1 but 1 is invalid in the last column
    // so we'll have to try again
    boolean conflict = true; // assume we have conflict to enter the while loop
    while(conflict) {
    conflict = false; // assume it worked
    // loop for each column of the row
    for(int i = 0; i < size; i++) {
    // initialized that all number form 0 to size are not used and are available
    for(int j = 0; j < size; j++)
    used[j] = false;
    // i cannot use any previous number used on that row so I set to true
    // all the already allocated numbers in that row
    for(int j = 0; j < i; j++)
    used[row[j]] = true;
    // i cannot use neither the numbers used in the same column in the previous rows already filled
    for(int j = 0; j < n; j++)
    used[grid[j][i]] = true;
    // fill the array list with the possible values
    al.clear(); // empty the arraylist
    for(int j = 0; j < size; j++) { // fill it with the permitted values
    if(!used[j]) { // if number not used
    al.add(j); // add it to arraylist
    }
    }
    // now case explained in comment for variable conflict
    // in that case no number would have been entered in the arraylist so its size would be 0
    if(al.size() == 0) {
    // if it is the case flag that there is a conflict
    conflict = true;
    break; // no need to continue the loop
    }
    // pickup a number randomly from the arraylist
    row[i] = al.remove(ran.nextInt(al.size()));
    }
    }
    }

    // to retreive the grid
    public int[][] getGrid() {
    return grid;
    }
    // to print the grid (numbers are from 0 to size-1)
    // but for regular user we will display from 1 to size
    public String toString() {
    String str = "";
    for(int i = 0; i < size; i++) { // for every row
    for(int j = 0; j < size; j++) { // and column
    str += " " + (grid[i][j] + 1); // add value to String
    }
    str += "\n"; // end of line
    }
    return str;
    }


    public static void main(String[] arg) {
    SudokuGenerator s = new SudokuGenerator(9);
    System.out.print(s);
    }
    }

  2. #2
    Join Date
    Jul 2005
    Location
    Currently in Mexico City
    Posts
    566

    Re: Last step in generating Sudoku Puzzles

    Sorry for a stupid question, I haven't ever played Sudoku, so I don't know the rules: what do you mean by "having only one of each number in a set of three"

    - you showed an example in the code but the sets were vertical only. Does the same rule apply to the horizontal sets as well?
    - can the game be 8x8 or it's always a multiplier of 3?
    - if yes, the uniqueness of sets you wanted is applied for 3x3 window only, or in case of 9x9 it should be 9x9 set uniqueness?

    I believe I could solve your problem, I'm just asking to be able to help...

    Edit: Ok I briefly revised the rules and I saw that I understood nothing about the thing you wrote about filling an instance with rows.
    What are additional rules/facts?
    Last edited by Xeel; May 7th, 2009 at 11:38 AM.
    Wanna install linux on a vacuum cleaner. Could anyone tell me which distro sucks better?

    I had a nightmare last night. I was dreaming that Iím 64-bit and my blanket is 32-bit and I couldnít cover myself with it, so Iíve spent the whole night freezing. And in the morning I find that my blanket just had fallen off the bed. =S (from: bash.org.ru)

    //always looking for job opportunities in AU/NZ/US/CA/Europe :P
    willCodeForFood(Arrays.asList("Java","PHP","C++","bash","Assembler","XML","XHTML","CSS","JS","PL/SQL"));

    USE [code] TAGS! Read this FAQ if you are new here. If this post was helpful, please rate it!

  3. #3
    Join Date
    May 2009
    Posts
    5

    Re: Last step in generating Sudoku Puzzles

    Basically the objective is to fill a 9◊9 grid so that each column, each row, and each of the nine 3◊3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid. The code now checks for conflicts in the rows and columns, I'm just not sure how to check for a conflict in a 3x3 set. The game technically can be 8x8 or 4x4, I just have it set to the standard 9x9 at the moment, which is what I will be using. The uniqueness is for the rows, columns, and 3x3 sets.

  4. #4
    Join Date
    Feb 2008
    Posts
    966

    Re: Last step in generating Sudoku Puzzles

    The checking of the 3x3 grid is the hardest part without a doubt. What you have to do is get the upper left hand location and make your ending conditions for your loop +3 from there.

    So basically you get the array[0][0] for the first grid. You check it while i < 3 and j < 3 making sure that the numbers 1-9 only appear once during your checks. Then you move on to the next one, making your starting points your previous ending points: while i = 3 and i < 3+3 = 6 (or j, depending on how you set up your loops), then repeat for the other loop variable.

    Something like this:
    Code:
    for(int k = 0; k < 9; k++) { // you have 9 3x3 squares
        //get i and j points
        //set i and j ending points
        for(;i < iEnd; i++) {
             for(;j < jEnd; j++) {
                //do your checking here
             }
        }
    }

    There is a neat way to get your i, j, iEnd and jEnd. I don't want to just give it to you, I want you to try and think of it first. Come up with what you think it should be and I'll help you with it. HINT* You should use k and &#37; somewhere in there. Good luck

  5. #5
    Join Date
    May 2009
    Posts
    5

    Re: Last step in generating Sudoku Puzzles

    I guess I'm just burnt out on Sudoku, this was the best I could do.




    for(int k = 0; k < 9; k++) {

    for( j = 0; j < j+3; j++ )
    {
    for(i=0; i< i+3; j++)
    used[grid[i][j]]=true
    }
    }



    Update:

    k&#37;3 ?
    Last edited by DT31; May 8th, 2009 at 04:54 AM.

  6. #6
    Join Date
    May 2009
    Posts
    5

    Re: Last step in generating Sudoku Puzzles

    I'm a bit confused as to how your code or hint fits into my code..I can't even think anymore, this program has me starting to hate Sudoku.


    Update: I still haven't gone to sleep and this STILL doesn't make any sense to me. I can't even set the loop up. I would really really like to both be able to go to sleep and be done with this program, so if anyone can help me out with what I need to add to my code it would be much, much, much, much,much appreciated. Thanks!
    Last edited by DT31; May 8th, 2009 at 04:48 AM.

  7. #7
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Last step in generating Sudoku Puzzles

    Once you get into that mental state, the best thing you can do is to go to sleep and dream about the problem. I usually find everything is clearer after a restless night's sleep

    It is probably best to work out how to do the checks step by step on paper before trying to write any code.

    Every now and then go away, have a little relaxation, for when you come back to your work your judgment will be surer. Go some distance away because then the work appears smaller and more of it can be taken in at a glance and a lack of harmony and proportion is more readily seen...
    Leonardo Da Vinci
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

  8. #8
    Join Date
    May 2009
    Posts
    5

    Re: Last step in generating Sudoku Puzzles

    I drew this picture...I understand what I need to do...just writing it is the problem haha. Thanks for the tip thought it was nice to get some rest.
    Attached Images Attached Images  
    Last edited by DT31; May 8th, 2009 at 11:48 AM.

  9. #9
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Last step in generating Sudoku Puzzles

    Quote Originally Posted by DT31 View Post
    I drew this picture...I understand what I need to do...just writing it is the problem haha.
    A diagram is a great way of understanding the problem, but not so great for figuring out what the code will be. You need an intermediate step between diagram and code. Try writing down how you would explain to someone how to do it - in simple steps in English. Don't worry about loops and ordering at first. Look at each step you've written and see if it can be broken down into simpler steps. When you have detailed all the different steps you think are needed, work out the order they must fit together and how you need to loop back to repeat steps, e.g. to do the rows and/or columns, etc. When you can describe what to do step by step, in English, you can then start thinking about how that would look as code.

    The problem is mainly a logic puzzle - work it out as fully as you can before translating it into Java. Writing code is hard enough without having to figure out the program design at the same time.

    If I had eight hours to chop down a tree, I would spend 6 hours sharpening an axe...
    Anon.
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center