में फंस गया मैं सुडोकू बैकट्रैकिंग सॉल्वर में तीन दिनों के लिए अपनी गलती का पता लगाने की कोशिश कर रहा हूं। समस्या लीटकोड Sudoku Solver से है।सुडोकू बैकट्रैकिंग सॉल्वर (जावा)
मेरा सॉल्वर संलग्न तस्वीर में कटौती पर आधारित है। समस्या यह है कि मेरा बोर्ड बदल जाता है भले ही रूट से पत्ती का पथ अमान्य हो।
दूसरे शब्दों में, यह एक अवैध पथ से गुजरने के बाद, मेरे द्वारा किए गए मान मेरे मूल बोर्ड में तय किए गए हैं। हालांकि, जब मैं अपने बच्चों को सच करता हूं तो मैं केवल अपने मूल बोर्ड को अपडेट करता हूं (सहायक विधि में हिस्सा देखें: // एक संख्या डालें और बच्चों को उत्पन्न करें)।
असल में, प्रत्येक '।' के लिए, मैं 1 से 9 तक सभी संभावनाएं उत्पन्न करता हूं, एक अस्थायी बोर्ड बनाता हूं जो वर्तमान 'भरता है।' एक संभावना के साथ, फिर अगले '।' के सहायक का आह्वान करें। अस्थायी बोर्ड के साथ। मुझे पता है कि अंतरिक्ष लागत की वजह से प्रत्येक संभावित बच्चे के लिए एक ही आकार बोर्ड को स्टोर करना अच्छा नहीं है, लेकिन मेरी मुख्य चिंता अब लागत को अनुकूलित करने से पहले समस्या को हल करना है।
बिलकुल बिलकुल नहीं, मेरा बोर्ड क्यों बदल रहा है भले ही सभी बच्चे मान्य न हों?
उदाहरण के लिए, प्रारंभिक बोर्ड
..9748 के आधार पर ...; 7 ........; .2.1.9 ...;
..7 ... 24 .; .64.1.59 .; .98 ... 3 ..;
... 8.3.2 .; ........ 6; ... 2759 ..;
मैं के बाद मैं चलाने के अंतिम परिणाम मिला:
139748652; 745326189; 826159437;
35769.24 .; .64.1.59 .; .98 ... 3 ..;
... 8.3.2 .; ........ 6; ... 2759 ..;
public void sudokuSolver(char[][] board) {
for (int i = 0 ; i < board.length ; i++) {
for (int j = 0 ; j < board.length ; j++) {
if (board[i][j] == '.') {
// find the first '.' as root
helper(i, j, board);
return;
}
}
}
}
private boolean helper(int row, int col, char[][] board) {
// case 2. check if it has following '.' and store its position
boolean hasNext = false;
boolean nextSearching = false;
int nextRow = row;
int nextCol = col;
for (int i = 0 ; i < board.length ; i++) {
for (int j = 0; j < board.length ; j++) {
if (nextSearching && !hasNext && board[i][j] == '.') {
hasNext = true; // there is next!
nextRow = i;
nextCol = j;
}
if (i == row && j == col) {
nextSearching = true;
}
}
}
// exit condition: last '.'
if (!hasNext) {
for (char put = '1' ; put <= '9' ; put ++) {
if (isValid(row, col, board, put)) {
return true;
}
}
return false;
}
// put a number and generate children
for (char put = '1' ; put <= '9' ; put ++) {
if (isValid(row, col, board, put)) {
char[][] boardTemp = board;
boardTemp[row][col] = put;
boolean valid = helper(nextRow, nextCol, boardTemp);
if (valid) {
// board is supposed to change only when valid is true.
board[row][col] = put;
return true;
}
}
}
return false;
}
private boolean isValid(int row, int col, char[][] board, char c) {
// go through each row, column, and subblock to determine if c is a valid choice based on current board.
for (int jCol = 0 ; jCol < 9 ; jCol ++) {
if (board[row][jCol] == c) {
return false;
}
}
for (int iRow = 0 ; iRow < 9 ; iRow ++) {
if (board[iRow][col] == c) {
return false;
}
}
for (int i = row/3*3 ; i < row/3*3 + 3 ; i++) {
for (int j = col/3*3 ; j < col/3*3 + 3 ; j++) {
if (board[i][j] == c) {
return false;
}
}
}
return true;
}
साइड नोट: अच्छा OO प्रोग्रामिंग उपयोगी संक्षेपण बनाने के बारे में है
char[][] boardTemp = board
वे एक ही स्मृति को इंगित मतलब है ... क्या आप अपने मूल कोड में याद किया में तुम्हारे जाने के बाद एक अमान्य संख्या डालelse
हिस्सा है। जैसे, आप अपने बोर्ड को "असली" कक्षाओं के साथ मॉडल कर सकते हैं; एक 2 मंद चार सरणी पर भरोसा करने के बजाय। "निम्न-स्तर" abstractions का उपयोग कर आप के परिणामस्वरूप; आपका कोड स्वयं बहुत सार है। और आपका नामकरण मदद नहीं करता है। एक नाम कहना चाहिए कि इसके पीछे क्या है। तो, * सहायक * कर रहे एक विधि क्या है? और यह एक बूलियन क्यों लौट रहा है ?! और फिर उस विधि में कम से कम 3 रिटर्न हैं। WTF ?! लंबी कहानी छोटी: यह कोड पढ़ने और समझने में मुश्किल है। इसमें कोई आश्चर्य की बात नहीं है कि इसमें बग शामिल हैं जो स्पॉट करना मुश्किल है! – GhostCatदूसरे शब्दों में: उदाहरण के लिए आपको "अमूर्तता की एकल परत" सिद्धांत के बारे में पढ़ना चाहिए। आपके पास एक ही सहायक विधि में ** सभी ** आपका कोड है। इसके बजाए, आपके पास बहुत सी छोटी विधियां होनी चाहिए जो ** एक ** प्रत्येक चीज करें। और कृपया ध्यान दें: यदि आपके पास कई छोटी विधियां हैं, तो आप उनमें से प्रत्येक के लिए छोटे यूनिट परीक्षण भी लिख सकते हैं (और कोई गलती नहीं करें: टीडीडी का उपयोग करने और यूनिट परीक्षण लिखने के लिए ऐसे असाइनमेंट ** सही ** हैं)। संक्षेप में: अपनी समस्या को छोटे से विच्छेदन करने का प्रयास करें; और स्वतंत्र रूप से उनको हल करें ... और उनका परीक्षण करें। फिर "बड़ी तस्वीर" को एक साथ खींचें। – GhostCat
आपकी टिप्पणी के लिए बहुत बहुत धन्यवाद।आपके द्वारा वर्णित सामान्य विधि को मेरे लिए बहुत छोटे उपप्रणाली में बड़ी समस्या को विघटित करना वास्तव में अच्छा होना चाहिए। तब मैं समझ सकता हूं कि यह कहां गलत हो जाता है। मैं इसे कुछ कठिन या कठिन समस्याओं के लिए उपयोग कर सकता हूं। –