Solved Sudoku Puzzle (Need help)

[jsanti2519]

Hey guys I need some help identifying the error in my program, as I'm using nested loops to print out a 2-D array of a solved Sudoku puzzle. I was trying to figure out the issue within the loop. But I am struggling to identify the problem.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(NULL));
    int arr[9][9];
    arr[0][0] = rand() % 9 + 1;
     
    for(int r = 0; r < 9; r++) {
        for(int c = 0; c < 9; c++) {
            if(r == 0 && c == 0) break;
            bool repeats = true;
            while(repeats) {
                arr[r][c] = rand() % 9 + 1;
                /* NOTE: We're going to check if either row or column repeats.
                If row or column repeats, the while loop will reiterate */
                for(int k = 0; k < r; k++) {//to check if row repeats.
                    for(int p = 0; p < c; p++) { //to check if column repeats.
                        if(arr[k][p] == arr[r][c] && (r == k || c == p)) repeats = true;
                        else repeats = false;
                        if(repeats) break;
                    }
                    if(repeats) break;
                }
            }
        }
    }
    for(int foo = 0; foo < 9; foo++) { //printing the 2-D array for solved Sudoku puzzle.
        for(int bar = 0; bar < 9; bar++) {
            cout << arr[foo][bar];
        }
        cout << endl;
    }
}

[dutch]

Two major problems.

Firstly, sudoku puzzles have a third property of not having repeats within 3x3 squares as well as within rows and columns (look up sudoku if you don't know what I'm talking about).

Secondly, your algorithm will never work since you have no way of backtracking. If it paints itself into a corner, which it will inevitably do, it has no way of undoing previous choices in order to try different ones.

GeeksforGeeks has a reasonable algorithm (in Java).
https://www.geeksforgeeks.org/program-sudoku-generator/

They randomly fill the "diagonal 3x3 boxes" first, since they don't interact with each other. From there they try different numbers in the empty locations until they're all filled.

[dutch]

If you really only need distinct numbers in every row and column, then you don't need backtracking. You can just fill the table originally like this:

1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 1 
3 4 5 6 7 8 9 1 2 
4 5 6 7 8 9 1 2 3 
5 6 7 8 9 1 2 3 4 
6 7 8 9 1 2 3 4 5 
7 8 9 1 2 3 4 5 6 
8 9 1 2 3 4 5 6 7 
9 1 2 3 4 5 6 7 8

Then shuffle the rows, which can be done with std::shuffle since C++ stores two-d arrays in column-major order. Example output of shuffling the rows:

7 8 9 1 2 3 4 5 6 
9 1 2 3 4 5 6 7 8 
6 7 8 9 1 2 3 4 5 
8 9 1 2 3 4 5 6 7 
3 4 5 6 7 8 9 1 2 
1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 1 
4 5 6 7 8 9 1 2 3 
5 6 7 8 9 1 2 3 4

Then rotate the grid 90 degrees.

7 9 6 8 3 1 2 4 5 
8 1 7 9 4 2 3 5 6 
9 2 8 1 5 3 4 6 7 
1 3 9 2 6 4 5 7 8 
2 4 1 3 7 5 6 8 9 
3 5 2 4 8 6 7 9 1 
4 6 3 5 9 7 8 1 2 
5 7 4 6 1 8 9 2 3 
6 8 5 7 2 9 1 3 4

Then shuffle the rows again.

5 7 4 6 1 8 9 2 3 
3 5 2 4 8 6 7 9 1 
7 9 6 8 3 1 2 4 5 
2 4 1 3 7 5 6 8 9 
1 3 9 2 6 4 5 7 8 
6 8 5 7 2 9 1 3 4 
8 1 7 9 4 2 3 5 6 
9 2 8 1 5 3 4 6 7 
4 6 3 5 9 7 8 1 2

#include <algorithm>
#include <iostream>
#include <random>

const int Size = 9;

void fill_grid(int a[][Size]) {
    for (int r = 0; r < Size; ++r)
        for (int c = 0; c < Size; ++c)
            a[r][c] = (c + r) % Size + 1;
}

void rotate_grid(int a[][Size]) {
    int b[Size][Size];
    for (int r = 0; r < Size; ++r)
        for (int c = 0; c < Size; ++c)
            b[c][r] = a[r][c];
    std::copy(&b[0][0], &b[Size][0], &a[0][0]);
}

void print_grid(int a[][Size]) {
    for (int r = 0; r < Size; ++r) {
        for (int c = 0; c < Size; ++c)
            std::cout << a[r][c] << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::default_random_engine rnd(std::random_device{}());
    int a[Size][Size];
    fill_grid(a);
    std::shuffle(&a[0], &a[Size], rnd);
    rotate_grid(a);
    std::shuffle(&a[0], &a[Size], rnd);
    print_grid(a);
}

[dhayden]

Line 13. What makes arr[0][0] so special that it doesn't need to be checked?
Line 16. Why are you changing the value of the cell?
Line 21. The condition is always false:

                for(int k = 0; k < r; k++) {//to check if row repeats.
                    for(int p = 0; p < c; p++) { //to check if column repeats.
                        if(arr[k][p] == arr[r][c] && (r == k || c == p)) repeats = true;

The for loops guarantee that k!=r and c!=p

Also why are you checking only the cells to the top/right of r,c?

The code to check for a valid board should be a series of loops:

for (each row) {
   check for duplicates in the row
}
for (each column) {
  check for duplicates in the column
}
for (each box) {
   check for duplicates in the box
}

Work on getting just one of these checks working. Once you have one, you can apply what you learned to the others.

Also, think about how you might check for duplicate entries a single row. Can you think of an efficient way to do it? It's possible to do it with a single pass through the entries.