Sudoku Solver (c++)

---

<< back to list of programming projects

The Sudoku Solver program uses a 2-dimensional vector of Field objects to keep track of all possible outcomes for each of the 81 Sudoku fields. I designed a Field class to store a vector of the 9 possible values in a given Sudoku board i.e. 1-9. Each Field object also has a counter keeping track of the number of possible solutions for that field, which identifies whether that particular Field has already been solved. At the start of the program, all possible values for all the Fields are set as “possible”. The Sudoku board is traversed primarily in 3 ways: rows, columns and squares (contains pointers to Fields in each of the 9 squares).

Once the user input is processed, each Field that contains a given value is set to that value and all instances of that value in the same row, column and square are set to “not-possible”. For example, in Field F1 in row i, col j and square k has a value of 4, all Fields in row i, col j and square k cannot have 4 as a value. After iterating through the input values, the program iteratively solves the Sudoku board using 3 main functions: solveRow(), solveCol() and solves(). Each of these functions determine if a Field in the respective row, column or square has a unique solution, and subsequently sets all relevant Field values as “not-possible”.

If the iterative process leads to all Fields being solved, the program first checks if the solution is valid, and then output the solved Sudoku to the user. If two consecutive iterations do not lead to any new Fields being solved, the program notifies the user that the Sudoku cannot be solved without guessing or advanced techniques. In future modifications to the program, I would like to build in a guessing and back-tracking algorithm into the code.

The program is written in C++.

Check out the code at: https://github.com/nablul/Sudoku-Solver

Welcome to the Sudoku solver!. Please enter your Sudoku as a continuous line of 81 numbers, with 0 representing unsolved fields

Also, please enter the Sudoku in row-by-row order i.e. the first 9 numbers represent the first row, next 9 the second row etc.

Enter Sudoku:

005700006060000850004060032000050300100829004007010000710080600032000040400002500

The Sudoku you entered:

0 0 5  7 0 0  0 0 6

0 6 0  0 0 0  8 5 0

0 0 4  0 6 0  0 3 2

0 0 0  0 5 0  3 0 0

1 0 0  8 2 9  0 0 4

0 0 7  0 1 0  0 0 0

7 1 0  0 8 0  6 0 0

0 3 2  0 0 0  0 4 0

4 0 0  0 0 2  5 0 0

Congrats! Sudoku was solved:

3 2 5  7 9 8  4 1 6

9 6 1  2 4 3  8 5 7

8 7 4  5 6 1  9 3 2

2 4 8  6 5 7  3 9 1

1 5 3  8 2 9  7 6 4

6 9 7  3 1 4  2 8 5

7 1 9  4 8 5  6 2 3

5 3 2  9 7 6  1 4 8

4 8 6  1 3 2  5 7 9

Welcome to the Sudoku solver!. Please enter your Sudoku as a continuous line of 81 numbers, with 0 representing unsolved fields

Also, please enter the Sudoku in row-by-row order i.e. the first 9 numbers represent the first row, next 9 the second row etc.

Enter Sudoku:

000028000000007426250900000007010300560000012008090600000009038975800000000650000

The Sudoku you entered:

0 0 0  0 2 8  0 0 0

0 0 0  0 0 7  4 2 6

2 5 0  9 0 0  0 0 0

0 0 7  0 1 0  3 0 0

5 6 0  0 0 0  0 1 2

0 0 8  0 9 0  6 0 0

0 0 0  0 0 9  0 3 8

9 7 5  8 0 0  0 0 0

0 0 0  6 5 0  0 0 0

Congrats! Sudoku was solved:

7 3 6  4 2 8  1 5 9

8 1 9  5 3 7  4 2 6

2 5 4  9 6 1  8 7 3

4 9 7  2 1 6  3 8 5

5 6 3  7 8 4  9 1 2

1 2 8  3 9 5  6 4 7

6 4 2  1 7 9  5 3 8

9 7 5  8 4 3  2 6 1

3 8 1  6 5 2  7 9 4

Welcome to the Sudoku solver!. Please enter your Sudoku as a continuous line of 81 numbers, with 0 representing unsolved fields

Also, please enter the Sudoku in row-by-row order i.e. the first 9 numbers represent the first row, next 9 the second row etc.

Enter Sudoku:

000010092900600570000908006007089030800000005040730200200503000061004003390070000

The Sudoku you entered:

0 0 0  0 1 0  0 9 2

9 0 0  6 0 0  5 7 0

0 0 0  9 0 8  0 0 6

0 0 7  0 8 9  0 3 0

8 0 0  0 0 0  0 0 5

0 4 0  7 3 0  2 0 0

2 0 0  5 0 3  0 0 0

0 6 1  0 0 4  0 0 3

3 9 0  0 7 0  0 0 0

Congrats! Sudoku was solved:

6 5 8  3 1 7  4 9 2

9 1 3  6 4 2  5 7 8

4 7 2  9 5 8  3 1 6

5 2 7  4 8 9  6 3 1

8 3 9  2 6 1  7 4 5

1 4 6  7 3 5  2 8 9

2 8 4  5 9 3  1 6 7

7 6 1  8 2 4  9 5 3

3 9 5  1 7 6  8 2 4

Welcome to the Sudoku solver!. Please enter your Sudoku as a continuous line of 81 numbers, with 0 representing unsolved fields

Also, please enter the Sudoku in row-by-row order i.e. the first 9 numbers represent the first row, next 9 the second row etc.

Enter Sudoku:

006203000200510006038004200000000014050020090180000000002900470400087003000402600

The Sudoku you entered:

0 0 6  2 0 3  0 0 0

2 0 0  5 1 0  0 0 6

0 3 8  0 0 4  2 0 0

0 0 0  0 0 0  0 1 4

0 5 0  0 2 0  0 9 0

1 8 0  0 0 0  0 0 0

0 0 2  9 0 0  4 7 0

4 0 0  0 8 7  0 0 3

0 0 0  4 0 2  6 0 0

Congrats! Sudoku was solved:

5 1 6  2 9 3  8 4 7

2 4 7  5 1 8  9 3 6

9 3 8  7 6 4  2 5 1

6 2 3  8 7 9  5 1 4

7 5 4  1 2 6  3 9 8

1 8 9  3 4 5  7 6 2

8 6 2  9 3 1  4 7 5

4 9 5  6 8 7  1 2 3

3 7 1  4 5 2  6 8 9

Welcome to the Sudoku solver!. Please enter your Sudoku as a continuous line of 81 numbers, with 0 representing unsolved fields

Also, please enter the Sudoku in row-by-row order i.e. the first 9 numbers represent the first row, next 9 the second row etc.

Enter Sudoku:

043020000809000050000430000034006000100000006000500730000094000060000105000050680

The Sudoku you entered:

0 4 3  0 2 0  0 0 0

8 0 9  0 0 0  0 5 0

0 0 0  4 3 0  0 0 0

0 3 4  0 0 6  0 0 0

1 0 0  0 0 0  0 0 6

0 0 0  5 0 0  7 3 0

0 0 0  0 9 4  0 0 0

0 6 0  0 0 0  1 0 5

0 0 0  0 5 0  6 8 0

Sorry! Sudoku could not be solved without guessing or advanced techniques that are not yet supported in this solver :(