Previous

Sudoku Solver

Tags:

I got bored a while back and wrote a sudoku solver as a way to practice my algorithms and data structures. I also wanted to make a point of using STL objects other than vector or string to stretch my limits. Specifically I used std::set and std::multiMap, since multiMap gives me a queue where members can have the same key, which I wanted to hold which cell had the fewest possibilities. I used set for the possibilities for each cell since each member had to be unique. The result uses recursion and takes the cell with the fewest options and tries filling it in.

The relevant files are:

Here is the body of sudokuSolver.h


#ifndef SUDOKUSOLVER_H
#define SUDOKUSOLVER_H

#include 
#include 
#include 
#include
#include 

#include 
#include 
#include 


class node {

 public:

  node(int dimension, int x, int y, int value=0);
  ~node() {}

  int x() { return m_x; } // return coordinates
  int y() { return m_y; }
  int z() { return m_z; }

  //void initialValue(int value) { m_value = value; } //set the value 
                                                      //of the node
  bool setValue(int value); //set the value of the node
  int value() {return m_value;} // return the value of the node

  void addNeighbor(node* neighbor); //add a neighbor node and remove 
                                    //its value from possibilities

  std::set< int > possibleValues();//holds the values the node could be 
  int numPossibleValues() { return m_possibleVals.size();}   
                         // end of number of possible values function
  std::string printPossibleValues(); // print the possible values for 
                                     // the node  (test function)

 private:
  int m_value; // the assigned value of the node, 1-9; 0 is unassigned
  int m_dim;//this is the size of a cluster, so a 9x9 board has m_dim=3
  int m_x;   // the x dimension of the node
  int m_y;   // the y dimension of the node
  int m_z; //z actually holds the cluster (usually 3x3 square) it is in
  std::vector *vec_neighbors; //all of the boards x,y, 
                                      //and cluster neighbors
  std::set< int > m_possibleVals; //the values that are allowed based 
                                  //on neighbors

  friend class sudoku;

}; // end of node class
/////////////////////////////////////////////////////////

class sudoku {
 public:

  sudoku(int dimension, std::string input); // initialize board
  std::string initialState() { return m_initialState; } //hold original  
                                       //board to check changes against
  std::string currentState(); //current state of the board
  std::vector options(); //finds the node with the fewest options
                                // and returns the possible boards 
                                //as a string

 private:
  std::string m_initialState;          //store the initial state used
                                       // to create the board
  int m_dim;                           //cluster dim, i.e. 
                                       //m_dim = sqrt(dimension), 
                                       //standard board is 3x3x3x3
  std::multimap map_board; //for minimum priority queue
  std::vector *vec_board; //for reading out by coordinates
  
  friend class sudokuSolver;

}; // end of sudoku class

////////////////////////////////////////////////////////////


class sudokuSolver {

 public:
  sudokuSolver(int dimension, std::string initialState){
    m_dim = dimension;
    m_initialState = initialState;
  }
  std::string solve(std::string input); //solve the puzzle
  std::string translate(std::string input); //translate to something
                                     // that looks more like a puzzle

 private:
  std::string m_initialState; //hold the initial state
  int m_dim;//hold the dimension, standard is 3 (based on cluster size)
};

#endif // SUDOKUSOLVER_H

And here is the body of the implementation, sudokuSolver.cxx (edited a bit to fit)


node::node(int dimension, int x, int y, int value) {
  m_dim = dimension;
  m_x = x;
  m_y = y;
  m_z =  (m_y - 1)/m_dim; 
  m_z = (m_x - 1)/m_dim + m_dim*m_z;
  
  m_value = value;
  vec_neighbors = new std::vector;
  for(int i = 1; i < m_dim*m_dim+1; ++i) {
       m_possibleVals.insert(i);
  }  //end of set buildup
  
} // end of constructor

bool node::setValue(int value) { 
  //set the value of the node
  if(m_possibleVals.count(value) == 1) {
    m_value = value;
    return true;
  }
  return false;
} // end of setValue

void node::addNeighbor(node* neighbor) { 
  //adds the neighbor node
  if(neighbor->x() == m_x 
     || neighbor->y() == m_y 
     || neighbor->z() == m_z){
    vec_neighbors->push_back(neighbor); 
    m_possibleVals.erase(neighbor->value());
  }
} // end of addNeighbors  

std::set< int > node::possibleValues() {
  //return the std::set of possible values
  return m_possibleVals;
} // end of possible values function


std::string node::printPossibleValues(){
  //print the possible values for the node  
  std::string printOut = "";
  for(std::set< int >::iterator iter = m_possibleVals.begin(); 
                              iter != m_possibleVals.end(); 
                              iter++){
      std::ostringstream os;
      os << (*iter);
      printOut += os.str() + " ";
  } 
  return printOut;
}// end of printPossibleValues


//////////////////////////////sudoku class - sudoku board class

sudoku::sudoku(int dimension, std::string input) {
  m_initialState = input;
  m_dim = dimension;
  vec_board = new std::vector; 
  
  int ex = 0;
  int why = 0;
  std::istringstream ins(m_initialState);   
  
  for(int j = 0; j < m_dim*m_dim*m_dim*m_dim; ++j)  
    {
      int n;
      ins >> n;
      ex = (j % (m_dim*m_dim)) + 1;
      why = 1 + j/(m_dim*m_dim);
      node *newNode = new node(m_dim, ex, why, n);
      vec_board->push_back(newNode);
    } // end of input loop
  
  for(int i = 0; i < vec_board->size(); ++i){
    for(int j = i + 1; j < vec_board->size(); ++j){
      if(vec_board->at(i)->x() == vec_board->at(j)->x()){
        vec_board->at(i)->addNeighbor(vec_board->at(j));
        vec_board->at(j)->addNeighbor(vec_board->at(i));
      } //x neighbors (vertical)
      if(vec_board->at(i)->y() == vec_board->at(j)->y()){
        vec_board->at(i)->addNeighbor(vec_board->at(j));
        vec_board->at(j)->addNeighbor(vec_board->at(i));
      } // y neighbors (horizonal)
      if(vec_board->at(i)->z() == vec_board->at(j)->z()){
          vec_board->at(i)->addNeighbor(vec_board->at(j));
          vec_board->at(j)->addNeighbor(vec_board->at(i));
      } //cluster neighbors       
    } // end of inner loop 
  }   // end of outer board loop
  
  for(int i = 0; i < vec_board->size(); ++i){
    if(vec_board->at(i)->value() == 0){
     map_board.insert(std::pair(vec_board->at(i)->numPossibleValues(), 
                                             vec_board->at(i)));
   }
  }   // end of outer board loop
} // end of constructor 



std::string sudoku::currentState() {
  //read out the current state of the board as a string
  std::string output = "";  
  for(int i = 0; i < vec_board->size(); ++i){
    std::ostringstream osIn;
    osIn << vec_board->at(i)->value();
    output += osIn.str() + " ";
  } // end of loop
  return output;
} // end of currentState

std::vector sudoku::options() {
  // returns all possible boards for 
  // options from node with least possibilities
  std::vector possibleBoards;
  node *bottomIt = (*map_board.begin()).second;
  std::set< int > possibilities = bottomIt->possibleValues();
  for(std::set< int >::iterator it = possibilities.begin(); 
                              it != possibilities.end(); 
                              ++it) {
    bottomIt->setValue((*it));
    possibleBoards.push_back(currentState());
    bottomIt->setValue(0);
  } // end of loop  
  return possibleBoards;
} // end of options


///////////////////////////////sudokuSolver class - solver class

std::string sudokuSolver::solve(std::string input){
  
  std::string newState = input;
  if(input.find("0") == std::string::npos) return input;
  sudoku board(m_dim, input);
  std::vector possibleBoards = board.options();
  int index = 0;
  while(newState == input && index < possibleBoards.size()) {
    newState = solve(possibleBoards.at(index));
    if(newState.find("0") == std::string::npos) return newState;
     if(newState == possibleBoards.at(index)) newState = input;
    index++;    
  }//end of loop

  return newState;
} // end of solve

std::string sudokuSolver::translate(std::string input){
//translate to something that looks more like a puzzle
  std::string output = "";
  int length = input.length();
 
  for(int i = 0; i < length; ++i){
    if(i % (2*m_dim*m_dim*m_dim) == 0){
       output += " -------------------------n";
    }
    if(i % (2*m_dim*m_dim) == 0) output += " | ";
    output += input.substr(i, 2*m_dim) + "| ";
    if((i + 2*m_dim) % (2*m_dim*m_dim) == 0  && i != length - 2*m_dim){
        output += "n";
    }
    i = i + 2*m_dim - 1;
  }
  output += "n -------------------------";

  return output;

}//end of translate

///////////////////////////////////////////////// main function


int main(int argc, char *argv[]){
  
  if (argc <= 1)
    {
      std::cout << 
      "Supply an argument (the input file) to sudokuSolver" 
      << std::endl;
    }
  
  char *inputFile = argv[1];

  std::ifstream ins;
  ins.open(inputFile);

  int dimension = 0;
  ins >> dimension;

  std::string input;
  std::string storage;
  for(int i = 0; i < dimension*dimension*dimension*dimension; ++i){
  ins >> storage;
  input += storage + " ";
  }
 
  sudoku board(dimension, input);
  sudokuSolver solveMe(dimension, input);
  std::string output = solveMe.solve(input);
  std::cout << "The result is " << std::endl <<  output << std::endl;
  std::cout 
  << "Formatted gives " << std::endl << solveMe.translate(output) 
  << std::endl;
  return 0;
}

Here are some example test files in the format I used:

I took these from http://www.sudoku.ws/easy.htm, where they each correspond to the first one of each class from their name.

The output of the extreme puzzle looks like:


The result is 
5 1 9 7 4 8 6 3 2 7 8 3 6 5 2 4 1 9 4 2 6 1 3 9 8 7 5 3 5 7 9 8 6 2 4 
1 2 6 4 3 1 7 5 9 8 1 9 8 5 2 4 3 6 7 9 7 5 8 6 3 1 2 4 8 3 2 4 9 1 7 
5 6 6 4 1 2 7 5 9 8 3 
Formatted gives 
 -------------------------
 | 5 1 9 | 7 4 8 | 6 3 2 | 
 | 7 8 3 | 6 5 2 | 4 1 9 | 
 | 4 2 6 | 1 3 9 | 8 7 5 | 
 -------------------------
 | 3 5 7 | 9 8 6 | 2 4 1 | 
 | 2 6 4 | 3 1 7 | 5 9 8 | 
 | 1 9 8 | 5 2 4 | 3 6 7 | 
 -------------------------
 | 9 7 5 | 8 6 3 | 1 2 4 | 
 | 8 3 2 | 4 9 1 | 7 5 6 | 
 | 6 4 1 | 2 7 5 | 9 8 3 | 
 -------------------------

I should probably test the margins more and run this through its paces, but for the moment I'm tired of it. If I do anything more with it, I'll translate it to Java and import it to an applet or Proce55ing, or something equivalent.

 

Anti-Social Media

Next

Similar Posts

R and GIS

Looking at Pennsylvania election data with R.

ATLAS Utilities

C++ utilities I used on the ATLAS experiment for analysis.