Printable View
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.
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.
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.
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 trackCode:#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, "%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.")
}
}
}
}
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
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
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.
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.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*/
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.
That should get you started. :)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;
}
}
}
}
Was this solved?
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.Quote:
Originally Posted by IdioticCreation
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!
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;
}
}
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.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;
}
}
Good luck you student guys.
Ajay