-1
$\begingroup$

To be able to solve a sudoku one usually has to first work out all the 'possible' numbers in an empty cell. How can one make a program to do this? In this case 'possible numbers' are ones which have not yet been provided elsewhere in the same line column or box and therefore this cell can possibly have those numbers.

enter image description here

This is not meant to solve the puzzle.But helpful for those who want to do it by hand. see also here

$\endgroup$
  • $\begingroup$ @martijnn2008 You have misunderstood the question. $\endgroup$ – Alan Ross Jun 1 '14 at 12:21
  • $\begingroup$ ok i did misunderstood the question, but what do you expect as answer? $\endgroup$ – martijnn2008 Jun 1 '14 at 15:15
  • $\begingroup$ @martijnn2008 A kind of pseudo code to provide the answer. Anyone doing a sudoku problem unless using my books which already provide it (see my profile) would need to use such a program before starting the solving itself. $\endgroup$ – Alan Ross Jun 1 '14 at 15:18
  • $\begingroup$ My previous question of how to make a sudoku puzzle was considered too broad so now I am splitting it up with many questions all necessary for the end product. $\endgroup$ – Alan Ross Jun 1 '14 at 15:50
  • $\begingroup$ see tex.stackexchange.com/questions/182608/… about my other questions and how I use 'black magic' to solve them! $\endgroup$ – Alan Ross Jun 2 '14 at 9:59
2
$\begingroup$

Algorithm:

int[][] sudoku = new int[9][9];
sudoku = [input the numbers]; // 0 if not known
for-each cell (x,y) do:
  int[] O = {1,2,3,4,5,6,7,8,9};
  // remove from O all numbers that are in the same square
  (bX, bY) = getBlockXY( cell (x,y) ); // this can be done with some if-statements
  for i = 1 to 3 do:
    for j = 1 to 3 do:
      if sudoku[bX * 3 + i][bY * 3 + j] then : // evaluates to true if known
        O.remove(sudoku[bX * 3 + i][bY * 3 + j]); 
      end if
    end for
  end for      

  // remove from O all numbers that are in the same row
  for i = 1 to 9 do:
    if sudoku[i][y] then :
      O.remove(sudoku[i][y]);
    end if
  end for

  // remove from O all numbers that are in the same column
  for i = 1 to 9 do:
    if sudoku[x][i] then :
      O.remove(sudoku[x][i]);
    end if
  end for

  print O
end for-each

I think you could do this more efficiently by using some kind of datastructure. I have no idea about that yet.

$\endgroup$
  • $\begingroup$ Correct that is the basic idea of what one has to do before venturing to solve a sudoko unless it has already been done for you. $\endgroup$ – Alan Ross Jun 1 '14 at 15:40
  • $\begingroup$ I hope this version is more usefull $\endgroup$ – martijnn2008 Jun 1 '14 at 16:46
1
$\begingroup$

I had my solver use a simple process of elimination. I gave each cell an array of possible values and linked them by row, column and grid. Then, whenever a number is selected, I removed it from the array of possible values in the grid, row and column for that number being selected. I then iteratively looked for the space with the fewest possible options and selected it next.

There are further efficiencies that can be gained, but this is one of the simplest ways to implement a solver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.