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

Hybrid View

  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
    557

    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 10: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 03: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 03:48 AM.

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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center