Inleiding
Sudoku, ook bekend als "Number Place" is een logisch spel waarvan het doel is relatief eenvoudig: de basis van het aantal reeds gegeven om op elk van haar cellen, een aantal dat nog niet in dezelfde in dezelfde kolom of rij, of in hetzelfde kwadrant of sector.
Sudoku modellen variëren, maar de meest verbreide, bestaat uit 9 rijen met 9 kolommen, 9 vierkanten, elk van haar 9 kwadranten en in elk van de rijen en kolommen moet worden geplaatst wijzerplaten nummers 1 tot 9. Een voorbeeld zou kunnen zijn:
Presentatie van de oplossing
De Backtracking programmering is een techniek die kan beginnen met de definitie van recursie (zie definitie van recursie) met het verschil dat in de backtracking, als er verschillende paden te kiezen, eenmaal bereikte de finale en niet voldeden aan de voorwaarde, ga terug en blijven alternatieve routes of andere en mogelijk onjuist te zoeken.
Het idee van terugkrabbelen als je nog niet begrepen, het ziet er vrij goed in deze voorbeelden van de bisschop en de pion, de pistes van de koning en de n-Concepten.
Upload ik mijn eigen programma dat sudoku puzzels die uitgaat van de techniek van het backtracking oplost. Vergeet niet dat de beste techniek is veel minder om puzzels op te lossen, maar in de praktijk gebruiken grof geweld om conflicten met de mogelijkheid om terug te gaan en zoekt meer wegen op te lossen.
Resolution Process
De raad van Sudoku op te lossen wordt gegeven door een ouder "Sol [1 .. 9,1 .. 9] van 0 .. 9", waar Sun [i, j] vertegenwoordigt de waarde die de cel, wat overeenkomt met 0 met neemt een leeg plein. Het maakt gebruik van een matrix assistent "initiële [1 .. 9 1 .. 9] van Bool", waar de eerste [i, j] vertegenwoordigt een cel met een oorspronkelijke waarde kan niet worden gewijzigd en komt overeen met de cel "Sol [i, j] ".
Wanneer de vertakkende boom van de exploratie, dan doen wij alleen als de gedeeltelijke oplossing is dat we behandelen k-veelbelovend, dat wil zeggen, indien na deze gedeeltelijke oplossing kan blijven gedeeltelijke oplossingen te bouwen. Om dit punt te pakken, maken we gebruik van een helper functie genaamd "es_factible.
De navigatiestructuur gegenereerd zal de volgende kenmerken:
- Hoogte = m + 1: Als m het aantal lege dozen in eerste instantie.
- Aantal kinderen van elke node = 9: Een kind voor elke mogelijke waarde van cel ij
Downloaden
Het programma dat ik heb gedaan tekst bevat alle bestanden die in de debug map van het project en het proces genereert een oplossing bestand voor elke sudoku en een algemene samenvatting bestand met de tijd die aan elk van hen op te lossen. Ik laat de broncode en een rapport in pdf.
hallo, ik heb een oefening met een terugkrabbelen en ik heb niet kunnen doen, als ik je kan helpen in de ziel agradeceria. Het probleem is ik heb een reeks cijfers en dit heb ik te verdelen in delen n +1, n geeft de gebruiker. en de som van de n delen moet gelijk zijn aan de n +1. bijvoorbeeld n = 5 str = 1002010002503001670
het resultaat zou worden 100 20 1000 250 300 1670. en het maximum van elk deel is 1000, maar het laatste dat zou 7000. bedankt