Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

Thread: Sudoku Creator (this could be a long one)

  1. #1
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Sudoku Creator (this could be a long one)

    Ok, so in the past I attempted to create a Sudoku Creating program. My first step was to create a program that could solve Sudoku Puzzles. After alot of work, that eventually happened. So I then attempted to revise it to create Sudoku Puzzles, but that fails miserably due to logic errors. So I figure I will start from the drawing board again and attempt to do this in my spare time.

    I am going to first start of making this as a static 3x3 Sudoku Creator. When I have it working well, I will modify it to be more dynamic and make larger puzzles.

    I'm short on time right now (got to get to work), so here is my basic methods that come to mind. I have provided what their return types will probably be and I have not provided method variables.

    boolean rowCheck()
    bolean colCheck()
    boolean boxCheck()
    boolean swapBox()
    boolean swapRow()
    boolean swapCol()
    void setNumber()
    ? getBox() -- Depends on how I do this



    So, first off. What sort of collection should I use for this? The first time around I used a 2 Dimensional Array, but that proved to be problematic when I had to deal with each 3x3 box. So that is preferably not my choice. Alternatively, I considered using a 2 Dimensional Linked List of 2 Dimensional Arrays. Where each 2 Dimensional Array will contain a 3x3 box, and they are linked together in a 2 Dimensional Linked List. But that may make it complicated to check horizontally and vertically along lines. Alternatively again, I think I will create a Box class of sorts that contains each box. But I will have to communicate with the other boxes to get their rows/columns when necessary. which could be a problem.

    I'll keep updating this as things come to mind. Any help is appreciated.
    Last edited by aussiemcgr; July 26th, 2010 at 09:44 AM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Sudoku Creator (this could be a long one)

    Writing a Sudoku game is a great all around learning project, because of the logic, design, and number of different ways it can be implemented. When I dabbled in them long ago, I ended up just using a 1d array for the puzzle and several lookup tables specifying the 'rules'. (these were just 2d arrays containing int's specifying the appropriate indexes in the 1d main array).
    As for creating the puzzle, there is actually a very simple method to generate the puzzle which doesn't involve tedious backtracking (hint, start with a solved puzzle).
    If you haven't yet, search the forums for sudoku to pull up more ideas.

  3. #3
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Re: Sudoku Creator (this could be a long one)

    Well, my plan for this is to tackle each box individually and attempt to add random numbers that are still unused in the box. When it reaches logic errors, it will swap numbers to find a solution that works.

  4. #4
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Re: Sudoku Creator (this could be a long one)

    Ok, so I'm working on figuring out the last part of creating the Sudoku Puzzle. After running through several checks and whatnot, it gets to the point where I have a few blank spots due to logic errors. What I need to do now is swap and insert numbers to fix the current logic errors. By doing so, I will create more logic errors, but those will get solved aswell. I've proven (through doing it by hand) that it is possible to swap around until all the answers are fixed, but I cant seem to think of a way to turn that into an algorithm.

    Here is what a puzzle looks like when it comes out (cant really format). 0s indicate a blank spot.
    7	8	2		4	1	6		9	3	5
    3	1	4		2	9	7		6	8	0
    9	0	6		5	8	3		7	1	2
     
    2	9	3		6	7	4		1	5	8
    4	6	8		1	5	2		3	9	7
    1	7	5		9	3	8		2	6	4
     
    8	4	1		7	6	5		0	2	9
    6	0	7		3	2	9		5	4	1
    5	3	9		8	4	1		0	7	6

    And here are two solutions I found doing it by hand
    7	8	2		4	1	6		9	3	5
    3	1	4		5	9	7		2	8	6
    9	5	6		2	8	3		7	1	4
     
    2	9	5		3	7	4		1	6	8
    4	6	8		1	5	2		3	9	7
    1	7	3		9	6	8		4	5	2
     
    8	3	1		7	2	5		6	4	9
    6	4	7		8	3	9		5	2	1
    5	2	9		6	4	1		8	7	3

    7	8	2		4	1	6		9	3	5
    3	5	4		2	9	7		6	8	1
    9	1	6		5	8	3		7	4	2
     
    2	9	3		6	7	4		1	5	8
    4	6	8		1	5	2		3	9	7
    1	7	5		9	3	8		2	6	4
     
    8	4	1		7	6	9		5	2	3
    6	2	7		3	4	5		8	1	9
    5	3	9		8	2	1		4	7	6

    Can anyone help me work out an algorithm to do the logic swapping? So far, I figure solving via column and inserting based on least amount of collateral damage is best. This mean swapping mainly along column lines inside of boxes and sometimes row lines inside of boxes.
    Last edited by aussiemcgr; July 26th, 2010 at 03:59 PM.

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,895
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Sudoku Creator (this could be a long one)

    You can easily generate a sudoku by starting with a "base" solved puzzle, then only swap rows/columns that reside in the same row/column of boxes. If you swap the these randomly several times, then randomly remove a bunch of numbers, you'll end up with a sudoku. Note: This method is not guaranteed to generate a "unique solution" sudoku (one that only has one possible solution).

    So, for example:

    You can swap row 0 with row 2 because they reside in the first 3 rows, and thus the first row of boxes.
    You can swap row 3 with row 4 because they reside in the second row of boxes.
    You can't swap row 0 with row 4 because they are in different rows of boxes.

    The same concept applies to columns.


    To solve a sudoku, the simplest solution is to just brute-force it. Just keep putting number into a spot and make sure the puzzle is still solvable. If it isn't try a different number. If you've exhausted all possible numbers for that spot, trace back and try a different number for the previous number to selected. There's few enough combinations that it can be solved by modern computers within a few seconds or less.

  6. #6
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Re: Sudoku Creator (this could be a long one)

    I dont want to start off with a base solved puzzle because this will be dynamic in size. Meaning when it's done it will be able to create 9x9,16x16,25x25,36x36,49x49, ect. For that to work with a base solved puzzle, I would have to find a puzzle for every possible square, which is insanity. For that reason, I am creating puzzles from scratch.

    I have already created a program that can solve a solvable puzzle. By a solvable puzzle, I mean one that actually has an answer, opposed to what I currently have with my Sudoku Puzzle Creator, where the puzzle cannot be solved due to logic errors.

    I am not attempting to solve the sudoku puzzle above, but rather make it solvable by finishing the creation of it.

  7. #7
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Sudoku Creator (this could be a long one)

    Quote Originally Posted by aussiemcgr View Post
    I dont want to start off with a base solved puzzle because this will be dynamic in size. Meaning when it's done it will be able to create 9x9,16x16,25x25,36x36,49x49, ect. For that to work with a base solved puzzle, I would have to find a puzzle for every possible square, which is insanity. For that reason, I am creating puzzles from scratch.
    Not to belabor the point, but the solution that I very poorly hinted at and helloworld explained more thoroughly works for any size - there is a simple algorithm to create a solved puzzle of any size, and a simple algorithm to shuffle the puzzle up - and its much faster than brute force. You can them incrementally remove positions to create a puzzle with a defined solution and degree of difficulty.

  8. #8
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Re: Sudoku Creator (this could be a long one)

    there is a simple algorithm to create a solved puzzle of any size, and a simple algorithm to shuffle the puzzle up
    Ok, wait. When you say "create a solved puzzle of any size" are you saying that the puzzle is stored in external memory or that an algorthm creates the puzzle? Because what I am currently doing is an algorithm that creates the puzzle. After I have it to a point where it can create a puzzle every time, I will incrementally remove positions and whatnot to create the actual puzzle. What I am trying to do right now is create a solved puzzle.

  9. #9
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Sudoku Creator (this could be a long one)

    There is a pattern to the following simple solution (for each row, shift the previous by 3: caveat: when you reach a boundary (eg row 4/7) shift the first row of the previous block by 1). You can create this pattern every time, or just have them saved in memory:
    1    2    3    4    5    6    7    8    9
    4    5    6    7    8    9    1    2    3
    7    8    9    1    2    3    4    5    6
    2    3    4    5    6    7    8    9    1
    5    6    7    8    9    1    2    3    4
    8    9    1    2    3    4    5    6    7
    3    4    5    6    7    8    9    1    2
    6    7    8    9    1    2    3    4    5
    9    1    2    3    4    5    6    7    8

    Now shuffle...randomly swap rows and columns that belong to the same 'block' (eg row 1 and 2, column 4 and 6, etc...I'm using 1-based integers here). Swap as many as you want to randomize. Each time you do this you are generating a pseudo random puzzle (and it holds true for other dimensions, just the block and shift size changes). You can also save this solved puzzle as a 'seed' to the next randomization. There is no necessity to backtrack or use brute force. Its actually, in my opinion, a bit elegant.
    Last edited by copeg; July 27th, 2010 at 12:23 PM.

Similar Threads

  1. java creator problem
    By vgenopoulos in forum Java Theory & Questions
    Replies: 5
    Last Post: July 7th, 2010, 09:58 AM
  2. How long did it take you to learn?
    By JavaLearner in forum The Cafe
    Replies: 5
    Last Post: March 24th, 2010, 04:42 PM
  3. Sudoku solver
    By Elliott50 in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 22nd, 2009, 02:03 PM
  4. Sudoku coding help...please
    By sketch_flygirl in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 5th, 2009, 10:07 PM
  5. Sudoku
    By mgutierrez19 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 30th, 2009, 10:09 PM