Własny brute force do sudoku - błąd logiczny

Trzy funkcje odpowiedzialne za rozwiązanie gotowego arkusza:

bool sudokuBoard::check(int column,int row,int checkedValue)
{
	int miniBoxFirstColumn;//0v3v6
	int miniBoxFirstRow;//0v3v6
	
	slotType miniBox[3][3];

	//column check

	for(int i=0; i< 9; i++) 
	{		
		if(i==row)continue;
					
		if(checkedValue==slot[column][i].value) return false;
	}	

	//row check

	for(int i=0; i<9; i++) 
	{	
		if(i==column)
		continue;
		if(checkedValue==slot[i][row].value) return false;
	}

	//3x3 box

	miniBoxFirstColumn=(column/3)*3;
	miniBoxFirstRow=(row/3)*3;

	for(int m=0;m<3;m++)
		for(int n=0;n<3;n++)
		{
			if(n==column && m==row) continue; 

			if(checkedValue == slot[miniBoxFirstColumn+n][miniBoxFirstRow+m].value) return false;			

		}
						
		return true;
}	

void sudokuBoard::resolve()
{
	while(!isFull())
	{
	for(int i=0; i<9; i++)
		for(int j=0; j<9; j++)
		{
	 			if(slot[j][i].value == 0)
				for(int k=1; k<=9; k++) 
				{
						if(check(j,i,k)) //Always false(WHY?);
						{
							slot[j][i].value=k; //breakpoint
							slot[j][i].fixed=false;
						}
				}				
		}
	}	
}

bool sudokuBoard::isFull()
{
	for(int i=0; i<9 ; i++)
		for(int j=0; j<9; j++)
			if(!slot[j][i].value) return false;
	return true;
}

Plik nagłówkowy
"sudoku.h"

namespace sudoku
{
struct slotType
{	
	int value;
	bool fixed;
};
class sudokuBoard
{
public:	
	sudokuBoard operator=(sudokuBoard ); 


	sudokuBoard();
	void switchSlotValue(int , int , int);
	//column, row, value

	void print() const;

	void createCustom();

	void load();

	bool check(int column,int row,int value); 

	void resolve();

	bool isFull();

private:
	 slotType slot[9][9]; 
};
}

Funkcja główna:

#include <iostream>
#include "sudokuBoard.h"

using namespace std;
using namespace sudoku;

int MainMenu();


int main(void)
{
	
	sudokuBoard currentBoard;

	switch(MainMenu())
	{	
		case 1:
			currentBoard.load();
			break;
		case 2:
			currentBoard.createCustom();
			break;
	}

	currentBoard.print();

	cout<<"\nResolving...\n";

	currentBoard.resolve();

	currentBoard.print();

	cout<<endl;
	system("PAUSE");
	return 0;
}

int MainMenu()
{
	int choice;
	
	cout<<"Sudoku Wizard (Console version)\n"
		<<"1.Load board\n"
		<<"2.Create a new board\n";
	
	cin>>choice;

	return choice;
}

Plansza

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

Do rzeczy - ustawiłem breakpointa w najbardziej wewnętrznej pętli funkcji resolve. Dlaczego, dla tego przykładu, osiągany jest on tylko 55 razy, po czym pętla rozwiązuje się w nieskończoność?. Najprawdopodobniej coś jest nie tak z funkcją check...

#include <iostream>
#include <vector>
#include <algorithm>

#define N 9

using namespace std;

void wczytaj(int tab[N][N])
{
    for(unsigned i=0;i<N;i++)
    {
        for(unsigned j=0;j<N;j++)
        {
            cin >> tab[i][j];
        }
    }
}

bool sprawdz_poziomo(int tab[N][N])
{
    vector<int>sortuj(N);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            sortuj[j]=tab[i][j];
        }
        sort(sortuj.begin(),sortuj.end());
        for(int k=0;k<N;k++)
        {
            if(sortuj[k]!=k+1)return false;
        }
    }
    return true;
}

bool sprawdz_pionoo(int tab[N][N])
{
    vector<int>sortuj(N);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            sortuj[j]=tab[j][i];
        }
        sort(sortuj.begin(),sortuj.end());
        for(int k=0;k<N;k++)
        {
            if(sortuj[k]!=k+1)return false;
        }
    }
    return true;
}

bool sprawdz_kwadrat(int tab[N])
{
    vector<int>sortuj(N);
    for(int i=0;i<N;i++)
    {
        sortuj[i]=tab[i];
    }
    sort(sortuj.begin(),sortuj.end());
    for(int i=0;i<N;i++)
    {
        if(sortuj[i]!=i+1)return false;
    }
    return true;
}

bool sprawdz(int tab[N][N],int kwadrat)
{
    int count=0,check[N],k=0;
    for(unsigned i=(kwadrat/3)*3;i<N;i++)
    {
        if(k==9)break;
        for(unsigned j=(kwadrat%3)*3;j<N+1;j++)
        {
            if(count==3)
            {
                count=0;
                break;
            }
            check[k]=tab[i][j];
            k++;
            count++;
        }
    }
    if(!sprawdz_kwadrat(check))return false;
    if(!sprawdz_poziomo(tab))return false;
    if(!sprawdz_pionoo(tab))return false;
    return true;
}


int main()
{
    int testy,sudoku[N][N];
    bool tab[N],jest=true;
    cin >> testy;
    while(testy--)
    {
        jest=true;
        wczytaj(sudoku);
        for(int i=0;i<N;i++)
        {
            tab[i]=sprawdz(sudoku,i);
            if(tab[i]==false)
            {
                jest=false;
                break;
            }
        }
        if(!jest)cout << "NIE\n";
        else cout << "TAK\n";
    }
    cout << endl;
    return 0;
}

To jest prawidlowe sprawdzanie sudoku. Poziom/pion/kwadrat. Pisane dosyc dawno na spoja.

Dobrze, widziałem już dużo gotowców w internecie . W tym temacie chodzi mi o znalezienie błędu w moim algorytmie , w którym też sprawdzam "pion-poziom-kwadracik", a jednak gdzieś jest drobny szkopuł. Na procesorze 3,3 ghz chodzi już od 2 godzin i wciąż tylko 55 razy funkcja chceck dała wartość true :(

Strasznie zagmatwany algorytm masz. Nie wiem czy komus bedzie sie chcialo ten tok myslenia analizowac. Po co az 3 petle oO. Nieoptymalne i troche na okretke zrobione rozwiazanie. Pomysl na czyms prostszym.

Nie wiem czy takie przekombinowane , taki algorytm wydaje mi się najprostszym. W funkcji resolve idąc od zewnątrz pętle oznaczają: wiersze, kolumny, przykładowe wartości.

Czyli po kolei , od lewej do prawej, w każdej luce testujemy po 9 cyfr. Jeśli nie pasuje żadna, idziemy do następnej. Jeśli pasuje, wpisujemy ją, oznaczamy jako niewpisaną domyślnie (fixed=false) i idziemy do następnej. Kończymy jak nie będzie żadnego zera. Zrobienie tego rekurencyjnie byłoby chyba trudniejsze i wolniejsze.

To mow ze tobie chodzi o losowanie poprawnej planszy sudoku. To najlepiej po prostu przy losowaniu kazdej cyfry robic 3 sprawdzenia. Czy wczesniej wpisane liczby w pionie/poziomie/kwadracie sa rozne od wylosowanej. Robisz do tego 3 metody i tyle. na pewno te 3 fory sa przekombinowane.

Nie, nie chodzi o losowanie planszy! Program ma rozwiązać przykładowy, gotowy arkusz który podałem w 1 poście.

Lepszym sposobem wydaje sie przeleciec raz plansze i oznaczyc mozliwe do wpisania w danym polu liczby. Jak juz bedziemy mieli takie cos to wpisujemy wszystkie te ktore maja tylko 1 opcje i znowu sprawdzamy mozliwosci. Przy 2 mozliwych trzeba losowo wybierac itd.