Forumet - suduku AI, lite funderingar och så.

suduku AI, lite funderingar och så.

82 0 7
Lite tankar kring hur man ska programera AI för en suduku lösare. Tanken är väl lite att de ska kodas i Java men... tror de termer jag använder mig av fungerar för de flesta objektorienterade programmeringspråk.

Göra en tredimensionell array x=9 y=9 z=9 boolean. Om det är sant på x=0 y=4 z= 5 betyder de att 0, 4 har värdet 5 eller att så kan vara möjligt. Om de däremot är falskt där betyder det att de inte är 5 i ruta 0, 4.

Gör en metod vid namn validateSquare() som räknar sant-värden på en xy ruta genom loop mot z,. Om den finner två sanna avbryter den processen och skickar iväg invalid. Om den däremot går igenom hela z och bara hittar en sann så betyder det att värtet på rutan sett från xy är funnet skickar valid och kör purifySquare() köras genom att man skickar iväg de värdet trueX=0 trueY=4 trueValue=5 tex. Och tar in posX och posY.

Gör en metod vid namn countSquare() som räknar falska på Z axel skickar ut zValue och tar in posX and posY.

Gör en metod vid namn dictateSquare() där de skickas med vad för siffra den är ruleNumber heter de värdet. Som sedan gör om sant och falskt för z raden. Och startar purify()

Göra metod vid namn purify() för xy ruta där det skrivs falskt på de lagret i z:nivå för 3x3 rutan, vertikalt och horisontellt. Tar in posX och posY and trueTarget. Ska använda sig av en vektor för att minnas alla kordinater. Som töms när den rensningen är färdig.

Gör en metod som listar upp koordinaterna för 3x3 rutan som skickade rutan ingår i.

Gör en metod som listar upp koordinaterna för vertikala linjen som skickade rutan ingår i.

Gör en metod som listar upp koordinaterna för horisontella linjen som skickade rutan ingår i.

Vad som behövs!! System som på ett så effektivt och i den mån möjligt smart sätt väljer ut vilka rutor den ska fokusera sig på. Några förslag? Något jag missat? Hur tycker ni mitt tillvägagångsätt är för att tackla problemet? Varit på birdie en dag nu och inte fått någon sömn men :PPP

OBS!! Jag har gått ut skolan och detta skrivs enbart för nöjes skull. Om de nu råkar vara så att du inte känner för att dela med dina av din kunskap så är de helt okej.

Dold text: Om ni har läst ner hit har ni varit väldigt duktiga [cute][cute]
Mr Brightside:

dela med dina av din kunskap


hade en lab på sudoku i min ai-kurs, vi skulle lösa det i prolog. skitenkelt i ett deklarativt språk, man typ körde permutationer av alla tal 1-9 i 9 listor och sen kollade man att det stämde. extrem brute-force, men jag antar att det är vad du letar efter också?

hänger inte riktigt med på vad dina metoder gör, men det kanske inte spelar någon roll. gillar 9x9x9-arrayen, även om det kan bli krångligt att koda. har du övervägt att dessutom ha en 9x9-array för rätta svaret? fast det kanske inte ger någon fördel. tänkte du att din spelare ska lösa på ett liknande sätt som människor? typ, gå igenom efter ettor först, sen tvåor osv, sen kanske kolla rader sen boxar.

isf skulle den kunna, när den hittat en etta, gå igenom de övriga två raderna och kolumnerna i rutan för att hitta fler ettor i boxarna horisontellt och vertikalt adjacent till boxen med nya ettan, så att en funnen etta skulle skicka ut så att fler försöker hittas, på så sätt löses det kanske snabbare.

eller om du vill lösa det brute force, sätt ut true i någon av rutorna för varje rad så att permutationer 1-9 bildas och kolla sen om ingen regel bryts. gör isf om senaste permutationen. du skulle kunna ha en 9x9-array där du kör permutationer och kollar regler, sen har du din kub där du satt allt till true och sen för varje fel du hittar kan du sätta false i kuben, vilket du kan utnyttja när du gör permutationer.

eller kör ett neuronnät med 3 lager neuroner, första lagret på 81 och sedan godtyckligt de andra och träna de att lösa :P

Dold text: helvete, skrev ju nästan lika långt som du! [tard]

Spana också in:

variabel:

har du övervägt att dessutom ha en 9x9-array för rätta svaret?


Jo precis, alltså för att svara på den andra fråga samtidigt. NEJ inte meningen att köra brute force. I den mån de går att vara lite mer sofistikerad. Poängen egentligen för mig är inte att få programmet lösa uppgiften. Utan att de ska ske effektivt. Tex om du ska göra schack bruteforce testa alla drag som finns emot något typ av poäng index. Då kan de ta ett tag om du ska tänka djupt. Om du tex däremot hoppar över de saker där de egentligen inte behövs tittas osv... finns en algoritm för detta minns bara inte vad den heter nu. Ja då får du ett snabbare program.

Min favorit är egentligen othello eftersom att man där vet att de max är sexti drag totalt. Vilket betyder att man kan optimera inför så många drag... och göra de fort. [cool]

IMO så handlar AI att inte räkna saker som den på någon logisk väg inte behöver räkna för att nå sitt mål. Att vara smart för en datorn är att vara effektiv i sin tankeprocess.

Grejen med alla abstrakta spel är ju att man med tillräcklig brute force och rätt värdesättning så att säga på vad som är bra drag kan lösa vad som helst om datorn är tillräckligt snabb.

Ideellt skulle jag ju vilja att datorn skulle lära sig utan hårdkodning efter x antar spelade matcher vad som är bra eller ej. Dock tänke jag att man ska ta en sak i taget. [cute]

variabel:

lösa på ett liknande sätt som människor?


Nej bara sofistikerat. Alltså, med suduku så på lätta suduku så om du säger att du skulle köra dictate på alla siffror som var med i sudukut så skulle vi ha tillräckligt många rutor som bara skulle ha ett alternativ. Alltså en sann kvar. Då gäller de ju att hitta dom.. helst utan att kolla i så få rutor som möjligt.

Vore nog bra om man hade ett värde som höll reda på hur många rutor som var fyllda typ såå den vet när vi är färdiga.

variabel:

på så sätt löses det kanske snabbare.


Jo precis.. dock vet jag inte dom de går snabbare [blush]

variabel:

kolla sen om ingen regel bryts.


Juste pro.. då behöver man inte hålla koll på hur många rutor som är lösta isf... som sagt brute force är att göra de lätt för sig och jobbigt för datorn [crazy]

variabel:

sen har du din kub där du satt allt till true och sen för varje fel du hittar kan du sätta false i kuben


jo precis de som kommer hända.... när man först använder sig av dictate de finns ju alltid vissa färdiga siffor med så att säga.

variabel:

du skulle kunna ha en 9x9-array där du kör permutationer och kollar regler


är väll de jag menar med "vad som behövs". ska kolla upp permuntationer osv... hehe

variabel:

eller kör ett neuronnät med 3 lager neuroner, första lagret på 81 och sedan godtyckligt de andra och träna de att lösa :P


hehehehe [cool]
Mr Brightside:

finns en algoritm för detta minns bara inte vad den heter nu. Ja då får du en snabbare dator.


du tänker på minmax med alfa-beta klippning? har gjort den som othelloagent, inte så svårt programmerat om man har algoritmen framför sig.

vet inte om du kanske redan skriv det, men din algoritm skulle kunna vara typ:

1. kolla om sudokut är löst. om inte:
2. gå igenom alla rutor efter ifyllda rutor och lägg de i en lista
3. för varje ifylld ruta (ensam true i z-arrayen för varje x och y) ta det värdet och sätt false på alla värden som går, ex om värde 5 hittats i en ruta kan z[5] sättas till false i hela den boxen och på hela raden och kolumnen. upprepa från 1.

eventuellt mer trixande, frågan är om det löser sudokut... hjälper gärna till att koda om jag har tid :)