Как решить судоку, если для любой из оставшихся пустых ячеек более одного значения?

Question

[Артём]

Как решить судоку, если для любой из оставшихся пустых ячеек более одного значения?
Т.е. мой алгоритм изначально перебирал ячейки, составляя для каждой пустой список возможных значений, если значение одно - то оно присваивалось ячейке и алгоритм начинался заново с учетом этого. Но вот в более-менее сложном судоку алгоритм доходит до момента, когда для всех оставшихся пустых ячеек существует минимум 2 возможных значения. Что делать в таком случае?

Comments

[longclaps]

Код покажи - есть подозрение, что ты крутишься в цикле. Если да - там надо переделывать в рекурсивный код.

[Артём]

longclaps,

function solveSudoku(matrix) {

    let arr = [1,2,3,4,5,6,7,8,9]
    workMatrix = matrix;
    obj = {};
    count = 0; 
    let tempC ;
    let f = 7
    for(let i = 0; i < 9; i++){
        for(let j = 0; j < 9; j++){
            if(workMatrix[i][j] == 0){
                count++;   
            }
        }
    }

    function solve(workMatrix){
        for(let i = 0; i < 9; i++){
            for(let j = 0; j < 9; j++){
                if(workMatrix[i][j] == 0){
                    
                       
                                 
                    if(!obj.hasOwnProperty([i])){ 
                            obj[i] = {}   
                          
                    
                             
                    }
                    if(obj.hasOwnProperty([i])){
                        if(!obj[i].hasOwnProperty([j])){
                            obj[i][j] = arr.slice();
                            // console.log('create'+ ' ' + i + ' ' +j)
                        }
                    }
                  

                   
                    if(obj.hasOwnProperty([i]) && obj[i].hasOwnProperty([j])){
                        console.log('tempC'+tempC+' count = '+ count)  
                       
                        console.log('k '+'i = '+i+' j = '+j+' count = '+ count)                       
                        checkRow(workMatrix,i,j);
                        checkCol(workMatrix,i,j);
                        checkSegment(workMatrix,i,j);
                      
                        if(obj[i][j].length == 1){
                            console.log('SS'+i+j+' count = '+ count)
                            workMatrix[i][j] = obj[i][j][0];                          
                            count--;    
                                    
                            console.log('tempC'+tempC+' count = '+ count)      
                            delete obj[i][j];
                            
                        }
                    
                    }  
                             
                } else {
                    continue;
                }
            }
        }
        f--
    if (f != 0){
        return solve(workMatrix)
       
    } else {
        return
      
    }
       
   
    }


    function checkRow(workMatrix,i,j){
       
        for(let k = 0; k < 9; k++){
                for(let t = 0; t < 9; t++){
                    if(workMatrix[i][k] ==  obj[i][j][t]){
                        obj[i][j].splice(t, 1)    
                }
            }
            
        }
    }

    function checkCol(workMatrix,i,j){
        for(let k = 0; k < 9; k++){
            for(let t = 0; t < 9; t++){
                if(workMatrix[k][j] ==  obj[i][j][t]){
                    obj[i][j].splice(t, 1)    
            }
        }
        
    }
}
    function checkSegment(workMatrix,i,j){

        if(i >= 0 && i <= 2 && j >= 0 && j <= 2 ){          
            for(let k = 0; k < 3; k++){
                for(let t = 0; t < 3; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        } 
         else if(i > 2 && i <= 5 && j >= 0 && j <= 2){
            for(let k = 3; k < 6; k++){
                for(let t = 0; t < 3; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }
        else if(i > 5 && i <= 8 && j >= 0 && j <= 2){
            for(let k = 6; k < 9; k++){
                for(let t = 0; t < 3; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }

        else if(i >= 0 && i <= 2 && j > 2  && j <= 5 ){
            for(let k = 0; k < 3; k++){
                for(let t = 3; t < 6; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }
        else if(i > 2 && i <= 5 && j > 2 && j <= 5 ){
            for(let k = 3; k < 6; k++){
                for(let t = 3; t < 6; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }
        else if(i > 5 && i <= 8 && j > 2 && j <= 5 ){
            for(let k = 6; k < 9; k++){
                for(let t = 3; t < 6; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }

       else  if(i >= 0 && i <= 2 && j > 5  && j <= 8 ){
            for(let k = 0; k < 3; k++){
                for(let t = 6; t < 9; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }
        else if(i > 2 && i <= 5  && j > 5  && j <= 8 ){
            for(let k = 3; k < 6; k++){
                for(let t = 6; t < 9; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }
        else  if(i > 5 && i <= 8 && j > 5  && j <= 8){
            for(let k = 6; k < 9; k++){
                for(let t = 6; t < 9; t++){
                    for(let z = 0; z < 8; z++){
                        if(workMatrix[k][t] == obj[i][j][z] ){
                            obj[i][j].splice(z, 1)   
                        }
                    }
                }
            }
        }        

    }


   
    solve(workMatrix)
    for(let i = 0; i < 9; i++){
        for(let j = 0; j < 9; j++){
            if(workMatrix[i][j] == 0){
                document.write('<br>'+ obj[i][j])   
            }
        }
    }

    // // console.log(obj[0][7]);
    // // console.log(obj[0][8]);

  
    // document.write('<br>'+ in_val)
    return workMatrix        
  }

  var in_val = [
    [6, 5, 0, 7, 3, 0, 0, 8, 0],
    [0, 0, 0, 4, 8, 0, 5, 3, 0],
    [8, 4, 0, 9, 2, 5, 0, 0, 0],
    [0, 9, 0, 8, 0, 0, 0, 0, 0],
    [5, 3, 0, 2, 0, 9, 6, 0, 0],
    [0, 0, 6, 0, 0, 0, 8, 0, 0],
    [0, 0, 9, 0, 0, 0, 0, 0, 6],
    [0, 0, 7, 0, 0, 0, 0, 5, 0],
    [1, 6, 5, 3, 9, 0, 4, 7, 0]
];

console.log(solveSudoku(in_val));

[longclaps]

Артём, о, я вижу никто не помог. А мне чота стрёмно стало, как посмотрел на эту простыню. Ты питон знаешь?

Answer 1

[timokins]

Разделяешь путь прохождения на несколько,
подставляя каждое возможное число и проходишься по каждому варианту,
если один из путей приводит к логической ошибке, то смотришь следующий и т.д., пока не будет найден верный вариант.

Answer 2

[Антон П.]

Если попробовать начать с этого. Например ваше поле

- 1 2 3   4 5 6   7 8 9
1
2   ?   
3         ?

4                   ?
5
...

В ячейке (2; 2) у вас могут быть цифры 2, 4, 6.
В ячейке (4; 3) у вас могут быть цифры 2, 3, 8.
В ячейке (8; 4) у вас могут быть цифры 1, 4, 8.

Мы получаем, что в первой ячейке не повторяется с остальными ячейками только цифра 6, ее и ставим.
Во второй ячейке - цифра 3.
В третьей - 1.

Или я не правильно понял вашу проблему?

Comments

[Артём]

не правильно вроде)