Sudoku

Hallo,

Ik ben bezig met een script dat automatisch Sudokus op moet lossen.
Nu is mij dit gelukt met dummy puzzels van makkelijk tot moeilijk.
Echter loop ik vast bij extra moeilijk (de moeilijkste die er zijn), deze krijg ik niet opgelost met mijn script en hier kom ik zelf niet uit.
Hiervoor vraag ik jullie hulp!

Mijn script heeft een erg moeilijke sudoku tot het volgende weten te brengen:

Alles wat daarin staat klopt en de Sudoku is oplosbaar.
Echter kan ik geen manier meer bedenken om dit verder op te lossen.
De vraag is nu dus, zouden de mensen met een beetje verstand van Sudoku willen proberen hier her en der nog een getal in te vullen.
Al kan je maar 1 getal ergens invullen, laat het weten en vermeld er vooral bij welke manier je hebt gebruikt om erachter te komen dat dat getal daar moet

Bij voorbaat dank!

Kun je misschien ook even het origineel plaatsen waarin nog niks is ingevuld?

Nice idee om te gaan oplossen Kun je ook voorbeelden van het script geven ofzo? De manier van oplossen lijkt me mooi om te weten

Idk of dit mogelijk is he ;
eerst kijken welke cijfers ontbreken in het 1e vierkant, dan checken of de overgebleven cijfers horizontaal/verticaal staan, als ze er neit staan, plaats je ze daar... Maarja, het kunnen altijd merdere mogenlijkheden zijn he, dus zou je die manier de hele tijd moeten herhalen totdat alles zeker is?
Btw, ik denk niet dat deze manier zal lukken

Leax schreef:

Idk of dit mogelijk is he ;
eerst kijken welke cijfers ontbreken in het 1e vierkant, dan checken of de overgebleven cijfers horizontaal/verticaal staan, als ze er neit staan, plaats je ze daar... Maarja, het kunnen altijd merdere mogenlijkheden zijn he, dus zou je die manier de hele tijd moeten herhalen totdat alles zeker is?
Btw, ik denk niet dat deze manier zal lukken

Kost veel vermogen, maar dat is volgensmij de enige mogelijkheid.

Dat is echt, veel werk..

Jenner schreef:

Eerdere citaten tonen

Leax schreef:

Idk of dit mogelijk is he ;

eerst kijken welke cijfers ontbreken in het 1e vierkant, dan checken of de overgebleven cijfers horizontaal/verticaal staan, als ze er neit staan, plaats je ze daar... Maarja, het kunnen altijd merdere mogenlijkheden zijn he, dus zou je die manier de hele tijd moeten herhalen totdat alles zeker is?
Btw, ik denk niet dat deze manier zal lukken
Kost veel vermogen, maar dat is volgensmij de enige mogelijkheid.

Het viel me nog mee, maar het is te doen op deze manier. Mijn oplosser werkt opzich ook wel. Heb je nog wat voorbeelden die ik erin kan proppen?

toevoeging op 28 december 2012, 2325:
Ik ben ook met een oplosser bezig, maar ik kom bijvoorbeeld ook niet uit deze: http://sudokus.robinu.nl/sudoku.php?id=32517

toevoeging op 28 december 2012, 23:34:08:
Ik heb een mogelijke oplossing, maar wordt hij daar wel een stuk complexer en intensiever van. Door op een gegeven moment hem op te delen om verschillende mogelijkheden te bekijken als er nog 2 mogelijkheden bij een vakje over zijn.

toevoeging op 29 december 2012, 01:31:40:
Oplossing gevonden: http://cl.ly/LqUs
Hierbij gaat hij niet uit van de diagonalen. (Even testen of ie het met diagonalen ook doet)

toevoeging op 29 december 2012, 01:39:14:
De andere optie met diagonalen is:
http://cl.ly/LqbD

toevoeging op 29 december 2012, 01:54:58:
En deze na een poosje ook (Kostte even wat rekenwerk, maar hij is er)
http://clevergames.files.wordpress.com/2009/05/extreme_sudoku.png?w=480&h=480
Tada: http://cl.ly/LqoE

Jenner schreef:

Nice idee om te gaan oplossen Kun je ook voorbeelden van het script geven ofzo? De manier van oplossen lijkt me mooi om te weten

Ik had eerst geprobeerd om de regels zoals ik ze gebruik te implementeren, maar dat bleek zwaar moeilijk. Dus zeg maar dat je gaat controleren of een getal binnen een hok van 3 rijen al op 2 verschillende rijen zat.
Dit was allemaal erg omslachtig en moest naar mijn idee makkelijker kunnen.
Uiteindelijk heb ik me puur gefocust op het bijhouden van de mogelijkheden van een bepaald hokje.
Als je de mogelijkheden van een hokje weet kan je die mogelijkheden met andere mogelijkheden gaan vergelijken en zodoende ontzettend ver komen.
Beetje bij beetje verschijnen er bij mijn sudoku steeds meer getallen, dus zal er uiteindelijk wel komen.

Moet trouwens zeggen dat ik, tot nu toe, totaal geen last heb van dat het te zwaar is oid.
Als ik refresh krijg ik zo goed als direct de pagina te zien, geen enkele ladingstijd

Zal zo meteen nog wel wat code plaatsen

toevoeging op 30 december 2012, 18:02:25:

[COLOR= #0000BB]<?php[/COLOR]
    [URL="http://www.php.net/private"]private[/URL] [COLOR= #007700]function[/COLOR] twinRow[COLOR= #007700](){[/COLOR]
        [URL="http://www.php.net/for"]for[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$i[/COLOR] [COLOR= #007700]=[/COLOR] [COLOR= #0000BB]1[/COLOR][COLOR= #007700];[/COLOR] [COLOR= #0000BB]$i[/COLOR] [COLOR= #007700]<=[/COLOR] [COLOR= #0000BB]9[/COLOR][COLOR= #007700];[/COLOR] [COLOR= #0000BB]$i[/COLOR][COLOR= #007700]++){[/COLOR]
            [COLOR= #0000BB]$array[/COLOR] [COLOR= #007700]=[/COLOR] [URL="http://www.php.net/array"]array[/URL][COLOR= #007700]();[/COLOR]
            [COLOR= #0000BB]$row[/COLOR] [COLOR= #007700]=[/COLOR] [COLOR= #0000BB]$this[/COLOR][COLOR= #007700]->[/COLOR]getRow[COLOR= #007700]([/COLOR][COLOR= #0000BB]$i[/COLOR][COLOR= #007700]);[/COLOR]
            [URL="http://www.php.net/foreach"]foreach[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$row[/COLOR] [COLOR= #007700]as[/COLOR] [COLOR= #0000BB]$col[/COLOR] [COLOR= #007700]=>[/COLOR] [COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700]){[/COLOR]
                [URL="http://www.php.net/if"]if[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$waarde[/COLOR] [COLOR= #007700]===[/COLOR] false[COLOR= #007700]){[/COLOR]
                    [COLOR= #0000BB]$poss[/COLOR] [COLOR= #007700]=[/COLOR] [URL="http://www.php.net/explode"]explode[/URL][COLOR= #007700]([/COLOR][COLOR= #DD0000]","[/COLOR][COLOR= #007700],[/COLOR] [COLOR= #0000BB]$this[/COLOR][COLOR= #007700]->[/COLOR]possible[COLOR= #007700][[/COLOR][COLOR= #0000BB]$i[/COLOR][COLOR= #007700]][[/COLOR][COLOR= #0000BB]$col[/COLOR][COLOR= #007700]]);[/COLOR]
                    [URL="http://www.php.net/foreach"]foreach[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$poss[/COLOR] [COLOR= #007700]as[/COLOR] [COLOR= #0000BB]$value[/COLOR][COLOR= #007700]){[/COLOR]
                        [COLOR= #0000BB]$array[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]$value[/COLOR][COLOR= #007700]][] =[/COLOR] [COLOR= #0000BB]$col[/COLOR][COLOR= #007700];
                    }
                }
            }[/COLOR]
            [COLOR= #0000BB]$check[/COLOR] [COLOR= #007700]=[/COLOR] [URL="http://www.php.net/array"]array[/URL][COLOR= #007700]();[/COLOR]
            [URL="http://www.php.net/foreach"]foreach[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$array[/COLOR] [COLOR= #007700]as[/COLOR] [COLOR= #0000BB]$integer[/COLOR] [COLOR= #007700]=>[/COLOR] [COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700]){[/COLOR]
                [URL="http://www.php.net/if"]if[/URL][COLOR= #007700]([/COLOR][URL="http://www.php.net/count"]count[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700]) ==[/COLOR] [COLOR= #0000BB]2[/COLOR][COLOR= #007700]){[/COLOR]
                    [URL="http://www.php.net/foreach"]foreach[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$check[/COLOR] [COLOR= #007700]as[/COLOR] [COLOR= #0000BB]$getal[/COLOR] [COLOR= #007700]=>[/COLOR] [COLOR= #0000BB]$true[/COLOR][COLOR= #007700]){[/COLOR]
                        [URL="http://www.php.net/if"]if[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$integer[/COLOR] [COLOR= #007700]!=[/COLOR] [COLOR= #0000BB]$getal[/COLOR] [COLOR= #007700]&&[/COLOR] [URL="http://www.php.net/in_array"]in_array[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]0[/COLOR][COLOR= #007700]],[/COLOR] [COLOR= #0000BB]$array[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]$getal[/COLOR][COLOR= #007700]]) &&[/COLOR] [URL="http://www.php.net/in_array"]in_array[/URL][COLOR= #007700]([/COLOR][COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]1[/COLOR][COLOR= #007700]],[/COLOR] [COLOR= #0000BB]$array[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]$getal[/COLOR][COLOR= #007700]])){[/COLOR]
                            [COLOR= #0000BB]$Poss[/COLOR] [COLOR= #007700]= ([/COLOR][COLOR= #0000BB]$integer[/COLOR] [COLOR= #007700]<[/COLOR] [COLOR= #0000BB]$getal[/COLOR] [COLOR= #007700]?[/COLOR] [COLOR= #0000BB]$integer[/COLOR][COLOR= #007700].[/COLOR][COLOR= #DD0000]","[/COLOR][COLOR= #007700].[/COLOR][COLOR= #0000BB]$getal[/COLOR] [COLOR= #007700]:[/COLOR] [COLOR= #0000BB]$getal[/COLOR][COLOR= #007700].[/COLOR][COLOR= #DD0000]","[/COLOR][COLOR= #007700].[/COLOR][COLOR= #0000BB]$integer[/COLOR][COLOR= #007700]);[/COLOR]
                            [COLOR= #0000BB]$this[/COLOR][COLOR= #007700]->[/COLOR]possible[COLOR= #007700][[/COLOR][COLOR= #0000BB]$i[/COLOR][COLOR= #007700]][[/COLOR][COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]0[/COLOR][COLOR= #007700]]] =[/COLOR] [COLOR= #0000BB]$Poss[/COLOR][COLOR= #007700];[/COLOR]
                            [COLOR= #0000BB]$this[/COLOR][COLOR= #007700]->[/COLOR]possible[COLOR= #007700][[/COLOR][COLOR= #0000BB]$i[/COLOR][COLOR= #007700]][[/COLOR][COLOR= #0000BB]$waarde[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]1[/COLOR][COLOR= #007700]]] =[/COLOR] [COLOR= #0000BB]$Poss[/COLOR][COLOR= #007700];
                        }
                    }[/COLOR]
                    [COLOR= #0000BB]$check[/COLOR][COLOR= #007700][[/COLOR][COLOR= #0000BB]$integer[/COLOR][COLOR= #007700]] =[/COLOR] true[COLOR= #007700];
                }
            }
        }
    }[/COLOR]
?>

Deze functie controleert op de twin regel binnen een rij, dus als er binnen een rij 2 getallen zijn die allebei alleen op 2 dezelfde hokjes kunnen. Dan worden alle andere mogelijkheden voor die 2 hokjes verwijderd omdat die een van die 2 waardes moet zijn

Lukt het ook goed met deze: http://clevergames.files.wordpress.com/2009/05/extreme_sudoku.png?w=480&h=480 ? Helemaal oplossen dan, want ik werk met het idee dat ik het vakje pak met de minste mogelijkheden. (Vaak 2 of 3) Splits dan je bord op in 2/3 borden en vul daarbij de mogelijkheden nog in. Ga daarmee verder en als je klaar bent met oplossen check je of hij nog correct is. Zo niet dan moet ie weg. Zo ja dan is dat je oplossing. Soms moet je deze manier meerdere keren toepassen om tot de uiteindelijke oplossing te komen.

Momenteel werkt hij uberhaupt nog niet op de moeilijkste bordenBen nog steeds bezig met meer mogelijkheden regelwijs op te lossen dus denk dan niet dat hij uit die gaat komen

2-2 : 5 of 7

Wanneer er op 2-2 een 5 gezet word
Moet op 2-9 een 7
Daardoor moet op 4-8 een 7 (want rij 7 en 9 zijn bezet door 7)
Hierdoor kan op 4-2 geen 7 meer en is de puzzel onoplosbaar

2-2 moet dus een 7 zijn, hierdoor moet 4-2 een 5 zijn en moet 2-9 een 5 zijn.

Dan moet dus ook 8-7 een 5 zijn (enz)

Good luck implementing that. Sudoku oplossen blijtf nog altijd het leukste door je verstand te gebruiken

Ja zulk soort dingen zie ik dus echt nietNetjes gedaan, zal es kijken of ik op deze manier verder kan!

Uiteraard is het leuker om een sudoku met je verstand op te lossen, maar het is zeker ook een uitdaging om een programma te maken dat het kan en dat is eigenlijk vooral de rede dat ik het doe

Mjah, er zijn volgens mij wel algoritmes beschikbaar die kunnen berekenen welk nummer waar moet op basis van de positie van andere nummers zegmaar. Sudokus maken zichzelf namelijk niet, daar bestaan ook programmas voor
Maar op die manier van mij moet je tussendoor dus superveel berekeningen gaan maken om verschillende scenarios te toetsen.

Rik schreef:

Mjah, er zijn volgens mij wel algoritmes beschikbaar die kunnen berekenen welk nummer waar moet op basis van de positie van andere nummers zegmaar. Sudokus maken zichzelf namelijk niet, daar bestaan ook programmas voor
Maar op die manier van mij moet je tussendoor dus superveel berekeningen gaan maken om verschillende scenarios te toetsen.

Lijkt een beetje op bruteforcing.

Alemaalte schreef:

Eerdere citaten tonen

Rik schreef:

Mjah, er zijn volgens mij wel algoritmes beschikbaar die kunnen berekenen welk nummer waar moet op basis van de positie van andere nummers zegmaar. Sudokus maken zichzelf namelijk niet, daar bestaan ook programmas voor

Maar op die manier van mij moet je tussendoor dus superveel berekeningen gaan maken om verschillende scenarios te toetsen.

Lijkt een beetje op bruteforcing.

Dat van mij komt in de buurt van Bruteforcing. Rik heeft iets meer systeem erin om onnodige berekeningen te voorkomen.