; --------------------------------------
; Programa: Solucionador de Sudokus
; --------------------------------------
;
; Descrição: "Backend" de um programa que resolve, avalia e gera
;            jogos de Sudoku nos modos 4x4, 9x9 e 16x16.
;
; Criado por: Miguel Pais (62466)
;             Bruno Franco (62478)
;             João Vieira (62526)
;
; Grupo Nº:   67
;
; Data de criação: 5 de Dezembro de 2007
;

; ----------------------------
; [!] Carregar: Interface
; ----------------------------
(require "interface.zo")

; ----------------------------
; [?] Bug: Interface
; ----------------------------
; carregar o mais possível no meio dos quadrados da grelha
; ou à esquerda destes senão os números são postos no quadrado à direita

; ----------------------------
; [=] Definição Tipo: Matriz
; ----------------------------
;
; Descrição: Uma matriz é representada por um vector
;            cujas componentes são também vectores que 
;            representam as linhas da matriz

; ======== construtores ========

(define (matriz d i)
  ; cria a estrutura de dados matriz de dim d inicializada a i
  (let ((m (make-vector d))
        (n 0)  ; percorre linhas
        (j 0)) ; percorre colunas
    (define (cria-linhas) ; cria sub-vectores da matriz, as linhas
      (if (< n d) ; enquanto menor indice que nº de linhas 
          (begin 
            (vector-set! m n 
                       (make-vector d)) ; cria vector-linha
            (set! n (+ n 1))
            (cria-linhas))))
    (define (inicializa-matriz)
      (if (< n d) ; enquanto menor indice que nº de linhas
          (begin
            (if (< j d) ; enquanto menor indice que nº colunas
                (begin
                  (coloca-matriz! m n j i) ; inicializa elemento
                  (set! j (+ j 1))) ; incializa o seguinte
                (begin
                  (set! j 0) ; lê-se o primeiro elemento...
                  (set! n (+ n 1)))) ; ... da coluna seguinte
            (inicializa-matriz)))) 
    (cria-linhas)
    (set! n 0) ; reutilizaçao de n
    (inicializa-matriz)
    m)) ; devolve a matriz

    (define (copia-matriz m d)
      (if (matriz? m)
          (let ((k (matriz d ""))
                (n 0)
                (j 0))
            (define (aux n j)
              (cond ((>= n d) k)
                    ((>= j d) 
                     (aux (+ n 1) 0))
                    (else
                     (coloca-matriz! k n j (el-matriz m n j))
                     (aux n (+ j 1)))))
            (aux 0 0)) 
          #f))

; ======== selectores ========

(define (el-matriz m l c)
  (vector-ref (vector-ref m l) c))

(define (dimensao-matriz m)
  (vector-length m))

; ======== modificadores ======== 

(define (coloca-matriz! m l c obj)
  (vector-set! (vector-ref m l) c obj))


; ======== reconhecedores ========

(define (matriz? arg)
  (if (not (vector? arg))
      #f
      (let ((d (vector-length arg))
            (n 0))
        (define (elem-vectores?)
          (if (>= n d) ; se já nao há mais linhas
              #t
              (if (not (vector? (vector-ref arg n)))
                  #f
                  (begin
                    (set! n (+ n 1))
                    (elem-vectores?)))))
        (elem-vectores?))))

(define (els-matriz-tipo? m p)
  (let ((d (dimensao-matriz m)))
    (define (els-matriz-aux n j)
      (cond ((>= n d) ; se ja nao ha mais linhas 
             #t)
            ((>= j d) ; se se ultrapassar os elementos de uma dada linha
             (els-matriz-aux (+ n 1) 0)) ; acede-se à linha seguinte
            (else
             (if (not (p (el-matriz m n j)))  ; se elemento em cada nao for do tipo p
                 #f 
                 (els-matriz-aux n (+ j 1)))))) ; senao continua a avaliar os restantes elementos
    (els-matriz-aux 0 0)))

; ----------------------------
; [=] Definição Tipo: Pilha
; ----------------------------
;
; Descrição: Uma pilha é representada por uma caixa
;            que contém uma estrutura de pares.

; ======== construtores ========

(define (nova-pilha)
  (box ()))

(define (empurra! el pilha)
  (set-box! pilha (cons el (unbox pilha))))

; ======== selectores ========

(define (topo pilha)
  (let ((conteudo (unbox pilha)))
    (car conteudo)))

(define (tira! pilha)
  (let ((conteudo (unbox pilha)))
    (set-box! pilha (cdr conteudo))))

; ======== reconhecedores ========

(define (pilha-vazia? pilha)
  (null? (unbox pilha)))

; ---------------------------------
; [»] Operações Interface Gráfica
; ---------------------------------
       
(define (resolve-puzzle dim)
  (create-grid-window dim #t))

; (digito-valido? carac d)
; ----------------------------
; Descrição: Este procedimento recebe um caracter e a
;            dimensão da matriz e devolve true se o
;            caracter é válido para matrizes dessa
;            dimensão e false em caso contrário.

(define (digito-valido? carac d)
  (cond ((= d 4) (and (string<=? carac "4") (string>=? carac "1")))
        ((= d 9) (and (string<=? carac "9") (string>=? carac "1"))) 
        ((= d 16) (or (and (string<=? carac "9") (string>=? carac "1")) 
                      (and (string<=? carac "G") (string>=? carac "A"))))))

; (resolve m)
; ----------------------------
; Descrição: Recebe a matriz inserida pelo utilizador
;            apresenta-a no ecrã caso seja possível
;            ou a corrspondente mensagem de impossibilidade

(define (resolve m)
  (let* ((d (dimensao-matriz m))
         (m (copia-matriz (resolve-sudoku m) d)))
    (if (matriz? m)
        (draw-grid m)
        (write-impossible-message))))

; (resolve-sudoku m)
; ----------------------------
; Descrição: Pega na matriz com elementos inseridos
;            pelo utilizador e executa uma série de
;            procedimentos iniciais com o objectivo de 
;            determinar a sua possibilidade. Caso não
;            detecte que o puzzle é impossível, aplica-lhe
;            o algoritmo de resolução, tendo para isso de
;            a depositar numa pilha. Caso o puzzle seja
;            possível é devolvida a solução.

(define (resolve-sudoku m)
  (let ((pilha (nova-pilha))
        (d (dimensao-matriz m)))
    (set! m (expande-matriz m d))
    (set! m (inspecciona-matriz m d))
    (set! m (reduz m d))   
    (if (not (testa-impossibilidade m d))
        (begin
          (empurra! m pilha)
          (resolve-aux pilha d))
        #f))) ;; valor retornado só para não validar o copia matriz 

; ---------------------------------
; [»] Operações de Alto Nível
; ---------------------------------

; (expande-matriz m d)
; ----------------------------
; Descrição: Recebe uma matriz m e a sua dimensão d,
;            coloca em cada posição não preenchida 
;            pelo utilizador uma lista com todas as 
;            possibilidades independentemente dos 
;            valores vizinhos e devolve a matriz
;            expandida que resulta da operação
;            descrita.

(define (expande-matriz m d) 
  (let* ((n 0)
         (j 0)
         (lista (devolve-lista-possibilidades d)))
    (define (percorre)
      (cond ((>= n d) m)
            ((>= j d)
             (set! j 0)
             (set! n (+ n 1))
             (percorre))
            ((string=? "" (el-matriz m n j))
             (coloca-matriz! m n j lista)
             (set! j (+ j 1))
             (percorre))
            (else (set! j (+ j 1))
                  (percorre))))
    (percorre)
    m))


; (inspecciona-matriz m d)
; ----------------------------
; Descrição: Recebe uma matriz m de dimensão d, remove
;            todas as hipóteses que se repetem na mesma
;            linha, coluna ou bloco e devolve a matriz
;            modificada.
;
;            Recorre ao seguinte algorítmo:
;            
;            (1) Percorre cada elemento da matriz procurando
;                por valores inseridos pelo utilizador.
;                Se não tiverem sido inseridos pelo utilizador
;                são passados à frente.
;                Caso tenham sido faz-se o seguinte:
;   
;                (1.1) Surpime-se esse elemento de todas as listas de 
;                      possibilidade da linha, usando o procedimento 
;                      suprime-na-linha
;
;                (1.2) Surpime-se esse elemento de todas as listas de 
;                      possibilidade da coluna, usando o procedimento 
;                      suprime-na-coluna
;
;                (1.3) Surpime-se esse elemento de todas as listas de 
;                      possibilidade do bloco, usando o procedimento 
;                      suprime-na-bloco

(define (inspecciona-matriz m d)
  (let ((n 0)
        (j 0)
        (sqrtd (sqrt d)))
    (define (inspecciona-matriz-aux)
      (cond ((>= n d) m)
            ((>= j d)
             (set! j 0)
             (set! n (+ n 1))
             (inspecciona-matriz-aux))
            ((list? (el-matriz m n j))
             (set! j (+ j 1))
             (inspecciona-matriz-aux))
            (else
             (let ((el (el-matriz m n j))
                   (nlimit "")
                   (jlimit ""))
               (set! m (suprime-na-linha m n 0 el d))
               (set! m (suprime-na-coluna m 0 j el d))
               (set! nlimit (car (coords-bloco n j sqrtd)))
               (set! jlimit (cdr (coords-bloco n j sqrtd)))
               (set! m (suprime-no-bloco m nlimit jlimit 
                                         (+ nlimit sqrtd) 
                                         (+ jlimit sqrtd) el sqrtd))
               (set! j (+ j 1))
               (inspecciona-matriz-aux)))))
    (inspecciona-matriz-aux)
    m))

; (suprime-na-linha m n j obj d)
; ----------------------------
; Descrição: Devolve uma versão simplificada da matriz
;            na qual são eliminadas das listas de possibilidades
;            dos elementos de uma dada linha o obj d
;
;            Recorre ao seguinte algorítmo:
;
;            (1) Percorre-se toda a linha e sempre que se identificar 
;                uma lista de possibilidades, retira-se o objecto 
;                obj a essa lista.
;
;            (2) Caso contrário, analisamos o próximo elemento (c+1)
;                dessa linha de acordo com (1).

(define (suprime-na-linha m n j obj d)
      (cond ((>= j d) m)
            ((list? (el-matriz m n j))
             (coloca-matriz! m n j (suprime (el-matriz m n j) obj))
             (suprime-na-linha m n (+ j 1) obj d))
            (else
             (suprime-na-linha m n (+ j 1) obj d))))

; (suprime-na-coluna m n j obj d)
; ----------------------------
; Descrição: Devolve uma versão simplificada da matriz
;            na qual são eliminadas das listas de possibilidades
;            dos elementos de uma dada coluna o obj d
;
;            Recorre ao seguinte algorítmo:
;
;            (1) Percorre-se toda a coluna e sempre que se identificar 
;                uma lista de possibilidades, retira-se o objecto 
;                obj a essa lista.
;
;            (2) Caso contrário, analisamos o próximo elemento (l+1)
;                dessa coluna de acordo com (1).
      
(define (suprime-na-coluna m n j obj d)
      (cond ((>= n d) m)
            ((list? (el-matriz m n j))
             (coloca-matriz! m n j (suprime (el-matriz m n j) obj))
             (suprime-na-coluna m (+ n 1) j obj d))
            (else
             (suprime-na-coluna m (+ n 1) j obj d))))

; (suprime-no-bloco m n j nlimit jlimit obj sqrt-d)
; ----------------------------
; Descrição: Devolve uma versão simplificada da matriz
;            na qual são eliminadas das listas de possibilidades
;            dos elementos de um dado bloco o obj d.
;
;            Recebe em l e c (inicialmente) o primeiro elemento 
;            (do canto superior esquerdo) de um dado bloco,
;            bem como os limites em linha e coluna de um
;            dado bloco (aos quais o ciclo não deve chegar).
;            O argumento sqrtd serve para conseguir calcular
;            de novo el do bloco a aceder após mudança de linha.
;
;            Dito isto, escreveu-se um algorítmo que executa as
;            seguintes instruções:
;
;            (1) Percorre todos os elementos de uma linha n que fazem
;                parte de um bloco até que se atinja uma coordenada que
;                esteja fora dos limites do bloco, indo eliminando
;                dos elementos que forem listas o objecto obj. 
;
;            (2) Após se atinjir o final da linha passa-se à seguinte 
;                (coordenada l incrementa um, coordenada c é
;                dada por climit - sqrt(d).
;

(define (suprime-no-bloco m n j nlimit jlimit obj sqrt-d)
  (cond ((>= n nlimit) m)
        ((>= j jlimit)
         (suprime-no-bloco m (+ n 1) 
                           (- jlimit sqrt-d) nlimit jlimit obj sqrt-d))
        ((list? (el-matriz m n j))
         (coloca-matriz! m n j (suprime (el-matriz m n j) obj))
         (suprime-no-bloco m n (+ j 1) nlimit jlimit obj sqrt-d))
        (else
         (suprime-no-bloco m n (+ j 1) nlimit jlimit obj sqrt-d))))

; (reduz m d)
; ----------------------------
; Descrição: Recebe uma matriz e a sua dimensão e, se algum dos
;            componentes é uma lista de um único
;            elemento, substitui essa lista pelo
;            próprio componente e devolve a matriz
;            modificada.

(define (reduz m d)
  (let ((n 0)
        (j 0))
    (define (percorre)
      (cond ((>= n d))
            ((>= j d)
             (set! j 0)
             (set! n (+ n 1))
             (percorre))
            ((lista-de-um? (el-matriz m n j))
             (coloca-matriz! m n j (car (el-matriz m n j)))
             (percorre))
            (else
             (set! j (+ j 1))
             (percorre))))
    (percorre)
    m))
     
; (testa-impossibilidade m d)
; ----------------------------
; Descrição: Recebe uma matriz m e a sua dimensão d,
;            e procura na matriz por:
;
;            (1) componentes sem quaisquer hipóteses 
;                (feito pelo ha-elementos-iguais?)
;            
;            (2) impossibilidades imediatas: dois 
;                (ou mais) elementos iguais na mesma 
;                linha, coluna e/ou bloco (feito pelo há-listas-vazias?
;                que subdivide em três pesquisas, na coluna, 
;                na linha e no bloco.



(define (testa-impossibilidade m d)
    (cond ((ha-listas-vazias? m d) #t)
          ((ha-elementos-iguais? m d) #t)
          (else #f)))


(define (ha-listas-vazias? m d)
  (define (ha-listas-vazias?-aux n j d)
    (cond ((>= n d) #f)
          ((>= j d)
           (ha-listas-vazias?-aux (+ n 1) 0 d))
          ((null? (el-matriz m n j))
           #t)
          (else
           (ha-listas-vazias?-aux n (+ j 1) d))))
  (ha-listas-vazias?-aux 0 0 (dimensao-matriz m)))

(define (ha-elementos-iguais? m d)
  (let ((sqrtd (sqrt d)))
    (define (ha-elementos-iguais?-aux n j d)   
      (cond ((>= n d) #f)
            ((>= j d)
             (ha-elementos-iguais?-aux (+ n 1) 0 d))
            ((list? (el-matriz m n j))
             (ha-elementos-iguais?-aux n (+ j 1) d))
            ((not (or (na-linha? m n 0 (el-matriz m n j) j d)
                      (na-coluna? m 0 j (el-matriz m n j) n d)
                      (no-bloco? m (car (coords-bloco n j sqrtd)) 
                                 (cdr (coords-bloco n j sqrtd)) 
                                 (+ (car (coords-bloco n j sqrtd)) sqrtd)
                                 (+ (cdr (coords-bloco n j sqrtd)) sqrtd)
                                 (el-matriz m n j) sqrtd n j)))
             (ha-elementos-iguais?-aux n (+ j 1) d))
            (else
             #t)))        
    (ha-elementos-iguais?-aux 0 0 (dimensao-matriz m))))


(define (na-linha? m n j obj saltaj d)
  (cond ((>= j d) #f)
        ((or (list? (el-matriz m n j)) (= j saltaj))
         (na-linha? m n (+ j 1) obj saltaj d))
        (else
         (if (string=? (el-matriz m n j) obj)
             #t
             (na-linha? m n (+ j 1) obj saltaj d)))))


(define (na-coluna? m n j obj saltan d)
  (cond ((>= n d) #f)
        ((or (list? (el-matriz m n j)) (= n saltan))
         (na-coluna? m (+ n 1) j obj saltan d))
        (else
         (if (string=? (el-matriz m n j) obj)
             #t
             (na-coluna? m (+ n 1) j obj saltan d)))))


(define (no-bloco? m n j nlimit jlimit obj sqrt-d saltan saltaj)
  (cond ((>= n nlimit) #f)
        ((>= j jlimit)
         (no-bloco? m (+ n 1) (- jlimit sqrt-d) nlimit jlimit obj sqrt-d saltan saltaj))
        ((or (list? (el-matriz m n j)) (and (= n saltan) (= j saltaj)))
         (no-bloco? m n (+ j 1) nlimit jlimit obj sqrt-d saltan saltaj))
        (else
         (if (string=? (el-matriz m n j) obj)
             #t
             (no-bloco? m n (+ j 1) nlimit jlimit obj sqrt-d saltan saltaj)))))



; (resolve-aux pilha d)
; ----------------------------
; Descrição: Recebe uma pilha 'pilha e a dimensão d
;            das matrizes da pilha e executa o seguinte
;            algorítmo:
;
;            (1) Verifica se a pilha é vazia,
;                (1.1) se a pilha for vazia envia
;                      uma mensagem de erro à interface
;                      gráfica.
;                (1.2) caso contrário,
;                      (1.2.1) copia para a matriz m a matriz do topo
;                              da pilha e faz dela a matriz de
;                              trabalho.
;                      (1.2.2) inspecciona a matriz m
;                      (1.2.3) reduz a matriz m
;                      (1.2.4) testa se a matriz m é possível,
;                              e:
;                              (1.2.4.1) caso seja impossível, retira o
;                                        actual topo da pilha e volta a 1
;                              (1.2.4.2) se a matriz está completa,
;                                        devolve a matriz.
;                              (1.2.4.3) caso contrário:
;                                        (1.2.4.3.1) retira o actual topo
;                                                    da pilha, seleciona o
;                                                    primeiro elemento da
;                                                    primeira lista de 
;                                                    hipóteses presenta na
;                                                    matriz m, coloca na 
;                                                    matriz a matriz m sem
;                                                    o primeiro elemento
;                                                    da primeira lista
;                                                    de possibilidades, e
;                                                    coloca na matriz a
;                                                    matriz com esse
;                                                    elemento substítuido
;                                                    pela primeira lista
;                                                    de possibilidades.
;                                                    Corre-se de novo 1.

(define (resolve-aux pilha d)
  (if (pilha-vazia? pilha)
      #f ; valor retornado apenas para que não seja validada a chamada (matriz? m) do resolve para que seja mostrada mensagem de puzzle impossível
      (let* ((m (copia-matriz (topo pilha) d))
             (res "")
             (k ""))  
        (set! m (inspecciona-matriz m d))
        (set! m (reduz m d))
        (set! k (copia-matriz m d))
        (cond ((testa-impossibilidade m d)
               (tira! pilha)
               (resolve-aux pilha d))
              ((matriz-completa? m) 
               m)
              (else
               (set! res (primeiro-el-lista-matriz m d))
               (tira! pilha)
               (empurra! (suprime-o-primeiro m d res) pilha)
               (empurra! (substitui-o-primeiro k d res) pilha)
               (resolve-aux pilha d))))))

; (primeiro-el-lista-matriz m d)
; -------------------------------
; Descrição: Recebe uma matriz e a sua dimensão e, retorna
;            o primeiro elemento da primeira lista
;            da matriz.

(define (primeiro-el-lista-matriz m d)
  (define (aux n j)
    (cond ((>= j d)
           (aux (+ n 1) 0))
          ((list? (el-matriz m n j))
           (car (el-matriz m n j)))
          (else
           (aux n (+ j 1)))))
  (aux 0 0)) 

; (suprime-o-primeiro m d obj)
; ----------------------------
; Descrição: Recebe uma matriz, a sua dimensão e um objecto e retorna
;            uma matriz correspondente à matriz inicial em que a 
;            sua primeira lista ficou sem o objecto obj (o objecto a
;            eliminar será sempre o primeiroda lista, implementa-se 
;            deste modo para não dar problemas com possíveis listas
;            vazias).
        
(define (suprime-o-primeiro m d obj)
  (define (aux n j)
    (cond ((>= j d)
           (aux (+ n 1) 0))
          ((list? (el-matriz m n j))
           (coloca-matriz! m n j (suprime (el-matriz m n j) obj)))
          (else
           (aux n (+ j 1)))))
  (aux 0 0)
  m)
                

; (substitui-o-primeiro m d obj)
; ----------------------------
; Descrição: Recebe uma matriz, a sua dimensão e um objecto e retorna
;            a matriz correspondente à inicial mas com o objecto obj 
;            substituído pela sua primeira lista.

(define (substitui-o-primeiro m d obj)
  (define (aux n j)
    (cond ((>= j d)
           (aux (+ n 1) 0))
          ((list? (el-matriz m n j))
           (coloca-matriz! m n j obj))
          (else
           (aux n (+ j 1)))))
  (aux 0 0)
  m)


; (puzzle-resolvido) 
;----------------------------------
;
; Descrição: Gera um puzzle já resolvido
;            tendo em conta um nível N de
;            aleatoriedade.

(define (puzzle-resolvido d)
  (create-grid-window d #f)
  (draw-grid (puzzle-aleatorio-resolvido d)))

; (puzzle-aleatorio-resolvido d)
;------------------------------------
; Descrição: Recebe uma dimensão, randomiza as coordenadas
;            de um elemento a colocar na primeira linha da
;            matriz e randomiza o valor a lá colocar. Aplica,
;            por fim, o algoritmo resolve a essa matriz e mostra.

(define (puzzle-aleatorio-resolvido d)
  (let ((m (matriz d ""))
        (coord "")
        (pilha (nova-pilha))
        (obj (+ 1 (random d))))
    (cond ((= obj 1) (set! obj "1"))
          ((= obj 2) (set! obj "2"))
          ((= obj 3) (set! obj "3"))
          ((= obj 4) (set! obj "4"))
          ((= obj 5) (set! obj "5"))
          ((= obj 6) (set! obj "6"))
          ((= obj 7) (set! obj "7"))
          ((= obj 8) (set! obj "8"))
          ((= obj 9) (set! obj "9"))
          ((= obj 10) (set! obj "A"))
          ((= obj 11) (set! obj "B"))
          ((= obj 12) (set! obj "C"))
          ((= obj 13) (set! obj "D"))
          ((= obj 14) (set! obj "E"))
          ((= obj 15) (set! obj "F"))
          ((= obj 16) (set! obj "G")))
    (set! coord (random d))
    (coloca-matriz! m 0 coord obj)
    (resolve-sudoku m)))

  
  
; (utilizador-resolve d) 
;----------------------------------------
;
; Descrição: Deixa o utilizador resolver um puzzle aleatório incompleto
;            avaliando a cada momento se a jogada é permitida.
;
;            Para tal cria-se primeiramente um objecto computacional e
;            uma dimensão globais para que os restantes procedimentos
;            saibam onde se encontra a matriz sobre a qual operam.
;            Seguidamente gera-se um puzzle resolvido, associa-se a
;            matrizglobal a esse puzzle e retiram-se aleatóriamente
;            alguns dos seus elementos. Apresenta-se o resultado e
;            prepaa-se o programa para receber digitos do utilizador.

(define matrizglobal "")
(define dim "")

(define (utilizador-resolve d)
  (define (utilizador-resolve-aux y)
    (if (= (quotient (expt d 2) 2) y)
        (begin (create-grid-window d #t)
               (draw-grid matrizglobal)
               (read-digit))
        (begin (coloca-matriz! matrizglobal (random d) (random d) "")
               (utilizador-resolve-aux (+ y 1)))))
  (set! matrizglobal (copia-matriz (puzzle-aleatorio-resolvido d) d))
  (set! dim d)
  (utilizador-resolve-aux 0))

; (digito-possivel? obj n j)
;-----------------------------------------
;
; Descrição: Caso o dígito esteja entre a range indicada para a
;            dimensão sobre a qual se está a operar, e não hajam
;            na mesma coluna, linha ou bloco elementos iguais,
;            aceita-se o dígito.

(define (digito-possivel? obj n j)
  (let* ((sqrtd (sqrt dim))
         (coord-bloco (coords-bloco n j sqrtd)))
    (and (not (or (na-linha? matrizglobal n 0 obj 17 dim)
                  (na-coluna? matrizglobal 0 j obj 17 dim)
                  (no-bloco? matrizglobal (car (coords-bloco n j sqrtd)) (cdr (coords-bloco n j sqrtd)) (+ (car (coords-bloco n j sqrtd)) sqrtd) (+ (cdr (coords-bloco n j sqrtd)) sqrtd) obj sqrtd n j)))
         (digito-valido? obj dim))))
  

; (recebe-digito obj n j)
;------------------------------------------
;
; Descrição: Sendo um dígto válido, este é colocado na matriz

(define (recebe-digito obj n j)
  (coloca-matriz! matrizglobal n j obj))
     
; ======== procedimentos auxiliares ========

; (coords-bloco n j sqrtd)
; ----------------------------
; Descrição: Recebe coordenadas n,j e a
;            raiz quadrada da dimensão da respectiva matriz
;            e devolve as coordenadas do 
;            primeiro elemento do bloco (do canto superior esquerdo) a que 
;            pertencem as coordenadas recebidas.

(define (coords-bloco n j sqrtd)
  (cons (* (quotient n sqrtd) sqrtd)
        (* (quotient j sqrtd) sqrtd)))

; (matriz-completa m)
; ----------------------------
; Descrição: Recebe uma matriz m e devolve
;            true se a matriz está preenchida
;            com valores ou false no caso de
;            algum dos elementos estar vazio ou
;            ser uma lista de hipóteses.

(define (matriz-completa? m)
  (els-matriz-tipo? m string?))

; (suprime lista i)
; ----------------------------
; Descrição: Recebe uma lista 'lista e remove
;            o elemento i da lista recebida.

(define (suprime lista i)
  (cond ((null? lista)
         ())
        ((string=? (car lista) i)
         (cdr lista))
        (else 
         (cons (car lista)
               (suprime (cdr lista) i)))))

; (suprime lista-de-um? lista)
; ----------------------------
; Descrição: Recebe uma lista 'lista e devolve
;            true se essa lista tem um único
;            elemento e false em caso contrário.

(define (lista-de-um? lista)
  (cond ((not (list? lista)) #f)
        ((null? lista) #f)
        ((null? (cdr lista)) #t)
        (else #f)))

; (devolve-lista-possibilidades d)
; -----------------------------------
; Descrição: Recebe uma dimensão d e devolve
;            uma lista de cadeia caracteres com
;            com os valores aceitáveis.
      
(define (devolve-lista-possibilidades d)
  (cond ((= d 4) '("1" "2" "3" "4"))
        ((= d 9) '("1" "2" "3" "4" "5" "6" "7" "8" "9"))
        ((= d 16) '("1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F" "G"))))