CODEWITHSUNDEEP
algorithmrecursioniteration
Héctor van den Boorn
Héctor van den Boorn

Reputation: 1218

Iterative Sudoku algorithm

I've created in the past a very simple algorithm to brute-force sudoku solutions. This was very easily done in a recursive way by putting each possible value in each cell in every single combination so long as there are no inconsistensies (like two cells in the same row having the same value).

recursively (in pseudocode):

solve_sudoku(int[][] cell, int x, int y)
if (isSolution)
{
   return field;
}
else
{
   for (int i=1; i<9; i++)
   {
     if (legal_move(x,y,i))
        cell[x][y] = i;
        solve_sudoku(cell,x+1,y);
   }
}

I'm wondering if there is an iterative method of bruteforcing sudoku solutions? I don't think it's possible, but I'm not sure. If it exists, how would that look like?

Héctor

Upvotes: 1

Views: 1515

Answers (1)

Benjamin Gruenbaum
Benjamin Gruenbaum

Reputation: 276296

Using a stack is the easiest way to convert recursive code to iterative code. That's how recursion works (with the function call stack) anyway.

Here is iterative pseudo code that is a rough translation of your recursive one.

while(!isSolution(head_of_stack) && stack_not_empty)
{
   current = pop_head_of_stack
   for(move in legal_moves(current)){
       stack.push(move) // move is your x,y passed recursively
                        // or the whole board - depending how you 'undo' moves
                        // at the recursive backtracking now
   }

}
return head_of_stack

Upvotes: 3

Related Questions