sudoku checker in c

[GioCSD]

Καλησπερα,

Εχω να κανω ελεγχο για ενα sudoku και εχω κολλησει στο εξης σημειο..

Αν εισαγω τους 81 αριθμους σωστα τοτε ολα ειναι οκ.Στην περιπτωση που εισαγω καποιο αριθμο 

σε 1 γραμμη 2 φορες να ηθελα να μου πεταει μηνυμα οτι δεν ειναι εγκυρο..Π.χ

 

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

 

 

θα πρέπει να τυπώσει:

 

 

Invalid row 1 Invalid column 1 Invalid column 2 Invalid block 1

 

Σας ευχαριστω εκ των πρωτερων

[Kercyn]

Πρέπει πρώτα να χωρίσεις αυτή τη μία γραμμή που έχεις σε γραμμές και στήλες 3x3. Στη συνέχεια μπορείς να δεις αν ένα μπλοκ είναι σωστά ορισμένο.

[M2000]

Είναι εύκολο και λογικά πρέπει το λάθος να δίνεται μόλις βρεθεί, χωρίς να συνεχίσουμε τη σάρωση.

Πρώτα μηδενίζουμε ένα πίνακα 9 θέσεων. Ο αλγόριθμος πρέπει να δουλεύει και αν ακόμα δεν υπάρχουν 81 νούμερα αλλά δύο π.χ. 9 9 . Κάθε φορά που διαβάζουμε 9 καλά νούμερα αυξάνουμε τον μετρητή νεαγραμμή κάθε νούμερο Χ αυξάνει το στοιχείο πίνακα Α(Χ). Ελέγχουμε αν το νούμερο είναι μεγαλύτερο με το μετρητή γραμμής. Αν ναι τότε έχουμε διπλό νούμερο. Ένα άλλος μετρητής μας μετράει τα νούμερα στην είσοδο. Πχ στο 9 9 έχουμε στο Α(9)=2 ενώ γραμμή=1 και νούμερα=2..Το Α(9)>γραμμή σημαίνει λάθος,το 2 mod 9 +1 μας δίνει το 2 την στήλη, την γραμμή την έχουμε. Η αλλαγή γραμμής, δηλαδή η αύξηση του μετρητή γίνεται με το μετρητή νούμερα. Γραμμή=νούμερα mod 9+1. Το +1 μας αλλάζει τη βάση σε 1. Ο πίνακας ας έχει 10 στοιχεία και το 0 δεν το χρησιμοποιούμε, δηλαδή σαν να έχουμε βάση 1.

Το μπλοκ βγαίνει ((γραμμή-1) div 3)*3+(((νούμερα-1) mod 9) div 3)*3+1

Αν βρούμε λάθος στο 15 νούμερο, τότε η γραμμή θα είναι η 2η, στήλη η 6η και μπλοκ 14 mod 9 δίνει 5, 5 div 3...δίνει 1 συν 1..2, άρα 2ο μπλοκ.

Είσαι έτοιμος

Λύνεις το πρόβλημα με τη σκέψη..πόσους μετρητές χρειάζομαι...

[M2000]

Σε περίπτωση που κάποιος θα ήθελε να ελέγχει αν ένας πίνακας έχει διπλοεγγραφές πριν τον συμπληρώσει...δεν χρησιμοποιεί την παραπάνω μέθοδο αλλά δυο πίνακες 9Χ9 και δύο 9 στοιχείων και τους γεμίζει με αρχικές τιμές. Κάθε φορά που βάζουμε ένα νούμερο αφαιρούμε από τους πίνακες το αντίστοιχο (το νούμερο το κάνουμε θέση, και στους δυο διαστάσεων η μία θέση είναι η γραμμή ή η στήλη ανάλογα). Οι πρόσθετοι πίνακες παίζουν ρόλο σημαίας. 

Οι πίνακες με βάση το 1 ή τους έχουμε με βάση το 0 και τους κάνουμε 10Χ10 και προσπέλαση από το 1,1

Για το Α(Χ,Υ) του ορατού πίνακα θα μπει τιμή 5 αν το Β(5,Υ)=-1 και το Γ(Χ,5)=-1 και αν Χ=Υ τότε ελέγχει  το Δ1(5)=-1 και το Δ2(5)=-1, όπου -1 σημαίνει αληθές (το έβαλα έτσι, το κάνει ο καθένας όπως θέλει)

Σημαντικό είναι ότι αν περάσει το τεστ πρέπει να γυρίσουμε τις σημαίες από -1 σε 0..ακριβώς στα ίδια σημεία.

Έτσι κάθε φορά θα έχουμε έλεγχο αν υπάρχει διαθέσιμο χωρίς να ελέγχουμε που είναι ακριβώς.

Εννοείται πως αν έχουμε έτοιμο το πίνακα Α() και θέλουμε να κάνουμε έλεγχο σαν να βάζαμε κάθε τιμή, θα μηδενίζαμε τους πίνακες Β(), Γ(), Δ1(), Δ2() και μετά θα προχωράγαμε από 1,1 σαν να πληκτρολογούσαμε...και κάποια στιγμή θα βγει λάθος, ίσως στο ενδιάμεσο ή θα τερματίσει στο 9,9 και θα είναι εντάξει.

 

Με την χρήση σημαιών αποφεύγουμε τις περιττές επαναλήψεις!

[παπι]

Γιατι το απλο να το κανουμε πολυπλοκο;

#include <stdio.h>

#define SUDOKU_OK			0
#define SUDOKU_OUT_OF_RANGE	1
#define SUDOKU_EXIST		2

//φτιαχνεις εναν πινκα sudoku που ειναι 9 επι 9. 
int sudoku_board[9][9] = { 0 };
//
int sudoku_board_add(int x, int y, int value);
void sudoku_board_print();

int main(int argc, char **argv)
{
	int x, y, value;
	for (;
	{
		sudoku_board_print();
		printf("insert x y valeu and press enter or 0 0 0 for exit...\n");
		fflush(stdin);//user friendly 
		scanf("%d %d %d", &x, &y, &value);
		if (!x)
			return 0;
		switch (sudoku_board_add(x - 1,y - 1,value))// 1..9 user friendly 
		{
		case SUDOKU_OK:
			break;
		case SUDOKU_OUT_OF_RANGE:
			printf("out of range input\n");
			break;
		case SUDOKU_EXIST:
			printf("puzzle error\n");
			break;
		default:
			break;
		}


	}
	return 0;
}

int sudoku_board_add(int x, int y, int value)
{
	int i, j;
	//ο ιουσερ ειναι βλαξ
	if (x < 0 || x >= 9 || y < 0 || x >= 9)
		return SUDOKU_OUT_OF_RANGE;
	//υπαρχει ο αριθμος στη στηλη ή στη γραμμη που θελει να βαλει ο ιουσερ;
	for (i = 0; i < 9; i++)
	{
		if (sudoku_board[y][i] == value || sudoku_board[i][x] == value)
			//υπαρχει, αρα δεν μπορουμε να το βαλουμε
			return SUDOKU_EXIST;
	}
	//υπαρχει ο αριθμος στο τετραγωνο που θελει να εισαγει ο ιουσερ;
	for (i = y / 3; i < y / 3 + 3; i++)
	{
		for (j = x / 3; j < x / 3 + 3; j++)
		{
			if (sudoku_board[i][j] == value)
				//υπαρχει, αρα δεν μπορουμε να το βαλουμε
				return SUDOKU_EXIST;
		}
	}
	//για να φτασαμε εδω, ουτε σε στηλη υπαρχει, ουτε σε γραμμη και ουτε στο τετραγωνο
	sudoku_board[y][x] = value;
	return SUDOKU_OK;
}

void sudoku_board_print()
{
	int i, j;
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			printf("%d  ",sudoku_board[j][i]);
		}
		printf("\n");
	}
}

[M2000]

Υπάρχουν πολλές απαντήσεις..

π.χ. Μπράβο έκανες 5..στα 10.

Μια άλλη:

Στον αλγόριθμο: Είναι σίγουρα φουσκωμένος και έχεις ξεχάσει τις δυο διαγώνιες, αλλά αυτό είναι το λιγότερο. Επιπλέον κάνεις έλεγχο σε κάθε εισαγωγή, πράγμα που είναι εκτός άσκησης. Ίσως σε μπέρδεψε το προηγούμενο μήνυμά μου με τους πίνακες με τις σημαίες..έγραφα "Σε περίπτωση που κάποιος θα ήθελε να ελέγχει αν ένας πίνακας έχει διπλοεγγραφές πριν τον συμπληρώσει".    Ασφαλώς και ο χρόνος αναμονής, για να βάλει νούμερο ο παίκτης, είναι τέτοιος που ό,τι αλγόριθμο βάλεις αν δουλεύει είναι οκ. Με την δική μου σκέψη ο πίνακας με τις σημαίες έχει και άλλες χρήσεις..που απλά εδώ δεν χρειάζονται. Αλλά ασφαλώς όπως έγραψα ο αλγόριθμος αν πάρει και το κομμάτι που λείπει, για κάθε διαγώνιο, είναι οκ, αλλά όχι για το αρχικό αίτημα. Δηλαδή στην ανάγνωση και επεξεργασία στοιχείων και για το εμφανιζόμενο μήνυμα!

Λογικά τώρα αν το καλοσκεφτείς, αν ο πίνακας 81 θέσεων εμφανιστεί για επεξεργασία με το σκεπτικό σου πρέπει να κάνεις για κάθε αριθμό 9+9+9=27 συγκρίσεις, ή 27Χ81 καθώς και για 18 νούμερα να δεις διαγώνιο 18*18, ή 2511 συγκρίσεις.

Εγώ παίρνω εννιάδες, αυξάνω εννιά μετρητές και κάνω έναν έλεγχο στα 9 αποτελέσματα. αυτό το κάνω το πολύ 9 φορές. Άρα στη χειρότερη έχω 81 προσθέσεις και 81 συγκρίσεις....υπάρχει μεγάλη διαφορά!