#1383 Beecrowd Online Judge Solution 1383 Sudoku Solution in C, C++, Java, Js and Python

Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1383

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1383

Sudoku

Maratona de Programação IME-USP

Brazil

Timelimit: 1

The Sudoku puzzle spread quickly across the world, being the most popular hobby in the planet today. Some people, however, fill the matrix incorrectly, breaking the rules. Your task is to write a program that checks whether a filled matrix is a solution to the puzzle or not.

The matrix is a 9 x 9 matrix of integers. To be considered a solution to the puzzle, each row and each column must contain all integer numbers between 1 and 9. Also, if the matrix is partitioned in nine 3 x 3 sub-matrices (as shown below), each one of them must also contain all numbers between 1 and 9. The following matrix is an example of a solution to the puzzle.

Input

Several instances are given. The first line of the input contains n > 0, the number of matrices in the input. The following lines describe n matrices. Each matrix is described by 9 lines. These lines contain 9 integers each.

Output

For each instance, your program must print a line containing "Instancia k" , where k is the instance number. In the second line, your program must print "SIM" (portuguese for yes) if the given matrix is a solution to the puzzle, or "NAO" (portuguese for no) otherwise. Print an empty line after each instance.

Sample Input	Sample Output
2 1 3 2 5 7 9 4 6 8 4 9 8 2 6 1 3 7 5 7 5 6 3 8 4 2 1 9 6 4 3 1 5 8 7 9 2 5 2 1 7 9 3 8 4 6 9 8 7 4 2 6 5 3 1 2 1 4 9 3 5 6 8 7 3 6 5 8 1 7 9 2 4 8 7 9 6 4 2 1 5 3 1 3 2 5 7 9 4 6 8 4 9 8 2 6 1 3 7 5 7 5 6 3 8 4 2 1 9 6 4 3 1 5 8 7 9 2 5 2 1 7 9 3 8 4 6 9 8 7 4 2 6 5 3 1 2 1 4 9 3 5 6 8 7 3 6 5 8 1 7 9 2 4 8 7 9 6 4 2 1 3 5	Instancia 1 SIM Instancia 2 NAO

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(){
  	int matriz[9][9], testador[10], i, j, k, h, n, teste = 0;
   
  	scanf("%d",&n);
  
  	for(h = 1; h  < = n; h++){
    	
    	teste = 0;
    	
    	for(i = 0; i  <  9; i++){
      		for(j = 0; j  <  9; j++)
    			scanf("%d",&matriz[i][j]);
    	}
     
	    for(i = 0 ; i  <  9 && !teste; i++){
	      	memset(testador, 0, sizeof(testador));
	      	for(j = 0; j  <  9 && !teste; j++){
	    		if(testador[matriz[i][j]])
	      			teste = 1;
	    		else
	      			testador[matriz[i][j]] = 1;
	      	}
	    }
	     
	    for(i = 0; i < 9 && !teste; i++){
	      	memset(testador, 0, sizeof(testador));
	      	for(j = 0; j  <  9 && !teste; j++){
	    		if(testador[matriz[j][i]])
	      			teste = 1;
	    		else
	      			testador[matriz[j][i]] = 1;
	      	}
	    }
	     
	    for(i = 2; i  <  9 && !teste; i+=3){
	      	memset(testador, 0, sizeof(testador));
	      	for(j = i - 2; j  < = i && !teste; j++){
	    		for(k = i - 2; k  < = i && !teste; k++){
	      			if(testador[matriz[j][k]])
	        			teste = 1;
	      			else
	        			testador[matriz[j][k]] = 1;
	    		}
	      	}
	    }

	    printf("Instancia %d\n",h);
	    printf("%s\n\n",(!teste)?"SIM":"NAO">;
  	}
  	
  	return 0 ; 
}

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

Instancia 1
SIM
Instancia 2
NAO

#2 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n, t = 1;
    cin >> n;
    for (int k = 0; k  <  n; ++k) {
        cout << "Instancia " << t++ << "\n";
        int sudoku[9][9];
        bool flag = true, regiao[9][9], coluna[9][9];
        for (int i = 0; i  <  9; ++i) {
            for (int j = i; j  <  9; ++j) {
                regiao[i][j] = regiao[j][i] = false;
                coluna[i][j] = coluna[j][i] = false;
            }
            regiao[i][i] = coluna[i][i] = false;
        }
        for (int i = 0; i  <  9; ++i) {
            bool linha[] = { false, false, false, false, false, false, false, false, false };
            for (int j = 0; j  <  9; ++j) {
                cin >> sudoku[i][j];
                if (linha[sudoku[i][j] - 1])
                    flag = false;
                else
                    linha[sudoku[i][j] - 1] = true;
                if (coluna[j][sudoku[i][j] - 1])
                    flag = false;
                else
                    coluna[j][sudoku[i][j] - 1] = true;
                if (i  <  3 && j < 3) {
                    if (regiao[0][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[0][sudoku[i][j] - 1] = true;
                } else if (i  <  6 && j < 3) {
                    if (regiao[1][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[1][sudoku[i][j] - 1] = true;
                } else if (i  <  9 && j < 3) {
                    if (regiao[2][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[2][sudoku[i][j] - 1] = true;
                } else if (i  <  3 && j < 6) {
                    if (regiao[3][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[3][sudoku[i][j] - 1] = true;
                } else if (i  <  6 && j < 6) {
                    if (regiao[4][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[4][sudoku[i][j] - 1] = true;
                } else if (i  <  9 && j < 6) {
                    if (regiao[5][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[5][sudoku[i][j] - 1] = true;
                } else if (i  <  3 && j < 9) {
                    if (regiao[6][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[6][sudoku[i][j] - 1] = true;
                } else if (i  <  6 && j < 9) {
                    if (regiao[7][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[7][sudoku[i][j] - 1] = true;
                } else if (i  <  9 && j < 9) {
                    if (regiao[8][sudoku[i][j] - 1])
                        flag = false;
                    else
                        regiao[8][sudoku[i][j] - 1] = true;
                }
            }
        }
        if (flag)
            cout << "SIM\n\n";
        else
            cout << "NAO\n\n";
    }

    return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

Instancia 1
SIM
Instancia 2
NAO

#3 Code Example with Java Programming

Code - Java Programming


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(in.readLine());
        int instance = 0;
        while (++instance  < = t) {
            boolean flag = true;
            int n = 9;

            int[][] sudoku = new int[n][n];
            for (int i = 0; i  <  n; i++) {
                String[] p = in.readLine().split("\\s");
                int[] row = new int[n];
                for (int j = 0; j  <  n; j++) {
                    row[j] = Integer.parseInt(p[j]);
                }
                sudoku[i] = row;
            }

            // Filas
            for (int i = 0; i  <  n; i++) {
                int[] aux = new int[n];
                for (int j = 0; j  <  n; j++) {
                    if (aux[sudoku[i][j] - 1] == 0) {
                        aux[sudoku[i][j] - 1]++;
                    } else {
                        flag = false;
                        break;
                    }
                }
            }
            // Columnas

            for (int i = 0; i  <  n; i++) {
                int[] aux = new int[n];
                for (int j = 0; j  <  n; j++) {
                    if (aux[sudoku[j][i] - 1] == 0) {
                        aux[sudoku[j][i] - 1]++;
                    } else {
                        flag = false;
                        break;
                    }
                }
            }

            int root = 3;
            for (int i = 0; i  <  n; i += root) {
                for (int j = 0; j  <  n; j += root) {
                    int[] aux = new int[n];
                    for (int k = i; k  <  i + root; k++) {
                        for (int l = j; l  <  j + root; l++) {
                            if (aux[sudoku[k][l] - 1] == 0) {
                                aux[sudoku[k][l] - 1]++;
                            } else {
                                flag = false;
                                i = n;
                                j = n;
                                k = i + root;
                                l = j + root;
                            }
                        }
                    }
                }
            }
            out.println("Instancia " + instance);
            out.println(flag ? "SIM\n" : "NAO\n");
        }
        out.close();
    }
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

Instancia 1
SIM
Instancia 2
NAO

#4 Code Example with Javascript Programming

Code - Javascript Programming


class SudokuSolver {
	static get #DEFAULT_BOARD_SIZE() { return 9 }

	/** @param {number[][]} board */
	static isValidFullFilledSudokuBoard(board) {
		if (board.length !== SudokuSolver.#DEFAULT_BOARD_SIZE) return false

		const box = /** @type {Set}*/ (new Set())
		const column = /** @type {Set}*/ (new Set())

		for (let i = 0; i  <  SudokuSolver.#DEFAULT_BOARD_SIZE; i += 1) {
			if (board[i].length !== SudokuSolver.#DEFAULT_BOARD_SIZE) return false

			for (let j = 0; j  <  SudokuSolver.#DEFAULT_BOARD_SIZE; j += 1) {
				const value = board[i][j]
				if (value <= 0 || value > SudokuSolver.#DEFAULT_BOARD_SIZE) return false
				if (board[i].includes(value, j + 1)) return false

				column.add(board[j][i])

				if (i % 3 !== 0 || j % 3 !== 0) continue

				for (let r = i; r  <  i + 3; r += 1)
					for (let c = j; c  <  j + 3; c += 1)
						box.add(board[r][c])

				if (box.size !== SudokuSolver.#DEFAULT_BOARD_SIZE) return false
				else box.clear()
			}

			if (column.size !== SudokuSolver.#DEFAULT_BOARD_SIZE) return false
			else column.clear()
		}

		return true
	}
}

//// MAIN ////

const { format } = require("node:util")
const { readFileSync } = require("node:fs")
const [[numCases], ...input] = readFileSync("/dev/stdin", "utf8")
	.split("\n")
	.map((line) => line.split(" ", 9).map(value => Number.parseInt(value, 10)))


function main() {
	const output = new Array(3 * numCases)

	for (let index = 0; index  <  numCases; index += 1) {
		const board = input.splice(0, 9)

		output[3 * index + 0] = format("Instancia %d", index + 1)
		output[3 * index + 1] = SudokuSolver.isValidFullFilledSudokuBoard(board) ? "SIM" : "NAO"
		output[3 * index + 2] = ""
	}

	console.log(output.join("\n"))
}

main()

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

Instancia 1
SIM
Instancia 2
NAO

#5 Code Example with Python Programming

Code - Python Programming


def s45(m, x1, y1, x2, y2):
    s = 0
    for i in range(x1, x2 + 1):
        for j in range(y1, y2 + 1):
            s += m[i][j]
    return True if s == 45 else False

q = int(input())
for p in range(1, q + 1):
    m = []
    su = True
    for i in range(9):
        e = [int(x) for x in str(input()).split()]
        m.append(e)

    for i in range(9):
        for j in range(1, 10):
            if m[i].count(j) != 1:
                su = False

    if su:
        t = [[lin[i] for lin in m] for i in range(len(m[0]))]

        for i in range(9):
            for j in range(1, 10):
                if t[i].count(j) != 1:
                    su = False

    if su:
        if not (s45(m, 0, 0, 2, 2) and s45(m, 3, 3, 5, 5) and s45(m, 6, 6, 8, 8) and s45(m, 6, 0, 8, 2) and s45(m, 0, 6, 2, 8) and s45(m, 0, 3, 2, 5) and s45(m, 3, 0, 5, 2) and s45(m, 6, 3, 8, 5) and s45(m, 3, 6, 5, 8)):
            su = False

    print('Instancia', p)
    print('SIM' if su else 'NAO')
    print()

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

Instancia 1
SIM
Instancia 2
NAO

Demonstration

Previous
#1379 Beecrowd Online Judge Solution 1379 Mean Median Problem Solution in C, C++, Java, Js and Python

Next
#1387 Beecrowd Online Judge Solution 1387 Og Solution in C, C++, Java, Js and Python

Try With Live Editor

Category - Beecrowd Online Judge Maniruzzaman Akash 1 year ago 515 0