← Back to branch summary

~ubuntu-branches/ubuntu/quantal/kdegames/quantal

« back to all changes in this revision

Viewing changes to ksudoku/src/logic/puzzle.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2011-12-15 14:17:50 UTC
  • mfrom: (1.3.14)
  • Revision ID: package-import@ubuntu.com-20111215141750-6tj6brf4azhrt915
Tags: 4:4.7.90-0ubuntu1
new upstream beta release

Show diffs side-by-side

added added

removed removed

Lines of Context:
ksudoku/src/logic/puzzle.cpp
25
25
#include <qstring.h>
26
26
 
27
27
#include <QtDebug>
28
 
#include <choiceitem.h>
 
28
 
 
29
#include "sudokuboard.h"
 
30
#include "plainsudokuboard.h"
 
31
#include "samuraiboard.h"
 
32
#include "roxdokuboard.h"
29
33
 
30
34
namespace ksudoku {
31
35
 
38
42
{ }
39
43
 
40
44
int Puzzle::value(int index) const {
41
 
        Item *item = m_graph->board()->itemAt(m_graph->cellPosX(index), m_graph->cellPosY(index), m_graph->cellPosZ(index));
42
 
        if(item && m_puzzle2.ruleset())
43
 
                return static_cast<ChoiceItem*>(item)->value(&m_puzzle2);
44
 
        return 0;
 
45
        return ((index < m_puzzle.size()) ? m_puzzle.at(index) : 0);
45
46
}
46
47
 
47
48
int Puzzle::solution(int index) const {
48
 
        Item *item = m_graph->board()->itemAt(m_graph->cellPosX(index), m_graph->cellPosY(index), m_graph->cellPosZ(index));
49
 
        if(item && m_solution2.ruleset())
50
 
                return static_cast<ChoiceItem*>(item)->value(&m_solution2);
51
 
        return 0;
 
49
        return ((index < m_solution.size()) ? m_solution.at(index) : 0);
 
50
}
 
51
 
 
52
int Puzzle::hintIndex(int moveNum) const {
 
53
        return ((moveNum >= m_hintList.count()) ? -1 : m_hintList.at(moveNum));
52
54
}
53
55
 
54
56
bool Puzzle::init() {
57
59
        if(m_withSolution)
58
60
                return false;
59
61
 
60
 
        m_puzzle2 = Problem(m_graph->rulset());
61
 
 
62
62
        return true;
63
63
}
64
64
 
65
 
bool Puzzle::createPartial(Solver *solver) {
66
 
        // TODO after finding a solution try to find simpler ones
67
 
        const ItemBoard *board = m_graph->board();
68
 
        for(;;) {
69
 
                ChoiceItem *choiceItem;
70
 
                for(;;) {
71
 
                        int x = rand() % board->size(0);
72
 
                        int y = rand() % board->size(1);
73
 
                        int z = rand() % board->size(2);
74
 
                        Item *item = board->itemAt(x, y, z);
75
 
                        if(!item) continue;
76
 
                        choiceItem = static_cast<ChoiceItem*>(item);
77
 
                        if(choiceItem->value(&solver->state())) continue;
78
 
                        break;
79
 
                }
80
 
                // TODO don't iterate from the minimum to the maximum
81
 
                // this will create relative easy puzzles with concentration of low values and almost no to none 9
82
 
                // TODO prepare the state to speedup deeper tries
83
 
                int min = choiceItem->minValue();
84
 
                int max = choiceItem->maxValue();
85
 
                int range = choiceItem->maxValue() - min + 1;
86
 
                int start = rand() % range;
87
 
                // count from start downward and continuing with max after min
88
 
                for(int i = range+start; i > start; --i) {
89
 
                        int val = min + i % range;
90
 
                        
91
 
                        if(!choiceItem->marker(&solver->state(), val)) continue;
92
 
 
93
 
                        solver->push();
94
 
                        choiceItem->setValue(&solver->state(), val);
95
 
                        solver->push();
96
 
                        solver->solve();
97
 
                        int count = solver->results().count();
98
 
                        if(count == 1)
99
 
                                m_solution2 = solver->results()[0];
100
 
                        solver->pop();
101
 
                        
102
 
                        if(count == 1) {
103
 
                                m_puzzle2 = solver->state();
104
 
                                return true;
105
 
                        } else if(count > 1) {
106
 
                                if(createPartial(solver))
107
 
                                        return true;
108
 
                        }
109
 
                        
110
 
                        solver->pop();
111
 
                }
112
 
        }
113
 
        return false;
114
 
}
115
 
 
116
65
bool Puzzle::init(int difficulty, int symmetry) {
117
66
        if(m_initialized) return false;
118
 
        Solver solver;
119
 
        solver.setLimit(2);
120
 
        solver.loadEmpty(m_graph->rulset());
121
67
 
122
 
        if(createPartial(&solver)) {
123
 
                return true;
 
68
        QObject * owner = new QObject();        // Stands in for "this".
 
69
        SudokuBoard * board = getBoard (owner);
 
70
        if (board == 0) {
 
71
            return false;
124
72
        }
125
73
 
126
 
        return false;
 
74
        // Generate a puzzle and its solution.
 
75
        BoardContents puzzle;
 
76
        BoardContents solution;
 
77
        board->generatePuzzle (puzzle, solution,
 
78
                              (Difficulty) difficulty, (Symmetry) symmetry);
 
79
        board->getMoveList (m_hintList);
 
80
        int boardSize = board->boardSize();
 
81
        delete owner;                   // Also deletes the SudokuBoard object.
 
82
 
 
83
        // Convert the puzzle and solution to KSudoku format.
 
84
        m_puzzle   = convertBoardContents(puzzle, boardSize);
 
85
        m_solution = convertBoardContents(solution, boardSize);
 
86
 
 
87
        return true;
127
88
}
128
89
 
129
90
int Puzzle::init(const QByteArray& values) {
130
91
        if(m_initialized) return -1;
131
 
        
132
 
        m_puzzle2 = Problem(m_graph->rulset());
133
 
        for(int x = 0; x < m_graph->sizeX(); ++x) {
134
 
                for(int y = 0; y < m_graph->sizeY(); ++y) {
135
 
                        for(int z = 0; z < m_graph->sizeZ(); ++z) {
136
 
                                int value = values[m_graph->cellIndex(x, y, z)];
137
 
                                Item *item = m_graph->board()->itemAt(x, y, z);
138
 
                                if(item && value)
139
 
                                        static_cast<ChoiceItem*>(item)->setValue(&m_puzzle2, value);
140
 
                        }
141
 
                }
142
 
        }
143
 
        
144
 
        Solver solver;
145
 
        solver.setLimit(2);
146
 
        solver.loadProblem(&m_puzzle2);
147
 
        solver.solve();
148
 
 
149
 
        int success = solver.results().count();
150
 
        if(success == 1 && m_withSolution) {
151
 
                m_solution2 = solver.results()[0];
152
 
        }
153
 
        
154
 
        return success;
 
92
 
 
93
        QObject * owner = new QObject();        // Stands in for "this".
 
94
        SudokuBoard * board = getBoard (owner);
 
95
        if (board == 0) {
 
96
            return 0;
 
97
        }
 
98
 
 
99
        // Convert the puzzle values to SudokuBoard format.
 
100
        BoardContents puzzleValues = board->fromKSudoku(values);
 
101
 
 
102
        // Save the puzzle values and SudokuBoard's solution (if any).
 
103
        m_puzzle = values;
 
104
        int boardSize = board->boardSize();
 
105
        m_solution = convertBoardContents
 
106
                        (board->solveBoard(puzzleValues), boardSize);
 
107
 
 
108
        // Get SudokuBoard to check the solution.
 
109
        int result = board->checkPuzzle (puzzleValues);
 
110
        if (result >= 0) {
 
111
            result = 1;         // There is one solution.
 
112
        }
 
113
        else if (result == -1) {
 
114
            result = 0;         // There is no solution.
 
115
        }
 
116
        else {
 
117
            result = 2;         // There is more than one solution.
 
118
        }
 
119
        m_hintList.clear();
 
120
        if (result != 0) {
 
121
            board->getMoveList (m_hintList);
 
122
        }
 
123
        delete owner;           // Also deletes the SudokuBoard object.
 
124
        return result;
 
125
}
 
126
 
 
127
const QByteArray Puzzle::convertBoardContents(const BoardContents & values,
 
128
                                              int boardSize) {
 
129
        // New solver stores by column within row and sets unused cells = -1.
 
130
        // KSudoku stores values by row within column and sets unused cells = 0,
 
131
        // e.g. the empty areas in a Samurai or Tiny Samurai puzzle layout.
 
132
        QByteArray newValues;
 
133
        if (values.size() < (boardSize * boardSize)) {
 
134
            return newValues;   // No solution.
 
135
        }
 
136
        char value = 0;
 
137
        int index = 0;
 
138
        for (int j = 0; j < boardSize; j++) {
 
139
            for (int i = 0; i < boardSize; i++) {
 
140
                index = i * boardSize + j;
 
141
                value = values.at(index) < 0 ? 0 : values.at(index);
 
142
                newValues.append(value);
 
143
            }
 
144
        }
 
145
        return newValues;
 
146
}
 
147
 
 
148
SudokuBoard * Puzzle::getBoard(QObject * owner) {
 
149
        int blockSize = 3;
 
150
        for (int n = 2; n <= 5; n++) {
 
151
            if (m_graph->order() == n * n) {
 
152
                blockSize = n;
 
153
            }
 
154
        }
 
155
        SudokuType type = m_graph->specificType();
 
156
        qDebug() << "Type" << type; // IDW test.
 
157
        SudokuBoard * board = 0;
 
158
        // Generate a puzzle and solution of the required type.
 
159
        switch (type) {
 
160
        case Plain:
 
161
            board = new PlainSudokuBoard (owner, type, blockSize);
 
162
            break;
 
163
        case XSudoku:
 
164
            board = new XSudokuBoard (owner, type, blockSize);
 
165
            break;
 
166
        case Jigsaw:
 
167
            board = new JigsawBoard (owner, type, blockSize);
 
168
            break;
 
169
        case Samurai:
 
170
            board = new SamuraiBoard (owner, type, blockSize);
 
171
            break;
 
172
        case TinySamurai:
 
173
            board = new TinySamuraiBoard (owner, type, blockSize);
 
174
            break;
 
175
        case Roxdoku:
 
176
            board = new RoxdokuBoard (owner, type, blockSize);
 
177
            break;
 
178
        case EndSudokuTypes:
 
179
            return 0;
 
180
            break;
 
181
        }
 
182
        board->setUpBoard();
 
183
        return board;
155
184
}
156
185
 
157
186
}