Thread: Sudoku

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    5

    Sudoku

    I am trying to write a program to check whther a given 9x9 grid is actually a solution to a sudoku puzzle. I dont really play the game and I cant seem to think how I will go about this. Any ideas would be great! I have started writing some code, but its nto nearly finished yet.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    This reminds me of the Dilbert cartoon where the boss tells the programmers to go ahead and start coding, while he then leaves to go ask the users what they want.

    In my opinion, you pretty much need to understand the game, inside and out, to be able to translate that understanding into program logic.
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Registered User
    Join Date
    Jan 2007
    Location
    Euless, TX
    Posts
    144
    Sudoku is based on each 3 by 3 square containing only 1 each of the numbers 1 through 9. Also each vertical and horizontal line must contain only one each of the numbers 1 through 9. So that is what you must do to check that the 9 by 9 array of numbers is a correct Sudoku solution.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    5
    Code:
    #include <stdio.h>
    #include <math.h>
    
    int sudoku[9][9];
    
    main()
    {
    	int sudoku, m, q, p, n;
    	FILE *inp; 
    	
    	*inp = fopen("sudoku-solution.txt", "r");
    	
    	
    	
    	while(fscanf(inp, "&#37;d", &sudoku) != EOF)
    	{
    		for(n = 0; n < 9; n++);
    		{
    			for(p = n + 1; p < 9; p++)
    			{
    				if(sudoku[n][9]==sudoku[p][9])
    					printf("The solution is not valid.")
    			}
    		}
    		for(q = 0; q < 9; q++);
    		{
    			for(m = q + 1; m < 9; m++)
    			{
    				if(sudoku[9][q]==sudoku[9][m])
    					printf("The solution is not valid.")
    			}
    		}	
    	
    	}
    
    }
    here is what i have so far, although there is an error when i compile of subscripted value is neither pointer nor array. I am not sure how to check the 3x3 boxes yet but just want to make sure im on the right track

  5. #5
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    main()
    should be int main(void) - http://faq.cprogramming.com/cgi-bin/...&id=1043284376

    int sudoku[9][9]; - why do you need it global?


    int sudoku, - you hide your sudoku array - it cannot be accessed from the main function

    sudoku[n][9] - 9 is not a valide index - valid indexes are from 0 to 8

    you should add return 0; at the end of main
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And you will most likely find that it's much easier to verify the soduko if you read all the 81 numbers first into a 9 x 9 matrix, then check the validity of the solution when you have the full matrix.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    There are two ways two ways I know of to check if an answer is "OK" in Sudoku.

    1) Everything the program does to solve the grid, is thoroughly legal. It never places an illegal candidate, or makes an illegal candidate, into an answer digit.

    Basically, once you're positive of that, you don't need to check anything else except that each cell has been assigned a value.

    2) Distributed counting.

    Code:
    int dc[10] = {0}; //dc[0] is not used since 0 is not allowed as a digit in a cell
    
    for each cell in the group you're focusing on right now (row, column or box)
       if(A[n])
          dc[n]++;
    
    /*dc is fully loaded here*/
    for(i = 1; i < 10; i++)
       if(dc[i] != 1)
          return 1;  /*solution was wrong*/
    
    return 0;  /*group (row, col, or box) was OK*/
    OK means just that, OK for now. To be a solution, each row, column and box must pass the above dc check AND they must have retained the original given values, in the correct cells.

    THEN it's a solution.

    This is code which uses a 3D array. You can ignore the third dimension here, however. Shows how to traverse all rows, all columns, or all boxes, however.

    PossAll = Possibles, All. The zero'th element of PossAll[row][column][candidate value], is
    never used, in any dimension, here.

    Code:
    /*zero's out any possibles resulting from a cell being assigned a value, in all boxes*/
    void BoxPossibles()	{	//
    	int box, c, col, lowcol, lowrow, n, r, row;  
    	lowrow = 1; lowcol = 1;
    	for(box = 1; box < 10; box++)	{ 
    		for(row=lowrow; row<lowrow+3; row++)	{
    			for(col=lowcol; col<lowcol+3; col++)	{
    				if(A[row][col])	{
    					n = A[row][col];
    					for(r = lowrow; r < lowrow + 3; r++)
    						for(c = lowcol; c < lowcol + 3; c++)
    							PossAll[r][c][n] = 0;
    				}
    			}
    		}
    		lowcol += 3;
    		if(lowcol > 9) {
    			lowcol = 1;
    			lowrow += 3;
    		}
    	}
    }
    /*zero's out all possibles for a cell with a value, in a column*/
    void ColPossibles()	{  
    	int c, i, r, n;
    	for(c = 1; c < 10; c++)	{
    		for(r = 1; r < 10; r++)	{
    			if(A[r][c])	{
    				n = A[r][c];
    				for(i = 1; i < 10; i++)
    					PossAll[i][c][n] = 0;
    			}
    		}
    	}
    }
    /*zero's out possibles across the row, for any sqr assigned a value*/
    void RowPossibles()	{	
    	int i, n, r, c;
    	for(r = 1; r < 10; r++)	{
    		for(c = 1; c < 10; c++)	{
    			if(A[r][c])	{
    				n = A[r][c];
    				for(i = 1; i < 10; i++)	
    					PossAll[r][i][n] = 0;
    			}
    		}
    	}
    }
    That should get you started.

  8. #8
    Registered User toadkiwi's Avatar
    Join Date
    Feb 2008
    Posts
    31
    Was this solved?

  9. #9
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    If you needed to know if the given numbers made for a possible solution, then I have some good news. I have a peer who's doing research over Sudoku and bipartite graphs. She found a way to tell if the given numbers would allow for non-unique solutions (multiple solutions) as well as some other things about the puzzle. I don't have her research right now, but if you need it I can get it.

    It's a really cool project. She's going to the international science fair with it.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by IdioticCreation View Post
    If you needed to know if the given numbers made for a possible solution, then I have some good news. I have a peer who's doing research over Sudoku and bipartite graphs. She found a way to tell if the given numbers would allow for non-unique solutions (multiple solutions) as well as some other things about the puzzle. I don't have her research right now, but if you need it I can get it.

    It's a really cool project. She's going to the international science fair with it.
    I'm just starting a Sudoku project which involves searching the entire space where a grid has 16 given values in it.

    And the thing I need most is a fast and accurate way of telling if the millions of grids my program generates, could lead to a unique solution.

    I would love to read all about her project, and thanks in advance for any help.

    Tell her good luck at the Science Fair!

  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    1

    Original Solution for this problem

    Sorry for giving you guys solution in the Java. But similar approach can be taken for writing in C. Infact, I prefer to write in C but since i am professional java developer, so i had to write. It was asked in one of the interview question from me.

    I have three files, test.java, Sudoku.java and Helper.java. Put all these three file in any defaul package and run the test.java and you have it.

    Code:
    **************************************
    test.java
    **************************************
    import java.util.ArrayList;
    import java.util.List;
    /**
     * @author Ajay.Singh
     *
     */
    public class test {
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		int i,j;
    		int inputArray[][] = Sudoku.sudoku();
    		List<Helper> verticalList = new ArrayList<Helper>();
    		List<Helper> boxList = new ArrayList<Helper>();
    		for(i=0;i<9;i++){
    			List<Integer> horzList = new ArrayList<Integer>(); 
    			for(j=0;j<9;j++){
    				//To check the distinct value in the row
    				if(!horzList.contains(inputArray[i][j]))
    					horzList.add(new Integer(inputArray[i][j]));
    				else
    					System.out.println("Not distinct element in the row" + inputArray[i][j] );
    				//To create 9 columns - 9 list
    				if(i==0){
    					List<Integer> list = new ArrayList<Integer>();
    					Helper element = new Helper ();
    					element.setRow(list);
    					verticalList.add(element);
    				}
    				//To create 9 boxes - 9 list
    				if(i%3==0 && j%3==0){
    					List<Integer> boxesList = new ArrayList<Integer>();
    					Helper element = new Helper ();
    					element.setRow(boxesList);
    					boxList.add(element);
    				}
    				//To check for duplicate entry or else store in list
    				if(verticalList.get(j).getRow().contains(inputArray[i][j]))
    					System.out.println("Not distinct element in column" + inputArray[i][j] );
    				verticalList.get(j).getRow().add(inputArray[i][j]);
    				//To check for duplicate entry or else store in list
    				if(boxList.get((i/3!=0?3*(i/3):0)+j/3).getRow().contains(inputArray[i][j]))
    					System.out.println("Not distinct element in box" + inputArray[i][j] );
    				boxList.get((i/3!=0?3*(i/3):0)+j/3).getRow().add(inputArray[i][j]);
    			}
    		}
    		System.out.println("Yes this is perfect sudoku for 9 by 9");
    	}
    }






    Code:
    *********************************************
    Helper.java
    *********************************************
    
    import java.util.List;
    
    
    public class Helper {
    	
    	public List<Integer> row;
    
    	/**
    	 * @return the row
    	 */
    	public List<Integer> getRow() {
    		return row;
    	}
    
    	/**
    	 * @param row the row to set
    	 */
    	public void setRow(List<Integer> row) {
    		this.row = row;
    	}
    	
    	
    
    }




    Code:
    ***********************************************
    Sudoku.java
    ***********************************************
    
    /**
     * @author Ajay.Singh
     *
     */
    public class Sudoku {
    	
    	/**
    	 * @return two dimensional array
    	 */
    	public static int[][] sudoku(){
    		final int sudoku[][]={
    				{7,6,2,5,8,9,3,4,1},
    				{1,5,3,2,6,4,9,7,8},
    				{4,8,9,1,3,7,5,6,2},
    				{6,4,1,3,2,8,7,5,9},
    				{5,9,7,6,4,1,2,8,3},
    				{2,3,8,7,9,5,4,1,6},
    				{9,2,4,8,7,6,1,3,5},
    				{8,7,5,9,1,3,6,2,4},
    				{3,1,6,4,5,2,8,9,7}
    		};
    		return sudoku;
    		
    	}
    
    }
    If anybody is really interested for this to be written in C, just contact me [email protected] and I will come back to you.

    Good luck you student guys.

    Ajay

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku 4 by 4 combination lister?
    By iskate4 in forum C++ Programming
    Replies: 2
    Last Post: 02-19-2009, 01:56 PM
  2. malloc, structures, arrays and sudoku!!
    By AmbliKai in forum C Programming
    Replies: 13
    Last Post: 10-15-2008, 03:05 AM
  3. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM
  4. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM