Sudoku solver in c++

  • C/++/#
  • Thread starter hermy
  • Start date
  • #1
41
0

Main Question or Discussion Point

You do NOT have to read the entire code to help me. :smile: It's just for your reference.

The problem: I keep getting the message that the file 'algorithm.h' can not be opened. But the header file is very much present in the include folder. What do i do?

The compiler I'm using is tubo c++ 4.5 . The file algorithm.h was not present in the original package, so i downloaded it from the net.


It would be convenient if you could cross-check the definition of algorithm.h:

#ifndef _GLIBCXX_ALGORITHM
#define _GLIBCXX_ALGORITHM 1

#pragma GCC system_header

#include <bits/stl_algobase.h>
#include <bits/stl_construct.h>
#include <bits/stl_uninitialized.h>
#include <bits/stl_algo.h>

#endif /* _GLIBCXX_ALGORITHM */




THE END




Here is the code for sudoku solver:

#include <iostream.h>
#include <ctype.h>
#include <algorithm.h>
#include <vector.h>
#include <cmath.h>

using namespace std;

#define PUZZLE_SIZE 16

// Rrint the puzzle out
// Returns: None
void print_puzzle(int **puzzle, int size) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size - 1; k++) {
printf("%i ", puzzle[j][k]);
}
printf("%i\n", puzzle[j][size-1]);
}
}

// Find valid entries for x,y in puzzle
// Returns: A vector<int> with valid numbers to put in x,y in puzzle[][]
vector<int> find_available(int **puzzle, int size, int x, int y) {
vector<int> ret;
vector<bool> used(size+1, false);
for (int i = 0; i < size; i++)
used[puzzle[x]] = true;
for (int i = 0; i < size; i++)
used[puzzle[y]] = true;
int rsize = (int) sqrt(size);
for (int i = 0; i < rsize; i++) {
for (int j = 0; j < rsize; j++) {
used[puzzle[rsize*(x/rsize)+j][rsize*(y/rsize)+i]] = true;
}
}

for (unsigned int i = 1; i < used.size(); i++) {
if (!used) {
ret.push_back(i);
}
}
return ret;
}

// Find the empty square with the least amount of available entries.
// Returns: A pair<int, int> representing the x,y coordinates of the entry in
// the puzzle - If the current puzzle has a conflic, returns -2,-2 If there are
// no more empty squares in the puzzle, returns -1,-1
pair<int, int> find_next_pos(int **puzzle, int size) {
unsigned int best = size+1;
vector<int> r;
pair<int, int> ret(-1, -1);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (puzzle[j] != 0)
continue;
r = find_available(puzzle, size, i, j);
if (r.size() == 0) {
return pair<int, int>(-2, -2);
}
if (r.size() < best) {
best = r.size();
ret = pair<int, int>(i, j);
}
}
}
return ret;
}

// recursive function to solve the puzzle, it works by finding the empty square
// with the least amount of possible solutions and then tries placing the
// possible solutions in that entry one at a time and trying to solve the
// resulting puzzle.
// Returns: True if the puzzle has been solved, else returns false
bool solve_puzzle(int **puzzle, int size) {
pair<int, int> r;
r = find_next_pos(puzzle, size);
// Is this a valid puzzle?
if (r.first == -2) {
return false;
}
// Was the puzzle solved?
if (r.first == -1) {
print_puzzle(puzzle, size);
return true;
}

// Place entries
vector<int> available = find_available(puzzle, size, r.first, r.second);

for (unsigned int i = 0; i < available.size(); i++) {
puzzle[r.first][r.second] = available;
if (solve_puzzle(puzzle, size))
return true;
}
puzzle[r.first][r.second] = 0;
return false;
}



int main(int argc, char **argv) {
int puzzle_size = PUZZLE_SIZE;

// create a puzzle matrix
int *puzzle[puzzle_size];
for (int i = 0; i < puzzle_size; i++) {
puzzle = (int *) malloc(sizeof(int) * puzzle_size);
}


// read the input into our puzzle matrix
int value;
for (int i = 0; i < puzzle_size; i++) {
for (int j = 0; j < puzzle_size; j++) {
cin >> value;
puzzle[j] = value;
}
}

// print the puzzle matrix and its solution
print_puzzle(puzzle, puzzle_size);
printf("Solution:\n---\n");
if (!solve_puzzle(puzzle, puzzle_size))
printf("impossible\n");

return 0;
}
 

Answers and Replies

  • #2
365
0
Look up the installation directory of turboC, sub-directory bin.
There should be a file called turboc.cfg. Look inside using a text editor and see if you find one or more lines of this format:

Code:
-Ic:\lang\bc45\include
If the file algorithm.h is not in one of these directories, that's the problem. Either you move the file to one of these directories, or you add the directory name to the list. If you add a directory, make sure there are no conflict with duplicate files.

If you are in a rush, you can get around the problem by placing the algorithm.h file in the same directory as the source file, but change the include line to:
Code:
#include "algorithm.h"
i.e. double quotes instead of angle brackets.
 
  • #3
41
0
hello mathmate!
i tried both the methods but it still gives the same error message. i have no idea what to do next...........
 
  • #4
365
0
The second method should always work.

Did you find the file (turboc.cfg) in the TurboC\bin and what lines do you find that start with -I?
Is your file algorithm.h in one of the directories named?

Sorry to suggest the obvious, but you may want to check the spelling of either the included file or the name of the file itself to see if they correspond.
 
  • #5
41
0
This is what the turbocfg file says:

-IC:\TCWIN45\INCLUDE
-LC:\TCWIN45\LIB

algorithm is located in include, where all the header files are located. And the names do match.

Maybe I should just give up on this one and find myself some other compiler......... Thanks for the help!
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
algorithm.h is not a standard C++ header. Unless you have a severely outdated C++ library, the header you are looking for is algorithm. Similar is true for the other headers you used: they should be iostream, cctype, vector, cmath
 
  • #7
365
0
If the error says "file cannot be opened", you may want to check its contents using an editor, just to be sure.

Is your file named algorithm or algorithm.h?
Some C++ header files drop the .h extension, but not in your case.

As I suggested, you can try:
#include "algorithm.h"
and put algorithm.h in the same directory as the source file.

If everything fails, the last resort is:
Insert the contents of algorithm.h into your source file. If that works, it will buy you time to search for the cause of the problem.
 
  • #8
490
2
The proper way to include standard headers is:

#include <iostream>
#include <ctype>
#include <algorithm>
#include <vector>
#include <cmath>

The brackets tell it to look in the system directory. For example,

#include <algorithm>

Tells it to look for a file called "algorithm.h" that is in the system directory for standard headers. You don't explicitly write ".h" with brackets like you do with your own headers.

The proper way to include non-standard headers is:

#include "myheader.h"

Or if you want to be anal-retentive, some people like to name them with .hpp to explicitly distinguish from c headers,

#include "myheader.hpp"
 

Related Threads for: Sudoku solver in c++

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
12
Views
768
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
1
Views
19K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
4K
Top