Code Dojo
Category: Problem solving
Restriction: Non
Time: Small
Write a sudoku solver that can solve following sudokus:
easy:
070630094
104000200
083420700
002040030
090080040
050060900
009054310
007000509
530092080
medium:
000007590
409008000
050010000
100200900
300070005
006003004
000080060
000500302
083700000
challenge:
000000000
000003085
001020000
000507000
004000100
090000000
500000073
002010000
000040009
Bench mark each run for the solver.
Solution
Hope all went well. The solution will be implement with three files: main.cc, util.h and util.cc. For each code snippet that is shown and explained I will write which file the code belong to.
The algorithm will be implemented in main.cc with helper methods in util.cc. Before that, we will setup util.h for util.cc. .h file in c++ are header files and they contains, for the most part, function declaration and definitions.
//util.h
#ifndef UTIL_H
#define UTIL_H
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
std::vector<std::vector<int>> readFile(const std::string);
void printSudoku(const std::vector<std::vector<int>>&);
bool canPlace(const std::vector<std::vector<int>>&,int,int,int);
#endif
Unlike previous Code Dojo solution, these are the methods we need to use. One method to read the file that contain the sudoku, one method to print the sudoku and one method that indicate if we can place a number at a spot.
At the start of every source file, .cc, we include libraries which hold definitions and function we want to use in that source file. The header file util.h will hold the reference to function in the source file util.cc. And each other source file that want to use function in util.cc only need to include util.h.
Not to make the compiler compile the header file for each source file that uses it, at the start of each header file we will define a specific tag. What happens is: we check if UTIL_H is define. If it is then don't continue. If it's not then define UTIL_H and continue.
As the source file will include the header file we can use the header file to include the standard libraries that the source file needs. The libraries we are going to use are: vector, string, fstream and iostream. Vector and String we will not get into but fstream is the library that is used for input streams and output streams of files. And iostream is library for input stream and output streams to the console. This is simplified but going forward this is how we will differentiate them.
Next we define the functions with structure:
return name(variable_type);
readFile function takes a string, the name, of the field we want to read and give it back the sudoku as a matrix of ints. const in front of the string indicate that we are only going to read the value and the method won't change anything.
printFiled is given a matrix of ints and doesn't return anything. printField have one interest bit: &. & mark that this is a reference. This mean the variable that is given is the variable that is used. Without & it would be a copy of the matrix and if we would modify it it would be modification of the copy and not the original. The & reference means we save memory by not copying the matrix.
We are now going to implement these
#include "util.h"
using namespace std;
#define SIZE 9
vector<vector<int>> readFile(const string name) {
ifstream in(name);
char c;
vector<vector<int>> file(SIZE, vector<int>(SIZE,1));
int x = 0, y = 0;
while(in.get(c)) {
if (c == '\n') {
file[++y];
x = 0;
continue;
}
file[y][x++] = (int) c - '0';
}
return file;
}
void printSudoku(const vector<vector<int>>& sudoku) {
for (int i = 0; i < SIZE; ++i) {
if (i % 3 == 0 && i > 0)
cout << endl;
for (int j = 0; j < SIZE; ++j) {
if (j % 3 == 0 && j > 0)
cout << " ";
cout << sudoku[i][j];
}
cout << endl;
}
}
we will implement the method 'canPlace' later as that have some private methods.
First is the inclusion of the header file for util. Next is the declaration of using namespace std. This mean anything from standard libraries, the ones we included in the header, doesn't need a prefix of std:: before them. Then we define SIZE to be 9 as that the size of a sudoku. This mean, when we use SIZE in our program we will reference 9.
Declaration of readFile. It takes a name, as string, as input. It then open a ifstream, input fstream, of the file with given name. A few more variables are declared. The while-loop will read character from the file and populate char c until there is nothing else to read. Then there is a check to see if there is a new line (not something we will populate our matrix with). There is an update to the matrix, to start a new row. Other wise the program cast the character to an integer and add it to the matrix, that hold our sudoku. The method end with returning the sudoku in the matrix.
Declaration of printSudoku. It will not modify the sudoku and only need a reference to it. By printing we want gaps after 3 numbers. And after 3 rows we want an empty row so better visualize the sudoku.
The main source file:
// main.cc
#include <iostream>
#include <vector>
#include "util.h"
#define SIZE 9
bool backTrack(std::vector<std::vector<int>>&);
int main(int argn, char** argv) {
if (argn < 2) {
std::cout << "Wrong number of arguments\n";
return 1;
}
std::vector<std::vector<int>> sudoku = readFile(argv[1]);
printSudoku(sudoku);
std::cout << "--------------------------\n";
backTrack(sudoku);
printSudoku(sudoku);
return 0;
}
bool backTrack(std::vector<std::vector<int>>& sudoku) {
for(int j = 0; j < SIZE; ++j) {
for(int i = 0; i < SIZE; ++i) {
if (sudoku[j][i] == 0) {
for (int n = 1; n <= 9; ++n) {
if (canPlace(sudoku, n, i, j)) {
sudoku[j][i] = n;
if (!backTrack(sudoku))
continue;
else
return true;
}
}
sudoku[j][i] = 0;
return false;
}
}
}
return true;
}
This is how the complete main will look. backTrack method is our algorithm to solve the sudoku.
Start by including libraries that will be in use. The include our own creation, util. As sudoku is square with size 9 we define SIZE to be 9. We then define method backTrack, like util.h define methods for util.cc.
Declaration of main. The two arguments are number of inputs to the program and what they are, representing as char*. To simplify think char* as string. The program expect the given file that contain a sudoku. If there is less than 2 arguments to the the program wasn't given a sudoku to solve and will quit.
We then read the file and get a sudoku from it in matrix format. We print the sudoku to the terminal to show the unsolved sudoku. Next we print a line of dashes to separate the unsolved sudoku to the solved sudoku.
A call to backTrack algorithm and print the solved sudoku.
Declaration of backTrack. This is the main algorithm to solve sudokus. Is a basic, brute force, simple solution. It will basically try a number on a spot until it find one that fit then continue to the next spot. If a spot can't be represented by any number it will go back and change a previous number until all spot has a number.
To break it down as it is written: loop through the sudoku. When a spot is reached that is represented by 0, that spot need to be filled in. Start with 1 throughout 9 to see which number can fit. Now we call the method in util canPlace(). This will check if the number interfere either along the horizontal or vertical line or inside the box. If returned true, the number can the placed in the spot. We do a recursive call to backTrack after the spot is represented by that number.
The backTrack have returned type bool. If the algorithm return false, it means that a spot can't be represented by any number between 1-9. This mean it will go "up" in the recur call which, looking at the if-statement, the algorithm will test another number. IF the backtrack have solved it, it will return true and go back up until it is in the main method again. Before we go "up" in the recur line, if a spot can't be represented, we need to revert the spot to 0 if we had change the number.
This is the algorithm. Time to look at the helper methods.
// util.cc
bool placeLine(const vector<vector<int>>& sudoku, int n, int x, int y) {
for (int i = 0; i < SIZE; ++i) {
if (sudoku[y][i] == n)
return false;
}
for (int i = 0; i < SIZE; ++i) {
if (sudoku[i][x] == n)
return false;
}
return true;
}
bool placeBox(const vector<vector<int>>& sudoku, int n, int x, int y) {
int lowX = x - x%3;
int lowY = y - y%3;
for (int i = lowY; i < lowY + 3; ++i)
for (int j = lowX; j < lowX + 3; ++j)
if (sudoku[i][j] == n)
return false;
return true;
}
bool canPlace(const vector<vector<int>>& sudoku, int n, int x, int y) {
return placeBox(sudoku, n, x, y) && placeLine(sudoku, n, x, y);
}
Declaration of canPlace. The arguments is reference to the sudoku, method won't change it thus const. Number n we want to test on the given spot. The coordinate x and y where we observing in the sudoku. The method until does two things: call placeBox and placeLine. Basically checking "can this number be placed in the box we currently in and does any number interfere with it on the line?"
Declaration of placeBox. Same arguments of canPlace. We build lowX and lowY out of the spot we are looking at. A box is 3x3 in a sudoku and we need to be in the correct box while comparing numbers. It loops through all the spot in the box and see if any number is the same to the number that we want to place. If it finds, return false. If so such number interfere we return true.
Declaration of placeLine. Same arguments as canPlace. All that is done here is loop horizontal and compare number with the number we want to place then loop vertical and compare. Return false as soon we see a number that is equal to the number we want to place. Return true if we can place.
Conclusion
The output from medium and challenge above:
$ time ./run medium
812 437 596
439 658 217
657 912 843
174 265 938
398 174 625
526 893 174
245 381 769
761 549 382
983 726 451
real 0m0.060s
user 0m0.026s
sys 0m0.004s
and
$ time ./run hard
987 654 321
246 173 985
351 928 746
128 537 694
634 892 157
795 461 832
519 286 473
472 319 568
863 745 219
real 1m4.001s
user 0m55.984s
As can be seen, the first sudoku is quite straightforward to solve with the backTracking algorithm. It take around 60 ms to solve it. The second one is constructed to be complicated. A brute force algorithm like backTracking took around 1 min to solve it. I did implement annealing algorithm which is to randomize number and place on empty spot, calculate number of errors and change number (those that were place) to minimize number of errors until it is solved. But because of the complexity of the sudoku it could never solve it. I tried solution other people made but even them couldn't solve the challenge. This make it a good challenge, as it need a good algorithm to solve it or tricks with brute forcing to save seconds here and there.
Next Code Dojo in November
Top comments (0)