# Sudoku

• 04-03-2008
mrusnak
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.
• 04-03-2008
Dino
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.
• 04-04-2008
kcpilot
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.
• 04-04-2008
mrusnak
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
• 04-04-2008
vart
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
• 04-04-2008
matsp
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
• 04-05-2008
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. :)
• 04-07-2008
• 04-07-2008
IdioticCreation
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.
• 04-08-2008
Quote:

Originally Posted by IdioticCreation
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.

Tell her good luck at the Science Fair!
• 03-20-2009
apts
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 ajay.pratap.singh@gmail.com and I will come back to you.

Good luck you student guys.

Ajay