Autor Wątek: pomysl na gre sieciowa w javie  (Przeczytany 2712 razy)

Offline alternativa

  • Użytkownik

# Listopad 24, 2006, 22:26:37
Witajcie :))
Chcialabym napisac jakas w miare prosta gierke w javie.. Musi byc sieciowa i wielowatkowa. Jak na razie zastanawialam sie nad pojedynkiem sudoku (generuje plansze, wygrywa ten, kto pierwszy rozwiaze), ale nie wiem jak wyglada sprawa z generowaniem sudoku.. Macie moze jakies inne pomysly?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xion

  • Redaktor
    • xion.log

# Listopad 24, 2006, 23:53:47
Nie.

Offline counterClockWise

  • Użytkownik

# Listopad 25, 2006, 00:02:24
Xion - nie zniechęcaj kobiet do forum. Pewnie ilość ich na forum da się na 2-3 bitach zapisać ;)

Ktoś pisał Sudoku tu na forum, więc na pewno zna jakieś efektywne algorytmy.

Z innych prostych gier sieciowych do napisania w Javie można wymienić choćby Statki, Monopol, Reversi, Warcaby.

5 sekund google dało taki hint, ale koleś chyba sam nie wie jak to dobrze zrobić :D

Cytuj
How can you generate Sudoku puzzles? I do not know what the 'best' algorithm is, but here is what I have done in my simple little python program.

First, we need a Sudoku solver. My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough.

   1. If only one number fits in a square without row, column, and box conflicts, we fill it in.
   2. If a number needed by a row, column, or box can only go in one square in that row, column, or box, we fill it in.
   3. If we can't fill in anything using rules 1 or 2, then we find a most-constrained place or number where we can guess (for example, two choices is better than three), and we try all the guesses.

The last bit about trying all the guesses will require some backtracking. When we are selecting a place to guess, we choose one randomly among the most-constrained places, and we shuffle the choices to try them in a random order.

The result is if we tell the solver to solve an empty board, we get a nice random fully-solved Sudoku board.

To generate Sudoku puzzles, we start with a solved board, and we choose some minimal hints to reveal as follows.

   1. Going through the squares in shuffled order, reveal each square only if it is not deduced by the other revealed squares (using the solver without guessing). This produces a list of about 30 to 40 hints which together dermine the 81 squares of the board.
   2. Going through the chosen hints in shuffled order, attempt dropping each one, and fully solve the board far enough to find two solutions if there are two. Replace the hint unless the solution is still unique with the hint removed.

Notice that generating a minimal puzzle this way requires us to do the work of solving a Sudoku board about twenty times, so it takes a lot more work to generate a minimal Sudoku puzzle than it does to solve one. If there are ways of generating Sudoku puzzles more quickly, I'd love to know.


« Ostatnia zmiana: Listopad 25, 2006, 00:05:13 wysłana przez counterClockWise »

Offline Wyszo

  • Użytkownik

# Listopad 25, 2006, 00:27:10
Myślę, że należałoby się zagłębić w to źródło: http://www.pro.or.jp/~fuji/numplace/makeproblem/numplace01.html.en

Offline alternativa

  • Użytkownik

# Listopad 25, 2006, 10:13:24
Dzieki:)
Jesli chodzi o pierwszy algorytym, to moim zdaniem on jest troche glupi, aczkolwiek zawsze jest to jakies rozwiazanie ;)

Ta ostatnia stronka jest ciekawa, ale takie algorytmy trudno zastosowac w programowaniu, bo opieraja sie na wielu zasadach, ktore dla czlowieka sa oczywiste, a dla komputera niekoniecznie ;)
Chetnie zobaczylabym jakis algorytm w C/C++/Pascalu czy nawet jakims pseudo-kodzie.
pozdro :)

Offline Esidar

  • Użytkownik

# Listopad 25, 2006, 20:58:08
Ktoś wyliczył, że Sudoku ma 6,670,903,752,021,072,936,960 kombinacji. Jakoś nie chce mi się sprawdzać czy to prawda  :D Kiedyś zastanawiałem się nad sposobem wygenerowania planszy Sudoku. Zamiast wstawiać cyfry można wstawić litery A,B,C,D,E,F,G,H,I a następnie wylosować kombinację cyfr i podstawić je pod litery czyli można wstawić np. 1,2,3,4,5,6,7,8,9 albo 4,8,3,1,5,9,7,2,6 itd. To dość przyśpieszy generację.
Co do wstawiania liter to pewnie pozostaje metoda losowania kombinacji. Wiadomo że jedną literę można wstawić na planszę w N kombinacjach. Trzeba wybrać jedną kombinację. Potem dostawić inną wylosowaną kombinację (taką która się nie pokrywa z poprzednimi) dla następnej litery i tak powtórzyć 9 razy. Jeśli się ma zapamiętane wszystkie kombinacje dla jednej litery to jest to zapewne kwestia parunastu porównań tych kombinacji. Pytanie tylko ile jest kombinacji dla jednej litery i czy da się przeliczyć i zapamiętać wszystkie kompinacje :)