download.bg
 Вход Списание  Новини  Програми  Статии  Форум  Чат   Абонамент  Топ95   Архив 

Алгоритъм за решаване на судоку

Автор
Съобщение
insecteater
Сря, 28.09.11, 08:31
Та някой да знае как се решава судоку. И най вече как се реализира програмно? Тъпото е, че ще трябва да го правя на Autohotkey, където по принцип не се поддържат масиви. Другият вариант е ако е на C++ или Basic или изобщо език, на който да се създаде dll файл, който да се извиква. Но това са незначителни подробности. Мен ме мъчи алгоритъма :)
Bruteforce-a е с неприемливо дълъг период на решаване :)
kookki
Сря, 28.09.11, 09:38
http://dzver.com/sudoku/sudoku.php
Става и с php. Все някъде има кодовете, но сега не ми се търси.
insecteater
Сря, 28.09.11, 10:13
Web базирани има на много места. Но на мен не ми вършат работа. Май намерих едно, което си е точно на autohotkey, и сега го гледам как да го подкарам.
anonymous
Сря, 28.09.11, 10:48
Ганчо май на работа скучаеш
vesov
Сря, 28.09.11, 11:27
Това върши ли работа:

#SingleInstance, Force
SetBatchLines, -1
SetTitleMatchMode, 3
 
    Loop 9 {
       r := A_Index, y := r*17-8 + (A_Index >= 7 ? 4 : A_Index >= 4 ? 2 : 0)
       Loop 9 {
          c := A_Index, x := c*17+5 + (A_Index >= 7 ? 4 : A_Index >= 4 ? 2 : 0)
          Gui, Add, Edit, x%x% y%y% w17 h17 v%r%_%c% Center Number Limit1 gNext
       }
    }
    Gui, Add, Button, vButton gSolve w175 x10 Center, Solve
    Gui, Add, Text, vMsg r3, Enter Sudoku puzzle and click Solve
    Gui, Show,, Sudoku Solver
Return
 
Solve:
    Gui, Submit, NoHide
    Loop 9
    {
       r := A_Index
       Loop 9
          If (%r%_%A_Index% = "")
             puzzle .= "@"
          Else
             puzzle .= %r%_%A_Index%
    }
    s := A_TickCount
    answer := Sudoku(puzzle)
    iterations := ErrorLevel
    e := A_TickCount
    seconds := (e-s)/1000
    StringSplit, a, answer, |
    Loop 9
    {
       r := A_Index
       Loop 9
       {
          b := (r*9)+A_Index-9
          GuiControl,, %r%_%A_Index%, % a%b%
          GuiControl, +ReadOnly, %r%_%A_Index%
        }
    }
    if answer
        GuiControl,, Msg, Solved!`nTime: %seconds%s`nIterations: %iterations%
    else
        GuiControl,, Msg, Failed! :(`nTime: %seconds%s`nIterations: %iterations%
    GuiControl,, Button, Again!
    GuiControl, +gAgain, Button
return
 
GuiClose:
    ExitApp
 
Again:
    Reload
 
#IfWinActive, Sudoku Solver
~*Enter::GoSub % GetKeyState( "Shift", "P" ) ? "~Up" : "~Down"
~Up::
    GuiControlGet, f, focus
    StringTrimLeft, f, f, 4
    f := ((f >= 1 && f <= 9) ? f+72 : f-9)
    GuiControl, Focus, Edit%f%
return
~Down::
    GuiControlGet, f, focus
    StringTrimLeft, f, f, 4
    f := ((f >= 73 && f <= 81) ? f-72 : f + 9)
    GuiControl, Focus, Edit%f%
return
~Left::
    GuiControlGet, f, focus
    StringTrimLeft, f, f, 4
    f := Mod(f + 79, 81) + 1
    GuiControl, Focus, Edit%f%
return
Next:
~Right::
    GuiControlGet, f, focus
    StringTrimLeft, f, f, 4
    f := Mod(f, 81) + 1
    GuiControl, Focus, Edit%f%
return
#IfWinActive
 
; Functions Start here
 
Sudoku( p ) { ;ErrorLevel contains the number of iterations
   p := RegExReplace(p, "[^1-9@]"), ErrorLevel := 0 ;format puzzle as single line string
   return Sudoku_Display(Sudoku_Solve(p))
}
 
Sudoku_Solve( p, d = 0 ) { ;d is 0-based
; http://www.autohotkey.com/forum/topic46679.html
; p: 81 character puzzle string
; (concat all 9 rows of 9 chars each)
; givens represented as chars 1-9
; fill-ins as any non-null, non 1-9 char
; d: used internally. omit on initial call
;
; returns: 81 char string with non-givens replaced with valid solution
;
   If (d >= 81), ErrorLevel++
      return p ;this is 82nd iteration, so it has successfully finished iteration 81
   If InStr( "123456789", SubStr(p, d+1, 1) ) ;this depth is a given, skip through
      return Sudoku_Solve(p, d+1)
   m := Sudoku_Constraints(p,d) ;a string of this level's constraints.
   ; (these will not change for all 9 loops)
   Loop 9
   {
      If InStr(m, A_Index)
         Continue
      NumPut(Asc(A_Index), p, d, "Char")
      If r := Sudoku_Solve(p, d+1)
         return r
   }
   return 0
}
 
Sudoku_Constraints( ByRef p, d ) {
; returns a string of the constraints for a particular position
     c := Mod(d,9)
   , r := (d - c) // 9
   , b := r//3*27 + c//3*3 + 1
   ;convert to 1-based
   , c++
   return ""
   ; row:
      . SubStr(p, r * 9 + 1, 9)
   ; column:
      . SubStr(p,c ,1) SubStr(p,c+9 ,1) SubStr(p,c+18,1)
      . SubStr(p,c+27,1) SubStr(p,c+36,1) SubStr(p,c+45,1)
      . SubStr(p,c+54,1) SubStr(p,c+63,1) SubStr(p,c+72,1)
   ;box
      . SubStr(p, b, 3) SubStr(p, b+9, 3) SubStr(p, b+18, 3)
}
 
Sudoku_Display( p ) {
   If StrLen(p) = 81
      loop 81
         r .= SubStr(p, A_Index, 1) . "|"
   return r
}

insecteater
Сря, 28.09.11, 12:20
Точно с това си троша зъбите. При мен резултата е едни йероглифи в първата половина и без промяна във втората половина на уж крайния резултат. Имам чувството, че NumPut функцията ми играе лоша шега...

Сега съм в обедна почивка :P

Редакция:
Писна ми на шапката и реших да използвам конзолния инструмент от http://code.google.com/p/evanescent/

редактиран от insecteater на 28.09.11 15:30
phrozencrew
Сря, 28.09.11, 21:35

RE: Алгоритъм за решаване на судоку

” Точно с това си троша зъбите. При мен резултата е едни йероглифи в първата половина и без промяна във втората половина на уж крайния резултат. „

Това е, защото вероятно си изтеглил много нова версия на Autohotkey, а скрипта е от 2009-та година. При мен си бачка, аз ползвам ей тая версия:
http://www.autohotkey.net/programs/AutoHotkey104805_Install.exe
Ето как изглежда едно решение:

Ако не си се отказал напълно от Autohotkey можеш да пробваш с тази версия.

kookki
Сря, 28.09.11, 22:13
Ганчо, има много кодове бе брато. Не потърси ли ?
http://trekto.info/algoritmi-strukturi-danni/9-vrashtane-nazad-sudoku/
тук в долния край на страницата има код на някаккъв език
и мното други.

Ей го и на ПХП
<?php
 
function return_row($cell){
	return floor($cell/9);
}
 
function return_col($cell){
	return $cell % 9;
}
 
function return_block($cell){
	return floor(return_row($cell)/3)*3+floor(return_col($cell)/3);
}
 
function is_possible_row($number,$row,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){		
		if($sudoku[$row*9+$x] == $number){
			$possible = false;
		}		
	}
	return $possible;
}
 
function is_possible_col($number,$col,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){
		if($sudoku[$col+9*$x] == $number){
			$possible = false;
		}
	}
	return $possible;
}
 
function is_possible_block($number,$block,$sudoku){
	$possible = true;
	for($x=0;$x<=8;$x++){
		if($sudoku[floor($block/3)*27+$x%3+9*floor($x/3)+3*($block%3)] == $number){
			$possible = false;
		}
	}
	return $possible;
}
 
function is_possible_number($cell,$number,$sudoku){
	$row = return_row($cell);
	$col = return_col($cell);
	$block = return_block($cell);
	return is_possible_row($number,$row,$sudoku) and is_possible_col($number,$col,$sudoku) and is_possible_block($number,$block,$sudoku);
}	
 
function print_sudoku($sudoku){
	$html = "<table bgcolor = \"#000000\" cellspacing = \"1\" cellpadding = \"2\">";
	for($x=0;$x<=8;$x++){
		$html .= "<tr bgcolor = \"white\" align = \"center\">";
		for($y=0;$y<=8;$y++){
			$html.= "<td width = \"20\" height = \"20\">".$sudoku[$x*9+$y]."</td>";
		}
		$html .= "</tr>";
	}
	$html .= "</table>";
	return $html;
}
 
function is_correct_row($row,$sudoku){
	for($x=0;$x<=8;$x++){
		$row_temp[$x] = $sudoku[$row*9+$x];
	}
	return count(array_diff(array(1,2,3,4,5,6,7,8,9),$row_temp)) == 0;
}
 
 
 
function is_correct_col($col,$sudoku){
	for($x=0;$x<=8;$x++){
		$col_temp[$x] = $sudoku[$col+$x*9];
	}
	return count(array_diff(array(1,2,3,4,5,6,7,8,9),$col_temp)) == 0;
}
 
function is_correct_block($block,$sudoku){
	for($x=0;$x<=8;$x++){
		$block_temp[$x] = $sudoku[floor($block/3)*27+$x%3+9*floor($x/3)+3*($block%3)];
	}
	return count(array_diff(array(1,2,3,4,5,6,7,8,9),$block_temp)) == 0;
}
 
function is_solved_sudoku($sudoku){
	for($x=0;$x<=8;$x++){
		if(!is_correct_block($x,$sudoku) or !is_correct_row($x,$sudoku) or !is_correct_col($x,$sudoku)){
			return false;
			break;
		}
	}
	return true;
}
 
function determine_possible_values($cell,$sudoku){
	$possible = array();
	for($x=1;$x<=9;$x++){
		if(is_possible_number($cell,$x,$sudoku)){
			array_unshift($possible,$x);
		} 
	}
	return $possible;
}
 
function determine_random_possible_value($possible,$cell){
	return $possible[$cell][rand(0,count($possible[$cell])-1)];
}
 
function scan_sudoku_for_unique($sudoku){
	for($x=0;$x<=80;$x++){
		if($sudoku[$x] == 0){
			$possible[$x] = determine_possible_values($x,$sudoku);
			if(count($possible[$x])==0){
				return(false);
				break;
			}
		}
	}
	return($possible);
}
 
function remove_attempt($attempt_array,$number){
	$new_array = array();
	for($x=0;$x<count($attempt_array);$x++){
		if($attempt_array[$x] != $number){
			array_unshift($new_array,$attempt_array[$x]);
		}
	}
	return $new_array;
}
 
 
function print_possible($possible){
	$html = "<table bgcolor = \"#ff0000\" cellspacing = \"1\" cellpadding = \"2\">";
	for($x=0;$x<=8;$x++){
		$html .= "<tr bgcolor = \"yellow\" align = \"center\">";
		for($y=0;$y<=8;$y++){
			$values = "";
			for($z=0;$z<=count($possible[$x*9+$y]);$z++){
				$values .= $possible[$x*9+$y][$z];
			}
			$html.= "<td width = \"20\" height = \"20\">$values</td>";
		}
		$html .= "</tr>";
	}
	$html .= "</table>";
	return $html;
}	
 
function next_random($possible){
	$max = 9;
	for($x=0;$x<=80;$x++){
		if ((count($possible[$x])<=$max) and (count($possible[$x])>0)){
			$max = count($possible[$x]);
			$min_choices = $x;
		}
	}
	return $min_choices;
}
 
 
function solve($sudoku){
	$start = microtime();
	$saved = array();	
	$saved_sud = array();
	while(!is_solved_sudoku($sudoku)){
		$x+=1;
		$next_move = scan_sudoku_for_unique($sudoku);
		if($next_move == false){
			$next_move = array_pop($saved);
			$sudoku = array_pop($saved_sud);
		}
		$what_to_try = next_random($next_move);	
		$attempt = determine_random_possible_value($next_move,$what_to_try);
		if(count($next_move[$what_to_try])>1){					
			$next_move[$what_to_try] = remove_attempt($next_move[$what_to_try],$attempt);
			array_push($saved,$next_move);
			array_push($saved_sud,$sudoku);
		}
		$sudoku[$what_to_try] = $attempt;	
	}
	$end = microtime();
	$ms_start = explode(" ",$start);
	$ms_end = explode(" ",$end);
	$total_time = round(($ms_end[1] - $ms_start[1] + $ms_end[0] - $ms_start[0]),2);
	echo "completed in $x steps in $total_time seconds";
	echo print_sudoku($sudoku);
}
 
$sudoku = array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
 
solve($sudoku);
?>

tegote
Сря, 28.09.11, 23:56
Хм.......
Гледам судокуто направо го написахте, пренаписахте го, (аман от разбирачи), а "уловката" на DIMIVA никой не успя да разкрие! Аман от разбирачи!
И за кво ми е туй судоку, като мобилния си ми го има? Играя си го всеки ден без ангажимент да влизам където и да е, да зачерквам каквото и да е, и да купувам което и да е?!

dreamskill
Чет, 29.09.11, 00:13

Ти наистина ли не можеш да схванеш идеята на темата?

tegote
Чет, 29.09.11, 00:51
Идеята може би е да съставите машина, която да ви даде отговорите на судоку! А то е същото като да напишеш едно судоку! Ти наистина ли ме питаш каква е идеята?
insecteater
Чет, 29.09.11, 08:20
Това с телефоните беше забавно :)
А иначе на мен ми трябваше за следното нещо- от момента на появяване на судоку-то в заредената страница до момента в който судокуто да бъде попълнено да мине минимално време.
Разбира се има доста online услуги за решаване на судоку, но да се препишат числата ръчно например минава доста време и често води до грешки.

А иначе програмата ми е готова. Темата се получи интересна и полезна, за което благодаря на включилите се.
--------------------------------------------------------------------------------
-Всеки човек има определен хоризонт. Когато той се свива и стане безкрайно малък, се превръща в точка. Тогава човекът казва: "Това е моята гледна точка".

Коментар

за нас | за разработчици | за реклама | станете автори | in english  © 1998-2024   Experta Ltd.