Algorithm to solve sudoku

Question

I'm trying to write an algorithm, which solves an extended Sudoku. I managed to find the solution for 9x9 Sudoku, but when I tried to extend it my program returns "No solution" and I don't have an idea what is wrong. Maybe someone can suggest where I made a mistake?

#include<stdio.h>
#include<algorithm>

int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9},
                    {4, 7, 0, 0, 0, 0, 0, 0, 0},
                    {0, 0, 0, 5, 6, 2, 0, 0, 3},
                    {0, 6, 0, 0, 0, 0, 0, 0, 0},
                    {0, 0, 4, 0, 0, 3, 0, 6, 0},
                    {0, 5, 9, 0, 0, 0, 0, 0, 0},
                    {0, 0, 0, 2, 0, 0, 0, 0, 0},
                    {6, 0, 0, 4, 0, 0, 0, 0, 0},
                    {0, 4, 8, 0, 0, 0, 6, 0, 0},
                    {0, 0, 4, 0, 0, 0, 0, 0, 0},
                    {0, 2, 0, 0, 0, 0, 1, 0, 0},
                    {0, 9, 1, 0, 0, 4, 0, 0, 5},
                    {0, 0, 0, 0, 0, 0, 0, 0, 0},
                    {4, 0, 0, 6, 0, 0, 0, 0, 5},
                    {5, 0, 0, 0, 0, 0, 8, 6, 0}};

bool isPossibleToInsert(int array[][9], int v, int x, int y){
    int rows = (x / 3) * 3;
    int columns = (y / 3) * 3;
    for (int i=0; i<9; i++){
            if (i < 3){
                    for (int j=0; j<7; ++j){
                            if (sudoku[j][y] == v) return false;
                    }
            }
            if (i > 5){
                    for (int j=8; j<=14; ++j){
                            if (sudoku[j][y] == v) return false;
                    }
            }
            if (array[x][i] == v) return false;
            if (array[i][y] == v) return false;
            if (array[rows + i%3][columns + i/3] == v) return false;
    }
    return true;
}

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y);
bool tryToSolve(int sudoku[][9], int temp[][9], int x_val, int y_val){
    if (sudoku[x_val][y_val] == 0){
            for (int i=1; i<=9; ++i){
                    if (isPossibleToInsert(temp,i,x_val,y_val)){
                            temp[x_val][y_val] = i;
                            if (checkNextCell(sudoku,temp,x_val,y_val)) return true;
                    }
            }
            temp[x_val][y_val] = 0;
            return false;
    }
    return checkNextCell(sudoku,temp,x_val,y_val);
}

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y){
    if ((x == 8) && (y == 8)) return true;
    else if (x == 8) return tryToSolve(orginal,copy,0,y+1);
    else return tryToSolve(orginal,copy,x+1,y);
}

int main(){
    /*int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9},
                        {4, 7, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 5, 6, 2, 0, 0, 3},
                        {0, 6, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 4, 0, 0, 3, 0, 6, 0},
                        {0, 5, 9, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 2, 0, 0, 0, 0, 0},
                        {6, 0, 0, 4, 0, 0, 0, 0, 0},
                        {0, 4, 8, 0, 0, 0, 6, 0, 0},
                        {0, 0, 4, 0, 0, 0, 0, 0, 0},
                        {0, 2, 0, 0, 0, 0, 1, 0, 0},
                        {0, 9, 1, 0, 0, 4, 0, 0, 5},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {4, 0, 0, 6, 0, 0, 0, 0, 5},
                        {5, 0, 0, 0, 0, 0, 8, 6, 0}};*/
    int arrayMain[9][9];
    std::copy(sudoku+7, sudoku+15, arrayMain);
    if (tryToSolve(sudoku,arrayMain,0,0)){
            for (int i=0; i<9; ++i){
                    for (int j=0; j<9; ++j){
                            printf("%d ",arrayMain[i][j]);
                    }printf("\n");
            }
    }
    else{
            printf("No solution");
    }
    return 0;
}

EDIT:
I'm sorry I didn't explain the problem properly. In the example above, the Sudoku has to be two separate 9x9 Sudokus (rows 1-9 it's first and 7-15 the another).

I did not go through the code (or the puzzle), just wondered if you have checked that the provided puzzle is actually solvable, or there is indeed "no solution". — vefthym, Apr 25 '17 at 07:44
Does your code check that each column has no duplicates? If so, then any more than 9 rows will result in no possible solution. — lockstock, Apr 25 '17 at 07:58
Sudoku has 15 rows only for tests. It's a part of bigger 21 row Sudoku and of course it's solvable — wege, Apr 25 '17 at 08:02
The definition of a Sudoku grid is that the columns don't have any duplicates, so are you checking the columns for duplicates? — lockstock, Apr 25 '17 at 08:05
This is perfectly applicable approach, instead of using 0..9, you have to add custom values with comparators, but you easly could solve 64x64 with this using base64 http://stackoverflow.com/a/16675419/6313992 — Tomasz Plaskota, Apr 25 '17 at 08:08
The `checkNextCell` method seems to only work for 9x9 if I am not mistaken? — lockstock, Apr 25 '17 at 08:19
I'm sorry I didn't explain the problem properly. In the example in my code, the Sudoku has to be two separate 9x9 Sudokus (rows 1-9 it's first and 7-15 the another). — wege, Apr 25 '17 at 09:17
@wege You should edit your question and include this very relevant information... — le_m, Apr 25 '17 at 12:08

score 1 · Answer 1 · answered Apr 25 '17 at 17:14

So you have a super-sudoku which consists of two sudokus that overlap in the rows 6-8 (I start to count at 0).

The problem is that you cannot solve them independently as your code does. Why? Because they are not two independent sudokus. The solution for a sudoku is unique by definition otherwise it is not a sudoku. The same is true for the super-sudoku. But if you look at the overlapping sudokus independently then the solution is (in most cases) not unique. Therefore the entire super-sudoku has to be solved as one puzzle and not two independent ones. In other words your algorithm finds a solution for the upper sudoku which makes it impossible for the lower sudoku to be solved.

Backtracking also works for the super-sudoku and the algorithm is very similar to the simple sudoku. But when you reach rows 6-8 you have to test them against the upper and the lower sudoku. After that you continue to solve the 2nd sudoku normally.

What happens when I have bigger super-sudoku for example composed of three Sudokus? Should I start to solve them from the top or maybe from the middle? — wege, Apr 25 '17 at 21:05
@wege That could be a good idea. The goal is to create conflicts as early as possible so that you can discard whole branches quickly (backtracking basically creates a tree with all possibilities but doesn't explore them all, just until there is a conflict or solution). — maraca, Apr 26 '17 at 18:14

Algorithm to solve sudoku

1 Answers1