Regras de Sudoku
Nos Jogos Sudoku, a grade clássica de nove gaiolas que consiste em 9 × 9 = 81 células e também forma 3 × 3 = 9 pequenas grades de nove gaiolas. É necessário preencher os números 1 ~ 9 em 81 células pequenas, e os números não podem ser repetidos em cada linha, coluna e cada pequena grade de nove gaiolas.
Habilidades Sudoku
Meus pensamentos
Design e implementação de soluções
Apenas uma matriz bidimensional é usada para armazenar o esquema Sudoku, uma matriz unidimensional é usada como pilha e uma variável booleana é usada como identificação de backtrack.
1. Definição variável:
Var Problem = [// Esta é a questão da dificuldade 10.7 mencionada no livro [8,0,0,0,0,0,0,0,0], [0,0,3,6,0,0,0,0,0,0], [0,7,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,] [0,0,0,0,0,4,5,7,0,0,0], [0,0,0,1,0,0,0, pilha = [], sinalizador = false;
2. Determinação da eficácia do plano:
O recurso de hash dos objetos JavaScript é totalmente utilizado. Para facilitar a depuração, o valor de retorno da função é 0 quando é válido e há três situações em que é inválido: conflito de linha, conflito de colunas e conflitos de grade de nove partes, que retornam 1, 2 e 3, respectivamente. Usei-o no julgamento antecipado e depois adicionei o julgamento relevante de vinte e frame. Esta função não é mais usada ao procurar a resposta.
função checkValid (sudo) {let subsudo = {} // variável auxiliar usada para determinar se a nona grade conflita (vamos i = 0; i <9; i ++) {let line = {}, colets = {} // Auxily Variable usado para determinar se as linhas e as colunas conflitos para (let para (} 0; sudo [i] [j], cur2 = sudo [j] [i] // variável autorizada completa o julgamento da linha e coluna ao mesmo tempo se (linha [cur1]) // o elemento atual apareceu na linha e o julgamento de zero for otimizado. Quando a chave é 0, o valor é 0, nenhum julgamento adicional é necessário. Retornar 1; // Retorno código de erro mais linha [cur1] = cur1 // O elemento atual não aparece na linha e é armazenado na variável auxiliar se (col [cur2]) // O julgamento da coluna é semelhante à linha. O julgamento de zero é otimizado. Quando a chave é 0, o valor é 0 e não há necessidade de julgamento adicional. Retornar 2; else col [cur2] = cur2; Let Key = Math.Floor (i/3)+'-'+Math.floor (J/3) // As diferentes teclas são geradas para diferentes grades de nove clientes se (subsudo [key]) {// O julgamento de zero já está lá e o julgamento de zero é otimizado. Quando a chave é 0, o valor é 0 e não há necessidade de julgamento adicional se (subsudo [key] [cur1]) // O julgamento de uma grade de nove client é semelhante ao de retornos de linha 3 mais subsudo [key] [CUR1] = CUR1} {// Este é o primeiro elemento em um pequeno e nine-dhish grid Subsudo [ grade de nove dish e salve o primeiro elemento em ele subsudo [key] [cur1] = cur1}}} retornar 0; // O programa pode executar isso, indicando que o plano é válido} 3. Determinação relevante de vinte categoria O princípio é o mesmo que o julgamento geral, e o destaque está no posicionamento da pequena grade de nove gaiolas. função check20Grid (sudo, i, j) {let row = {}, col = {}, subsudo = {} // Variável de fornecimento para (Seja k = 0; k <9; k ++) {let cur1 = sudo [i] Quando a chave é 0, o valor é 0 e não há necessidade de julgamento adicional se (linha [cur1]) retornar 1; // Retorne o código de erro mais linha [cur1] = cur1 // O elemento atual não aparece na linha e é armazenado na variável auxiliar} if (cur2) {// O julgamento da coluna é semelhante à linha. O julgamento da perda zero é otimizado. O valor é 0 quando a chave é 0. Não há necessidade de julgamento adicional se (col [cur2]) retornar 2; else col [cur2] = cur2; } // As coordenadas da variável do loop de conversão para a nona grade Let Key = sudo [Math.floor (i/3)*3 + math.floor (k/3)] [Math.floor (J/3)*3 + math.floor (k%)] se (Subsudo [key] //. O julgamento da perda zero é otimizado. O valor é 0 quando a chave é 0. Não há necessidade de devolução adicional de julgamento 3 mais subsudo [key] = key} retornar 0;}4. Solução Traversal
Usando elementos com o valor inicial de zero no estado do elemento é um recurso pendente e, com a assistência da pilha, nenhum espaço de armazenamento adicional é aberto.
função findanswer () {for (vamos i = 0; i <9; i ++) {for (vamos j = 0; j <9;) {if (problema [i] [j] === 0 || sinalizador) {// A posição atual é o primeiro processamento do elemento a ser determinado ou de volta à posição atual. As duas situações parecem ser diferentes, mas na verdade o processamento é o mesmo. Adicione 1 sinalizador por si mesmo = false; Seja k = problema [i] [j] + 1; // Pesquise para avançar em direção ao próximo valor legal enquanto (k <10) {// loop para encontrar o próximo problema de valor legal [i] [j] = k; // preencha if (check20Grid (problema, i, j) == 0) {// O padrão é legal, e o julgamento relevante do vinte eixos é Stack.push ([i, j ++]) // armazenamento o ponto de rastreamento e entra no intervalo; } k ++; } if (k> 9) {// O valor legal não pode ser encontrado na posição atual, o problema de rastreamento [i] [j] = 0; // retorna antes do traceback, deixe rt = pilha.pop (); // Recuperar as informações de rastreamento na pilha if (! Rt) // sem julgamento da solução, retornar 0 retornar 0; i = rt [0] // Travel J = rt [1] sinalizador = true; }} else {// O número da posição atual é fornecido J ++; }}} retornar 1; // encontrou com sucesso um conjunto de soluções}