OKlibrary  0.2.1.6
Sudoku.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 21.11.2006 (Swansea)
00002 /* Copyright 2006 - 2007 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00013 #ifndef SUDOKU_jJJnbfr44ttr
00014 #define SUDOKU_jJJnbfr44ttr
00015 
00016 #include <utility>
00017 #include <stack>
00018 #include <tr1/array>
00019 
00020 #include <boost/logic/tribool.hpp>
00021 
00022 #include <OKlib/Satisfiability/Assignments/PartialAssignments/MultivaluedPartialAssignments.hpp>
00023 #include <OKlib/Satisfiability/ProblemInstances/Variables/TrivialVariables.hpp>
00024 
00025 namespace OKlib {
00026   namespace LatinSquares {
00027 
00038     template <int Box_size, class BijectivityConstraint>
00039     class SudokuProblem {
00040 
00041     public :
00042 
00043       static const int N = Box_size;
00044       static const int N2 = N * N;
00045       static const int n = N2 * N2;
00046 
00047       typedef int box_index; // 1 .. Box_size
00048       typedef int square_index; // 1 .. N2
00049       typedef int entry_type; // 1 .. N2
00050 
00051       typedef std::pair<box_index, box_index> box_point_type;
00052       typedef std::pair<box_point_type, box_point_type> point2_type;
00053       typedef std::pair<square_index, square_index> point_type;
00054 
00055       typedef BijectivityConstraint constraint_type;
00056 
00057       typedef OKlib::Variables::Variables_unsigned_int variables_type;
00058       typedef OKlib::PartialAssignments::MultiPASS<entry_type, n, variables_type> partial_assignment_type;
00059       typedef typename partial_assignment_type::domain_type domain_type;
00060       typedef typename partial_assignment_type::literal_type literal_type;
00061 
00062 
00063       SudokuProblem(partial_assignment_type& phi) : phi(phi) {
00064         
00065         // set up constraints XXXXXXXXXXXXXX
00066       }
00067 
00068       point_type point(const point2_type& p) const {
00069         assert(p.first.first >= 1);
00070         assert(p.first.first <= N);
00071         assert(p.first.second >= 1);
00072         assert(p.first.second <= N);
00073         assert(p.second.first >= 1);
00074         assert(p.second.first <= N);
00075         assert(p.second.second >= 1);
00076         assert(p.second.second <= N);
00077         return point_type((p.first.first - 1) * N + p.second.first, (p.first.second - 1) * N + p.second.second);
00078       }
00079 
00080       variables_type var(const point_type& p) const {
00081         assert(p.first >= 1);
00082         assert(p.second <= N2);
00083         return (p.first - 1) * N2 + p.second;
00084       }
00085 
00086       void add_assignment(const literal_type& l) {
00087         stack.push(phi.get_token());
00088         phi.set(l.first, l.second);
00089       }
00090 
00091       void undo() {
00092         assert(not stack.empty);
00093         phi.undo(stack.top());
00094         phi.pop();
00095       }
00096 
00097     private :
00098 
00099       partial_assignment_type phi;
00100       typedef typename partial_assignment_type::token_type token_type;
00101       typedef std::stack<token_type> stack_type;
00102       stack_type stack;
00103 
00104       std::tr1::array<constraint_type, 3 * N2> constraints;
00105       typedef int constraint_index; // 0 .. 3*N2-1
00106       enum constraint_types {row_constraint, column_constraint, box_constraint};
00107 
00108       constraint_index index_any(const square_index i, const constraint_types t) {
00109         assert(i >= 1);
00110         assert(i <= N2);
00111         switch (t) {
00112         case row_constraint : return i - 1;
00113         case column_constraint : return N2 - 1 + i;
00114         case box_constraint : return 2 * N2 - 1 + i;
00115         }
00116       }
00117       constraint_index index_box(const box_point_type& p) {
00118         assert(p.first >= 1);
00119         assert(p.first <= N2);
00120         assert(p.second >= 1);
00121         assert(p.second <= N2);
00122         return 2 * N2 - 1 + N * (p.first - 1) + p.second;
00123       }
00124 
00125     };
00126 
00127     // #################################################
00128 
00137     template <class SudokuP>
00138     class Trivial_reduction_Sudoku {
00139 
00140     public :
00141 
00142       typedef SudokuP sudoku_type;
00143       typedef typename sudoku_type::literal_type literal_type;
00144 
00145       boost::logic::tribool operator()(const sudoku_type& P) {
00147       }
00148 
00149 
00150     };
00151 
00152   }
00153 }
00154 
00155 #endif
00156