# How does one make a program to provide all the 'possible' numbers in an empty cell

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.

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

• @martijnn2008 You have misunderstood the question. – Alan Ross Jun 1 '14 at 12:21
• ok i did misunderstood the question, but what do you expect as answer? – martijnn2008 Jun 1 '14 at 15:15
• @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. – Alan Ross Jun 1 '14 at 15:18
• 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. – Alan Ross Jun 1 '14 at 15:50
• see tex.stackexchange.com/questions/182608/… about my other questions and how I use 'black magic' to solve them! – Alan Ross Jun 2 '14 at 9:59

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.

• 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. – Alan Ross Jun 1 '14 at 15:40
• I hope this version is more usefull – martijnn2008 Jun 1 '14 at 16:46

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.